Topologically Reliable Curve Intersection And Quadric Intersection With Tolerance Control

Curve/curve intersection and surface/surface intersection are fundamental research problems in computer-aided design and computer graphics.The study of intersection problems of curves and surfaces has a long history and has wide-ranging applications in many fields.In computer graphics,the results of curve and surface intersection are essential for constructing complex geometric models and rendering realistic threedimensional objects.In robotics,intersection problems are critical for path planning and collision detection.In computer-aided design,curve and surface intersection is the foundation of Boolean operations on geometric models,and the intersection algorithm directly affects the robustness of geometric modeling systems.A good intersection algorithm needs to balance robustness,accuracy,and efficiency.This article mainly focuses on the robustness and accuracy of intersection problems.Robustness in this article refers to topological reliability.For curve intersection,topological reliability means not missing intersection points or adding redundant ones.For surface intersection,topological reliability means ensuring that the topological structure of the calculated intersection curve is entirely correct,without missing or adding redundant curve segments,closed curve segments,or singular points.For accuracy,this article explains it as controllable error,which means ensuring that the error of the calculated intersection points or intersection curves is less than the given tolerance.Chapter 3 mainly studies the intersection problem of two algebraic curves,focusing on the intersection of two algebraic curves in a bounded region.This chapter proposes a robust and efficient algorithm that uses subdivision methods to quickly reject regions that do not contain intersection points,and then uses the Krawczyk method to approximate the intersection points and ensure controllable error.For the ill-posed case,this chapter uses Sturm’s theorem to determine whether there are intersection points in the undetermined region and to determine the number of intersection points in the undetermined region.The algorithm proposed in this chapter is compared with classical and latest methods,and experiments show that the proposed algorithm performs better in terms of robustness and efficiency.Chapter 4 studies the topological classification problem of intersection curves of quadratic surfaces and proposes a new method to classify the topologies of intersection curves of quadratic surfaces by using a set of discriminants related to quadratic surfaces.This new topological classification method is derived from the method based on Signature sequences for topological classification,and establishes an equivalence condition between the Signature sequence and a set of discriminants by analyzing the roots of the characteristic polynomial and the inertia indices of the quadratic surface bundle at specific points.Ultimately,this chapter constructs 35 topological classifications of intersection curves of quadratic surfaces based on a set of discriminants.This new topological classification method ensures that each classification case has a visible expression,which is more theoretically valuable compared to the method of classifying using Signature sequences.Combining the conclusions about the topological classification of the intersection curves of two quadratic surfaces in Chapter 4,Chapter 5 proposes a robust algorithm for computing intersection segments based on the parametrization representation of the intersection curves of two quadratic surfaces.In practical problems,quadratic surfaces often appear in the form of truncated quadratic surfaces,which means a quadratic surface is subject to several plane constraints.In this chapter,our algorithm guarantees the correct topological relationship between the intersection curves of two truncated quadratic surfaces,and ensures that the endpoint approximation error of the intersection segments is less than the given tolerance.Error control is based on the effective solution of a set of polynomial inequality systems using the real root isolation technique.The robustness and effectiveness of our algorithm are verified through some examples.In Chapter 6,we studied the intersection problem between bounded ruled surfaces and truncated quadratic surfaces.For the problem of intersection between parameter surfaces and implicit surfaces,the parameter equation of the bounded ruled surface can be directly substituted into the quadratic surface to obtain the planar trajectory of the parameter curve and the parameter equation of the intersection at the same time.In order to ensure the correctness of the topology,we also need to analyze the singular points of the intersection curve.This can still be transformed into a problem of solving a series of inequality constraints,which can be solved using the algorithm in Chapter 5 and ensure that the approximation error of the intersection segment is less than the given tolerance.Finally,in Chapter 7,we summarize the main work of this thesis and provide an outlook for future research.