Martti Mäntylä
ABSTRACT
Set operation algorithms form an important component of solid modeling systems. Their efficiency can be enhanced by localizing the search for geometric intersections to the region of overlap using a spatial directory. We present an algorithm that employs a three-dimensional extendible cell (EXCELL) directory to the set operation problem, and demonstrate by practical experiments the efficiency and the local nature of the algorithm.
- 1.Baumgart, B.G., Geometric modeling for computer vision. Report No. AIM-249, STAN-CS-74-463, Stanford AI Lab., Stanford University, Oct. 1974Google Scholar
- 2.Bentley, J.L. and Friedman, J.H., A survey of algorithms and data structures for range searching. ACM Comp. Surv. 11(1979)4, p. 397-409. Google ScholarDigital Library
- 3.Bentley, J.L. and Wood D. An optimal worst case algorithm for reporting intersections of rectangles. IEEE Trans. Comp. C-29(1980)7, p. 571-577.Google Scholar
- 4.Braid, I.C., Notes on a Geometric Modeller. CAD Group Document No. 101, Computer Laboratory, University of Cambridge, Cambridge, England, June, 1979Google Scholar
- 5.Eastman, C.M. and Weiler, K., Geometric Modeling Using the Euler Operators. Proc. First Ann. Conf. on Computer Graphics in CAD/CAM Systems, MIT, Apr,. 1979, p. 248-254Google Scholar
- 6.Fagin, R., Nievergelt, J., Pippenger, N. and Strong H.R., Extendible hashing, a fast access method for dynamic files. ACM TODS 4(1979)3, p. 315-344. Google ScholarDigital Library
- 7.Franklin, W.R., A linear exact hidden surface algorithm. ACM Computer Graphics 14(1980)3, p. 117-123. Google ScholarDigital Library
- 8.Griffiths, J.G., Eliminating hidden edges in line drawings. Comput. Aided Des. 11(1979)2, p. 71-78.Google ScholarCross Ref
- 9.Kedem, G., The quad-CIF tree data structure for hierarchical on-line algorithms, Proc. ACM Nineteenth Design Automation Conference, 1982, Las Vegas. Google ScholarDigital Library
- 10.Lomet, D.B., Digital B-trees. Proc. 7th Int. Conf. on Very Large Data Bases, Cannes 1981, p. 333-344.Google Scholar
- 11.Meagher, D., Geometric modeling using octree encoding. Computer Graphics and Image Processing 19(1982), p. 129-147.Google ScholarCross Ref
- 12.Mäntylä, M. and Sulonen, R., GWB - A Solid Modeler With Euler Operators. IEEE Computer Graphics & Applications 2(1982)7, p. 17-31Google Scholar
- 13.Nievergelt, J. and Preparata, F.P., Plane-sweep algorithms for intersecting geometric figures. Comm. ACM 25(1982)10; p. 739-747. Google ScholarDigital Library
- 14.Okino, N. et al., TIPS-1 '77 Version. Hokkaido University, 1977.Google Scholar
- 15.Quinlan, K.M. and Woodwark, J.R., A spatially-segmented solids datamase - justification and design, Proc. CAD 82 Conference, Brighton, England, 1982.Google Scholar
- 16.Requicha, A.A.G., Representations of rigid solids: theory, methods and systems. ACM Comp. Surv. 12(1980), p. 437-464. Google ScholarDigital Library
- 17.Requicha, A.A.G. and Voelcker, H.B., Constructive Solid Geometry. Tech. Memo. No 25, Production Automation Project, University of Rochester, Rochester, N.Y., 1977.Google Scholar
- 18.Requicha, A.A.G. and Voelcker, H.B., Solid modeling: a historical summary and contemporary assessment. IEEE Computer Graphics and Applications 2(1982)6, p. 9-24.Google ScholarDigital Library
- 19.Roth, S.D., Ray Casting for Modeling Solids. Computer Graphics and Image Processing 18(1982)2, p. 109-144Google ScholarCross Ref
- 20.Shamos, M.I., Computational Geometry. PhD thesis, Yale University, 1978. Google ScholarDigital Library
- 21.Six, H.W. and Wood, D., Counting and reporting intersections of d-ranges. IEEE trans. Comp. C-31(1982)3, p. 181-187.Google Scholar
- 22.Steinberg, H.A., Overlap and separation calculations using the SynthaVision three dimensional solid modeling system. Proc. Conf. On CAD/CAM Technology in Mechanical Engineering, Cambridge, Mass., March 24-26, 1982, p. 13-19.Google Scholar
- 23.Sutherland, I.E., Sproull, R.F. and Schumacher, R.A., A characterization of ten hidden-surface algorithms. ACM Comp. Surv. 6(1974)1, p. 1-55. Google ScholarDigital Library
- 24.Tamminen, M., A note on extendible hashing with overflow. Info. Proc. Lett. 15(1982)5, p. 227-232.Google ScholarCross Ref
- 25.Tamminen, M. and Sulonen, R., The EXCELL method for efficient geometric access to data. Proc. ACM Nineteenth Design Automation Conference, 1982, Las Vegas, p. 345-351. Google ScholarDigital Library
- 26.Tikkanen, M., User's manual of Blk. Rep. HTKK-TKO-B36, CAD-Project, Laboratory of Information Processing Science, Helsinki University of Technology, Espoo, 1981Google Scholar
- 27.Tilove, R.B., Set membership classification: a unified approach to geometric intersection problems. IEEE Trans. Computers, C-29(1980)10, p. 874-883.Google Scholar
- 28.Tilove, R.B., Exploiting spatial and structural locality in geometric modeling. Tech. Memo. No 38, Production Automation Project, University of Rochester, 1981.Google Scholar
- 29.Voelcker, H.B. and Requicha, A.A.G., Geometric Modeling of Mechanical Parts and Processes. IEEE Computer 10(1977)2, p. 48-57Google Scholar
Index Terms
- Localized set operations for solid modeling
Recommendations
Localized set operations for solid modeling
Set operation algorithms form an important component of solid modeling systems. Their efficiency can be enhanced by localizing the search for geometric intersections to the region of overlap using a spatial directory. We present an algorithm that ...
Cyclides in Surface and Solid Modeling
Special issue on computer-aided geometric designIt is shown that Dupin cyclides (C.P. Dupin, 1822), as surfaces in computer-aided geometric design (CAGD), have attractive properties such as low algebraic degree, rational parametric forms, and an easily comprehensible geometric representation using ...
Comments