Guaranteed consistency of surface intersections and trimmed surfaces using a coupled topology resolution and domain decomposition scheme. (English) Zbl 1118.65011

Hass, Joel; Farouki, Rida T.; Han, Chang Yong; Song, Xiaowen; Sederberg, Thomas W.

Adv. Comput. Math. 27, No. 1, 1-26 (2007).

Summary: We describe a method that serves to simultaneously determine the topological configuration of the intersection curve of two parametric surfaces and generate compatible decompositions of their parameter domains, that are amenable to the application of existing perturbation schemes ensuring exact topological consistency of the trimmed surface representations. To illustrate this method, we begin with the simpler problem of topology resolution for a planar algebraic curve \(F (x, y)=0\) in a given domain, and then extend concepts developed in this context to address the intersection of two tensor-product parametric surfaces \({\mathbf p}(s, t)\) and \({\mathbf q}(u, v)\) defined on \((s, t)\in [0,1]^{2}\) and \((u, v)\in [0,1]^{2}\). The algorithms assume the ability to compute, to any specified precision, the real solutions of systems of polynomial equations in at most four variables within rectangular domains, and proofs for the correctness of the algorithms under this assumption are given.

MSC:

65D17

Computer-aided design (modeling of curves and surfaces)

Keywords:

curve topology; ambient isotopy; tensor-product surfaces; surface perturbations; topological consistency; numerical examples; algorithms

References:

[1]	S. Arnborg and H. Feng, Algebraic decomposition of regular curves, J. Symbolic Comput. 5 (1988) 131–140. · Zbl 0666.14012 · doi:10.1016/S0747-7171(88)80009-9
[2]	D.S. Arnon, Topologically reliable display of algebraic curves, ACM Computer Graphics 17 (1983) 219–227. · doi:10.1145/964967.801152
[3]	D.S. Arnon, G.E. Collins and S. McCallum, Cylindrical algebraic decomposition I: The basic algorithm, SIAM J. Comput. 13 (1984) 865–877. · Zbl 0562.14001 · doi:10.1137/0213054
[4]	D.S. Arnon, G.E. Collins and S. McCallum, Cylindrical algebraic decomposition II: An adjacency algorithm for the plane, SIAM J. Comput. 13 (1984) 878–889. · Zbl 0562.14001 · doi:10.1137/0213055
[5]	D.S. Arnon and S. McCallum, A polynomial-time algorithm for the topological type of a real algebraic curve, J. Symbolic Comput. 5 (1988) 213–236. · Zbl 0664.14017 · doi:10.1016/S0747-7171(88)80013-0
[6]	C. Bajaj, C.M. Hoffmann, R.E. Lynch and J.E.H. Hopcroft, Tracing surface intersections, Comput. Aided Geom. Design 5 (1988) 285–307. · Zbl 0659.65012 · doi:10.1016/0167-8396(88)90010-6
[7]	P. Cellini, P. Gianni and C. Traverso, Algorithms for the shape of semialgebraic sets: A new approach, in: Lecture Notes in Computer Science, Vol. 539 (Springer, New York, 1991) pp. 1–18. · Zbl 0779.14022
[8]	G. Farin, Curves and Surfaces for Computer Aided Geometric Design (Academic Press, 1997). · Zbl 0919.68120
[9]	R.T. Farouki, The characterization of parametric surface sections, Computer Vision, Graphics, Image Processing 33 (1986) 209–236. · Zbl 0631.65012 · doi:10.1016/0734-189X(86)90115-5
[10]	R.T. Farouki, Closing the gap between CAD model and downstream application (Report on the SIAM Workshop on Integration of CAD and CFD, UC Davis, April 12–13, 1999), SIAM News 32 (1999) 1–3.
[11]	R.T. Farouki and T.N.T. Goodman, On the optimal stability of the Bernstein basis, Math. Comput. 65 (1996) 1553–1566. · Zbl 0853.65051 · doi:10.1090/S0025-5718-96-00759-4
[12]	R.T. Farouki, C.Y. Han, J. Hass and T.W. Sederberg, Topologically consistent trimmed surface approximations based on triangular patches, Comput. Aided Geom. Design 21 (2004) 459–478. · Zbl 1069.65552
[13]	R.T. Farouki and V.T. Rajan, On the numerical condition of polynomials in Bernstein form, Comput. Aided Geom. Design 4 (1987) 191–216. · Zbl 0636.65012 · doi:10.1016/0167-8396(87)90012-4
[14]	R.T. Farouki and V.T. Rajan, Algorithms for polynomials in Bernstein form, Comput. Aided Geom. Design 5 (1988) 1–26. · Zbl 0648.65007 · doi:10.1016/0167-8396(88)90016-7
[15]	L. Gonzalez-Vega and I. Necula, Efficient topology determination of implicitly defined algebraic plane curves, Comput. Aided Geom. Design 19 (2002) 719–743. · Zbl 1043.68105 · doi:10.1016/S0167-8396(02)00167-X
[16]	T.A. Grandine and F.W. Klein, A new approach to the surface intersection problem, Comput. Aided Geom. Design 14 (1997) 111–134. · Zbl 0906.68151 · doi:10.1016/S0167-8396(96)00024-6
[17]	H. Hong, An efficient method for analyzing the topology of plane real algebraic curves, Math. Comput. Simulation 42 (1996) 571–582. · Zbl 1037.14503 · doi:10.1016/S0378-4754(96)00034-1
[18]	J.M. Lane and R.F. Riesenfeld, Bounds on a polynomial, BIT 21 (1981) 112–117. · Zbl 0472.65041 · doi:10.1007/BF01934076
[19]	M.H.A. Newman, Topology of Plane Sets (Cambridge Univ. Press, Cambridge, 1939). · Zbl 0021.06704
[20]	M.-F. Roy and A. Szpirglas, Complexity of the computation of cylindrical decomposition and topology of real algebraic curves using Thom’s lemma, in: Lecture Notes in Mathematics, Vol. 1420 (Springer, New York, 1990) pp. 223–236. · Zbl 0718.14028
[21]	T. Sakkalis, The topological configuration of a real algebraic curve, Bull. Austral. Math. Soc. 43 (1991) 37–50. · Zbl 0716.14034 · doi:10.1017/S0004972700028756
[22]	T.W. Sederberg, Implicit and parametric curves and surfaces for computer aided geometric design, Ph.D. thesis, Purdue University (1983).
[23]	E.C. Sherbrooke and N.M. Patrikalakis, Computation of the solutions of nonlinear polynomial systems, Comput. Aided Geom. Design 10 (1993) 379–405. · Zbl 0817.65035 · doi:10.1016/0167-8396(93)90019-Y
[24]	X.W. Song, T.W. Sederberg, J. Zheng, R.T. Farouki and J. Hass, Linear perturbation methods for topologically consistent representations of free-form surface intersections, Comput. Aided Geom. Design 21 (2004) 303–319. · Zbl 1069.65567 · doi:10.1016/j.cagd.2003.11.004