moreillo@disuns2.epfl.ch (Guy Moreillon) (04/11/91)
I've got a problem concerning space subdivision and triangles: Let's say the space is subdivided in NxNxN voxels. The length, width and height of the voxels need not be equal, most likely there're not. Now, let's consider a triangle in that space. My question is : how do I find ALL the voxels that the triangle cuts? When I mean cut, I mean that the list of the voxels in which you can find a corner of the triangle will not do. If a part of the triangle goes through a voxel, then that voxel has to be in the list. I guess one could use some kind of incremental algorithm (like a 3DDDA, but I was wondering if there wasn't something niftier around... Anyone got any idea ? Guy Moreillon moreillo@disun20.epfl.ch moreillon@eldi.epfl.ch
mg@ (Mike Gigante) (04/13/91)
What I do is for each voxel overlapping bbox of triangle substitute each corner of voxel into plane eqn of triangle. If sign of resultant substitution is the same for all corners, then you can reject the voxel (i.e. it lies entirely on one side of the triangle) This gets rid of most of the obvious voxels, but you can still end up with some voxels that cross the *plane* of the triangle, but not containing the triangle. This is mostly a problem for long, thin triangle that are not conveniently aligned with the coordinate system. Further effort (eg performing clipping tests on the triangle for each voxel), wasn't warranted in my case as all the triangles are the result of "nice" tesselations. Now is it worth it? I am undecided, I suspect not tho' as long as you have the raytag/ray-id/mailbox optimization... Mike Gigante, RMIT