A constructive approach to calculate parameter ranges for systems of geometric constraints

ABSTRACT

Geometric constraints are at the heart of parametric and feature-based CAD systems. Changing values of geometric constraint parameters is one of the most common operations in such systems. However, because allowable parameter values are not known to the user beforehand, this is often a trial-and-error process. We present a solution for automatically determining the allowable range for parameters of geometric constraints. Considered are systems of distance and angle constraints on points in 3D that can be decomposed into triangular and tetrahedral subproblems, by which most practical situations in parametric and feature-based CAD systems can be represented. Our method uses the decomposition to find critical parameter values for which subproblems degenerate. By solving one problem instance for each interval between two subsequent critical values, the exact parameter ranges are determined for which a solution exists.

REFERENCES

• 1: Bettig, B., and Shah, J. 2003. Solution selectors: a user-oriented answer to the multiple solution problem in constraint solving. Journal of Mechanical Design 125, 3, 443--451.
• 2: Bidarra, R., and Bronsvoort, W. F. 2000. Semantic feature modelling. Computer-Aided Design 32, 3, 201--225.
• 3: Bouma, W., Fudos, I., Hoffmann, C., Cai, J., and Paige, R. 1995. A geometric constraint solver. Computer-Aided Design 27, 6, 487--501.
• 4: C. Essert-Villard , P. Schreck , J.-F. Dufourd, Sketch-based pruning of a solution space within a formal geometric constraint solver, Artificial Intelligence, v.124 n.1, p.139-159, Nov 2000 [doi>10.1016/S0004-3702(00)00061-8]
• 5: Ioannis Fudos , Christoph M. Hoffmann, A graph-constructive approach to solving systems of geometric constraints, ACM Transactions on Graphics (TOG), v.16 n.2, p.179-216, April 1997 [doi>10.1145/248210.248223]
• 6: Hoffmann, C. M., and Kim, K.-J. 2001. Towards valid parametric CAD models. Computer-Aided Design 33, 1, 81--90.
• 7: Hoffmann, C. M., and Vermeer, P. J. 1995. Geometric constraint solving in R2 and R3. In Computing in Euclidean Geometry, Second Edition, World Scientific Publishing, Singapore, D. Du and F. Hwang, Eds., 266--298.
• 8: Decomposition plans for geometric constraint systems, part I: performance measures for CAD, Journal of Symbolic Computation, v.31 n.4, p.367-408, April 1, 2001 [doi>10.1006/jsco.2000.0402]
• 9: Joan-Arinyo, R., and Mata, N. 2001. Applying constructive geometric constaint solvers to geometric problems with interval parameters. Nonlinear Analysis - Theory, Methods & Application 47, 1, 213--224.
• 10: Noort, A., and Bronsvoort, W. F. 2001. Enforcing model validity by automatic adjustment. Journal of Computing and Information Science in Engineering 1, 4, 311--319.
• 11: Jianjun Oung , Meera Sitharam , Brandon Moro , Adam Arbree, FRONTIER: fully enabling geometric constraints for feature-based modeling and assembly, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.307-308, May 2001, Ann Arbor, Michigan, United States [doi>10.1145/376957.376995]
• 12: Podgorelec, D. 2002. A new constructive approach to constraint-based geometric design. Computer-Aided Design 34, 11, 769--785.
• 13: Raghothama, S., and Shapiro, V. 2000. Consistent updates in dual representation systems. Computer-Aided Design 32, 8--9, 463--477.
• 14: Vadim Shapiro , Donald L. Vossler, What is a parametric family of solids?, Proceedings of the third ACM symposium on Solid modeling and applications, p.43-54, May 17-19, 1995, Salt Lake City, Utah, United States [doi>10.1145/218013.218029]
• 15: van der Meiden, H. A., and Bronsvoort, W. F. 2004. An efficient method to determine the intended solution for a system of geometric constraints. Submitted for publication; available upon request.
• 16: Weisstein, E. W. 2004. Degenerate. From MathWorld-A Wolfram Web Resource. http://mathworld.wolfram.com/Degenerate.html.

INDEX TERMS

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

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

Keywords:
geometric constraint solving, parameter range computation