Public Group

# Building a regular grid for a raytracer

This topic is 3937 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello everyone, I hope i have placed this topic in the right subforum. Anyway, i have built a raytracer last year when i was taking a linear algebra course. The raytracer is very simple and i have no optimizations whatsoever. Now i want implement a regular grid to speed things up a bit (kd-trees for another time, i want to keep it simple). This is what i came up with:
struct aabb {
public:
aabb() : pos(Float3d(0.0f, 0.0f, 0.0f)), size(Float3d(0.0f, 0.0f, 0.0f)) {};
aabb(Float3d ', Float3d &asize) : pos(apos), size(asize) {};
Float3d& GetPos() { return pos; }
Float3d GetSize() { return size; }
bool Intersect(Triangle& t) {

return false;
}

private:
Float3d pos, size;
Triangle* triangles;
};


My idea was to use aabb-triangle intersection in every aabb and to place those triangles in the pointer-array. 1. Is this a 'good' way? Are there better ways of doing this? 2. I have been struggeling to find some code for the intersection and i have searched the forums and found Moller, SAT, N-tutorials and whatnot, but the point is that i don't understand them all too well. I hope i have been clear :)

##### Share on other sites
That isn't really the best way to handle a regular grid - you're not taking advantage of it being a regular grid :)

The aabbox of each cell is implicit in the bounding box of the whole grid (along with the resolution of the grid).

Something like this would serve better:

