Constraints in constructive solid geometry

ABSTRACT

The success of solid modelling in industrial design depends on facilities for specifying and editing parameterized models of solids through user-friendly interaction with a graphical front-end. Systems based on a dual representation, which combines Constructive Solid Geometry (CSG) and Boundary representation (BRep), seem most suitable for modelling mechanical parts. Typically they accept a CSG-compatible input (Boolean combinations of solid primitives) and offer facilities for parameterizing and editing part definitions. The user need not specify the topology of the boundary, but often has to solve three-dimensional trigonometric problems to compute the parameters of rigid motions that specify the positions of primitive solids. A front-end that automatically converts graphical input into rigid motions may be easily combined with boundary-oriented input, but its integration in dual systems usually complicates the editing process and limits the possibilities of parameterizing solid definitions. This report proposes a solution based on three main ideas: (1) enhance the semantics of CSG representations with rigid motions that operate on arbitrary collections of sub-solids regardless of their position in the CSG tree, (2) store rigid motions in terms of unevaluated constraints on graphically selected boundary features, (3) evaluate constraints independently, one at a time, in user-specified order. The third idea offers an alternative to known approaches, which convert all constraints into a large system of simultaneous equations to be solved by iterative numerical methods. The resulting front-end is inadequate for solving problems where multiple constraints must be met simultaneously, but provides a powerful tool for specifying and interactively editing parameterized models of mechanical parts and mechanisms. The order in which constraints are evaluated may also be used as a language for specifying the sequence of assembly and set-up operations. An implementation under way is based on the interpreter of a new object oriented programming language, enhanced with geometric classes. Constraint evaluation results in the activation of methods which compute rigid motions from surface information. The set of available methods may be extended by the users, and methods may be integrated in higher level functions whose algorithmic nature simplifies the treatment of degenerate cases. Graphic interaction is provided through a geometrical engine which lets the user manipulate shaded images produced efficiently from the CSG representation of solid models.

REFERENCES

