An Efficient And Robust Polynomial Parametric Surface Intersection Algorithm

Finding the intersection curves of two parametric surfaces is one of primary important problems in Computer-Aided Design, which suffers from robustness,efficiency and accuracy. After carefully analyzing the problems on determining topological structure of intersection curves and marching methods, we proposed following improvements and solutions from the points of view of robustness and efficiency: (1) Detecting intersection loops: first calculate turning points of intersection loop's pre-images in the parametric space, then begin to trace the intersection loops by using turning points as start points .(2) High order marching method: obtain the Taylor series expansion of the intersection curve at the starting point by computing the high order derivatives. Then the Taylor series expansion is converted to a Bezier curve. The control polygon of the Bezier curve is adopted to determine the marching step. (3) Marching method with multiple steps: based on high order marching method, continue marching steps along a polyline path of the intersection curve approximation until the accumulated error exceed the predefined threshold. The thesis is organized as follows:Chapter 1 introduces surface/surface intersection problems in CAD. Among them, topological analysis and marching methods for intersection curves are carefully analyzed. At last, the motivations of our improvements for surface/surface intersection are described.Chapter 2 introduces a robust geometric solver for nonlinear polynomial equation systems. Since the topological analysis of intersection curves can be described by nonlinear polynomial equation systems, robustness of the system solver is important to our method.Chapter 3 presents a novel method for determining the topology of the intersection curves. First the turning points are computed in the parametric space.Thus each intersection loop could be traced which is starting from the corresponding turning point. Then the singular points are detected, where the tracing step should be shortened to avoid straying and looping.Chapter 4 introduces how to evaluate the first, second and higher order derivatives along intersection curves which will be applied to the following efficient and robust intersection algorithm in Chapter 5.Chapter 5 presents an improved marching method for the surface intersection. First High order Taylor series expansion at the beginning point is adopted as the marching path, where the Taylor series expansion is converted to a Bezier curve. The control polygon of the Bezier curve can be used for determining the tracing step due to its convex hull property. At the end of the path, the intersection curve is approximated by a polyline. The marching will go on along the polyline for a relative longer step.Chapter 6 gives implementation results of four typical surface intersection cases. Compared with the other marching method, the proposed method is robust and efficient.Chapter 7 summarizes the thesis. Finally some further research topics are given.