- View PDF version of TR-94-06 (155860 bytes)
- View PostScript version of TR-94-06
- Save PostScript version of TR-94-06
- Save gzipped PostScript version of TR-94-06 (49186 bytes)

- Constant Time Parallel Indexing of Points in a Triangle, February 1994 Simon Kahan and Pierre Kelsen, 9 pages
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.