• 1: D. Meagher, "Geometric modeling using octree encoding", Computer Graphics and Image Processing, vol. 19, no. 2, pp. 129-147, June 1982.
• 2: R.F. Sarraga and W.C. Waters, "Free-form surfaces in GMSOLID: Goals and issues", in M. S. Pickett and J. W. Boyse, Eds., Solid Modeling by Computers. New York: Plenum Press, pp. 187-209, 1984.
• 3: A.A.G. Requicha and H.B. Voelcker, "Solid modelling: Current status and research directions", IEEE Computer Graphics and Applications, vol. 3, no. 7, pp. 25-37, October 1983.
• 4: J.W. Boyse and J.E. Glichrist, "GMSolid: lntersactive modelling for design and analysis of solids", IEEE Computer Graphics and Applications, vol. 2, no. 2, pp. 27-40, March 1982.
• 5: Dwight D Freund, An interactive procedure for constructing line and circle tangencies, IEEE Computer Graphics and Applications, v.6 n.4, p.59-63, April 1986 [doi>10.1109/MCG.1986.276721]
• 6: W.F. Fitzgerald, "Using actual dimensions to determine the proportions of line drawings in computer graphics", Computer Aided Design, vol. 13, no. 6, pp. 377-382, November 1981.
• 7: D.L. Vossler, "Sweep-to-CSG conversion using pattern recognition techniques", IEEE Computer Graphics and Applications, vol. 5, no. 8, pp. 61-68, August 1985.
• 8: A.A.G. Requicha, "Representation of tolerances in solid modeling: Issues and alternative approaches", in M.S. Pickett and J.W. Boyse, Eds., Solid Modelling by Computers, New York: Plenum Press, pp. 3-22, 1984.
• 9: 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]
• 10: M.A. O'Connor, "Projection of natural quadrics", IBM Research Report RC 11188, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, June 1985.
• 11: R.F. Sarraga, "Algebraic methods for intersections of quadric surfaces in GMSOLID", Computer Vision, Graphics and Image Processing, vol. 22, no. 2, pp. 222-238, May 1983.
• 12: A.P. Morgan and R.F. Sarraga "A method for computing three surface intersection points in GMSOLID", Report GMR-3964, General Motors Research Labs., Warren, MI, February 1982.
• 13: N.M. Samuel, A.A.G. Requicha and S.A. Elkind, "Methodology and results of an industrial part survey", Tech. Memo. No. 21, Production Automation Project, Univ. of Rochester, July 1976.
• 14: J.R. Rossignac and A.A.G. Requicha, "Constant radius blending in Solid Modelling", Computers in Mechanical Engineering, vol. 3, no. 1, pp. 65-73, July 1984.
• 15: G. Monge, Applications de l'analyse glla gdometrie. Paris: Bachelier, 5th ed., 1849.
• 16: J.R. Rossignac and A.A.G. Requicha, "Piecewise Constant Curvature Approximations for Geometric Modelling", IBM Research Report RC 12171, IBM, T.J. Watson Research Center, Yorktown Heights, NY, October 1986.
• 17: Wolfgang Böhm , Gerald Farin , Jürgen Kahmann, A survey of curve and surface methods in CAGD, Computer Aided Geometric Design, v.1 n.1, p.1-60, July 1984 [doi>10.1016/0167-8396(84)90003-7]
• 18: Hiroaki Chiyokura , Fumihiko Kimura, Design of solids with free-form surfaces, Proceedings of the 10th annual conference on Computer graphics and interactive techniques, p.289-298, July 25-29, 1983, Detroit, Michigan, United States
• 19: D.D. Grossman, "Procedural representation of threedimensional objects", IBM Journal of Research and Development, vol. 20, pp. 582-589, November 1976.
• 20: N. Okino et al., "TIPS- 1 ", Institute of Precision Engineering, Hokkaido University, Sapporo, Japan, 1978.
• 21: K.j. Weiler, "Edge-based data structure for solid modelling in curved surface environments", IEEE Computer Graphics and Applications, vol. 5, no. 1, pp. 21-40, January 1985.
• 22: William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
• 23: D Krishnan , L M Patnaik, GEODERM: Geometric shape design system using an entity-relationship model, Computer-Aided Design, v.18 n.4, p.207-218, May 1986 [doi>10.1016/0010-4485(86)90132-6]
• 24: C.M. Eastman and K. Weiler, "Geometric modelling using the Euler operators", Proc. First Annual Conf. on Computer Graphics in CAD~CAM Systems, MIT Cambridge, MA, pp. 248-259, April 9-11, 1979.
• 25: M. Mantyla and R. Sulonen, "GWB: a solid modeller with Euler operators", IEEE Computer Graphics and Applications, vol. 2, no. 7, pp. 17-31, September 1982.
• 26: A.A.G. Requicha, "Mathematical models of rigid solid objects", Teeh. Memo. No. 28, Production Automation Project, Univ. of Rochester, November 1977.
• 27: Christoph M. Hoffmann , John E. Hopcroft, Automatic Surface Generation in Computer Aided Design, Cornell University, Ithaca, NY, 1985
• 28: J R Rossignac , A A G Requicha, Offsetting operations in solid modelling, Computer Aided Geometric Design, v.3 n.2, p.129-148, August 1986 [doi>10.1016/0167-8396(86)90017-8]
• 29: Aristides G. Requicha, Representations for Rigid Solids: Theory, Methods, and Systems, ACM Computing Surveys (CSUR), v.12 n.4, p.437-464, Dec. 1980 [doi>10.1145/356827.356833]
• 30: R.B. Tilove, "Set membership classification: A unified approach to geometric intersection problems", IEEE Trans. on Computers, vol. C-29, no. 10, pp. 874-883, October 1980.
• 31: A.A.G. Requicha and H.B. Voelcker, "Boolean Operations in Solid Modelling: Boundary Evaluation and Merging Algorithms" Proceedings of the IEEE, Vol. 73, No 1, January 1985.
• 32: Jaroslaw Roman Rossignac, Blending and offsetting solid models (cad/cam, computational geometry, representations, curves, surfaces, approximation), 1985
• 33: C.M. Brown, "PADL-2: A technical summary", IEEE Computer Graphics and Applications, vol. 2, no. 2, pp. 69-84, March 1982.
• 34: J.R. Rossignac and H.B.Voelcker, "Active Zones in Constructive Solid Geometry for Redundancy and Interference Detection", IBM Research Report, RC 11991, IBM, T.J. Watson Research Center, Yorktown Heights, NY, June 1986.
• 35: J.R. Rossignac and A.A.G. Requicha, "Depth buffering display techniques for constructive solid geometry", IEEE, Computer Graphics and Applications, vol. 6, no. 9, pp. 29-39, September 1986.
• 36: A.A.G. Requicha and S.C. Chan, "Representation of geometric features, tolerances and attributes in solid modellers based on constructive geometry", IEEE Journal of Robotics and Automation, vol. 2, no. 3, September 1986.
• 37: S.D. Roth, "Ray casting for modeling solids", Computer Graphics and Image Processing, vol. 18, no. 2, pp. 109-144, February 1982.
• 38: David C Anderson, Closing the gap: A workstation-mainframe connection, Computers in Mechanical Engineering, v.4 n.6, p.16-24, May 1986
• 39: P.G. Molari, (Private communication), Facolta di ingegneria, Instituto di Meccanica Applicata alle macchine, University of Bologna, Italy, August 1986.
• 40: L.I. Liberman and M.A. Wesley, "An automatic programming system for computer controlled mechanical assembly", IBM Journal of Research and Development, vol. 21, no. 4, pp. 321-333, July 1977.
• 41: M.A. Wesley, T. Lozano-Perez, L.I. Lieberman, M.A. Lavin, and D.D.Grossman, "A geometric modelling system for automated mechanical assembly", IBM Journal of Research and Development, vol. 24, no. 1, pp. 64-74, January 1980.
• 42: C.M. Eastman, The design of assemblies, SAE Technical Paper Series, Society of Automotive Engineers, Inc., USA, 1981.
• 43: Kunwoo Lee , David C. Gossard, A hierarchical data structure for representing assemblies: part I, Computer-Aided Design, v.17 n.1, p.15-19, Jan./Feb. 1985 [doi>10.1016/0010-4485(85)90005-3]
• 44: I. Sutherland, "Sketchpad, a man-machine graphical communication system", PhD thesis, MIT, January 1963.
• 45: R. C. Hillyard , I. C. Braid, Characterizing non-ideal shapes in terms of dimensions and tolerances, ACM SIGGRAPH Computer Graphics, v.12 n.3, p.234-238, August 1978
• 46: Greg Nelson, Juno, a constraint-based graphics system, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.235-243, Jul. 1985
• 47: V. C. Lin , D. C. Gossard , R. A. Light, Variational geometry in computer-aided design, ACM SIGGRAPH Computer Graphics, v.15 n.3, p.171-177, August 1981
• 48: F. Kimura, H. Suzuki, and L. Wingard, "A uniform approach to dimensioning and tolerancing in product modelling", Proc. CAPE'86, 1986.
• 49: M. Managaki and K. Kawago, "Parametric man/machine interactions with semantic data", Computer Graphics, vol. 7, no. 3-4, pp. 233-242, 1983.
• 50: A.P. Ambler and R.J. Poppelstone, "Inferring the positions of bodies from specified spatial relationships" Artificial Intelligence vol. 6, pp. 15 7-174, 1975.
• 51: Kunwoo Lee , Guy Andrews, Inference of the positions of components in an assembly: part 2, Computer-Aided Design, v.17 n.1, p.20-24, Jan./Feb. 1985 [doi>10.1016/0010-4485(85)90006-5]
• 52: Alan Borning, The Programming Language Aspects of ThingLab, a Constraint-Oriented Simulation Laboratory, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.4, p.353-387, Oct. 1981 [doi>10.1145/357146.357147]
• 53: L.R. Nackman, M.A. Lavin, R.H. Taylor, W.C. Dietrich, and D.D. Grossman, "AML/X: a programming language for design and manufacturing", IBM Research Report RC 11992, july 1986.
• 54: M. Orlowski, "The computation of the distance between polyhedra in 3-space", presented at SlAM Conference on Geometric Modeling and Robotics, Albany, NY, July 1985.
• 55: S.A. Cameron and R.K. Culley, "Determining the minimum translational distance between two convex polyhedra", Proc. 1986 IEEE lnt'l Conf. on Robotics and Automation, San Francisco, CA, pp. 591-596, April 7-10, 1986.
• 56: J.R. Rossignac, "Simple geometry in AML/X: points, vectors, coordinate frames, and linear transformations", Internal report, Design Automation Group, IBM, T.J. Watson Research Center, Yorktown Heights, NY, May 1986.
• 57: M. V. Wilkes, Constraint-type statements in programming languages, Communications of the ACM, v.7 n.10, p.587-588, Oct. 1964 [doi>10.1145/364888.364967]
• 58: S.C. Chan and H.B. Voelcker, "An introduction to MPL- A new machining process/programming language", Proc. 1EEE Internat. Conf. on Robotics and Automation" San Francisco, CA, pp. 333-344, April 7-10, 1985.
• 59: G.J. Sussman and G.L. Steele Jr. "CONSTRAINTS- A language for expressing almost-hierarchical descriptions", Artificial Intelligence, vol. 14, pp. 1-39, 1980.
• 60: F. Arbab and J.M. Wing, "Geometric reasoning: A new paradigm for processing geometric information", Report TR-85-333, Computer Science Department, University of Southern California, Los Angeles, July 1985.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Constructive solid geometry (CSG)**

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Performance, Theory

Keywords:
computer graphics, constraints, quadric surfaces, rigid motions, solid modelling