Geometric constraint solving

Last updated

Geometric constraint solving is constraint satisfaction in a computational geometry setting, which has primary applications in computer aided design. [1] A problem to be solved consists of a given set of geometric elements and a description of geometric constraints between the elements, which could be non-parametric (tangency, horizontality, coaxiality, etc) or parametric (like distance, angle, radius). The goal is to find the positions of geometric elements in 2D or 3D space that satisfy the given constraints, [2] which is done by dedicated software components called geometric constraint solvers.

Contents

Geometric constraint solving became an integral part of CAD systems in the 80s, when Pro/Engineer first introduced a novel concept of feature-based parametric modeling concept. [3] [4]

There are additional problems of geometric constraint solving that are related to sets of geometric elements and constraints: dynamic moving of given elements keeping all constraints satisfied, [5] detection of over- and under-constrained sets and subsets, [6] [7] auto-constraining of under-constrained problems, etc.

Methods

A general scheme of geometric constraint solving consists of modeling a set of geometric elements and constraints by a system of equations, and then solving this system by non-linear algebraic solver. For the sake of performance, a number of decomposition techniques could be used in order to decrease the size of an equation set: [8] decomposition-recombination planning algorithms, [9] [10] tree decomposition, [11] C-tree decomposition, [12] graph reduction, [13] re-parametrization and reduction, [14] computing fundamental circuits, [15] body-and-cad structure, [16] or the witness configuration method. [17]

Some other methods and approaches include the degrees of freedom analysis, [18] [19] symbolic computations, [20] rule-based computations, [21] constraint programming and constraint propagation, [21] [22] and genetic algorithms. [23]

Non-linear equation systems are mostly solved by iterative methods that resolve the linear problem at each iteration, the Newton-Raphson method being the most popular example. [21]

Applications

Geometric constraint solving has applications in a wide variety of fields, such as computer aided design, mechanical engineering, inverse kinematics and robotics, [24] architecture and construction, molecular chemistry, [25] and geometric theorem proving. The primary application area is computer aided design, where geometric constraint solving is used in both parametric history-based modeling and variational direct modeling. [26]

Software implementations

The list of geometric constraint solvers includes at least

See also

Related Research Articles

<span class="mw-page-title-main">Computer-aided design</span> Constructing a product by means of computer

Computer-aided design (CAD) is the use of computers to aid in the creation, modification, analysis, or optimization of a design. This software is used to increase the productivity of the designer, improve the quality of design, improve communications through documentation, and to create a database for manufacturing. Designs made through CAD software help protect products and inventions when used in patent applications. CAD output is often in the form of electronic files for print, machining, or other manufacturing operations. The terms computer-aided drafting (CAD) and computer-aided design and drafting (CADD) are also used.

<span class="mw-page-title-main">Constructive solid geometry</span> Creating a complex 3D surface or object by combining primitive objects

Constructive solid geometry is a technique used in solid modeling. Constructive solid geometry allows a modeler to create a complex surface or object by using Boolean operators to combine simpler objects, potentially generating visually complex objects by combining a few primitive ones.

<span class="mw-page-title-main">Solid modeling</span> Set of principles for modeling solid geometry

Solid modeling is a consistent set of principles for mathematical and computer modeling of three-dimensional shapes (solids). Solid modeling is distinguished within the broader related areas of geometric modeling and computer graphics, such as 3D modeling, by its emphasis on physical fidelity. Together, the principles of geometric and solid modeling form the foundation of 3D-computer-aided design and in general support the creation, exchange, visualization, animation, interrogation, and annotation of digital models of physical objects.

<span class="mw-page-title-main">Computer-aided architectural design</span>

Computer-aided architectural design (CAAD) software programs are the repository of accurate and comprehensive records of buildings and are used by architects and architectural companies for architectural design and architectural engineering. As the latter often involve floor plan designs CAAD software greatly simplifies this task.

A geometric modeling kernel is a solid modeling software component used in computer-aided design (CAD) packages. Available modelling kernels include:

CAD data exchange is a method of drawing data exchange used to translate between different computer-aided design (CAD) authoring systems or between CAD and other downstream CAx systems.

<span class="mw-page-title-main">Mesh generation</span> Subdivision of space into cells

Mesh generation is the practice of creating a mesh, a subdivision of a continuous geometric space into discrete geometric and topological cells. Often these cells form a simplicial complex. Usually the cells partition the geometric input domain. Mesh cells are used as discrete local approximations of the larger domain. Meshes are created by computer algorithms, often with human guidance through a GUI, depending on the complexity of the domain and the type of mesh desired. A typical goal is to create a mesh that accurately captures the input domain geometry, with high-quality (well-shaped) cells, and without so many cells as to make subsequent calculations intractable. The mesh should also be fine in areas that are important for the subsequent calculations.

