“Localized set operations for solid modeling” by Mantyla and Tamminen

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. 1974
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.
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.
4. Braid, I.C., Notes on a Geometric Modeller. CAD Group Document No. 101, Computer Laboratory, University of Cambridge, Cambridge, England, June, 1979
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-254
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.
7. Franklin, W.R., A linear exact hidden surface algorithm. ACM Computer Graphics 14(1980)3, p. 117-123.
8. Griffiths, J.G., Eliminating hidden edges in line drawings. Comput. Aided Des. 11(1979)2, p. 71-78.
9. Kedem, G., The quad-CIF tree data structure for hierarchical on-line algorithms, Proc. ACM Nineteenth Design Automation Conference, 1982, Las Vegas.
10. Lomet, D.B., Digital B-trees. Proc. 7th Int. Conf. on Very Large Data Bases, Cannes 1981, p. 333-344.
11. Meagher, D., Geometric modeling using octree encoding. Computer Graphics and Image Processing 19(1982), p. 129-147.
12. Mäntylä, M. and Sulonen, R., GWB – A Solid Modeler With Euler Operators. IEEE Computer Graphics & Applications 2(1982)7, p. 17-31
13. Nievergelt, J. and Preparata, F.P., Plane-sweep algorithms for intersecting geometric figures. Comm. ACM 25(1982)10; p. 739-747.
14. Okino, N. et al., TIPS-1 ’77 Version. Hokkaido University, 1977.
15. Quinlan, K.M. and Woodwark, J.R., A spatially-segmented solids datamase – justification and design, Proc. CAD 82 Conference, Brighton, England, 1982.
16. Requicha, A.A.G., Representations of rigid solids: theory, methods and systems. ACM Comp. Surv. 12(1980), p. 437-464.
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.
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.
19. Roth, S.D., Ray Casting for Modeling Solids. Computer Graphics and Image Processing 18(1982)2, p. 109-144
20. Shamos, M.I., Computational Geometry. PhD thesis, Yale University, 1978.
21. Six, H.W. and Wood, D., Counting and reporting intersections of d-ranges. IEEE trans. Comp. C-31(1982)3, p. 181-187.
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.
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.
24. Tamminen, M., A note on extendible hashing with overflow. Info. Proc. Lett. 15(1982)5, p. 227-232.
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.
26. Tikkanen, M., User’s manual of Blk. Rep. HTKK-TKO-B36, CAD-Project, Laboratory of Information Processing Science, Helsinki University of Technology, Espoo, 1981
27. Tilove, R.B., Set membership classification: a unified approach to geometric intersection problems. IEEE Trans. Computers, C-29(1980)10, p. 874-883.
28. Tilove, R.B., Exploiting spatial and structural locality in geometric modeling. Tech. Memo. No 38, Production Automation Project, University of Rochester, 1981.
29. Voelcker, H.B. and Requicha, A.A.G., Geometric Modeling of Mechanical Parts and Processes. IEEE Computer 10(1977)2, p. 48-57