Efficiently Computing Intersection Curves of A Plane and A Surface of Revolution

Jinyuan Jia
Liaoning University of Petroleum &Chemistry Technology, Fushun, Liaoning Province, P. R. China, 113001
Zhuhai College, Jilin University, Zhuhai, Guangdong Province, P. R. China, 519041
csjyjia@yahoo.com.cn

Kai Tang
The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong
mektan@ust.hk

Ajay Joneja
The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong
joneja @ust.hk

Ki-Wan Kwok
Dept. of Computing, Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong
cskwkwok@comp.polyu.edu.hk

Abstract

Computing the planar sections of objects is a fundamental operation in solid modeling. Subdivision method is commonly used for solving such intersection problems. In this paper, a novel revolute quadric decomposition is proposed for surfaces of revolution, which are subdivided into a set of coaxial revolute quadrics along the generatrix. This reduces the intersection problem of a plane and a surface of revolution to the intersection problem of a plane and a revolute quadric, which has robust, accurate and efficient geometric solution. Further, the intersection curves can be represented with a group of G¹ conic arcs. A new concept, valid intersection interval (VII), is introduced and a new technique, cylindrical bounding shell clipping, is proposed for efficient intersection detection for a plane and a surface of revolution. Finally, a tracing algorithm is presented for recognizing singular points and closed loops of intersection curves. Implemented examples show the robustness and effectiveness of the proposed algorithm.

1. Introduction

The plane/surface intersection problem is essential in geometric modeling and can find wide applications in CAD, CAM, VR and computer graphics, e.g. numerical control machining (milling) involves intersections of offset surfaces with a series of parallel planes to create machining paths for ball cutters. Alternatively, in Constructive Solid Geometry (CSG) modeling applications, planes are usually used to construct new objects with surfaces altogether that involve the intersection curves of planes and surfaces for representing their boundaries. Computing plane sections of surfaces is required for rendering the contours of surfaces, which is very useful in descriptive geometry, drafting and manufacturing. Developing robust, accurate and efficient algorithms for surface intersections remains a challenging task for many years. Surface of revolution is an important member of CSG library and is frequently used in various applications of CAD/CAM, VR and CG. It is necessary to develop a robust, accurate and efficient algorithm for computing plane sections of surfaces of revolution.

In general, there are four approaches to solving surface intersection problems: subdivision method, algebraic method, lattice method and tracing method, a good summary can be found in [17]. Subdivision method is the most robust among them. Basically, subdivision method subdivides surfaces into quadrilateral/triangular meshes and reduces the surface/surface intersection problem to the quad/ quad or triangle/triangle intersection problem. However, it is quite difficult to balance between subdivision density and precision. If the triangular mesh is subdivided densely for achieving good approximation quality, it will lead to data proliferation and slow computation; if meshed sparsely, the resulting intersection curves may miss the tiny loops and generate incorrect results topologically.

As a possible remedy to the problems, quadric decomposition is proposed in [5] for rendering purpose; instead of quads or triangles, quadric decomposition subdivides the surface into piecewise quadric patches. There has been some existing work [2, 4, 5, 9, 10, 18] on how to construct a G¹ triangular quadric net. However, all of them are for general surfaces, which might not be efficient when applied to special surfaces, e.g. surfaces of revolution. There should be more efficient quadric decomposition for these special surfaces. In this paper, we present a specific revolute quadric decomposition for surfaces of revolution. Based on the proposed revolute quadric decomposition, a new algorithm for computing the plane sections of surfaces of revolution is devised especially.

2. Related work

There are a few previous reports involving computing the plane sections of surfaces of revolution. Firstly, Kim et al [13] used algebraic method to give an elegant closed form representation for the intersection curves of a plane and a surface of revolution; however, it contains square roots and have to be further approximated by a group of lower-degree rational curve segments piecewisely, since most CAD systems can only deal with rational curves and surfaces currently. Moreover, from the given representation, we cannot directly detect closed loops and singular points of the intersection curves, recognizing them still requires numerical solutions of high-degree algebraic equations.

Considering the fact that approximations cannot be avoided during intersection processing, Baciu et al [1] proposed a subdivision method for solving this problem, which subdivides a surface of revolution into a sequence of coaxial truncated cones along its generatrix and reduces the intersection problem of plane/surface of revolution to the intersection problem of plane/truncated cones; but it requires too many truncated cones to approximate surfaces of revolution for good approximation quality and produces densely G⁰ piecewise conic arcs as the final plane section curves of surfaces of revolution, since truncated cone decomposition is a low-efficient quadric decomposition for surfaces of revolution.

