A non-iterative method for robustly computing the intersections between a line and a curve or surface

Xiao Xiao 1 Laurent Busé 2 Fehmi Cirak 1
2 AROMATH - AlgebRe, geOmetrie, Modelisation et AlgoriTHmes
CRISAM - Inria Sophia Antipolis - Méditerranée , National and Kapodistrian University of Athens
Abstract : The need to compute the intersections between a line and a high-order curve or surface arises in a large number of finite element applications. Such intersection problems are easy to formulate but hard to solve robustly. We introduce a non-iterative method for computing intersections by solving a matrix singular value decomposition (SVD) and an eigenvalue problem. That is, all intersection points and their parametric coordinates are determined in one-shot using only standard linear algebra techniques available in most software libraries. As a result, the introduced technique is far more robust than the widely used Newton-Raphson iteration or its variants. The maximum size of the considered matrices depends on the polynomial degree $q$ of the shape functions and is $2q \times 3q$ for curves and $6 q^2 \times 8 q^2$ for surfaces. The method has its origin in algebraic geometry and has here been considerably simplified with a view to widely used high-order finite elements. In addition, the method is derived from a purely linear algebra perspective without resorting to algebraic geometry terminology. A complete implementation is available from http://bitbucket.org/nitro-project/.
Complete list of metadatas

https://hal.inria.fr/hal-02009104
Contributor : Laurent Busé <>
Submitted on : Wednesday, February 6, 2019 - 10:18:57 AM
Last modification on : Thursday, October 17, 2019 - 1:56:26 PM

Links full text

Identifiers

Collections

Citation

Xiao Xiao, Laurent Busé, Fehmi Cirak. A non-iterative method for robustly computing the intersections between a line and a curve or surface. International Journal for Numerical Methods in Engineering, Wiley, In press, International Journal for Numerical Methods in Engineering, ⟨10.1002/nme.6136⟩. ⟨hal-02009104⟩

Share

Metrics

Record views

62