Jump to content
  • Advertisement
Sign in to follow this  

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.

If you intended to correct an error in the post then please contact us.

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 {
	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;

	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 this post

Link to post
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 T

for(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];
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) */

/* 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 */
if(min>boxhalfsize[X] || max<-boxhalfsize[X]) return false;

/* test in Y-direction */
if(min>boxhalfsize[Y] || max<-boxhalfsize[Y]) return false;

/* test in Z-direction */
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 */
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 this post

Link to post
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 this post

Link to post
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

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!