There are three existing decomposition schemes for solving intersection problem of surfaces of revolution, namely quad/triangle decomposition [8], circle decomposition [14], truncated cone decomposition [1] (see Fig. 1). In this paper, we propose a new quadric decomposition, revolute quadric decomposition, which subdivides a surface of revolution into a sequence of G¹ coaxial revolute quadrics along its revolute axis and reduces the intersection problem of plane and surface of revolution to the intersection problem of a plane and revolute quadrics. It produces much fewer but more smoothly basic fitting elements than other three existing schemes, and the resulting intersection curves can be represented by a group of fewer G¹ piecewise conic arcs.

(a) (b)

(c) (d)

Fig 1. Four decompositions of surfaces of revolution: (a) quadrilateral decomposition, (b) circle decomposition, (c) truncated cone decomposition, (d) revolute quadric decomposition

Comparing with the two previous methods, our new method is based on revolute quadric decomposition, it possesses the following advantages:

· Fundamentally, there is a geometric method to compute the plane sections of revolute quadric robustly, accurately and efficiently.

· The final intersection curves can be represented by G¹ piecewise conic arcs; conic arc is a good form for contemporary CAD/CAM systems.

· Detection of the closed loops and singular points of the intersection curve becomes very easy by tracing piecewise conic arcs sequentially along the revolute axis.

3. Revolute quadric decomposition

A surface of revolution is an envelope of the generatrix about its axis. So subdividing it into a collection of revolute quadrics in 3D space is equivalent to subdividing its generatrix into a collection of coaxial conic arcs along the axis in 2D space. In this section, we propose two kinds of coaxial conic interpolator to gneeratrix, G⁰ single LS coaxial conic fitting and G¹ bi-coaxial conic arc spline, to approximate the generatrix for revolute quadric decomposition to surfaces of revolution.

A conic section in the xy plane is represented as Ax² + By² + Cxy + Dx + Ey + F = 0 in general. It can be reduced to Ax² + By² + Dx + F = 0 by assuming that the revolute axis is the x-axis, and further to Ax² + y² + Dx + F = 0 by isolating the degenerated case of vertical line B = 0. There are only three freedoms A, D and F; geometrically, they correspond to two axial radii r_a, r_b, and the x-coordinate C_x of the center of a conic section. If we assume that the axis of the surface of revolution is the x-axis, the problem becomes how to approximate the generatrix optimally with a group of coaxial conic arcs C_i: A_ix² + y² + D_ix + F_i = 0.

Many general conic fitting algorithms were suggested in the literature, which involve how to approximate a curve into a sequence of general conic arcs, but not coaxial conic arcs. So, the restriction ‘coaxial’ is too strong for any general conic arc fitting algorithms to be employable in this special problem. Therefore, it is necessary to develop a specific coaxial conic arc fitting method for subdividing the generatrix effectively.

Locally, we construct two kinds of coaxial conci arc interpolators, (1) single G¹ coaxial conic arc interpolator, and (2) bi-coaxial conic spline. Globally, we fit the generatrix with coaxial conic spline, by moving G¹ coaxial bi-conic arc interpolator adaptively and sequentially from one endpoint to the other one. Once a coaxial bi-conic arc to fit the generatrix is determined by stretching it to the longest, we start the next coaxial bi-conic arc fitting. This marching coaxial bi-conic arc interpolator is repeated until the other endpoint of the generatrix is reached.

Coaxial conic arc fitting method consists of three major steps as follows:

· [Polygonization] To sample the generatrix into a set of points P_i and tangent vectors T_i;

· [Local conic fitting] To construct a coaxial conic interpolator to fit the generatrix optimally;

· [Global conic fitting] To move coaxial conic interpolator along generatrix adaptively and progressively.

3.1. GC⁰ single coaxial conic fitting

It is worth noting that since our polygonization is independent of the form of the generatrix, it is applicable to both parametric and algebraic representations, and even the discrete form. Each conic arc C_j is defined on the interval [x_m, x_n] (0 ≤ m ≤ j ≤ n ≤ N) and computed by using the least square method to estimate A_i, D_i and F_i. By minimizing the sum of square distance differences of all sampling points and two interpolation constraints at two endpoints P_m (x_m, y_m) and P_n (x_n, y_n), C⁰ least square estimation of A_i, D_i and F_i is derived as follows:

