Topology driven approximation to rational surface-surface intersection via interval algebraic topology analysis
Article No.: 38, Pages 1 - 16
Abstract
Computing the intersection between two parametric surfaces (SSI) is one of the most fundamental problems in geometric and solid modeling. Maintaining the SSI topology is critical to its computation robustness. We propose a topology-driven hybrid symbolic-numeric framework to approximate rational parametric surface-surface intersection (SSI) based on a concept of interval algebraic topology analysis (IATA), which configures within a 4D interval box the SSI topology. We map the SSI topology to an algebraic system's solutions within the framework, classify and enumerate all topological cases as a mixture of four fundamental cases (or their specific sub-cases). Various complicated topological situations are covered, such as cusp points or curves, tangent points (isolated or not) or curves, tiny loops, self-intersections, or their mixtures. The theoretical formulation is also implemented numerically using advanced real solution isolation techniques, and computed within a topology-driven framework which maximally utilizes the advantages of the topology maintenance of algebraic analysis, the robustness of iterative subdivision, and the efficiency of forward marching. The approach demonstrates improved robustness under benchmark topological cases when compared with available open-source and commercial solutions, including IRIT, SISL, and Parasolid.
Supplementary Material
References
[1]
G Alcázar and R Sendra. 2005. Computation of the topology of real algebraic space curves. Journal of Symbolic Computation 39, 6 (2005), 719--744.
[2]
CL Bajaj, CM Hoffmann, RE Lynch, and J Hopcroft. 1988. Tracing surface intersections. Computer Aided Geometric Design 5, 4 (1988), 285--307.
[3]
CL Bajaj and G Xu. 1994. NURBS approximation of surface/surface intersection curves. Advances in Computational Mathematics 2, 1 (1994), 1--21.
[4]
RE Barnhill, G Farin, M Jordan, and BR Piper. 1987. Surface/surface intersection. Computer Aided Geometric Design 4, 1 (1987), 3--16.
[5]
RE Barnhill and SN Kersey. 1990. A marching method for parametric surface/surface intersection. Computer Aided Geometric Design 7, 1--4 (1990), 257--280.
[6]
M Barton, G Elber, and I Hanniel. 2011. Topologically guaranteed univariate solutions of underconstrained polynomial systems via no-loop and single-component tests. Computer-Aided Design 43, 8 (2011), 1035--1044.
[7]
L Busé, M Elkadi, and A Galligo. 2008. Intersection and self-intersection of surfaces by means of Bezoutian matrices. Computer Aided Geometric Design 25, 2 (2008), 53--68.
[8]
S Chau and A Galligo. 2014. Topology of the Intersection of Two Parameterized Surfaces, Using Computations in 4D Space. SAGA-Advances in ShApes, Geometry, and Algebra: Results from the Marie Curie Initial Training Network 10 (2014), 123.
[9]
JS Cheng, K Jin, and D Lazard. 2013. Certified rational parametric approximation of real algebraic space curves with local generic position method. Journal of Symbolic Computation 58 (2013), 18--40.
[10]
JS Cheng and J Wen. 2019. Certified numerical real root isolation for bivariate polynomial systems. In Proceedings of the 2019 on international symposium on symbolic and algebraic computation. 90--97.
[11]
JS Cheng and J Wen. 2022. Certified Numerical Real Root Isolation of Zero-dimensional Multivariate Real Nonlinear Systems. CoRR abs/2211.05266 (2022). arXiv:2211.05266
[12]
D Cox, J Little, and D OShea. 2013. Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra. Springer Science & Business Media.
[13]
J Dedieu and M Shub. 2000. Newton's method for overdetermined systems of equations. MMathematics of Computation 69, 231 (2000), 1099--1115.
[14]
T Dokken. 1985. Finding intersections of B-spline represented geometries using recursive subdivision techniques. Computer Aided Geometric Design 2, 1--3 (1985), 189--195.
[15]
G Elber. 2021. IRIT, Guiirit V12.0. https://www.cs.technion.ac.il/~irit/.
[16]
G Elber, T Grandine, and M-S Kim. 2009. Surface self-intersection computation via algebraic decomposition. Computer-Aided Design 41, 12 (2009), 1060--1066.
[17]
RT Farouki. 1986. The characterization of parametric surface sections. Computer Vision, Graphics, and Image Processing 33, 2 (1986), 209--236.
[18]
LD Figueiredo. 1996. Surface intersection using affine arithmetic. In Proc. Graphics Interface. 168--175.
[19]
G Gatelier, A Labrouzy, B Mourrain, and J-P Técourt. 2005. Computing the topology of three-dimensional algebraic curves. In Computational Methods for Algebraic Spline Surfaces. Springer, 27--44.
[20]
M Gleicher and M Kass. 1992. An interval refinement technique for surface intersection. In Proc. Graphics Interface. 242--249.
[21]
D Goldberg. 1991. What every computer scientist should know about floating-point arithmetic. Comput. Surveys 23, 1 (1991), 5--48.
[22]
L Gonzalez-Vega and I Necula. 2002. Efficient topology determination of implicitly defined algebraic plane curves. Computer Aided Geometric Design 19, 9 (2002), 719--743.
[23]
TA Grandine and FW Klein IV. 1997. A new approach to the surface intersection problem. Computer Aided Geometric Design 14, 2 (1997), 111--134.
[24]
J Harris. 2013. Algebraic geometry: a first course. Vol. 133. Springer Science & Business Media.
[25]
J Hass, RT Farouki, YH Chang, X Song, and TW Sederberg. 2007. Guaranteed consistency of surface intersections and trimmed surfaces using a coupled topology resolution and domain decomposition scheme. Advances in Computational Mathematics 27, 1 (2007), 1--26.
[26]
CM Hoffmann. 1989. Geometric and solid modeling : an introduction. Morgan-Kaufmann, San Mateo, CA.
[27]
E Houghton, R Emnett, J Factor, and C Sabharwal. 1985. Implementation of a divide-and-conquer method for intersection of parametric surfaces. Computer Aided Geometric Design 2, 1--3 (1985), 173--183.
[28]
CY Hu, T Maekawa, EC Sherbrooke, and NM Patrikalakis. 1996. Robust interval algorithm for curve intersections. Computer-Aided Design 28, 6--7 (1996), 495--506.
[29]
Y Huang and D Wang. 2011. Computing intersection and self-intersection loci of parametrized surfaces using regular systems and Gröbner bases. Computer Aided Geometric Design 28 (2011), 566--581.
[30]
X Jia, F Chen, and S Yao. 2022. Singularity Computation for Rational Parametric Surfaces Using Moving Planes. ACM Transactions on Graphics (2022).
[31]
B Jüttler and R Piene. 2008. Geometric modeling and algebraic geometry. Springer.
[32]
R Krawczyk. 1969. Newton-algorithmen zur bestimmung von nullstellen mit fehlerschranken. Computing 4, 3 (1969), 187--201.
[33]
GA Kriezis, NM Patrikalakis, and F-E Wolter. 1992. Topological and differential-equation methods for surface intersections. Computer-Aided Design 24, 1 (1992), 41--55.
[34]
GA Kriezis, PV Prakash, and NM Patrikalakis. 1990. Method for intersecting algebraic surfaces with rational polynomial patches. Computer-Aided Design 22, 10 (1990), 645--654.
[35]
A Krishnamurthy, R Khardekar, S Mcmains, K Haller, and G Elber. 2009. Performing efficient NURBS modeling operations on the GPU. IEEE Transactions on Visualization and Computer Graphics 15, 4 (2009), 530--543.
[36]
A Leykin, J Verschelde, and A Zhao. 2006. Newton's method with deflation for isolated singularities of polynomial systems. Theoretical Computer Science 359, 1 (2006), 111--122.
[37]
C Liang, B Mourrain, and J-P Pavone. 2008. Subdivision methods for the topology of 2D and 3D implicit curves. In Geometric Modeling and Algebraic Geometry. Springer, 199--214.
[38]
JM Lien, V Sharma, G Vegter, and C Yap. 2014. Isotopic arrangement of simple curves: an exact numerical approach based on subdivision. In Mathematical Software - ICMS 2014. Springer, 277--282.
[39]
HW Lin, Y Qin, HW Liao, and YY Xiong. 2014. Affine arithmetic-based B-Spline surface intersection with GPU acceleration. IEEE Transactions on Visualization and Computer Graphics 20, 2 (2014), 172--181.
[40]
Y Ma and Y-S Lee. 1998. Detection of loops and singularities of surface intersections. Computer-Aided Design 30, 14 (1998), 1059--1067.
[41]
D Manocha and JF Canny. 1991. A New Approach For Surface Intersection. International Journal of Computational Geometry & Applications 1, 4 (1991).
[42]
B Marussig and JRH Thomas. 2017. A Review of Trimming in Isogeometric Analysis: Challenges, Data Exchange and Simulation Aspects. Archives of Computational Methods in Engineering 25 (2017), 1059 -- 1127.
[43]
RE Moore. 1966. Interval Analysis. Vol. 4. Prentice-Hall Englewood Cliffs, NJ.
[44]
RE Moore. 1977. A test for existence of solutions to nonlinear systems. SIAM J. Numer. Anal. 14, 4 (1977), 611--615.
[45]
B Mourrain and JP Pavone. 2009. Subdivision methods for solving polynomial equations. Journal of Symbolic Computation 44, 3 (2009), 292--306.
[46]
T Ojika, S Watanabe, and T Mitsui. 1983. Deflation algorithm for the multiple roots of a system of nonlinear equations. J. Math. Anal. Appl. 96, 2 (1983), 463--479.
[47]
Y Park, Q Hong, M Kim, and G Elber. 2021. Self-intersection computation for freeform surfaces based on a regional representation scheme for miter points. Computer Aided Geometric Design 86 (2021).
[48]
Y Park, S-H Son, M-S Kim, and G Elber. 2020. Surface-Surface-Intersection computation using a bounding volume hierarchy with osculating toroidal patches in the leaf nodes. Computer-Aided Design 127 (2020), 270--276.
[49]
NM Patrikalakis. 1993. Surface-to-Surface Intersections. IEEE Computer Graphics and Applications 13, 1 (1993), 89--95.
[50]
NM Patrikalakis and T Maekawa. 2002. Shape Interrogation for Computer Aided Design and Manufacturing. Vol. 15. Springer.
[51]
AG Requicha and JR Rossignac. 1992. Solid modeling and beyond. IEEE Computer Graphics and Applications (1992), 31--44.
[52]
SM Rump. 1983. Solving algebraic problems with high accuracy. In A new approach to scientific computation. Elsevier, 51--120.
[53]
TW Sederberg, HN Christiansen, and Katz S. 1989. An improved test for closed loops in surface intersections. Computer-Aided Design 21, 10 (1989), 505--508.
[54]
TW Sederberg and RJ Meyers. 1988. Loop detection in surface patch intersections. Computer Aided Geometric Design 5 (1988), 161--171.
[55]
W Shao, F Chen, and X Liu. 2022. Robust Algebraic Curve Intersections with Tolerance Control. Computer-Aided Design 147 (2022), 103236.
[56]
Siemens. 2022. Parasolid, V35.0.
[57]
SINTEF. 2021. SISL, V4.7. http://www.sintef.no/sisl.
[58]
V Skytt. 2005. Challenges in surface-surface intersections. In Computational Methods for Algebraic Spline Surfaces. Springer.
[59]
X Song, TW Sederberg, J Zheng, RT Farouki, and J Hass. 2004. Linear perturbation methods for topologically consistent representations of free-form surface intersections. Computer Aided Geometric Design 21, 3 (2004), 303--319.
[60]
C Tu, W Wang, B Mourrain, and J Wang. 2009. Using signature sequences to classify intersection curves of two quadrics. Computer Aided Geometric Design 26 (2009), 317--335.
[61]
P Volino and NM Thalmann. 1994. Efficient self-collision detection on smoothly discretized surface animations using geometrical shape regularity. Computer Graphics Forum 13, 3 (1994), 155--166.
[62]
ST Wu and NA Lenimar. 1999. Marching along a regular surface/surface intersection with circular steps. Computer Aided Geometric Design 16, 4 (1999), 249--268.
[63]
Y Yamaguchi, R Kamiyama, and F Kimura. 2001. Surface-Surface Intersection with Critical Point Detection Based on Bézier Normal Vector Surfaces. Springer US, Boston, MA, 287--308.
Index Terms
- Topology driven approximation to rational surface-surface intersection via interval algebraic topology analysis
Recommendations
Topology Guaranteed B-Spline Surface/Surface Intersection
The surface/surface intersection technique serves as one of the most fundamental functions in modern Computer Aided Design (CAD) systems. Despite the long research history and successful applications of surface intersection algorithms in various CAD ...
Surface approximation with rational B-splines
Many modern geometric modelers use nonuniform rational B-spline curves and surfaces as their canonical representations. Rational B-splines are a versatile representation, encompassing integral B-splines and the basic classical primitives such as conics, ...
Recognizing implicitly given rational canal surfaces
It is still a challenging task of today to recognize the type of a given algebraic surface which is described only by its implicit representation. In this paper we will investigate in more detail the case of canal surfaces that are often used in ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 26 July 2023
Published in TOG Volume 42, Issue 4
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- National Key R&D Program of China
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 777Total Downloads
- Downloads (Last 12 months)408
- Downloads (Last 6 weeks)46
Reflects downloads up to 18 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in