Root-finding Method For Nonlinear Equations In Computer Graphics

The root-finding problem of nonlinear equation is one of the fundamental problems in computer graphics,which has wide applications in the fields of computer graphics and computer aided geometric design.For example,the collision detection of the game,the point projection of curves and surfaces geometric modeling system,the interference detection,and so on,can be reduced to the solution of the nonlinear equation.In this paper,some root-finding problems of nonlinear equations are studied,including:(1)Fast approach for computing the minimum distance between a point and a NURBS curve.Point projection problem can be transformed into the root-finding problem of nonlinear equation.It combines a control-polygon-based method for searching the subdivision positions the classification based clipping method with progressive root-finding technique.It firstly translates the square distance function into Bézier form;secondly,estimates the subdivision positions by using the control polygon,and does the clippings based on classification;finally,it computes the minimum distance by using progressive root-finding technique.Numerical examples show that the new method can achieve better clipping efficiency and better computational efficiency than those of circle clipping method and other prevailing methods.(2)Efficient rational quadratic clipping method for computing roots of a polynomial.A rational quadratic clipping method is represented for computing a simple root of a polynomial f(t)of degree n within an interval,which preserves the computation stability of the Bernstein-Bézier representation.Different from previous clipping methods based on interpolation,it optimizes the selection of the inner point,which can achieve the convergence rate 12 by using rational quadratic polynomials.Difference from previous clipping methods by computing bounding polynomials,it provides a simple method of linear complexity to directly bound the root;at the same time,it needs to compute the roots of quadratic polynomials and avoids solving cubic equations,and leads to a higher computational efficiency.In principle,it can workswell for a non-polynomial case.Numerical examples show higher convergence rate and better computation efficiency of the new method.(3)An efficient method for computing planar Bézier curve/curve intersections.In principle,the intersection problem of two Bézier curves,of degree n and m,respectively,can be transformed into the root-finding problem of nonlinear equations.This paper presents a new method for computing the intersections between two planar Bézier curves.There are three main contributions.Firstly,by combining the control net of the distance function of two Bézier curves and local quadratic surface approximation technique,it obtains a good initial value for each intersection point in a much faster way than prevailing subdivision methods.Secondly,it provides a derivative estimation based method for a traversal case.Thirdly,it presents a new iterative formula of convergence rate 2 for a contact case,which achieves much better performance than those of prevailing Newton’s method and clipping methods.Numerical experimental results show that the new method can achieve much better computational efficiency or much better convergence performance than those of prevailing hybrid clipping methods and the Newton’s method.