to differentiate f with respect to A_i, D_i, F_i, l₁ and l₂ respectively,

We can obtain A_i, D_i, and F_i, by solving the following linear equation system:

Hc = b, (1)

Where

,

,

.

However, H is possibly singular if two given endpoints coincide, that implies, the determinant of H becomes zero if x_m = x_n. In this case, the equation (1) has no unique solution. We have two methods to solve this problem: (1) we can restrict each fitting curve segment to be an open one, because the proposed global coaxial conic fitting is just a marching procedure, the fitting interval can be controlled freely by shrinking or stretching it to avoid such closed loop during the conic fitting; (2) we can calculate the pseudo inverse H⁺ of H [7], instead of the real inverse of H, that is a least square solution to H^-1.

3.2. GC¹ coaxial bi-conic splines

A single axial conic arc G¹ interpolating two given endpoints and two associate tangential vectors requires four constraints of two position interpolations and two tangential interpolations in total, but an axial conic arc has only three freedoms - A, D, and F - and is thus over-constrained for the four constraints. Here, we propose a coaxial bi-conic arc spline to G¹ interpolate two specified endpoints P₁ (x₁, y₁) and P₂ (x₂, y₂) and their associated tangent vectors T₁ (T_x1, T_y1) and T₂ (T_x2, T_y2), by using two coaxial conic arcs, which preserves continuity at their common endpoint P_m (x_m, y_m), instead of a single axial conic arc. This idea is inspired by circular biarc spline. Two coaxial conic arcs C₁: A₁x² + y² + D₁x + F₁ = 0 on the interval [x₁, x_m], and C₂: A₂x² + y² + D₂x + F₂ = 0 on the interval [x_m, x₂] are used together to fit the generatrix on the interval [x₁, x₂], which provide six freedoms A₁, D₁, F₁, A₂, D₂, F₂ to solve six constraintes (by G¹ position and tangential interpolation on P₁, P₂ and P_m) as follows:

· C₁ interpolates at the endpoint P₁;

· C₁ interpolates at tangent vector T₁;

· C₂ interpolates at the endpoint P₂;

· C₂ interpolates at tangent vector T₂;

· C₁ joins C₂ at P_m(x_m, y_m) with G⁰ continuity;

· C₁ joins C₂ at P_m(x_m, y_m) with G¹ continuity;

Here, P_m is not asked definitely to lie on the generatrix in order to fit it more flexibly. Because y_m depends on x_m, there is only one constraint x_m actually. Six linear equations are formed for estimating six coefficients A₁, D₁, F₁, A₂, D₂, F₂ of coaxial bi-conic arc interpolator as follows:

By eliminating y_m in the fifth and sixth equations, we obtain the system (2) of linear equations about x_m as

(2)

The coefficients A₁, D₁, F₁, A₂, D₂, and F₂ are expressed below explicitly as functions of the two end points and their associated tangents, in addition to x_m which is the only unknown variable that is left as a freedom for the optimal bi-conic fitting. Similar to circular biarc spline, coaxial bi-conic arc spline also has two types, (1) C-type coaxial bi-conic arc spline as shown in Fig. 2, it may be composed of two joining elliptic arcs; and (2) S-type coaxial bi-conic arc spline as shown in Fig. 3, it may be composed of an elliptic/parabolic arc joining with a coaxial hyperbolic arc together. Combing the two types of coaxial bi-conic splines can flexibly fit arbitrary generatrices. Thus, such bi-coaxial conic arc spline successfully resolves the over-constrained problem faced by single coaxial conic fitting.

Fig 2. C-type coaxial bi-conic arc spline

Fig 3. S-type coaxial bi-conic arc spline

3.3 Optimal coaxial bi-conic arc fitting

In the above equation system (2), x_m is an unknown variable, apparently, it is a freedom for optimally fitting the generatrix. As shown in Fig. 4, choosing different section point x_m = x₁+ t(x₂ - x₁) (0 £ t £ 1) can produce different approximation effects, the problem is how to find the best t for the optimal coaxial bi-conic arc fitting. Theoretically, it can be transformed into a complicated optimization problem as follows:

