An Expanding Algorithm of Geometric Constraint Solving in Semantic Feature Modeling

INTRODUCTION

Parametric design (Hoffmann and Kim, 2001; Sun and Liu, 2011) has become the core technology in CAD system in recent years and the geometric constraint solving (Hoffmann, 2005) is the most important part in semantic feature modeling (Bronsvoort et al., 2006). But so far, although geometric constraint has been brought into three-dimensional field, it can be better used in the field of two-dimension. It can solve some problems about parts assembling (Sun and Ding, 2010; Ding and Sun, 2009) but the existing solving methods (Xueliang et al., 2010; Wei et al., 2008) in three-dimensional geometry have many difficulties in the applications.

Now, cluster solving method (Bettig and Hoffmann, 2010) is the most mature approach, namely geometric constraint problems are decomposed into several well-constrainted sub-problems. Each single sub-problem is solved independently, then all sub-solutions are combined into a generic solution and the generic solution is the solution of the whole constraint system. Cluster solving method has two modes: rewriting rule method (Durand and Hoffmann, 2000; Hoffmann and Vermeer, 1995) and degree of freedom based rule method (Kramer, 1992; Gao et al., 2006).

Rewriting rule method is that modeling system tries to find some subsets of constraint problem and these subsets must be well-constrained and they have accurate and efficient methods corresponding for solving, so the constraint system can be solved quickly. But this method is not perfect for three-dimensional problems because there is no rule which can decompose a constraint system into several well-constrained sub-problems. Therefore, this method can not be used to solve all of well-constrained problems and may result in under-constrained (Sun et al., 2010).

Degree of freedom based rule is that it determines well-constrained sub-problems by using degree of freedom analysis. For the specific sub-problems, solving algorithm may be unknown and algebraic method (Van-der-Meiden and Bronsvoort, 2005) is used to solve in this approach, it will increase greatly the cost of computation when constraint system is very large, so degree of freedom based rule is also imperfect.

Both of methods require constraint system can be decomposed into several well-constrained subsets, based on rewriting rule and degree of freedom based rule, a new solving approach is presented in this study. Firstly constraint system is decomposed into three types subset: rigid subset, scalable subset and radial subset. Then incremental algorithms are applied and at last the generic solution will be get. This approach can get solution for the constraint system that can not be decomposed into sub-problems solved independently.

A constraint problem instance is shown in Fig. 1. There are five points in three-dimension space where, pBAC, pDAC, pEAD, pBAE, pABC, pADC, pADE, pEAB are constrained by angle constraint and a distance constraint lies between point B and point F.

Fig. 1:	Instance model and its constraint representation

It is easy to get hat the whole system is well-constrained but it is difficult to decompose the system into several well-constrained subsets. Therefore, the whole system must be solved in both of method aforementioned. Present approach can be used easily to decompose the system into several subset and solving process is effected very light when a few variables changes.

DEFINITION OF SUBSET

A cluster (Van-der-Meiden and Bronsvoort, 2006) basically represents a collection of distance and angle constraints on a set of points. We define three types of subset: rigid subset, scalable subset and radial subset. The type of a subset determines which distances and angles are constrained by it. Also, a set of configurations is associated with a subset, each of which determines an alternative set of values for the distances and angles constrained by the subset.

Subset distance constraints δ (m, n) are defined as follows:

Subset angle constraints p(m, n, t) are defined as follows:

where, m, n, tεR² or R³ are points in the cluster.

By this definition, distances and angles are unsigned; i.e., δ (m, n)≥0 and 0≤p(m, n, t)≤π.

Definition 1: Rigid subset is a constraint set of all the points [a₁, a₂, …, a_n] such that the relation position of all points is constrained in two- or three-dimensional models, i.e. all distances and angles in point set are constrained. As shown in Fig. 2a, the rigid subset is well-constrained and has no internal degree of freedom but it can be translated or rotated.

Fig. 2:	Three types of clusters

The notation for the subset on a set of points [a₁,a₂,…, a_n] is RIGD ([a₁,a₂, …, a_n]).

