# 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://www.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://www.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://www.eecs.berkeley.edu/Pubs/TechRpts/1988/5508.html %F Segal:CSD-88-450