Sign in to follow this  
Cappie35

Ray tracer : fill an uniform grid

Recommended Posts

Cappie35    107

Hello,

 

I wrote a simple ray tracer, and now I try to implement an uniform grid. There is a lot of documentation on how to traverse the grid, but I don't know how to construct the grid.

I have my uniform grid and my triangles. How could I know, which cell(s) in the grid correspond(s) to my triangles ? Some triangles can be in several cells.

Thank you for your answers.

Share this post


Link to post
Share on other sites
ADDMX    281

In each cell of the grid you need to store LIST of ALL trinagless that colide with that cell (this willprobably lead to many list sharing one triangle situation) the other approach is to take each triangle and clip it to each cell, then store resulting triangles in that cell - this step is costly, and due to numerical rounding errors can lead to seams on final image

(but most of the time its ok))

Share this post


Link to post
Share on other sites
Cappie35    107

So, for the first solution I need to test the intersection between a cell and each triangles; and for the second solution I have to cut triangles by planes of the cells and I will have reference of triangles just once in the grid.

 

For the first solution is there an algorithm to speed up? 

Share this post


Link to post
Share on other sites
Bacterius    13165


For the first solution is there an algorithm to speed up? 

 

You could start with all the triangles in your scene and remove a triangle when you've fully explored all the cells that might contain it, then you have less and less triangles to process as you work through the algorithm. I would personally start by walking the grid along the triangle's edges, and then exploring the cells "in between". Your code might end up looking somewhat like a 3D "scanline" (or, more appropriately, scanplane) algorithm.

 

A more efficient method could be to partition your triangles into an octree (this might require your grid to be a power of two). Once you've done that it's a simple matter of looking up each triangle at the right depth (depending on your grid's resolution) and binning it inside the corresponding cells. It might be possible to do it all in one step by building the grid at the same time you build the octree, but I can't think of a way right now. This seems to handle enormous triangles which overlap lots of cells much better than the first approach.

 

There's probably a better way to do it, but that could be a starting point. I'd go with a divide and conquer approach anyway, anything else is likely to not scale well with the number of triangles.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this