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 ?

Thanks fo your answers.

  • $\begingroup$ Is someone can explain me how to insert my triangles in an regular grid? Do I have to follow each segment to know which cells match with the triangles? Or another option, do I have to cut my triangles by planes of the grid? I don't know what is better... if someone knows i will be glad to know the answer. $\endgroup$ – Cappie Dec 11 '13 at 16:45
  • $\begingroup$ A uniform rectilinear grid is often refined into triangles by adding parallel diagonals to bisect each rectangle. However I don't think much more can be said, and I suspect this is something you've already considered. $\endgroup$ – hardmath Dec 25 '13 at 19:18

You don't have to form and store a uniform mesh explicitly since you can do arithmetic to compute cell indicies. If you know you have $N_x$ cells in the $x$ direction on a grid over $\left[0,L_x\right]$, then you know the $x$-index of the cell is $$ i=\left\lfloor \frac{x N_x}{L_x}\right\rfloor $$ You can do the same for each of the three coordinates for each of the three corners of your triangle. The indices you generate uniquely define the cell than contains each corner. A cell contains an entire triangle if it contains all three corners.

This index is 0-based. Add 1 if your arrays are 1-based (e.g. Fortran or MATLAB).

  • $\begingroup$ I don't understand. I understand how to match a point to a cell, but if the 3 points of the triangle are not in the same cell : we have to store the reference of the triangle in several cells. So, how could I know all cells of the grid corresponding to a triangle (where the 3 points are not in the same cells) ? $\endgroup$ – Cappie Dec 10 '13 at 15:32

Not the answer you're looking for? Browse other questions tagged or ask your own question.