دانلود رایگان مقاله الگوریتم برای تشخیص وابستگی و زیر سیستم سخت برای CAD

Abstract

Automated approaches for detecting dependencies in structures created with Computer Aided Design software are critical for developing robust solvers and providing informative user feedback. We model a set of geometric constraints with a bi-colored multigraph and give a graph-based pebble game algorithm that allows us to determine combinatorially if there are generic dependencies. We further use the pebble game to yield a decomposition of the graph into factor graphs which may be used to give a user detailed feedback about dependent substructures in a specific realization of a system of CAD constraints with non-generic properties.

6. Conclusions

The approach presented in this paper is part of a larger research path to provide computational tools that will give users information about dependencies present in CAD structures in terms of the original geometric constraint system. A prototype of Algorithm 1 has been implemented, with a long-term goal to see the pebble game and factor algorithms incorporated into commercial CAD software packages. By analyzing the pure condition, we can detect special positions of a generically minimally rigid body-and-cad structure. However, since CG vanishes when G(p) is infinitesimally flexible, special positions that we find may not be truly flexible. These positions may still be of interest to a CAD user, as an infinitesimally flexible framework carries an internal stress, indicative of structural weaknesses. Moreover, we may be able to combine conditions implying a special position to create degenerate embeddings with true motions. We conclude with a brief discussion of open questions that arise as we move toward further development of our approach. Algorithm 4 returns factor graphs of the pure condition of an [a, b]-graph, but it remains open as to whether these factors are irreducible or not. When b = 0, the results of White and Whiteley (1987) show that irreducible factors of CG correspond to circuits in G; this correspondence implies that Algorithm 3 produces irreducible factors for body-and-bar graphs. A better understanding of circuits would allow us to similarly conclude of the factors identified by Algorithm 4 are always irreducible. We were able to carry out an analysis in the case study of Section 3 where the pure condition was just a product of brackets, and its vanishing was implied by either making two bars parallel or two lines parallel. More generally, a geometric interpretation of the vanishing of a more complicated non-monomial bracket polynomial may be possible via the process of Cayley factorization, which takes as input a polynomial written in terms of brackets of vectors and outputs an expression in terms of meets and joins in the Grasmann–Cayley algebra of those points if such an expression exists. There is a Cayley factorization algorithm due to White (White, 1991; Sturmfels, 2008), and it would be interesting to see if it could be modified (and sped up) if the input bracket polynomial is known to be a pure condition. Even when a Cayley factorization does exist, it may be nontrivial to extract geometric information about the original framework from it. One issue that adds complexity in general is that a single cad constraint may impose multiple linear constraints, so conditions may need to be expressed in terms of sets of vectors. Furthermore, in 3D, the vectors in the brackets do not live in a space dual to our realization space (as they do in 2D), complicating translation of the vanishing of the pure condition into the setting of our original constraints. Finally, the results in this work rely on the combinatorial characterization of Lee-St.John and Sidman (2013), which apply to 3D body-and-cad structures without point–point coincidence constraints. While a combinatorial characterization that incorporates these constraints remains unknown, 3D body-and-cad frameworks with point–point coincidences share similar properties with presumed barriers to a combinatorial characterization of 3D bar-and-joint frameworks.