(3)

where C₁(x, x_m) and C₂(x, x_m) are the explicit equations of the two coaxial bi-conic arcs, and G(x) is the explicit representation of the generatrix.

The optimization problem (3) is rather complicated usually and cannot be solved easily. Considering that golden section searching is the simplest optimization method and easy to implement, we choose it to determine the best t_m. Its main idea is to compare the maximum errors e₁ and e₂ at two golden points t_m = t₀ + 0.382(t₁ – t₀) and t_u = t₀ + 0.618(t₁ - t₀) within the interval [0, 1] (initially, t₀ = 0.0, t₁ = 1.0), and see if e_m > e_u, then the subinterval [t₀, t_m] is thrown away, otherwise the subinterval [t_u, t₁] is thrown away. By performing such golden section searching recursively until [t_m, t_u] is small enough (less than the specified threshold ε, ε is set as e/10 in our program, where e is the specified error tolerance), the best t_b is set as (t_m + t_u)/2, the mid-point of [t_m, t_u]. However, such searching may only find a locally optimal point and miss the global optimal t_m when the objective function is a multimodal one.

To avoid missing the global optimal point, in each round of compressing the interval [t_m, t_u], we choose e_m = min(e₀, e_m) and e_u = min(e₂, e_u). If e_m < e₀, we set t₀ = t_m, t_m = t₀ + 0.382(t₁ – t₀) and e₀ = e_m. Similarly, if e_u < e₁, we set t₁ = t_u, t_u = t₀ + 0.618(t₁ – t₀) and e₁ = e_u. Then we estimate new e_m and e_u as to new t_m and t_u, and keep such compressing the interval [t_m, t_u] until finding the best section point x_b.

Fig 4. Finding the best x_m by golden ratio searching

3.4. Bisection marching

Under the specified tolerance d, how to stretch each fitting conic arc along the generatrix as long as possible for achieving the least number of fitting conic arcs globally? Adaptive error-driven bisection marching is employed in our method. Initially, the first conic arc is used to fit the generatrix on [x₁, x₂], and then we compare the error measure e with d, where, e is measured by averaging the maximum horizontal and vertical distances between the original generatrix and the fitting conic arc. The global marching idea can be sketched as follows:

Repeat the following three steps until x = x₂:

· If d = e, end this round of fitting conic arc and start next round of conic arc fitting from x;

· If d < e, enlarge x to (x+x₂)/2 and redo the conic fitting on the new interval [x₁, (x+x₂)/2];

· If d > e, reduce x to (x₁+x)/2 and redo the conic fitting on the new interval [(x+x₁)/2, x].

(1) if d = e, start next bi-conic fitting

(2) if d > e, shrink and refit

(3) if d < e, stretch and refit

Fig 5. Bisection marching bi-conic arc interpolator

3.5 An experimental example

We implemented an example as shown in Fig. 6 by using linear approximation (truncated cone decomposition), G⁰ single coaxial conic fitting and G¹ bi-coaxial conic arc fitting (revolute quadric decomposition) respectively. The performance data in Table 1 shows that the ratio of the number of the required linear segments and the number of the required conic arcs become larger and larger when e becomes smaller and smaller. At the tolerance 10^-1, the number of line segments is 1.75 times of the number of the required conic arcs. At the tolerance 10^-3, the number of line segments is 3 times of the number of conic arcs. At the tolerance 10^-5, the number of line segments is 6.5 times of the number of the conic arcs. Therefore, revolute quadric decomposition is considerably more efficient than truncated cone decomposition for surfaces of revolution. The major computations are analytical, and the algorithm guarantees that coaxial bi-conic arcs interpolate at the sampling points and the associated tangent vectors on the generatrix exactly. It is robust, simple and easy to implement in practice. It should be pointed out that although the single-revolute-quadric-based decompsition generates less conic arcs than our bi-revolute-quadrics-based decomposition, it is at the cost of lossing G¹ continuity on the approximated generatrix, which is usually prohibited in most applications.

Fig 6. Coaxial bi-conic fitting generatrix with e = 10^-2

Table 1. Performance data of three quadric decompositions, truncated cone (TC) vs. GC⁰ single coaxial conic fitting (single RQ) vs. GC¹ coaxial bi-conic fitting (Bi-RQ)

