ALGEBRAIC PRUNING - A FAST TECHNIQUE FOR CURVE AND SURFACE INTERSECTION

Computing the intersection of parametric and algebraic curves and surf aces is a fundamental problem in computer graphics and geometric model ing. This problem has been extensively studied in the literature and d ifferent techniques based on subdivision, interval analysis and algebr aic formulation are known. For low degree curves and surfaces algebrai c methods are considered to be the fastest, whereas techniques based o n subdivision and Bezier clipping perform better for higher degree int ersections, In this paper, we introduce a new technique of algebraic p runing based on the algebraic approaches and eigenvalue formulation of the problem. The resulting algorithm corresponds to computing only se lected eigenvalues in the domain of intersection, This is based on mat rix formulation of the intersection problem, power iterations and geom etric properties of Bezier curves and surfaces. The algorithm prunes t he domain and converges to the solutions rapidly. It has been applied to intersection of parametric and algebraic curves, ray tracing and cu rve-surface intersections, The resulting algorithm compares favorably with earlier methods in terms of performance and accuracy. (C) 1997 El sevier Science B.V.