MPhil Thesis Defence


"Efficient Algorithms for Intersections of Surfaces of Revolution"

By

Mr. Ki-Wan Kwok


Abstract

Surfaces of revolution belong to an important class of geometric models
with simpler shape characteristics and useful geometric properties. In CAD
and geometric modeling systems, solid models are often composed of planes
and surfaces of revolution. Thus, it is important to develop efficient
algorithms on planes intersecting surface of revolution and intersection
between two surfaces of revolution. Despite its importance, there seems to
be a lack of reported work in this area.

In this thesis, we propose an efficient algorithm to compute planar
section of a surface of revolution and an algorithm to compute
intersection between two surfaces of revolution. These algorithms first
subdivide the surface of revolution into a series of consecutive coaxial
truncated cones or revolute quadrics according to a user supplied error
bound. Thus, the problem is reduced to finding intersections on truncated
cones or revolute quadrics.

Our planar section algorithm detects intervals of consecutive truncated
cones or revolute quadrics that contain non-empty intersections using a
bounding volume tree. Then, it finds planar sections of each resulting
truncated cone or revolute quadric that would intersect the plane. Finally
joining them together into complete intersection curves. Our
representation of complete intersection curves facilitates 2D operations
on the intersection plane and generates 3D points quickly on demand.

Our intersecting algorithms detect intervals of consecutive truncated
cones that contain non-empty intersections using binary searching. Then
for each truncated cone T_{1i} within the valid intersection interval of
the first revolution surface, we find the intersection curves S_{ij}
between T_{1i} and all truncated cones T_{1j} within the valid
intersection interval of the other revolution surface. Finally, we join
all S_{ij} together into a complete curve representation which generates
3D points quickly on demand.


Date:			Monday, 20 August 2001

Time:			10:00a.m.-12:00noon

Venue:			Room 4334
			Lift 3

Committee Members:		Dr. George Baciu (Supervisor)
			Dr. Wilfred Ng (Chairman)
			Prof. Maria Orlowska


**** ALL are Welcome ****