Tolerance		10^-2	10^-3	10^-4	10^-5	10^-6	10^-7
Num. of fitting conic arcs	TC	42	134	421	1329	4202	13284
	Single RQ	18	34	70	152	325	689
	Bi-RQ	30	52	104	212	536	910

4. Intersection determination

This section addresses how to take fast intersection detections. Firstly, cylindrical bounding shell (CBS) is devised for fast intersection rejection of plane and surfaces of revolution. Although a surface of revolution is subdivided into many trimming coaxial revolute quadrics, not all of them have intersection with the cutting plane, usually, only very few of them have real intersection with the surface of revolution. Then, a notation, valid intersection intervals (VII), is introduced to rule out those revolute quadrics that are guaranteed not to intersect the cutting plane, for which it is unnecessary to perform intersection computations. Furthermore, cylindrical bounding shell clipping technique is proposed to efficiently determine VII of a plane intersecting a surface of revolution.

4.1. Cylindrical bounding shell (CBS)

Bounding volume is an important technique for efficiently computing surface intersections. It can help do easy and fast intersection rejections. Two popular types of bounding volumes are bounding sphere and bounding box; [3] and [11] propose using bounding cylinder specifically for surfaces of revolution. In our method, we use cylindrical bounding shell (CBS) (see Fig. 7(a)) to enclose a surface of revolution both internally and externally by using the double bounding cylinders, with the maximum and minimum distances of generatrix to axis as the internal and external radii respectively. It is based on two considerations:

· It can enclose a surface of revolution more tightly than the traditional bounding box, bounding sphere, or a single bounding cylinder;

· Intersection determination of plane/cylinder (geometric method) is much easier to do than intersection determination of plane/revolute quadric, which can be further reduced to intersection determination of line/rectangle by projection along the cross product of the axial vector and normal vector of the cutting plane, which can be done by using only linear computations.

4.2. Valid intersection intervals (VII)

Valid intersection interval (VII) is defined as a set of axial Z-intervals, used to find out all the revolute quadrics for valid intersection computations. We only need to take intersection tests for these revolute quadrics. Cylindrical bounding shell and valid intersection intervals can combine together to make rough intersection detection as follows:

(a) (b) (c) (d) (e)

Fig. 7 Valid intersection intervals VII and cylindrical bounding shell of surfaces of revolution

· If a plane intersects the exterior bounding cylinder, then it may either intersect the surface of revolution or not, e.g. in Fig. 7(b), the red plane does not intersect surface of revolution, but the pink plane traverses the surface of revolution horizontally and produces a single VII (blue subintervals);

· Plane cuts both bottom or top circles and produces multiple VII, as shown in Fig. 7(c);

· If a plane intersects the interior bounding cylinder, then it definitely intersects the surface of revolution. If the plane cuts interior bounding cylinder at the top and bottom circles vertically as shown in Fig. 7(d), then the plane intersects all the subdivided RQs and VII contains all the Z-interval of generatrix;

· If a plane has no intersection with the exterior bounding cylinder as shown in Fig. 7(e), then the plane is impossible to intersect the surface of revolution and VII becomes an empty set.

4.3. Cylindrical bounding shell clipping

Determining VII plays an important role on efficient computing of plane sections of surfaces of revolution. However, computing VII exactly and directly is a non-trivial task due to the need of solving a high-degree polynomial equation with numerical solutions. Here, we propose a simple algorithm to approximate VII by refining the potential intersection intervals of plane and CBS recursively, it is noted as cylindrical bounding shell clipping; as a result, it becomes much easier to compute the VII of the plane and the bounding cylinder. A plane clipping a CBS may form three types of intersection intervals as follows:

_· Definite intersection intervals V_in

o Plane clips the interior bounding cylinder.

o Revolute quadrics within V_in intersect the plane definitely.

o Put it into VII.

· Null intersection intervals

·

· V_ex

·

o Plane clips the exterior bounding cylinder.

o The revolute quadrics within V_ex definitely do not intersect the plane.

· Potential intersection intervals

·

·

· V_po

·

·

· between V_ex and V_in

·

o The revolute quadrics within V_po may or may not intersect the cutting plane.

o It still needs further clipping CBS (recursive refinement).

