Font Size: a A A

Research On Geometric Constraint Modeling And Solving Technology

Posted on:2010-08-23Degree:MasterType:Thesis
Country:ChinaCandidate:N LiuFull Text:PDF
GTID:2178360272497474Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
Parametric design is a key research subject of CAD in practice; it not only enables CAD systems having the ability of interactive drawing but also the ability of automatically drawing. And it is one of key subject and it need more research. Parametric design distinguishes itself from other drawing systems due to the fact that it can not only presents topological information but can describes various constraint relations of geometric primitives as well. There is two of main elegance of parametric design: one is that engineers don't need to take every detail into account but focus on the draft of product model, and the precise result will be generated by the CAD system which uses parametric design; the other is that we could change some constraint parameters to update the design, excluding involving the whole design process.Among various design constraints, geometrical constraint is the most fundamental method and it serves the basis of other design constraints; which is the first issue to address in constraint management and solving techniques. Geometric constraint is the core of Parametric Technology, given the size of designed draft and the bound of topological relations, system can generate corresponding designed draft automatic. The system of geometric constraint-based parametric creates products and modify designs in a new way. So, geometric constraint management and solving technology has been the key element of technical in current CAD field, it is the peek of a new generation of CAD technology, and the importance has been realized widely. Studying and mastering geometric constraint management and solving technology is the key of developing the new generation of CAD system of independent intellectual property rights.Many problems of the field of engineering design would be reduced to geometric constraint solving problem. The quality and maturity of geometric constraint solving technology decide the standards of corresponding application fields. After studying the field of geometric constraint solving problem deeply, I proposed two new algorithms:First, a new geometric constraint model based on weighted constraint graph and solution has been proposed. In the geometric constraint system, constraint relation between geometric entities is very complex, and how to build an effective geometric constraint system model is the basic of studying geometric constraint system. This article which is at the basic of building models of geometric constraint system in the geometric constraint graph approach proposed a new geometric constraint model based on the weighted constraint graph and proposed new solution.The idea of building models: any weighted edge of weighted constraint graph together with its starting point and terminating point forms the expression of graphical model of geometric constraint. And its nodes are expressed as N(X,Y), N is the name of an entity, X is the initial degree of freedom of an entity, Y is the degree of freedom in the process; the number of each edge is on behalf of the value of loss of freedom. When forming a weighted constraint graph model, we need to deal with the situation of non-weighted edge first, which means we need to deal with location constraint first, then we need to deal with the relationship between bound.Solution: The solution is on the basic of the attenuation of the freedom of geometric entities. Dividing some entities into a group is the key of the solution. According to degrees of freedom, we can divide entities into three groups by lower priority. The first group: the entities whose freedom changed, the second group: the entity group whose freedom didn't change, but it has the relationship with the entities whose freedom changed; the third group: the freedom didn't change, but it doesn't have the relationship with the entities whose freedom changed. The solution is against the completely divided nodes of the constraint graph. The process of finding nodes whose freedom is zero is the process of constraint solve problems, we need to adjust the freedom of the nodes in finding process, which means we need to change the freedom of the nodes that connects to the nodes whose freedom is zero into the difference of its original freedom and the weighted value of its corresponding edge, and delete the nodes whose freedom is zero and its corresponding edge.Proved by the test, the model lays an efficient foundation for solving model, has a strong value, and the solution can significantly reduce the computational complexity and improve the speed and efficiency.Second, I proposed a new hybrid genetic ant initial quasi-Newton method. The Algorithm design is like this: After achieving continuous k-generation evolution to the genetic groups, I can get the path information; I will use the path information as initial value, and get several groups of better initial ant individual information set S after using ant solution. Then I will sort the information according to their quality, and select the first element as the initial value of quasi-Newton method to iterative. After N times, if quasi-Newton method does not converge, I will drop the value, then I will fetch next element to do the same thing until I find a solution of meeting the requirements of accuracy and having convergence.The essence of geometric constraint solving problem is equivalent to the solution of resolving problems of nonlinear equations, we can use numerical methods to solve problems. Newton method (Newton-Raphson) is a more general numerical method, but it has some defects, Quasi-Newton method is a modified Newton's algorithm, comparing with Newton method, it has many advantages, such as: First, it needs only one derivative, but Newton method needs second derivative. Quasi-Newton method has the lower requirements of the continuity of function, and makes the range of adapting the equations to be solved wider. Second, it can resolve the problems, such as: Jacobian matrix's larger scale and sick problems In a major CAD systems, constraint equations coefficient matrix always be large-scale sparse and sick matrix, and Jacobian matrix is hard to be resolved, so Quasi-Newton method has better adaptability. Third, each iteration needs O(n2) times involutions, but Newton method needs O(n3) times, it shortens the computing time, and this is in line with, strong interaction characteristics of the CAD system. So, this article adopts Quasi-Newton method, but Quasi-Newton method still has defects of sensitive to the initial value.This article proposed a new mixed genetic and ant initial value's Quasi-Newton method.Using the advantages of fast, random and global search capability genetic algorithm has, I designed encoding and fitness function, and made a selection of the chromosome species generation and the chromosome selection, generated pheromone distribution by setting crossover operator and mutation operator. I also took the advantage of ant Algorithm positive feedback and has the distributed parallel global search capabilities, built a strength update modal by determining the attractive intensity of the initial value, so, I can get more precise solution, I select the more precise solution as the initial value of Quasi-Newton method, it effectively overcame the sensitive problems to initial value of quasi-Newton method; at the same time, I introduced quasi-Newton iterative method to local search in elite individuals, this can overcomes the defects, such as: slow convergence and bad accuracy of genetic algorithms, and the defect of resolving problems using ant algorithm, making algorithm has higher convergence speed and accuracy. Experimental shows that the hybrid algorithm has more convergence speed and accuracy comparing with the simple quasi-Newton method, and has better effect in solving the geometric constraint problems.In conclusion, the achievements of this dissertation make the applied research on the geometric constraint solving theory progress. It has a certain theory significance and application importance. It provides effective methods and means for the research on the geometric constraint solving.
Keywords/Search Tags:CAD, Geometric Constraint Modeling, Geometric Constraint Solving, Weighted Constraint Graph, Genetic Algorithm, Ant Algorithm, Quasi-Newton Method
PDF Full Text Request
Related items