Implementing Ray Tracing on GPU
Part 4

Intersection Test

The traverser shader checks if the current voxel contains elements (triangles). If triangles are found, the ray is set to a “wait” state, those triangles are ready to be checked for intersection, but during ray traversal there is nothing more to do, they are rejected for further traversal operations. If current voxel is empty, next voxel will be calculated using the voxel traversal program. The information if triangles are in voxels, is stored in the “Voxel Index” texture. A value of -1 means there are no triangles to check, otherwise it contains a value pointing to a “Grid Element” Texture, containing the list of triangles for that voxel. If the end of the grid is reached, the ray is set to a “overflow” state and is not processed anymore.

Ray States

*state-name*	*state #*	*description*
active	-10	traverse Grid
wait	>= 0	ready to check intersections.
dead	-50	ray doesn’t hit grid (was already rejected in voxel precalculation)
inactive	-20	a valid hit point was found
overflow	-30	traversal left voxel space (no valid hits)

Triangle Intersection Test (2-sided)

float intersect(Ray r, Triangle tri, out vec4 ret)
{
   vec3 edge1, edge2, tvec, pvec, qvec;
   float det;
   float result = -1.0;
   ret = vec4(0.0,0.0,0.0,0.0);
   qvec = vec3(0.0,0.0,0.0);
   
   edge1 = tri.B-tri.A;
   edge2 = tri.C-tri.A;
 
   pvec = cross(r.direction, edge2);
   det = dot(edge1, pvec);
  
   if (det > _EPSILON_)
   { 
      result = 1.0;
      tvec = r.startpoint - tri.A;                
      ret.x = dot(tvec, pvec);            
      if (ret.x < 0.0 || ret.x > det) result = -1.0;
      if (result > 0.0)
      {
         qvec = cross(tvec, edge1);          
         ret.y = dot(r.direction, qvec);          
         if ((ret.y < 0.0) || ((ret.x + ret.y) > det)) result = -1.0;
      }
   }

   if (det < -_EPSILON_)
   {  
      result = 1.0;
      tvec = r.startpoint - tri.A;
      ret.x = dot(tvec, pvec);
      if (ret.x > 0.0 || ret.x < det) result = -1.0;
      if (result > 0.0)
      {
         qvec = cross(tvec, edge1);
         ret.y = dot(r.direction, qvec);
         if ((ret.y > 0.0) || ((ret.x + ret.y) < det)) result = -1.0;
      }
   }
   
   if (result > 0.0)
   {
      ret.z = dot(edge2, qvec);
      ret /= det;
   }
   
   if (ret.z<_EPSILON_) result = -1.0;
   
   return result;
}
//-----------------------------------------------
// return value:
//   result > 0.0: intersection found
//   result < 0.0: no intersection found
//
//   ret.x --> barycentric u
//   ret.y --> barycentric v
//   ret.z --> Hitpoint t (ray)
//   ret.w --> reserved for triangle num
//-----------------------------------------------

Utility Functions:

// Voxel coordinates -> world coordinates
vec3 voxel2world(vec3 xyz)  { return xyz * _len + g1;}

// World Coordinates Voxel (start- and end-point)
void voxelbounds(vec3 ijk, out vec3 v1, out vec3 v2) 
{   
   v1 = voxel2world(ijk);   
   v2 = v1 + _len;   
}

// Calculate texture coordinate of array element (2D Texture -> 1D Array)
vec2 Coord2D(float listnumber, float texturesize)
{   
   vec2 result;    
   result.y = listnumber/texturesize;   
   result.y = INTEGER(result.y);   
   result.x = listnumber-texturesize*result.y;   
   return result/texturesize; 
}

// Calculate texture coordinate of array element (2D Data-Texture -> 1D Array)
vec2 ElementCoord2D(float listnumber, float texturesize, float align)
{
vec2 result; 
   float align_size = texturesize / align;
   result.y = listnumber/align_size;
   result.y = INTEGER(result.y);
   result.x = listnumber-align_size*result.y;
   
   result.x /= align_size;    // auf [0,1] skalieren
   result.y /= texturesize;   // auf [0,1] skalieren
   return result;
}

Load scene data which is stored in texture and perform intersection tests

void intersect_check(inout Ray r, inout Triangle tri, inout vec4 raydir, inout vec4 raypos, 
                     inout vec4 voxel, inout vec4 uvt)
{
   vec2 GEcoord = Coord2D(voxel.w, GEsize);  // calculate coordinates for Grid Element list
   float elementnum = tex2D(GE, GEcoord).x;   // Element num for EDlist.
  
   vec2 EDcoord = ElementCoord2D(elementnum, EDsize, TRIANGLE_ELEMENTS*4.0);
      
   tri.A = tex2D(ED, EDcoord);
   tri.B = tex2D(ED, vec2(EDcoord.x+2.0/EDsize,EDcoord.y));
   tri.C = tex2D(ED, vec2(EDcoord.x+4.0/EDsize,EDcoord.y));  
      
   bool p0 = (elementnum == -1);
   bool p1 = (uvt.w == -1);
   bool p2 = (uvt.w >= 0);
    
      
   if (p0 && p1) // FAIL -> continue to traverse
   { 
         voxel.w = -10; 
         uvt.xyz = vec3(0,0,_INF_);
   }
   
   if (p0 && p2) // DONE -> intersection found!
   {
         voxel.w = -20;
   }
   
   if (elementnum >=0 )
   {
      voxel.w = voxel.w + 1.0; // next element (for next pass)

      vec3 intersect_result;
      float intersecttest = intersect(r,tri, intersect_result);

      // calculate voxel bounds
      vec3 v1 = voxel.xyz * _len + g1; //voxelbounds(voxel.xyz, v1, v2);
      vec3 v2 = v1 + _len; 
   
      vec3 hitpoint = raypos.xyz + raydir.xyz*intersect_result.z;
   
      bool c0 = inbox(hitpoint, v1,v2);
      bool c1 = (uvt.z >= intersect_result.z);
      bool c2 = (intersecttest > 0.0);
      bool c3 = (elementnum != raypos.w); // don't test same element twice
      bool c4 = c0 && c1 && c2 && c3;
   
      if (c4)
      {
         uvt.xyz = intersect_result.xyz;
         uvt.w = elementnum;
         raypos.w = elementnum;
      }
   } 
}

go to: [part 5 ][home]

Implementing Ray Tracing on GPU Part 4

Intersection Test

Implementing Ray Tracing on GPU
Part 4