FRONTIER: fully enabling geometric constraints for feature-based modeling and assembly

ABSTRACT

In the full paper [1], we discuss the functionality and implementation challenges of the Frontier geometric constraint engine, designed to address the main reasons for the underutilization of geometric constraints in today's 3D design and assembly systems. Here, we motivate the full paper by outlining the advantages of Frontier.

• Frontier fully enables both (a) the use of complex, cyclic, spatial constraint structures as well as (b) feature-based design. To deal with Issue (a), Frontier relies on the efficient generation of a close-to-optimal decomposition and recombination (DR) plan for completely general variational constraint systems (see Figure 1). A serious bouleneck in constraint solving is the exponential time dependence on the size of the largest system that is simultaneously solved by the algebraic-numeric solver. In most naturally occurring cases, Frontier's DR-plan is guaranteed in minimize this size (to within a small constant factor). To deal with Issue (b), Frontier's DR-plan admits the independent and local manipulation of features and sub-assemblies in one or more underlying feature hierarchies that are input (Figures 1 and 2). A DR-plan satisfying the above requirements is generated by the new Frontsier vertex Algorithm (FA): the DR problem and its significance as well as FA and its performance with respect to several relevant and newly formalized abstract measures are described in [2, 3].

• Frontier employs a crucial representation of the DR-plan's subsystems or clusters, their hierarchy and their interaction This representation merges network flow information, as well as other geometric and combinatorial information in a natural manner. Some of this information is obtained from an efficient flow-based algorithm for detecting small rigid sub-systems presented in [4]. The clarity of this representation is crucial in the concrete realization of FA's formal performance. More significantly, this representation allows Frontier to take advantage of its DR-plan in surprising and unsuspected ways listed below.

REFERENCES

• 1: http://www.cise.ufl.edu/'sitharam/full-frontier.ps
• 2: C.M. Hoffmann, A. Lomonosov, and M. Sitharam. Decomposition of geometric constraints systems 1: performance measures. To appear in Journal of Symbolic Computation.
• 3: Christoph M. Hoffman , Andrew Lomonosov , Meera Sitharam, Decomposition plans for geometric constraint problems, part II: new algorithms, Journal of Symbolic Computation, v.31 n.4, p.409-427, April 1, 2001 [doi>10.1006/jsco.2000.0403]
• 4: C.M. Hoffmann, A. Lomonosov, and M. Sithararn. Geometric constraint decomposition. In Bruderlin and Roller Ed.s, editors, Geometric Constraint Solving. Springer-Verlag, 1998.
• 5: I. Fudos and C. M. Hoffmann. Correctness proof of a geometric constraint solver. Intl. J. of Computational Geometry and Applications, 6:405--420, 1996.
• 6: J. Owen. Constraints on simple geometry in two and three dimensions. In Third SIAM Conference on Geometric Design. SIAM, November 1993.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.7 Feature Measurement
          Subjects: Feature representation

General Terms:
Design, Performance, Theory