Each clipping of CBS produces three kinds of intersection intervals by the plane clipping interior and exterior bounding cylinders respectively. The first round of clipping of the initial CBS CBS₀ rules out null intersection intervals V_ex1 and V_ex2, merges definite intersection interval V_in into VII, and produces potential intersection intervals V_po1 and V_po2. In the second round of clipping, we construct two new cylindrical bounding shells CBS₁₀ and CBS₁₁ for those revolute quadrics within two potential intersection intervals V_po1 and V_po2 and clip them respectively. Plane clipping CBS₁₀ produces a definite intersection interval V_in2 and a potential intersection interval V_po3. Plane clipping CBS₁₁ produces a definite intersection interval V_in3 and a potential intersection interval V_po4. Put two new definite intersection intervals V_in2 and V_in3 into VII. After the second CBS clipping, the union of three definite intersection intervals V_in1, V_in2 and V_in3 has approximated the real VII very well. The third round of CBS clipping can be done on the two new potential intersection intervals V_po3 and V_po4 recursively. So CBS clipping technique is a good way to estimate VII. The following algorithm1 sketches the above idea. We can end the recursive procedure of refinement if (i) the potential intervals cannot be shortened in the two consecutive refinements and (ii) the current potential (purple) intersection intervals only contain less than 3 revolute quadrics.

Fig 8. Two consecutive cylindrical bounding shell clippings for intersection searching

Algorithm 1. Computing the valid intersection intervals (VII) of a plane and a surface of revolution

Proc Search_PR_VII (plane, CBS₀)

Input: plane, CBS₀;

Output: valid intersection intervals VII (initially, it is set as nil );

Begin Proc

1 { I_exterior, I_interior, I_potential } = PlaneClipCBS(plane, CBS₀)

2 if I_interior is not empty

3 VII = VII + { I_interior };

4 end if;

5 if I_potential contains less than 2 RQs

6 VII = VII + { I_potential };

7 return VII;

8 else

9 locate all the RQs within I_potential;

10 if the number of RQs within I_potential decreases

11 form new cylindrical bounding shells CBS₁₀ and CBS₁₁;

12 Search_PR_VII(plane, CBS₁₀);

13 Search_PR_VII(plane, CBS₁₁);

14 else // CBS clipping cannot shrink I_potential

15 return VII;

16 end if;

17 end if;

End Proc.

5. Computing and tracing plane sections of surfaces of revolution

Basically, computing the intersection curves consists of three integral parts, (1) computing the intersection curves efficiently, (2) classifying the intersection curves topologically, and (3) representing the intersection curves rationally. Because our idea is to subdivide surfaces of revolution into a set of G¹ coaxial revolute quadrics along its generatrix, the intersection problem of surfaces of revolution is reduced to the intersection problem of revolute quadrics. For (1), we propose CBS clipping for VII and employ the fundamental geometric method in [19] to compute the plane sections of revolute quadric. For (2), we propose a simple algorithm of tracing the final intersection curves topologically as a group of independent branches and loops. For (3), the final intersection curves are composed of a group of G¹ conic arcs, which can be represented naturally as piecewise rational Bezier curves or NURBS curves, two standard forms in CAD/CAM systems. Detailed derivation can be found in [15].

How to detect the connected components and singular points of the intersection curves are important issues of boundary representation in solid modeling. This problem becomes relatively easier when tracing the intersection curves of plane and surfaces of revolution - it becomes how to connect those conic arcs into the closed loops and recognize the singular points during tracing. Here, we present a simple algorithm of tracing the intersection curves of a plane and a surface of revolution. Basically, there are three types of the trimming intersection curves (conic arcs) of a plane and a revolute quadric:

· Isolated point. It is a tangential point of a plane and a revolute quadric, in this case, the algorithm reports this point as a singular point.

· Double branch. In this case, a plane has two intersection points with each bounding circle respectively (top and bottom) for a truncated revolute quadric, the resulting intersection curve becomes a pair of symmetric conic arcs (elliptic, hyperbolic, parabolic, two separated line segments, two crossing line segments). We concatenate them at their coincident endpoints along the generatrix sequentially.

· Single branch. There are four cases: (i) a plane has intersection points with only one bounding circle (top or bottom circle), the resulting intersection curve is a trimming conic arc; (ii) a plane has intersection points with neither of the two bounding circles, the resulting intersection curve is a complete conic section, which itself is a closed loop; (iii), a plane has two intersection points with one bounding circle and one intersection (tangential) point with the other bounding circle. Such single branch begins or ends a closed loop during tracing; finally, (iv) when a revolute quadric is a truncated cone, its planar section is a single line segment, which is a degenerated case of a double-branch and can be treated as a double-branch during tracing.

