Consider a triangle whose three vertices are grid points. Let k denote the number of grid points in the triangle. We describe an indexing of the triangle: a bijective mapping from {0, ..., k-1} to the grid points in the triangle. Computing such a mapping is a fundamental subroutine in fine-grained parallel computation arising in graphics applications such as ray-tracing. We describe a very fast indexing algorithm: after a preprocessing phase requiring time proportional to the number of bits in the vertices of the triangle, a grid point in the triangle can be computed in constant time from its index. The method requires only constant space.
If you have any questions or comments regarding this page please send mail to help@cs.ubc.ca.