hackification

Homepage

...rediscover the joy of coding

Experiments in Ray-Tracing, Part 6: Intersection Tests

I wasn't going to present quite so much code in this series, but the following intersection tests are (a) tricky to get working correctly and quickly, and (b) they're not exactly exciting, so I thought I'd include them here as reference. I've also been saying things like "if the ray intersects the object..." without covering how you'd actually go about detecting that, so this article covers that.

(Please note that these algorithms most definitely aren't my work: I've adapted most of them from "Real-Time Rendering").

So here we go: a variety of intersection methods, implemented in C#.

Intersection Constructor

The intersection tests return either an intersection object, if the ray intersects the object, or null, if not. The constructor of the intersection class has the following form:
public Intersection( Vector position, Vector normal, double t )
The plane tests given determine whether the object is completely on one side of the given plane, completely on the other side, or whether the plane passes through the object. Planes are represented as a point on the surface, and the surface normal.

Ray-Sphere Intersection
public override Base.Intersection Intersect( Base.Ray ray )
{
  var el = _center - ray.Start;
  var d = Base.Vector.Dot( el, ray.Vector );
  var els = Base.Vector.Dot( el, el );
  var rs = _radius * _radius;

if( d < 0 && els > rs ) { return null; }

var ms = els - d * d;

if( ms > rs ) { return null; }

var q = Math.Sqrt( rs - ms ); double t;

if( els > rs ) { t = d - q; } else { t = d + q; }

var p = ray.Start + ray.Vector * t;

return new Base.Intersection( p, ( p - _center ).Normalize(), t ); }
Ray-Triangle Intersection

Note that _epsilon is somee small number, say 0.00001. _p0, _p1, and _p2 are the three vertices of the triangle.
public override Base.Intersection Intersect( Base.Ray ray )
{
  var e1 = _p1 - _p0;
  var e2 = _p2 - _p0;
  var p = Base.Vector.Cross( ray.Vector, e2 );
  var a = Base.Vector.Dot( e1, p );

if( a > -_epsilon && a < _epsilon ) { return null; }

var f = 1 / a; var s = ray.Start - _p0; var u = f * Base.Vector.Dot( s, p );

if( u < 0 || u > 1 ) { return null; }

var q = Base.Vector.Cross( s, e1 ); var v = f * Base.Vector.Dot( ray.Vector, q );

if( v < 0 || u + v > 1 ) { return null; }

var t = f * Base.Vector.Dot( e2, q );

if( t < 0 ) { return null; }

var position = ray.Start + ray.Vector * t;

return new Base.Intersection( position, _normal, t ); }
Plane-Sphere Test
public override Base.PlaneSide GetPlaneSide( Base.Plane plane )
{
  var p = _center - plane.Point;
  var distance = Base.Vector.Dot( p, plane.Normal );

if( distance > _radius ) { return Base.PlaneSide.NormalSide; } else if( distance < -_radius ) { return Base.PlaneSide.OtherSide; } else { return Base.PlaneSide.Intersects; } }
Plane-Triangle Test
public override Base.PlaneSide GetPlaneSide( Base.Plane plane )
{
  var p0 = _p0 - plane.Point;
  var d0 = Base.Vector.Dot( p0, plane.Normal );
  var p1 = _p1 - plane.Point;
  var d1 = Base.Vector.Dot( p1, plane.Normal );
  var p2 = _p2 - plane.Point;
  var d2 = Base.Vector.Dot( p2, plane.Normal );

if( d0 > 0 && d1 > 0 && d2 > 0 ) { return Base.PlaneSide.NormalSide; } else if( d0 < 0 && d1 < 0 && d2 < 0 ) { return Base.PlaneSide.OtherSide; } else { return Base.PlaneSide.Intersects; } }