The following algorithm outlines the rough idea of tracing these conic arcs piece by piece along the spine curve sequentially, by checking coincidence of endpoints of two adjacent conic arcs, and then concatenating them into a set of connected components one by one.

Algorithm 2. Tracing plane sections of surface of revolution

Proc. Tracing_Sect_RS(plane,RS)

Input: a list of conic arcs CS_i (i=1,2, …, n) ;

Output: a list of branches PB, (PB_j, j=1,2, …, m);

Begin Proc

1. j = 1;

2. for i = 1 to m

3. if PB_j is empty

4. insert CS_i into the current component PB_j;

5. if CS_i is a complete conic section

6. close the current component PC_j;

7. j++;

8. end if;

9. if CS_i is an isolated point

10. close the current component PC_j;

11. j++;

12. identify it as the singular point;

13. end if;

14. else

15. if CS_i is a single or double-touch to current PC_j

16. concatenate it into the current branch PC_j;

17. close the current branch PC_j;

18. j++;

19. else

20. concatenate it into the current branch PC_j;

21. end if;

22. end if;

23. end for;

End Proc.

6. Implemented examples

We have implemented the presented revolute quadric decomposition idea and the intersection algorithm and three examples are given here to testify the robustness and efficiency of our algorithm. The first example is a pair of symmetric open branches by a plane intersecting a dumbbell as shown in Fig. 9. The second example is two closed loops by a plane intersecting a bottle as shown in Fig. 10. The third example is three branches by a plane intersecting a chalice as shown in Fig. 11, among them, two are closed loops and one is an open branch. For comparison purpose, we also implemented plane sections of surface of revolution based on truncated cone decomposition.

(1)

(2)

Fig 9. The Intersection curve of two open branches

(1)

(2)

Fig 10. The two-loop intersection curves

(1)

(2)

Fig 11. The intersection curves with one open branch and two loops

Table 2. Comparison on truncated cone and revolute quadric decomposition at tolerance 10^-4

Examples	Truncated cone decomposition		Revolute quadric decomposition
	Consumed memory	Computing time (s)	Consumed memory	Computing time (s)
Dumbbell	420 KB	0.107s	63.7 KB	0.039s
Bottle	436 KB	0.125s	72.2 KB	0.059s
Chalice	1.2 MB	0.455s	258KB	0.23s

Table 3. Comparison on the intersection algorithms based on truncated cone and revolute quadric decomposition at the tolerance 10^-4

Examples	Truncated cone decomposition		Revolute quadric decomposition
	# of fitting conic arcs	Intersection time	# of fitting conic arcs	Intersection time
Dumbbell	41	0.00032s	14	0.0000014s
Bottle	(13, 9)	0.005s	(4, 4)	0.00062s
chalice	(66, 10, 27)	0.04s	(27, 6, 13)	0.01s

From the performance data given in Table 2, the revolute quadric decomposition based algorithm outperforms truncated cone decomposition based algorithm in terms of both the CPU time and consumed memory. The tighter the tolerance, the larger difference in both computing time and consumed memory. Also, Table 3 shows that, in the computing time and total number of conic arcs of the intersection curves of a plane and a surface of revolution, revolute quadric decomposition based algorithm outperforms greatly truncated cone decomposition based algorithm. Assuming that the total fitting components is N, both the computing time and memory cost for decompositions are O(N). But, for intersections, the computing time and memory cost is only O(logN) on average, with the help from CBS clipping. It is noted that the decomposition time is much more than the intersection time; however, since the decomposition belongs to preprocessing stage, it is executed only once, while the intersection operations are performed frequently and recurrently.

7. Conclusion

Quadric decomposition brings a new perspective to solving surface intersection problem. It reduces surface intersection problem to quadric intersection problems. In this paper, we revisit the problem of plane intersecting surfaces of revolution by proposing using revolute quadric decomposition for approximating surface of revolution. Implementation results show that revolute quadric decomposition outperforms truncated cone decomposition greatly in terms of the computing time, consumed memory, and total number of the required conic arcs. It also is more convenient to represent the intersection curves rationally and much easier to trace the intersection curves for identifying the closed loops and singular points than the Kim’s method [13]. Since we employ a fundamental geometric method [19] to compute plane sections of revolute quadrics which is robust, efficient and accurate, so is our algorithm. Its accuracy can be specified by the precision of quadric subdivision of surface of revolution in advance. The other contributions are cylindrical bounding shell and plane clipping CBS technique which are proposed for valid intersection interval detection.