<span class="mw-page-title-main">Solid Edge</span> Computer-aided design software

Solid Edge is a 3D CAD, parametric feature and synchronous technology solid modeling software. It runs on Microsoft Windows and provides solid modeling, assembly modelling and 2D orthographic view functionality for mechanical designers. Through third party applications it has links to many other Product Lifecycle Management (PLM) technologies.

The term "feature" implies different meanings in different engineering disciplines. This has resulted in many ambiguous definitions for feature. A feature, in computer-aided design (CAD), usually refers to a region of a part with some interesting geometric or topological properties. These are more precisely called form features. Form features contain both shape information and parametric information of a region of interest. They are now ubiquitous in most current CAD software, where they are used as the primary means of creating 3D geometric models. Examples of form features are extruded boss, loft, etc. Form feature is not the only type of feature that is discussed in CAD literature. Sometimes a part's functional or manufacturing features of the subject of attention. Although it is quite possible to see form features and manufacturing features are called by the same name, they are not exactly the same concepts. For example, one may either use the name "pocket" to refer to a swept cut on the boundary of a part model, or to refer to a trace left on the part boundary by a specific machining operation. The former is exclusively concerned with a geometric shape whereas the latter is concerned with both the geometric shape and a manufacturing operation, needing more parameters in its definition. As such, a manufacturing feature can be minimally defined as a form feature, but not necessarily vice versa. Machining features are an important subset of manufacturing features. A machining feature can be regarded as the volume swept by a "cutting" tool, which is always a negative (subtracted) volume. Finally, there is also the concept of assembly feature, which encodes the assembly method between connected components.

Architectural design optimization (ADO) is a subfield of engineering that uses optimization methods to study, aid, and solve architectural design problems, such as optimal floorplan layout design, optimal circulation paths between rooms, sustainability and the like. ADO can be achieved through retrofitting, or it can be incorporated within the initial construction a building. Methods of ADO might include the use of metaheuristic, direct search or model-based optimisation. It could also be a more rudimentary process involving identification of a perceived or existing problem with a buildings design in the concept design phase.

<span class="mw-page-title-main">BricsCAD</span> Computer-aided design software

BricsCAD® is a software application for computer-aided design (CAD), developed by Bricsys nv. The company was founded in 2002 by Erik de Keyser, a longtime CAD entrepreneur. In 2011 Bricsys acquired the intellectual property rights from Ledas for constraints-based parametric design tools, permitting the development of applications in the areas of direct modeling and assembly design. Bricsys is headquartered in Ghent, Belgium, and has additional development centers in Nizhny Novgorod and Novosibirsk, Russia; Bucharest, Romania and Singapore. Bricsys is a founding member of the Open Design Alliance, and joined the BuildingSMART International consortium in December 2016.

<span class="mw-page-title-main">Geometric design</span> Branch of computational geometry

Geometrical design (GD) is a branch of computational geometry. It deals with the construction and representation of free-form curves, surfaces, or volumes and is closely related to geometric modeling. Core problems are curve and surface modelling and representation. GD studies especially the construction and manipulation of curves and surfaces given by a set of points using polynomial, rational, piecewise polynomial, or piecewise rational methods. The most important instruments here are parametric curves and parametric surfaces, such as Bézier curves, spline curves and surfaces. An important non-parametric approach is the level-set method.

<span class="mw-page-title-main">Generative design</span> Iterative design process

Generative design is an iterative design process that uses software to generate outputs that fulfill a set of constraints iteratively adjusted by a designer. Whether a human, test program, or artificial intelligence, the designer algorithmically or manually refines the feasible region of the program's inputs and outputs with each iteration to fulfill evolving design requirements. By employing computing power to evaluate more design permutations than a human alone is capable of, the process is capable of producing an optimal design that mimics nature's evolutionary approach to design through genetic variation and selection. The output can be images, sounds, architectural models, animation, and much more. It is therefore a fast method of exploring design possibilities that is used in various design fields such as art, architecture, communication design, and product design.

<span class="mw-page-title-main">OpenSCAD</span> Free software for creating 3D objects

OpenSCAD is a free software application for creating solid 3D computer-aided design (CAD) objects. It is a script-only based modeller that uses its own description language; the 3D preview can be manipulated interactively, but cannot be interactively modified in 3D. Instead, an OpenSCAD script specifies geometric primitives and defines how they are modified and combined to render a 3D model. As such, the program performs constructive solid geometry (CSG). OpenSCAD is available for Windows, Linux, and macOS.

