“Boundary evaluation of non-convex primitives to produce parametric trimmed surfaces” by Crocker and Reinke

To integrate a CSG-based solid modeler into an existing wireframe/surface modeling system, new boundary evaluation technology has been developed. This scheme uses exact representations for the simple quadric surfaces and both exact and approximate representations of higher-order curved surfaces. It supports parametric primitives (box, wedge, sphere, cylinder, cone, torus), procedural primitives (extrusion, revolution, tube) and a sculptured surface primitive. The output includes curves, parametric trimmed surfaces, and a data structure of adjacency information.An existing boundary evaluator (PADL-2’s) has been enhanced to allow a general non-convex faceted primitive with planar and quadric facets. This new hybrid evaluator combines two techniques for curve/primitive classification. PADL-2’s existing halfspace-based classification is reserved for the simple convex primitives, and a new ray firing based classification is applied to the non-convex primitives. After evaluation, approximate intersection curves (from intersections involving higher order surfaces) are refined to a specified tolerance by exploiting an exact parametric representation of the surfaces of the primitives. The refined curves and the quadric surface intersection curves are used to create a parametric trimmed surface representation of the solid. This combination of techniques and representations offers advantages in accuracy, robustness and efficiency suitable to a production environment.

1. Baumgart B.G., “Geometric Modeling for Computer Vision,” rep, STAN-CS-74-463, Stanford Artificial Intelligence Lab., Stanford Univ., Stanford, CA 1974.
2. Boyse, J.W., Gilchrist J.E., “GMSolid: Interactive Modeling for Design and Analysis of Solids,” IEEE Computer Graphics and Applications, Vol. 2, No 2, pp. 27-40, Mar. 1982.
3. Braid, l.C., “The Synthesis of Solids Bounded by Many Faces,” Communications of the ACM, Vol. 18, No. 4, April 1975, pp. 209-216.
4. Carlson, W.E., “An Algorithm and Data Structures for 3D Object Synthesis Using Surface Patch Intersections,” ACM Computer Graphics, Vol. 16, No. 3, July 1982, pp. 255-263.
5. Eastman C.M., Yessios C.J., “An Efficient Algorithm for Finding the Union, Intersection, and Differences of Spatial Domains,” Tech. Rep 31, Institute of Physical Planning, Carnegie-Mellon Univ., Pittsburgh, PA. Sept. 1972.
6. Franklin, W.R., “Efficient Polyhedron Intersection and Union,” Proc. Graphics Interface ’82, (Toronto, Canada, May 17-21, 1982), pp. 73-80.
7. Glassner, A.S., “Space Subdivision for Fast Ray Tracing,” IEEE Computer Graphics and Applications, Vot. 4, No. 10, October 1984, pp. 15-22.
8. Hillyard R.C,, “The Build Group of Solid Modelers,” 1EEE Computer Graphics and Applications, Vol. 2, No. 2, March 1982, pp. 43-52.
9. Katay Y.E., Eastman, C.M., “Shape Operations: An Algorithm for Spatial-Set Manipulations of Solid Objects,” CAD Graphics Lab., Carnegie-Mellon Univ., Pittsburgh, PA, July 1980.
10. Lee Y.T., Requicha, A.A.G., “Algorithms for Computing the Volume and Other Integral Properties of Solids. I. Known Methods and Open Issues,” Communications of the ACM, Vol. 25, No. 9, September 1982, pp. 635-641.
11. Miller, J.R., “Sculptured Surfaces in Solid Models: Issues and Alternative Approaches,” IEEE Computer Graphics and Applications, Vol. 6, No. 12, December 1986, pp. 37-48.
12. Mortenson, Michael E. Geometric Modeling. John Wiley & Sons, New York, 1985, ch. 6.
13. Pfeifer, H., “Methods used for Intersecting Geometrical Entities in the GMP Module for Volume Geometry,” Computer-Aided Desion, Vol. 17, No. 7, September 1985, pp. 311-318.
14. Putnam, L.K., Subrahmanyam, P.A., “Computation of the Union, Intersection and Difference of n-dimensional Objects via Boundary Classification,” Department of Computer Science, University of Utah, Salt Lake City, UT, 1982.
15. Requicha, A.A.G., Voelcker, H.B., “Boolean Operations in Solid Modeling: Boundary Evaluation and Merging Algorithms,” Proceedings of the IEEE, Vol, 73, No. 1, January 1985, pp. 30-44
16. Requicha, A.A.G., Voetcker, H.B., “Boolean Operations in Solid Modeling: Boundary Evaluation and Merging Algorithms,” Tech. Memo. 26, Production Automation Project, Univ, of Rochester, Rochester, NY, Jan 1984.
17. Requicha, A.A.G., Voelcker, H.B., “Solid Modeling: A Historical Summary and Contemporary Assessment,” IEEE Computer Graphics and Applications, Vol. 2, No. 2, March 1982, pp. 9-24.
18. Requicha, A.A.G., Voelcker, H.B., “Solid Modeling: Current Status and Research Directions,” IEEE Computer Graphics and Applications, Vol. 3, No. 7, October 1983, pp. 25-37.
19. Sarraga, R.F., Waters, W.C., “Free-Form Surfaces in GMSolid: Goals and issues,” Solid Modeling by Computers. Plenum Press, New York, 1984, pp. 187-210.
20. Tilove, R.B., “Exploiting Spatial and Structural Locality in Geometric Modeling,” Tech. Memo. 38, Production Automation Project, Univ. of Rochester, Rochester, NY, October 198t.
21. Tilove, R.B., “Set Membership Classification: A Unified Approach to Geometric Intersection Problems,” IEEE Transactions on Computers, Vol. C-29, No. 10, October 1980, pp. 874-883.
22. Tilove, R.B., Requicha, A.A.G, “Closure of Boolean Operations on Geometric Entities,” Computer-Aided Des., Vot. 12, No. 5, September 1980, pp. 219-220,
23. Weiler, K., “Polygon Comparison Using a Graph Representation,” ACM Computer Graphics, Vol 14, No 3, July 1980, pp. 10-18.
24. Weiler, K., “Edge-Based Data Structures for Solid Modeling in Curved-Surface Modeling Environments,” IEEE Computer Graphics and Applications, Vol. 5, No. 1, January 1985, pp. 21-40.
25. Yamaguchi, F., Tokieda, T., “A Unified Algorithm for Boolean Shape Operations,” IEEE Computer Graphics and Applications, Vol. 4, No 6, pp. 24-37, June 1984.