Local analysis of curves and surfaces intersection problem using tracing

S. Yu. Gatilov

Sibirskij žurnal čistoj i prikladnoj matematiki, Tome 16 (2016) no. 1, pp. 57-89

Résumé

The tracing method for finding intersections of parametric curves and surfaces is considered. The suggested approach is based on the numeric predictor-corrector method, where Runge–Kutta or Adams method is the predictor, and Newton’s method is the corrector. Special equation system is used to find simple singular intersections, its rank is analysed. The tracing step is chosen adaptively. The resulting curve is represented as cubic spline. Finally, the problems of finishing tracing exactly and tracing along boundary are considered.

Détail

Keywords: surfaces intersection, curve tracing, Newton’s method.

Bibliographie

[1] Hiroyuki Nakamura, Masatake Higashi, Mamoru Hosaka, “Robust Computation of Intersection Graph Between Two Solids”, Computer Graphics Forum, 16:3 (1997), 79–88

[2] Les Piegl, Wayne Tiller, The NURBS Book, 2$^{\mathrm{nd}}$ ed., Springer-Verlag, New York, 1997

[3] Miller J. R., Goldman R. N., “Geometric Algorithms for Detecting and Calculating All Conic Sections in the Intersection of Any Two Natural Quadric Surfaces”, Graph. Models Image Process, 57:1 (1995), 55–66 | DOI

[4] Dupont L., Lazard D., Lazard S., Petitjean S., “Near-Optimal Parameterization of the Intersection Of Quadrics. I: The Generic Algorithm”, J. of Symbolic Computation, 43:3 (2008), 168–191 | DOI | MR | Zbl

[5] Ku-Jin Kim, Torus and Simple Surface Intersection Based on Configuration Space Approach, Ph.D. thesis, Pohang University of Science and Technology, 1998

[6] Sederberg Th. W., Parry S. R., “Comparison of Three Curve Intersection Algorithms”, Comput. Aided Des., 18:1 (1986), 58–63 | DOI

[7] Sederberg T., Nishita T., “Curve Intersection Using Bézier Clipping”, Computer-Aided Design, 22:9 (1990), 538–549 | DOI | Zbl

[8] Patrikalakis N. M., Takashi Maekawa, Shape Interrogation for Computer Aided Design and Manufacturing, Springer, 2002 | MR | Zbl

[9] Toth D. L., “On Ray Tracing Parametric Surfaces”, SIGGRAPH Comput. Graph, 19:3 (1985), 171–179 | DOI

[10] Martin W., Cohen E., Fish R., Shirley P., “Practical Ray Tracing of Trimmed Nurbs Surfaces”, J. Graph. Tools, 5:1 (2000), 27–52 | DOI

[11] Pabst H.-F., Springer J. P., Schollmeyer A., Lenhardt R., Lessig C., Froehlich B., “Ray Casting of Trimmed Nurbs Surfaces on the GPU”, IEEE Symposium on Interactive Ray Tracing (2006), 151–160

[12] Bajaj Ch. L., Hoffmann Ch. M., Lynch R. E., Hopcroft J. E., “Tracing Surface Intersections”, Computer Aided Geometric Design, 5:4 (1988), 285–307 | DOI | MR | Zbl

[13] Barnhill R. E., Kersey S. N., “A Marching Method for Parametric Surface/Surface Intersection”, Computer Aided Geometric Design, 7:1–4 (1990), 257–280 | DOI | MR | Zbl

[14] Barnhill R. E., Farin G., Jordan M., Piper B. R., “Surface/Surface Intersection”, Computer Aided Geometric Design, 4:1–2 (1987), 3–16 | DOI | MR | Zbl

[15] Golovanov N., Geometric Modeling: The Mathematics of Shapes. CreateSpace, Independent Publishing Platform, 2014

[16] Hohmeyer M. E., Robust and Efficient Surface Intersection for Solid Modeling, Ph. D. thesis, University of California, 1986

[17] Grandine Th. A., Klein F. W., “A New Approach to the Surface Intersection Problem”, Comput. Aided Geom. Des., 14:2 (1997), 111–134 | DOI | MR | Zbl

[18] Krishnan Sh., Manocha D., “An Efficient Surface Intersection Algorithm Based on Lower-Dimensional Formulation”, ACM Trans. Graph., 16:1 (1997), 74–106 | DOI | MR

[19] Kubica B. J., “Interval Methods for Solving Underdetermined Nonlinear Systems”, Reliable Computing, 15 (2011), 207–217 | MR

[20] Gatilov S., “Properties of Nonlinear Systems and Convergence of the Newton-Raphson Method in Geometric Constraint Solving”, Bull. Nov. Comp. Center, 32 (2011), 57–75

[21] Dennis J. E., Schnabel R. B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Classics in Applied Mathematics, 16, SIAM, Philadelphia, 1996 | MR | Zbl

[22] Xiao-Chuan Cai, Keyes D. E., “Nonlinearly Preconditioned Inexact Newton Algorithms”, SIAM J. Sci. Comput., 24:1 (2002), 183–200 | DOI | MR | Zbl

[23] Gatilov S., “Using Low-Rank Approximation of the Jacobian Matrix in the Newton-Raphson Method to Solve Certain Singular Equations”, J. of Computational and Applied Mathematics, 272 (2014), 8–24 | DOI | MR | Zbl

[24] Allgower E. L., Georg K., Introduction to Numerical Continuation Methods, Classics in Applied Mathematics, 45, SIAM, 2003 | MR | Zbl

[25] Hiroshi Akima, “A New Method of Interpolation and Smooth Curve Fitting Based on Local Procedures”, J. ACM, 17:4 (1970), 589–602 | DOI | Zbl

[26] Catmull E., Rom R., “A Class of Local Interpolating Splines”, Computer aided geometric design, eds. R. E. Barnhill, R. F. Reisenfeld, Academic Press, New York, 1974, 317–326 | DOI | MR

[27] Bajaj Ch. L., Guoliang Xu, “Nurbs Approximation of Surface/Surface Intersection Curves”, Adv. in Computational Math., 2:1 (1994), 1–21 | DOI | MR | Zbl

[28] Dormand J. R., Prince P. J., “A Family of Embedded Runge–Kutta Formulae”, J. of Computational and Applied Mathematics, 6:1 (1980), 19–26 | DOI | MR | Zbl

[29] Floater M. S., Evaluation and Properties of the Derivative of a Nurbs Curve, Academic Press Professional, Inc., San Diego, 1992, 261–274 | MR

[30] Kyu-Yeul Lee, Doo-Yeoun Cho, Tae-Wan Kim, “A Tracing Algorithm for Surface-Surface Intersections on Surface Boundaries”, J. of Computer Science and Technology, 17:6 (2002), 843–850 | DOI | MR | Zbl