Definition 2: Scalable subset is a constraint set of all the points [a₁, a₂, …, a_n] such that for all i, j, kε [1, n] and the angles (a_i, a_k, a_j) are constrained, shown in Fig. 2b. The scalable subset has one internal degree of freedom, it can be scaled uniformly. The notation for the subset on a set of points [a₁, a₂, …, a_n] is SCLB ([a₁, a₂, …, a_n]).

Definition 3: Radial subset is a constraint set of all the points [a_m, a₁, a₂, …, a_n] such that for all i, jε [1, n] and the angles (a_i, a_m, a_j) are constrained, shown in Fig. 2c. Point am is called the centre point and points [a₁, a₂,…, a_n] are called the radial points. The radial subset has n internal degrees of freedom. The notation for the subset on a set of points [a_m, a₁, a₂,…, a_n] is RADI ([a_m, a₁, a₂,…, a_n]).

REWRITING APPROACH

Re-writing process: To solve a constraint system, rewriting the system to a single rigid cluster by trying to apply a set of rewrite rules in this approach. A rewrite rule specifies a pattern, describing its input clusters and its output cluster in a generic way and it specifies a procedure to determine the configurations of the output cluster from the configurations of the input clusters. A rewrite rule can be applied if a set of clusters is found in the system that matches the input clusters in the pattern. The corresponding output cluster is added to the system and the configurations of the output cluster are determined by the procedure.

A pattern specifies a number of input clusters of a given type and a number of pattern variables. These pattern variables are matched by the solving algorithm to the point variables of the clusters in the system, such that the number of variables and the type of the cluster match. A pattern may also specify that an input cluster can match any cluster with a superset of the given variables. If a variable name occurs several times in the pattern, it must be matched with a single point variable that is constrained by several clusters in the constraint system.

To determine the configurations of the output cluster of a rewrite rule, the procedural part of the rule is applied for every combination of input cluster configurations. Suppose, for example, that two clusters are used as the input of a rewrite rule and that each cluster has two configurations associated with it; then four different configurations for the output cluster are computed.

The generic solution is initially empty. When the user adds a cluster to the problem (Algorithm 1), the cluster is added to the generic solution. The algorithm then searches for possible rewrite applications on that new cluster, i.e., rewrite rule applications where the cluster is used as input (Algorithm 3). When a cluster is removed (Algorithm 2), it is removed from the generic solution. The rewriting approach is implemented as follows:

Algorithm 1:	Adding a subset

Algorithm 2:	Removing a subset

Algorithm 3:	Searching for rewrite rule applications

Rewriting rules: If a₁, a₂, a₃, …,a_nεR³.

Rule 1:

This rule can be applied when two radial subset share three points. When a match is found, a new scalable subset is added to the system.

This rule can be applied to the problem in Fig. 1, as follows:

Rule 2:

Two subsets can be combined into one new one when the shared points between two scalable subsets have the same coordinate. The rule can be applied repeatedly, in the example problem, as follows:

Rule 3:

The rule can be applied to the example system, resulting in a cluster RIGD ([A, B, C, D, E, F]) which constrains all the variables of the problem.

The solving constraint problem process is indicated by a directed acyclic graph of subset and rewrite rules. The solving process of Fig. 1 is shown in Fig. 3. In Fig. 3 arrows indicate dependency relations between subset created by rewrite rules. In Fig. 3, the subset with no incoming arrows are problem subsets and the subset with no outgoing arrows is the solution subsets.

From its process, we can know whether a problem is well-constrained, under-constrained and over-constrained:

Fig. 3:	Generic solution fo the problem in Fig. 1

REWRITING RULE APPLICATION

Specific steps of subset rewriting approach are explained in a instance, as shown in Fig. 1, based on the approach introduced in this study, geometric constraint system can be indicated as follows:

Re-writing constraint system using rule 1 as follows:

Re-writing constraint system using rule 2 as follows:

Rule 2 was applied again:

Re-writing constraint system using rule 3 as follows:

So, we can get generic solution of geometric constraint problems shown in Fig. 1 by using subset rewriting approach.

This method indicates that only one sub set of rewriting rules is changed when any distance or angle constraint in models is being modified and the change can only affect the sub set which it located, not affect as traditional approach that all constraint sub-system was modified.