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 objects can mean the difference between a realistic and relevant simulation, and a slow program that produces results that do not keep pace with user manipulation of 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) 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.
- Computational Geometry,
- Digital Arithmetic,
- Multimedia Systems,
- Computer Display,
- Computer Graphics Rendering,
- Display Resolutions,
- Efficient Computation,
- Floating Point Errors,
- Human Perception,
- Object Boundaries,
- Physical Simulation,
- Computer Graphics
Available at: http://works.bepress.com/jennifer-leopold/11/