Research On The Parametric Modeling And Geometric Constraint Solving Technology

Recent years, Parametric Design is becoming a popular subject of CADtechnology because of its strong scketch-design and dimension-drivenfunctions. The main difference between the parametric design system and thegeneral graph system is that it can express not only the geometric topologicalinformations but also the geometric constraint informations. Parametric systemhas two major advantages. Firstly, the designers are free to consider the details,what they need to do is to draw a scketch as soon as possible,and theparametric system will produce the accurate figure, secondly, the parametricsystem can update the design by changing some constraint parameters insteadof repeating the whole design process.Geometric Constraint Solving (GCS) is the core of the parametrictechnology. It means that once the demention constraints and topologicalconstraints are given, the system will produce the design graph automatically.Many problems in engineering can be dealed as GCS, Further research onthe theory of GCS is significative to enhance parametric level and industrialcompetitive ability. This research has been supported by National NatureScience Foundation of China. (Authorizing number: 60573182).There are several approaches to GCS: the numerical approach, thesymbolic approach, the regulation approach and the graph analysis approach.The basal idea of the graph analysis approach is to build a GeometricConstraint Graph (GCG) for the geometric constraint problem, in the GCG, thevertex represents the geometric entity, the edge represents the constraint.Using the graph theory also considering the constraint information todecompose and combine the GCG. The purpose of decomposition is to convertthe strongly coupled graph to subgraphs, and solve them separately, at the end,combine them as a whole.The GCG can be not directed and directed, The Directed GeometricConstraint Graph (DGCG) takes plenty consideration of the constraint's spreaddirection. We can easly judge whether the constraint status is well-constraint,and control the constraint's spread range as small as possible when its valuechanged, accordingly, the compute complexity will reduce, the efficiency of CAD system will be improved, meanwhile lots of modifications will beavoided.The performance of the DGCG which you build will affect thecomplexity and efficiency of the solving process. Therefore, a good matchingalgorithm for DGCG is vital.Aimming at many problems we should meet with during GCP decomposesand combines, this paper proposes two kinds of new algorithms as follows:(1)This paper proposes a new matching algorithm for DGCG. Based on theDGCG solving theory, according to geometric constraint bipartite graphmatching algorithm, using Remain Degree Of Freedom (RDOF) analyse, thispaper propose the concept of the geometric element priority. The priority ofbasic geometric element is Point>Line>Circle. The new algorithm regulates:when adding a new constraint Ct to the DGCG, firstly, find the vertex'V'whose RDOF is >0 in Ct's related Vertex set S{Vi,Vj}, if exist, Ct matcheswith it, else, recursively search for the reversible path of Vi or Vj, if failed, itindicate that Ct is redundant, if succeed, reverse the arc of Vi or Vj, one DOFwill added to Vi or Vj, then Ct matches with it. During all the process, thedirected arc is first point to the low priority element. The algorithm makes useof the symmetry of two-element constraint, dynamicly inspect constraintredundant, and modify it timely. In the end the DGCG can be decomposed intomany subgraphs by regulation, Experiments shows that the algorithm isefficient in the decomposition of highly coupled under-constraint systems, thesolving complexity is not more than two times.(2)This paper proposes a Simulate-Newton algorithm which is based onReal-Code Genetic Algorithm (RGA) to generate the initial value. Thisalgorithm has improved the Simulate-Newton which is sensitive to the initialvalue. Firstly RGA generate the initial value set S, initial values in S are sortedby fitness from high to low, then Simulate-Newton algorithm use the firstvalue in the set S as its initial value, if it is not convergent after N iterations,turn to the next element in the S, repeat until the result is precision satisfied.GCG after being decomposed can be converted to non-linear equationgroup, and solved with numerical approach. Newton-Raphson method iscommon used, but it has many shortcomings, one shortcoming is sensitive toinitial value which is hard to estimate in 3D-Design space, this will lead the Newton-Raphson method not convergent and failed to find the result. Anothershortcoming is that Jacobin matrix is diseased.The Simulate-Newton method is a betterment of Newton-Raphsonmethod. Compared to Newton-Raphson method, it has many advantages asfollows:(1)Only one-rank differential coefficient is needed, butNewton-Raphson method need two-rank differential coefficient,(2)Theshortcoming that Jacobi matrix is too large to compute is solved, soStimu-Newton method is more adaptable. (3)The complexity of each iterationis O(n 2) , but the Newton-Raphson method is O(n 3), time is greatly saved,and the CAD system can react real time.RGA codes the results space directly, compared with Binary GeneticAlgorithm, it is good at global search, high accuracy, low complexity, highefficiency, but at the end of the algorithm, the convergent efficiency is low andprematurity convergence situation will happened. This paper propose the RGAinitial value based Simulate-Newton method, this method fully make use ofthe RGA's global space search ability to find the viable space for initial value,The Simulate-Newton method iterated at the space and find the result which issatisfy the precision request. This algorithm makes the designers get rid ofblindly guessing for the initial value, the convergent probability and theresult's precision is enhanced. We apply this algorithm into the GCSsuccessfully.The experiment shows that the new algorithm is efficient.This paper also analysises the advantages and limits of many approach,compute the time complexity of some representational method, at last thispaper designs a geometric constraint solver, introduce the refered main classesand data-structure in detail.