Maintaining Topology in Geometric Descriptions with Numerical Uncertainty

Mark G. Segal and Carlo H. Séquin

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-88-450
June 1988

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/CSD-88-450.pdf

Algorithms for computer graphics or computational geometry often infer the topological structure of geometrical objects from numerical data. Unavoidable errors (due to limited precision) affect these calculations so that their use may produce ambiguous or contradictory inferences.

An object description associating a tolerance with each of its topological features (vertices, edges and faces) is introduced. The possible effects of limited precision on geometric algorithms that operate on such descriptions are investigated. Methods are given for creating and manipulating such descriptions that produce topologically consistent object definitions. The methods minimize the occurrence of ambiguities and indicate those situations in which they may occur. These techniques have been incorporated into a program that computes constructive solid geometry (CSG) operations on polyhedral boundaries.


BibTeX citation:

@techreport{Segal:CSD-88-450,
    Author = {Segal, Mark G. and Séquin, Carlo H.},
    Title = {Maintaining Topology in Geometric Descriptions with Numerical Uncertainty},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1988},
    Month = {Jun},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/5508.html},
    Number = {UCB/CSD-88-450},
    Abstract = {Algorithms for computer graphics or computational geometry often infer the topological structure of geometrical objects from numerical data. Unavoidable errors (due to limited precision) affect these calculations so that their use may produce ambiguous or contradictory inferences.   <p>An object description associating a tolerance with each of its topological features (vertices, edges and faces) is introduced. The possible effects of limited precision on geometric algorithms that operate on such descriptions are investigated. Methods are given for creating and manipulating such descriptions that produce topologically consistent object definitions. The methods minimize the occurrence of ambiguities and indicate those situations in which they may occur. These techniques have been incorporated into a program that computes constructive solid geometry (CSG) operations on polyhedral boundaries.}
}

EndNote citation:

%0 Report
%A Segal, Mark G.
%A Séquin, Carlo H.
%T Maintaining Topology in Geometric Descriptions with Numerical Uncertainty
%I EECS Department, University of California, Berkeley
%D 1988
%@ UCB/CSD-88-450
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/5508.html
%F Segal:CSD-88-450