struct TriangleList{  std::vector<int> tri_refs;};struct RegularGrid{  int dims[3];  // resolution of grid  float bounds[2][3];  // bounding box of whole grid  TriangleList** grid;  // alloc this as new TriangleList*[dims[0]*dims[1]*dims[2]]; };

For each triangle, take its bounding box and insert it into the grid at just those cells it overlaps:

RegularGrid* grid = ...for each T in triangles:int min_cell[3];int max_cell[3];float tri_bounds[2][3] = bounds_of Tfor(int axis=0;axis<3;axis++){  min_cell[axis] = ((tri_bounds[0][axis] - grid->bounds[0][axis])/(grid->bounds[1][axis]-grid->bounds[0][axis]) * dims[axis];  max_cell[axis] = ((tri_bounds[1][axis] - grid->bounds[axis][0])/(grid->bounds[1][axis]-grid->bounds[0][axis]) * dims[axis];}for(int k=min_cell[2];k<max_cell[2];k++)  for(int j=min_cell[1];j<max_cell[1];j++)    for(int i=min_cell[0];i<max_cell[0];i++)    // yes, these really are nested    grid->grid[i + (j*grid->dim[0]) + (k * grid->dim[0] * grid->dim[1])]->tri_refs.push_back( index_of T );

This isn't optimal as you can guess. A better option is to do an aabox/triangle test within the nested loop there. The aabox of each cell is easy to determine, so all that is left is the triangle/aabox code. As you point out there are plenty of options, below is code from [1]:

#define X 0#define Y 1#define Z 2#define CROSS(dest,v1,v2)           dest[0]=v1[1]*v2[2]-v1[2]*v2[1];            dest[1]=v1[2]*v2[0]-v1[0]*v2[2];           dest[2]=v1[0]*v2[1]-v1[1]*v2[0]; #define DOT(v1,v2) (v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2])#define SUB(dest,v1,v2)           dest[0]=v1[0]-v2[0];            dest[1]=v1[1]-v2[1];           dest[2]=v1[2]-v2[2]; #define FINDMINMAX(x0,x1,x2,min,max)   min = max = x0;     if(x1<min) min=x1;  if(x1>max) max=x1;  if(x2<min) min=x2;  if(x2>max) max=x2;inline int planeBoxOverlap(const float normal[3],float d, const float maxbox[3]){  int q;  float vmin[3],vmax[3];  for(q=X;q<=Z;q++)  {    if(normal[q]>0.0f)    {      vmin[q]=-maxbox[q];      vmax[q]=maxbox[q];    }    else    {      vmin[q]=maxbox[q];      vmax[q]=-maxbox[q];    }  }  if(DOT(normal,vmin)+d>0.0f) return 0;  if(DOT(normal,vmax)+d>=0.0f) return 1;    return 0;}/*======================== X-tests ========================*/#define AXISTEST_X01(a, b, fa, fb)			   	p0 = a*v0[Y] - b*v0[Z];			       	   	p2 = a*v2[Y] - b*v2[Z];			       	           if(p0<p2) {min=p0; max=p2;} else {min=p2; max=p0;} 	rad = fa * boxhalfsize[Y] + fb * boxhalfsize[Z];   	if(min>rad || max<-rad) return false;#define AXISTEST_X2(a, b, fa, fb)			   	p0 = a*v0[Y] - b*v0[Z];			           	p1 = a*v1[Y] - b*v1[Z];			       	           if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} 	rad = fa * boxhalfsize[Y] + fb * boxhalfsize[Z];   	if(min>rad || max<-rad) return false;/*======================== Y-tests ========================*/#define AXISTEST_Y02(a, b, fa, fb)			   	p0 = -a*v0[X] + b*v0[Z];		      	   	p2 = -a*v2[X] + b*v2[Z];	       	       	           if(p0<p2) {min=p0; max=p2;} else {min=p2; max=p0;} 	rad = fa * boxhalfsize[X] + fb * boxhalfsize[Z];   	if(min>rad || max<-rad) return false;#define AXISTEST_Y1(a, b, fa, fb)			   	p0 = -a*v0[X] + b*v0[Z];		      	   	p1 = -a*v1[X] + b*v1[Z];	     	       	           if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} 	rad = fa * boxhalfsize[X] + fb * boxhalfsize[Z];   	if(min>rad || max<-rad) return false;/*======================== Z-tests ========================*/#define AXISTEST_Z12(a, b, fa, fb)			   	p1 = a*v1[X] - b*v1[Y];			           	p2 = a*v2[X] - b*v2[Y];			       	           if(p2<p1) {min=p2; max=p1;} else {min=p1; max=p2;} 	rad = fa * boxhalfsize[X] + fb * boxhalfsize[Y];   	if(min>rad || max<-rad) return false;#define AXISTEST_Z0(a, b, fa, fb)			   	p0 = a*v0[X] - b*v0[Y];				   	p1 = a*v1[X] - b*v1[Y];			                   if(p0<p1) {min=p0; max=p1;} else {min=p1; max=p0;} 	rad = fa * boxhalfsize[X] + fb * boxhalfsize[Y];   	if(min>rad || max<-rad) return false;inline bool triBoxOverlap(const float boxcenter[3],const float boxhalfsize[3],const Vec3& trip0,const Vec3& trip1,const Vec3& trip2){  /*    use separating axis theorem to test overlap between triangle and box */  /*    need to test for overlap in these directions: */  /*    1) the {x,y,z}-directions (actually, since we use the AABB of the triangle */  /*       we do not even need to test these) */  /*    2) normal of the triangle */  /*    3) crossproduct(edge from tri, {x,y,z}-directin) */  /*       this gives 3x3=9 more tests */   float v0[3],v1[3],v2[3];   float axis[3];   float min,max,d,p0,p1,p2,rad,fex,fey,fez;   float normal[3],e0[3],e1[3],e2[3];   /* This is the fastest branch on Sun */   /* move everything so that the boxcenter is in (0,0,0) */   SUB(v0,trip0,boxcenter);   SUB(v1,trip1,boxcenter);   SUB(v2,trip2,boxcenter);   /* compute triangle edges */   SUB(e0,v1,v0);      /* tri edge 0 */   SUB(e1,v2,v1);      /* tri edge 1 */   SUB(e2,v0,v2);      /* tri edge 2 */   /* Bullet 3:  */   /*  test the 9 tests first (this was faster) */   fex = fabs(e0[X]);   fey = fabs(e0[Y]);   fez = fabs(e0[Z]);   AXISTEST_X01(e0[Z], e0[Y], fez, fey);   AXISTEST_Y02(e0[Z], e0[X], fez, fex);   AXISTEST_Z12(e0[Y], e0[X], fey, fex);   fex = fabs(e1[X]);   fey = fabs(e1[Y]);   fez = fabs(e1[Z]);   AXISTEST_X01(e1[Z], e1[Y], fez, fey);   AXISTEST_Y02(e1[Z], e1[X], fez, fex);   AXISTEST_Z0(e1[Y], e1[X], fey, fex);   fex = fabs(e2[X]);   fey = fabs(e2[Y]);   fez = fabs(e2[Z]);   AXISTEST_X2(e2[Z], e2[Y], fez, fey);   AXISTEST_Y1(e2[Z], e2[X], fez, fex);   AXISTEST_Z12(e2[Y], e2[X], fey, fex);   /* Bullet 1: */   /*  first test overlap in the {x,y,z}-directions */   /*  find min, max of the triangle each direction, and test for overlap in */   /*  that direction -- this is equivalent to testing a minimal AABB around */   /*  the triangle against the AABB */   /* test in X-direction */   FINDMINMAX(v0[X],v1[X],v2[X],min,max);   if(min>boxhalfsize[X] || max<-boxhalfsize[X]) return false;   /* test in Y-direction */   FINDMINMAX(v0[Y],v1[Y],v2[Y],min,max);   if(min>boxhalfsize[Y] || max<-boxhalfsize[Y]) return false;   /* test in Z-direction */   FINDMINMAX(v0[Z],v1[Z],v2[Z],min,max);   if(min>boxhalfsize[Z] || max<-boxhalfsize[Z]) return false;   /* Bullet 2: */   /*  test if the box intersects the plane of the triangle */   /*  compute plane equation of triangle: normal*x+d=0 */   CROSS(normal,e0,e1);   d=-DOT(normal,v0);  /* plane eq: normal.x+d=0 */   if(!planeBoxOverlap(normal,d,boxhalfsize)) return false;   return true;   /* box and triangle overlaps */}

(apologies for poor formatting, URL to code is listed in paper)

[1]: Fast 3D Triangle-Box Overlap Testing - Tomas Akenine-MÄoller

##### Share on other sites
Hey thanks alot for the detailed answer! +rep for you :)

I have a question though. Why is the first method not optimal? Does it not find triangles that do not have a vector inside the aabb but still contain a part of it in the aabb?

About the second method, i found it but it was the only method i found. Aren't there other methods?

Thanks again!

##### Share on other sites
Yep thats exactly why it isn't optimal. Imagine a long thin triangle lying diagonally within the grid so that it overlaps many cells. The AA box of the triangle overlaps many more cells than the triangle actually intersects (probably > 3x). For each of those boxes that the triangle is said to overlap but doesn't really you'll be wasting a ray/triangle intersection.

As for other tri/box tests - there are more but I don't have any to hand right now :) Simple googling doesn't turn up much - I guess Mollers method is pretty optimal and noone can be arsed to do more research ;P

1. 1
2. 2
Rutin
24
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 23
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631766
• Total Posts
3002234
×