Hackification > Blog Posts > 2008 > Experiments in Ray-Tracing, Part 6 - Intersection Tests

Experiments in Ray-Tracing, Part 6 - Intersection Tests

This is a very old article, included for historical interest only!

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 some 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;
  }
}

Published: Friday, July 25, 2008

You may be interested in...

Hackification.io is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to amazon.com. I may earn a small commission for my endorsement, recommendation, testimonial, and/or link to any products or services from this website.