Technical Reports

The ICICS/CS Reading Room

UBC CS TR-94-06 Summary

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