Curve And Surface Intersection Algorithm For Geometric Modeling Software System

Geometry modeling is one of the kernels of a lot of software systems on Computer-Aided Design, Computer-Aided Manufacturing and Computer Graphics. In geometry modeling, the curve and surface intersection algorithms are the fundamental operation for Boolean operations and to produce necessary elements of B-Rep solid bodies. The performance of the intersection algorithms mainly determines the efficiency and the stability of the geometry modeling software. The main works of this thesis are as follows.1 The thesis provides a new intersection algorithm between a cylinder and a quadratic surface. The algorithm first turns the original intersection problem into another intersection problem between a set of lines and a quadratic surface, and obtains the parametric form of the intersection curves. Then, all the key positions are determined. Lastly, it calculates the intersection intervals and the corresponding intersection curves by using mid-point judging method.2 The thesis proposes a new algorithm to find the closest point of a given point and to calculate the corresponding parameter of the closest point. The new algorithm does not need any initial value. The point projection problem is turned into a root finding problem. Sturm theorem is then utilized to find the intervals, which contain at most one element in the root set. And a bisection algorithm is provided to obtain the roots from the intervals.3 The thesis analyzes on four common cases of the sequence produced by a standard Newton iterative method based on the work by Lakshmikantham and Vatsala, which was published on Applied Mathematics and Computation in 2005. Some numerical results are used to illustrate the analysis.