Boundary evaluation of non-convex primitives to produce parametric trimmed surfaces

ABSTRACT

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.

REFERENCES

• 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: I. C. Braid, The synthesis of solids bounded by many faces, Communications of the ACM, v.18 n.4, p.209-216, April 1975 [doi>10.1145/360715.360727]
• 4: Wayne E. Carlson, An algorithm and data structure for 3D object synthesis using surface patch intersections, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.255-263, July 1982
• 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: Yong Tsui Lee , Aristides A. G. Requicha, Algorithms for computing the volume and other integral properties of solids. I. known methods and open issues, Communications of the ACM, v.25 n.9, p.635-641, Sept 1982 [doi>10.1145/358628.358643]
• 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: Michael E. Mortenson, Geometric modeling, John Wiley & Sons, Inc., New York, NY, 1985
• 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: Kevin Weiler, Polygon comparison using a graph representation, ACM SIGGRAPH Computer Graphics, v.14 n.3, p.10-18, July 1980
• 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Modeling packages; Geometric algorithms, languages, and systems

General Terms:
Algorithms, Design, Theory