Spectral shape analysis relies on the spectrum of the Laplace–Beltrami operator to compare and analyze geometric shapes. Since the spectrum of the Laplace–Beltrami operator is invariant under isometries, it is well suited for the analysis or retrieval of non-rigid shapes, i.e. bendable objects such as humans, animals, plants, etc.

<span class="mw-page-title-main">Alibre Design</span> CAD software

Alibre Design is a 3D parametric computer aided design software suite developed by Alibre for Microsoft Windows. Available in fifteen languages. Alibre is a brand of Alibre, LLC, a company based in Texas.

<span class="mw-page-title-main">SolveSpace</span> Open-source computer-aided design software

SolveSpace is a free and open-source 2D/3D constraint-based parametric computer-aided design (CAD) software that supports basic 2D and 3D constructive solid geometry modeling.

<span class="mw-page-title-main">Constraint (computer-aided design)</span> Imposed limitations in computer-aided design

A constraint in computer-aided design (CAD) software is a limitation or restriction imposed by a designer or an engineer upon geometric properties of an entity of a design model that maintains its structure as the model is manipulated. These properties can include relative length, angle, orientation, size, shift, and displacement. The plural form constraints refers to demarcations of geometrical characteristics between two or more entities or solid modeling bodies; these delimiters are definitive for properties of theoretical physical position and motion, or displacement in parametric design. The exact terminology, however, may vary depending on a CAD program vendor.

<span class="mw-page-title-main">C3D Toolkit</span> Geometric modelling kernel

C3D Toolkit is a proprietary cross-platform geometric modeling kit software developed by Russian by C3D Labs. It's written in C++. It can be licensed by other companies for use in their 3D computer graphics software products. The most widely known software in which C3D Toolkit is typically used are computer aided design (CAD), computer-aided manufacturing (CAM), and computer-aided engineering (CAE) systems.

