On a Fundamental Physical Principle Underlying the Point Location
Algorithm in Computer Graphics
Sumit Ghosh
Department of Computer Science & Engineering
Arizona State University
Tempe, AZ 85287
sumit.ghosh@asu.edu
|
Abstract
The issue of point location is an important problem in computer graphics
and the study of efficient data structures and fast algorithms is an
important research area for both computer graphics and computational
geometry disciplines. When filling the interior region of a planar polygon
in computer graphics, it is necessary to identify all points that lie
within the interior region and those that are outside. Sutherland and
Hodgman are credited for designing the first algorithm to solve the
problem. Their approach utilizes vector construction and vector cross
products, and forms the basis of the ``odd parity'' rule. To verify whether
a test point is within or outside a given planar polygon, a ray from the
test point is drawn extending to infinity in any direction without
intersecting a vertex. If the ray intersects the polygon outline an odd
number of times, the region is considered interior. Otherwise, the point is
outside the region. In 3 dimensional space, Lee and Preparata propose an
algorithm but their approach is limited to point location relative to
convex polyhedrons with vertices in 3D-space. Although it is rich on optimal
data structures to reduce the storage requirement and efficient algorithms
for fast execution, a proof of correctness of the algorithm, applied to the
general problem of point location relative to any arbitrary surface in
3D-space, is absent in the literature. This paper argues that the
electromagnetic field theory and Gauss's Law constitute a fundamental basis
for the ``odd parity'' rule and shows that the ``odd parity'' rule may be
correctly extended to point location relative to any arbitrary closed
surface in 3D-space.