【正文】 n 1). Although filters are not emphasized in this paper, they influence the basic design of our algorithms. We expect most filters to be easily incorporated into our algorithm with minor changes. 5. Section 3 provides the first plete criterion for detecting noncrossing intersection (NIC) of elementary Bezier Curves. By an “elementary curve” we mean the graph of a convex or concave function. 6. Our algorithm uses various numerical and geometric approximations as subroutines. Two key subroutines are for intersecting an elementary Bezier curve with a line (Section 4) and for evaluating signs of the “alpha function” (Section5). 7. The Δbounds require careful application (it is not just a matter of substituting some Δ bound for ε in the generic intersection algorithm). Likewise, the application of the noncrossing intersection criterion (NIC) requires preparation: in Section 6, we describe a coupling process to create the necessary preconditions for applying NIC. 8. What about nonelementary Bezier curves? A general Bezier curve has critical points。 elementary curves have no critical points. There are general methods to break up an algebraic curve at critical points (., [2, 14]). These involve algebraic, nonadaptive methods which we wish to avoid. Instead, Section 7 shows how subdivisioning with separation bounds can detect and isolate such critical points. Section 8 presents the overall intersection algorithm. 9. All our numerical putations are ultimately reduced to ring operations (+,?,) on (binary) bigfloats, ., rational numbers of the form n2m where n,m ∈ Z. These operations are3 carried out exactly. For reasons of efficiency, we do not manipulate algebraic or even general rational numbers. We also do not manipulate polynomials or perform subresultant calculations, such as is found in the current exact intersection algorithms. 10. To emphasize the role of bigfloats in our representations, it is useful to introduce the following terminology. First, define the “standard parametrizations” of points, lines and Bezier curves as follows: a point p is given by its coordinates p = (x, y), a line  is given by the coefficients of its equation  : aX + bY + c, and a Bezier curve is given by its control points (which are in turn given by coordinates). When such standard parameters x, y, a, b, c, etc, are bigfloats, we called them direct objects。 otherwise they are indirect objects. For instance, intersecting a “direct line”  with a “direct Bezier curve” F yields a point whose coordinates are generally algebraic numbers. So is an indirect object. We must then provide alternate means of representing (and approximating) indirect objects by direct objects. We use “expressions” over direct objects. For instance, if is the unique intersection of  and F, we may use the expression “Point[, F]” to represent . Thus, , F are direct objects that serve as nonstandard parameters for p?. This representation can be refined as follows: subdivide F into the pair of subcurves (F0, F1) using De Casteljau’s algorithm as in the generic algorithm. Check whether  intersects F0 (Section 4)。 if so, the refined representation is Point[, F0], otherwise it is Point[, F1]. This process can be repeated as often as we wish, giving better and better approximation of . Computations with approximations of indirect objects are necessarily iterative, with stopping criteria given by appropriate Δbounds. To illustrate, suppose we wish to test whether p? = Point[, F] lies on a standard Bezier curve G. Assume we could pute a bound Δ 0 such that if p? does not lie on G, then its distance from G is at least Δ (Section 2). Then we refine Point[, F] as indicated above, until diam(F) Δ/2. Next, we repeatedly subdivide G into subcurves Gj (j = 0, 1, . . .) using De Casteljau’s algorithm. We discard Gj if CH(Gj ) ∩ CH(F) is empty。 we also stop the subdivision on Gj when diam(Gj) Δ/2. Finally, we conclude that p lies on G iff the convex hulls CH(F),CH(Gj) intersect for some j. The correctness of this procedure is not hard to see. 11. An appendix contains all the omitted proofs. Our full paper is available from Related Work. The putational literature on algebraic curves and surfaces is very large and diverse. We may roughly divide the putational approaches into two distinct viewpoints: (A) The Algebraic Viewpoint treats curves and surfaces as systems of algebraic equations to be solved,usually using symbolic or algebraic techniques. Such “algebraic algorithms” are exact and are (or can be made) plete. (B) The Geometric Viewpoint prefers curves and surfaces in parametric form, usually solved using numerical techniques such as homotopy or subdivision. Such “geometricalgorithms” are often inplete but widely used in practice. The Algebraic Viewpoint has made impressive advances in the last 20 years [3]. Nevertheless, many algebraic algorithms are not considered practical. The curves and surfaces in applications are usually bounded subsets (“patches”) of an algebraic set. The geometric algorithms directly manipulate such patches。 the algebraic algorithms treat plete algebraic sets, often assumed to be irreducible. This fact reduces the applicability of algebraic algorithms. To specify patches of an algebraic set, one could use semialgebraic formulas (., introduce inequalities). But it is not easy, say, to specify a particular branch of a curve in the neighborhood of a selfintersection using this method. The putation and topological analysis of real plane curves is a well studied problem [1, 18], but the worst case plexity is prohibitive。 the best current theoretical bound is O(n16 log5 n) time for a curve F(X, Y) = 0 of degree ≤ n with 2norm ≤ n [11]. Such algorithms are not consideredpractical [9]. When algebraic algorithms are bined with numerical techniques, more practical algorithms can be achieved [13, 12]. Recently, putational geometers have begun to address curves and surfaces [4, 10, 21]. The