An Algorithm for Geometric Set Operations Using Cellular Subdivision Techniques
- 1 May 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Computer Graphics and Applications
- Vol. 7 (5) , 44-55
- https://doi.org/10.1109/mcg.1987.276987
Abstract
Geometric set operations play an integral role in systems for CAD/CAM, for robot planning, and for modeling objects such as underground formations from empirical data. Two major issues in the implementation of geometric set operations are efficiency in the search for geometric intersections and effectiveness in the treatment of singular intersection cases. This article presents an algorithm for geometric set operations on planar polyhedral nonmanifold objects that addresses both these issues. First, an efficient search for geometric intersections is obtained by localizing the search to small regions of object space through a cellular subdivision scheme using the polytree data structure. Second, an effective treatment of singular intersection cases is obtained by mapping each singular intersection occurring in a region into one of a small set of cases.Keywords
This publication has 12 references indexed in Scilit:
- A Geometric Modeller Based on the Exact Octtree Representation of PolyhedraComputer Graphics Forum, 1986
- Boolean operations of 2-manifolds through vertex neighborhood classificationACM Transactions on Graphics, 1986
- Object representation by means of nonminimal division quadtrees and octreesACM Transactions on Graphics, 1985
- Boolean operations in solid modeling: Boundary evaluation and merging algorithmsProceedings of the IEEE, 1985
- Efficient editing of solid models by exploiting structural and spatial localityComputer Aided Geometric Design, 1984
- Localized set operations for solid modelingACM SIGGRAPH Computer Graphics, 1983
- Geometric modeling using octree encodingComputer Graphics and Image Processing, 1982
- Set Membership Classification: A Unified Approach to Geometric Intersection ProblemsIEEE Transactions on Computers, 1980
- Closure of Boolean operations on geometric entitiesComputer-Aided Design, 1980
- A linear time exact hidden surface algorithmPublished by Association for Computing Machinery (ACM) ,1980