Computing the Intersection of Two Rational Surfaces Using Matrix Representations. (September 2022)

• Record Type: Journal Article
• Authors: Jia, Xiaohong; Li, Kai; Cheng, Jinsan
• Is Part Of: Computer aided design. Volume 150(2022)
• Publication Date: 2022-09
• Subjects: Rational surface -- Intersection -- Matrix representation -- Marching squares; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2022.103303
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: The surface–surface intersection computation is fundamental to CAD/CAM, since it is crucial to boundary representation, mesh generation, rendering, hidden surface removal and CNC machining. In this paper, we present an efficient algorithm for computing the intersection of two rational parametric surfaces, which is an algebraic technique based on a hybrid of a matrix-representation and a hierarchical lattice method. Given two rational surfaces, the Dixon matrix representation of one surface is first constructed; then the marching squares technique is applied on lattices of the parametric domain of the other surface to extract the intersection points. Extensive experiments have been conducted on various surfaces, including Utah teapot patches and some classic surfaces that have complex self-intersection features. These examples have covered rich intersection curve topology with multiple branches and singular points. All examples show that our algorithm is efficient and numerically stable. Graphical abstract: Highlights: An efficient algorithm of computing the intersections of two rational surfaces is provided based on the using of a new Dixon matrix presentation. A marching squares strategy is adopted in the parametric domain to extract intersection parameters from the Dixon matrix representation. Comparisons with several classic algorithms including the algebraic-tracing method, the subdivision method and the method using Buse's matrix representation on rich examples have been conducted, showing the best efficiency our algorithm in the same setting of accuracy.