The presented method of globally fitting a surface of revolution by revolute quadrics is just a sub-optimal method, developing a true optimal method becomes our future work. Quadric decomposition also can be applied to computing the intersection problem of two surfaces of revolution and other geometric computing problems of surfaces of revolution, e.g. isophot, bisector, distance computing and so on.

8. References

[1] Baciu G., Kwok K. W. and Jia J. Y., “An efficient method of computing planar sections of surfaces of revolution”, Proceedings of CAD & CG, pp. 111-119, Academic Publisher, Kunming, China, 2001.

[2] Bangert, C. and Prautzsch, H., “Quadric spline”, CAGD, 16(6), pp. 497-515, 1999.

[3] Burger P. and Gillies D., “Rapid Ray Tracing of General Surfaces of Revolution”, New Advances in Computer Graphics, Proceedings of CGI’89, Springer-Verlag Press, 1989.

[4] Dahmen W., “Smooth piecewise quadric surfaces”, Mathematical methods in computer aided geometric design, edited by Lyche T. and Schumaker, L., Academic Press, pp. 181-194, 1989.

[5] Froumentin M. and Chaillou C., “Quadric surfaces: a survey with new results”, The Mathematics of Surfaces VII, pp. 363-381, Edited by Tim Goodman and Ralph Martin, 1997.

[6] FU Q. X., “The intersection of a bicubic Bezier patch and a plane”, Computer Aided Geometric Design, 7(6), pp. 475-488, 1990.

[7] Golub G. H., Loan C. F., “Matrix computations”, Johns Hopkins University Press, Edition 3, Baltimore, 1996.

[8] Goldman R. N., “Intersection of parametric surface and a plane”, IEEE Computer Graphics & Applications, 4 (8), pp. 48-51, 1984.

[9] Guo B., “Quadric and cubic bitetrahedral patches”, The Visual Computer, Vol. 7, pp. 253-262, 1991.

[10] Guo B., “Representation of arbitrary shapes using implicit quadrics”, The Visual Computer, Vol. 9, pp. 267-277, 1993.

[11] Jia J., “Rapid Ray Tracing Surfaces of Revolution”, Master Thesis of Jilin University, China, 1991.

[12] Johnstone J. K. and Shene C. K., “Computing the intersection of a plane and a natural quadric”, Computers & Graphics, 16 (2), pp. 179-186, 1992.

[13] Kim K. J., Kim M. S., and Martin R., ”Intersecting a translationally or rotationally swept surface with a plane of a sphere”, Proceeding of Korea-Israel Bi-National Conference on Geometric Modeling and Computer Graphics, pp. 165-193, Seoul, Korea, September 30 - October 1, 1999.

[14] Kim M. S., “Intersecting surfaces of special types”, Proceeding of Shape Modeling and Processing 99, pp.122-128, Univ. of Aizu, Japan, March 1999.

[15] Kwok K. W., “Efficient computing intersection curves of surfaces of revolution”, Master of Philosophy Thesis, Department of Computer Science, HKUST, May, 2001.

[16] Miller J. R. and Goldman R. N., “Using tangent ball to find plane sections of natural quadrics”, IEEE Computer Graphics & Applications, 12(2), pp 68-82, 1992.

[17] Patrikalakis N. and Maekawa T., “Intersection Problem”, Handbook of Computer Aided Geometric Design, Farin G., Hoschek J. and Kim M. S. (Eds.), Elsevier, Amsterdam, 2001.

[18] Powell, M. J. D. and Sabin M. A., “Piecewise quadratic approximations on triangles”, ACM Transaction on Mathematical Software, Vol. 3, pp. 316-325, 1977

[19] Shene C. K. and Johnstone J. K., “Computing the intersection of a plane and a revolute quadric”, Computers & Graphics, 18 (1), pp. 47-60, 1994.

[20] Zheng J. L. and Millham C. B., “A linear pivoting method for detecting and tracing planar section curves of free form surfaces”, Computer & Graphics, 16(4), pp. 411-420, 1992.