Constant Time Queries on Uniformly Distributed Points on a Hemisphere

摘要

A set of uniformly distributed points on a hemisphere is generated using a popular method based on triangle subdivision. In computer graphics applications, each data point (for example, representing a direction from a point on a surface) is typically associated with additional information (for example, a radiance value). Given an arbitrary query point on the hemisphere, we require the nearest data point from the given distribution. An algorithm is presented that finds the data point in constant time, independently of the number of original points in the distribution. A portion of the hemisphere is rendered such that each point in the distribution has an associated set of quadrilaterals rendered with a unique color index for that point. The frame-buffer for the rendered hemisphere portion can be stored in off-screen memory. Any query point can be projected into this off-screen frame buffer, projected to a 'pixel' location, and the color index stored at this pixel location found. This color index is a lookup into an array of the original data points. This algorithm is presented in detail, and an illustrative implementation in OpenGL is described. The sample code is available at the website given at the end of this paper.