发布时间 : 星期二 文章Bézier曲线的细分技术毕业论文外文翻译更新完毕开始阅读7c77118e10a6f524cdbf8536
(i) (ii) Figure 5: Singular cubic Bezier curve: (i) controlpolygon, (ii) hodograph
Let Fx(t), Fy(t) be the coordinate functions of F = F[0, 1], i.e., F(t) = (Fx(t), Fy(t)), and let F?? = (F??x , F??y ) denote derivatives with respect to t. Call t ∈ (0, 1) a critical value, and F(t) a critical point, if one of the following conditions hold (cf. Kim and Lee [14]): (i) F(t) is stationary, i.e.,Fx'(t)?Fy'(t)?0；
'(ii) F(t) is x-extreme, i.e.,Fx'(t)?0,Fx'(t?)Fx'(t?)?0，Fy(t)?0；
(iii) F(t) is an inflexion point, i.e., HF (t) = 0 and HF (t+)HF (t?) < 0, where
'H（?Fx'(t)Fy''(t)?Fy(t)Fx''(t). Ft）：Lemma 9. If F has no critical points in its relative interior then F is elementary. Conversely, if F is elementary, then it has no x-extreme or inflexion points in its relative interior.
Critical values are algebraic numbers. Hence we do not propose to subdivide Bezier
curves into elementary parts by subdividing at critical points. Instead, we will subdivide a Bezier curve at bigfloat values so that the resulting subcurves are either elementary or contain at most one critical point. Call a curve containing exactly one critical point an elementary critical curve. Now, we appeal to additional separation bounds which are summarized by a single number Δ? > 0 to be explained.
In the rest of this section, assume that the control polygons of F and G are P(F) = (p0, . . . , pm) and P(G) = (q0, . . . , qn). Moreover, the coordinates of the pi’s and qj ’s are L-bit bigfloats. First, we bound the degree and norms of critical points: Lemma 10.
(i) If F(t) = (Fx(t),Fy(t)) is a stationary or x-extreme point, then Fx(t) and Fy(t) have
m（4L9mm）degrees ≤ m ? 1 and 2- norms at most
(ii) If F(t) is an inflexion point, then F(t) has degree ≤ 2m ? 3 and 2-norm at most （2m416L81m）m. This gives us:
Corollary 11. Let p, q be two distinct critical points of F. If 2 ≤ m ≤ n then either |p.x ? q.x|
-mor |p.y ? q.y| is larger than?4：. ?（16m?2256L812mm5） Next, we generalize Theorem 3 to the case where q is any algebraic point:
Theorem 12. Let q = (q.x, q.y) where q.x, q.y are algebraic numbers with 2-norm ≤ c and degree ≤ d. Let the polynomial A(X, Y ) have 2-norm a and degree m. If the curve A(X, Y) = 0 does not contain a circle centered at q then the distance from q to A = 0 is at least
?（? （2NK）25m，a，L，c，d）32-D-12m2d2 where
5?2m?2d4423??），D?m2d（. N?（）K?max｛13，4ma，c｝，md5 Let Δ6 = Δ(m, n, L) be the minimum separation between the curve G and a critical point p of F, assuming p ∈ G. This bound comes from plugging Lemma 10 into Theorem 12. Finally, choose Δ? to be the minimum of the bounds Δ1 (Theorem 1), Δ2 (Theorem 2), Δ4 and Δ6. If diam(F) < Δ?, we may call F a micro curve. It is well-known that the derivative with respect to t is given by
F(t)?m?(pi?pi?1)B'i?1mi?1m?1i?1(t)?m??piBm?1(t) where we define?pi:?pi?1?pi
i?1mAlso, let ?P(F) denote (?p1, . . . ,?pm). Thus, we see that m?P(F) is the control polygon for the curve F??(t), known as the hodograph of F. Hence F contains a stationary point iff F??(t) passes through the origin. E.g., Figure 5(ii) shows ?P(F) for the cubic Bezier of Figure 5(i); we may check that the hodograph passes through the origin in this case. Theorem 13 (Stationary Points). Let diam(F) < Δ3(m ? 1,ma, 2)/m. Then F contains a stationary point iff the convex hull of ?P(F) contains the origin (0, 0).
Theorem 14 (x-Extreme Points). Let diam(F) < Δ?. Then F contains an x-extreme point iff
(?p1).x(?pm).x?0 and (?p1).y(?pm).y?0.
If p, q, r are planar points, let det(p, q, r) be the determinant of the 3 × 3 matrix whose rows are ph, qh, rh, where ph = (p.x, p.y, 1). Also let det(p, q) denote p.xq.y ? p.yq.x. Theorem 15 (Inflexion Points). Let diam(F) < Δ*. Then F contains an inflexion point iff det(p0, p1, p2) det(pm?2, pm?1, pm) < 0.
The preceding three theorems give us complete criteria for checking if a micro curve is an elementary critical curve.
8. INTERSECTION ALGORITHM
We now present the global algorithm for intersecting two arbitrary Bezier curves. We design the algorithm so that the generic intersection algorithm (see Introduction) is naturally embedded as the first phase of our algorithm. Simplicity rather than practical efficiency is the aim of the following description.
We have two work queues Q0 and Q1. Each queue is just a list of candidate pairs. A candidate pair (F,G) is called a micro pair if the diameter of CH(F) ∪ CH(G) is less than Δ*; it is a macro pair otherwise. Call Q0 and Q1 the macro queue and micro queue, as they contain macro pairs and micro pairs, respectively. After the obvious initialization of Q0, Q1, the algorithm operates in two phases:
Macro Phase: This is basically the generic intersection algorithm of Section 1, operating on Q0. The key difference is that after splitting a pair (F,G) into (Fi,G) (i = 0, 1), if (Fi,G) is a candidate pair, we place it into Q0 or Q1, depending on whether it is a macro or micro pair. If we did nothing else in the macro phase, we would still be correct. But in practice, we would perform a variety of efficient partial criteria (e.g., a test for transversal intersection). This phase ends when Q0 is empty.
Micro Phase: We now operate on Q1: for each pair (F,G) extracted from Q1, we check if F contains a critical point (Section 7). If so, we can output the pair. Otherwise, we apply the coupling process (Section 6).
Remarks. The macro phase is ―standard‖ and easy to implement. The micro phase treats degenerate and unlikely situations. At the end of the macro phase, the micro queue is expected to be small or empty for ―nice‖ inputs. 9. OPEN PROBLEMS
This paper opens up the possibility of achieving fully adaptive algorithms with exactness guarantees for other computational problems involving curves and surfaces. This new direction is intrinsically tied to the use of geometric separation bounds. Most obvious problems are open, so we only list a few questions related to the current paper:
? Our algorithm for intersecting F,G has this Antipodal Assumption: F,G have finitely many antipodal pairs. As noted, it generalizes the standard assumption that F,G are relatively prime. Clearly, if F is an offset of G, or vice-versa, then the Antipodal Assumption fails. We conjectured that the converse holds. Sungwoo Choi4 has proved this conjecture. Choi’s theorem implies that a Δ-separation property holds even when the Antipodal Assumption fails. Thus, the Antipodal Assumption is not essential. Unfortunately, we do not know how to bound Δ without the Antipodal Assumption.
? Give a complexity analysis of our algorithm, or some variant thereof. In general, the
complexity of subdivision algorithms seems little understood.
? Implement an adaptive algorithm such as ours, and compare to non-robust subdivision algorithms, or to algebraic algorithms.
? Improve our separation bounds. We have somewhat improved bounds that exploit the fact that the curves are Bezier; these have been omitted for brevity. Developing bounding techniques that exploit the geometry would be of great interest.
? Provide a simpler algorithm in case there are only transversal intersections.
Acknowledgments
Special thanks to Professor Myung-Soo Kim for his warm hospitality at SNU. We have greatly benefited from discussions with Myung-Soo Kim, Gershon Elber, Joon-Kyung Seong and Iddo Hanniel. Professor Wen-ping Wang pointed out the need to distinguish between tangential crossing and tangential non-crossing cases. 10. REFERENCES
[1] D. S. Arnon and S. McCullum. A polynomial-time algorithm for the topological type of a real algebraic curve. J. of Symbolic Computation, 5:213–236, 1988.
[2] C. Bajaj and M.-S. Kim. Algorithms for planar geometric models. In Proc. 15th Int. Colloq. Automata, Languages and Programming, pages 67–81, 1988. Lecture Notes in Computer Science.
[3] S. Basu, R. Pollack, and M.-F. Roy. Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics. Springer, 2003.
[4] E. Berberich, A. Eigenwillig, M. Hemmer, S. Hert, K. Mehlhorn, and E. Sch¨omer. A computational basis for conic arcs and boolean operations on conic polygons. In Proc. 10th European Symp. On Algorithms (ESA’02), pages 174–186. Springer, 2002. Lecture Notes in CS, No. 2461.
[5] H. Br¨onnimann, C. Burnikel, and S. Pion. Interval arithmetic yields efficient dynamic filters for computational geometry. Discrete Applied Mathematics, 109(1-2):25–47, 2001. [6] E. Cohen, R. Riesenfeld, and G. Elber. Geometric Modeling with Splines: An Introduction. A.K. Peters, Ltd, Wellesley, MA, 2001.
[7] G. Elber and M.-S. Kim. Geometric constraint solver using multivariate rational spline functions. In Proc. 6th ACM Symp. on Solid Modeling and Applications, pages 1–10. ACM Press, 2001.
[8] G. Farin. Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide. Academic Press, Inc, second edition, 1990.
[9] R. T. Farouki. Numerical stability in geometric algorithms and representation. In D. C.