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.


closed as unclear what you're asking by boyfarrell, Christian Clason, Brian Borchers, Dan, hardmath Dec 25 '13 at 19:18

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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.