Efficient Computation of Object Boundary Intersection and Error Tolerance in VRCC-3D+
Nathan W. Eloe, Jennifer L. Leopold, Chaman L. Sabharwal · Distributed Multimedia Systems · 2012
Ƞ Computational geometry is a field that is relevant to computer graphics rendering, computational physical simulation, and countless other problem domains involving the use of image data. Efficiently determining the intersection of the boundaries, interiors, and exteriors of two 3D objects can mean the difference between a realistic and relevant simulation, and a slow program that produces results to that do not keep pace with user interaction with the object. However, the speed of these calculations is not the only area of concern. Taking into consideration the finite unit of resolution in a computer display (the pixel), the minimum change in distance the human eye can perceive, and error in the floating-point representation of numbers, it may be the case that the perceived correctness of these computations does not necessarily correspond to the accuracy with which the calculations are carried out. In this paper, we examine two of the most well-known methods of determining such intersections, as well as various programming language libraries available to perform these calculations. These existing approaches are considered with respect to limitations in human perception, display resolution, and floating point error. We also propose a new method which lends itself to exploiting the inherently parallel nature of these calculations. 뀀ഀȠ