# Triangles in a uniform grid

What is the most efficient way to determine whether a triangle is in a grid voxel or not? I initialize a uniform grid (64 by 64 by 64 voxels of length/width/height of 1.0f each) and then a bunch of triangles (by triangles I mean 3 sets of float3 vertices. It is easy to determine whether a vertex is in a voxel or not, but not an edge… or even harder: the inside of a triangle (no edge or vertex presence). What is the most efficient way to either determine or initialize triangles such that the uniform grid voxels keep a record of which triangles they contain?

Here’s useful code for performing generalized triangle/box intersection:
http://jgt.akpeters.com/papers/AkenineMoller01/tribox.html
So find the minimum and maximum range of your triangle vertices, which gives you a set of potential voxels your triangle falls into. Use the test function to see which voxels actually contain the triangle.

If your triangles are very large compared to the grid, you’d likely change your strategy… the fact you have a uniform grid gives you some large advantages. In that case you could apply fancy but complicated techniques:
http://www.graphicsinterface.org/proceedin…08/paper108.pdf

There are likely other methods as well, especially with uniform grids.