References

  1. ↑ Roller, edited by Beat Brüderlin, Dieter (1998). Geometric Constraint Solving and Applications. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 3–23. ISBN   978-3-642-58898-3.{{cite book}}: |first1= has generic name (help)CS1 maint: multiple names: authors list (link)
  2. ↑ Christoph M. Hoffmann; Pamela J. Vermeer. Geometric constraint solving in R2 and R3. doi:10.1142/9789812831699_0008. S2CID   18272588.
  3. ↑ Robert Joan-Arinyo. Basics on Geometric Constraint Solving. CiteSeerX   10.1.1.331.9554 .
  4. ↑ R. Anderl; R. Mendgen (1996). "Modelling with constraints: theoretical foundation and application". Computer-Aided Design. 28 (3): 155–168. doi:10.1016/0010-4485(95)00023-2.
  5. ↑ Marc Freixas; Robert Joan-Arinyo; Antoni Soto-Riera (2010). "A constraint-based dynamic geometry system". Computer-Aided Design. 42 (2): 151–161. doi:10.1016/j.cad.2009.02.016.
  6. ↑ Rossignac, Jaroslaw; SIGGRAPH, Joshua Turner, editors; sponsored by ACM (1991). Proceedings : Symposium on Solid Modeling Foundations and CAD/CAM Applications, Radisson Plaza Hotel, Austin, Texas, June 5-7, 1991. New York: Association for Computing Machinery. ISBN   978-0-89791-427-7.{{cite book}}: |first2= has generic name (help)CS1 maint: multiple names: authors list (link)
  7. ↑ Simon E.B.Thierry; Pascal Schreck; Dominique Michelucci; Christoph Fünfzig; Jean-David Génevaux (2011). "Extensions of the witness method to characterize under-, over- and well-constrained geometric constraint systems" (PDF). Computer-Aided Design. 43 (10): 1234–1249. doi:10.1016/j.cad.2011.06.018.
  8. ↑ Pascal Mathis; Simon E. B. Thierry (2010). "A formalization of geometric constraint systems and their decomposition". Formal Aspects of Computing. 22 (2): 129–151. doi: 10.1007/s00165-009-0117-8 . S2CID   16959899.
  9. ↑ Christoph M.Hoffman; Andrew Lomonosov; Meera Sitharam (2001). "Decomposition Plans for Geometric Constraint Systems, Part I: Performance Measures for CAD". Journal of Symbolic Computation. 31 (4): 367–408. doi: 10.1006/jsco.2000.0402 .
  10. ↑ Christoph M.Hoffman; Andrew Lomonosov; Meera Sitharam (2001). "Decomposition Plans for Geometric Constraint Problems, Part II: New Algorithms". Journal of Symbolic Computation. 31 (4): 409–427. doi: 10.1006/jsco.2000.0403 .
  11. ↑ Marta Hidalgoa; Robert Joan-Arinyo (2015). "h-graphs: A new representation for tree decompositions of graphs" (PDF). Computer-Aided Design. 67–68: 38–47. doi:10.1016/j.cad.2015.05.003. hdl: 2117/78683 .
  12. ↑ Xiao-Shan Gao; Qiang Lin; Gui-Fang Zhang (2006). "A C-tree decomposition algorithm for 2D and 3D geometric constraint solving" (PDF). Computer-Aided Design. 38: 1–13. doi:10.1016/j.cad.2005.03.002.
  13. ↑ Samy Ait-Aoudia; Sebti Foufou (2010). "A 2D geometric constraint solver using a graph reduction method". Advances in Engineering Software. 41 (10–11): 1187–1194. doi:10.1016/j.advengsoft.2010.07.008.
  14. ↑ Hichem Barki; Lincong Fang; Dominique Michelucci; Sebti Foufou (2016). "Re-parameterization reduces irreducible geometric constraint systems" (PDF). Computer-Aided Design. 70: 182–192. doi:10.1016/j.cad.2015.07.011.
  15. ↑ R.Joan-Arinyo; M.Tarrés-Puertas; S.Vila-Marta (2014). "Decomposition of geometric constraint graphs based on computing fundamental circuits. Correctness and complexity". Computer-Aided Design. 52: 1–16. doi:10.1016/j.cad.2014.02.006.
  16. ↑ Kirk Haller; Audrey Lee-St.John; Meera Sitharam; Ileana Streinu; Neil White (2012). "Body-and-cad geometric constraint systems". Computational Geometry. 45 (8): 385–405. arXiv: 1006.1126 . doi:10.1016/j.comgeo.2010.06.003.
  17. ↑ Dominique Michelucci; Sebti Foufou (2006). "Geometric constraint solving: The witness configuration method". Computer-Aided Design. 38 (4): 284–299. CiteSeerX   10.1.1.579.2143 . doi:10.1016/j.cad.2006.01.005.
  18. ↑ Kramer, Glenn A. (1992). Solving geometric constraint systems : a case study in kinematics (1:a upplagan. ed.). Cambridge, Mass.: MIT Press. ISBN   9780262111645.
  19. ↑ Xiaobo Peng; Kunwoo Lee; Liping Chen (2006). "A geometric constraint solver for 3-D assembly modeling". The International Journal of Advanced Manufacturing Technology. 28 (5–6): 561–570. doi:10.1007/s00170-004-2391-1. S2CID   120186972.
  20. ↑ Xiao-Shan Gao; Shang-Ching Chou (1998). Solving Geometric Constraint Systems II. A Symbolic Approach and Decision of Rc-constructibility. doi:10.1016/s0010-4485(97)00055-9. S2CID   775489.
  21. 1 2 3 William Bouma; Ioannis Fudos; Christoph M. Hoffmann; Jiazhen Cai; Robert Paige (1993). A Geometric Constraint Solver.
  22. ↑ Michela Farenzena; Andrea Fusiello (2009). "Stabilizing 3D modeling with geometric constraints propagation". Computer Vision and Image Understanding. 113 (11): 1147–1157. doi:10.1016/j.cviu.2009.05.004.
  23. ↑ R. Joan-Arinyo; M.V. Luzón; A. Soto (2002). Parallel Problem Solving from Nature — PPSN VII. Lecture Notes in Computer Science. Vol. 2439. pp. 759–768. doi:10.1007/3-540-45712-7_73. ISBN   978-3-540-44139-7.
  24. ↑ "Geometric constraint solver".
  25. ↑ Rémi Imbach; Pascal Schreck; Pascal Mathis (2014). "Leading a continuation method by geometry for solving geometric constraints". Computer-Aided Design. 46: 138–147. doi:10.1016/j.cad.2013.08.026.
  26. ↑ Dmitry Ushakov (2008). Variational Direct Modeling: How to Keep Design Intent in History-Free CAD (PDF).
  27. ↑ "2D Dimensional Constraint Manager (D-Cubed 2D DCM)".
  28. ↑ "D-Cubed Customers".
  29. ↑ "Bricsys Component Technology for Constraint Management in 2D/3D".
  30. ↑ "Cimatron to Introduce New Motion Simulator Powered by LEDAS LGS 3D".
  31. ↑ "Exclusive Q&A: What it means, now that Bricsys bought IP from Ledas".
  32. ↑ "C3D Solver".
  33. ↑ "C3D Toolkit".
  34. ↑ "GeoSolver Project Page".
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.