Image Processing Reference
In-Depth Information
6.6.2 The Algorithm
For computing the cross-sections of 3-D objects with a given plane P, the
objects are rotated in such a way that the normal of the plane is aligned
with the z-axis of the coordinate space. For applying this transformation to
a 3-D object represented by MAT, computation is carried out only with the
vertices of its medial spheres. Next, the intersection points between edges of
a medial sphere and the cross-sectional plane (i.e., the plane whose normal is
now along the z-axis) are obtained. Finally, the intersecting convex polygon
is constructed by angularly sorting these points. We may use another data
structure for representing a polyhedra (such as a doubly connected edge list
(DCEL) [169]) for computing the vertices of a convex polygon by a linear scan
(of the number of faces and edges of the polyhedra). However, as the number
of edges are small and constant for an individual MAT representation, the cost
due to sorting could be taken as constant. The algorithm for the computation
of an intersection of a digital sphere with a plane is described below.
Algorithm 14: Computation of Cross-Sections of 3-D Objects
Algorithm: Cross Sectioning Using MAT (CSUM)
Input: The MAT M of an object, the digital distance function used in
computing M, and a Plane P.
Output: A Convex polygon
1. For each medial sphere s ∈ M with its center as o
s
and radius as r
s
,
compute the following:
1a. Compute the edges and the vertices of s in the 3-D coordinate
system.
1b. Apply the transformation to the vertices of the polyhedron so
that the cross-sectional plane P lies along the xy plane.
1c. For each edge, compute the intersection point with xy (z = 0)
plane.
1d. Perform angular sorting of the intersection points about their
centroid. The sequence provides the vertex sequence of the convex
polygon
End Cross Sectioning Using MAT (CSUM)
Since the intersection of a plane and a convex polytope is a convex polygon,
in Step 1d of the above algorithm, it is su
cient to sort the intersecting points
by their angles formed at their centroid with any arbitrary reference axis. This
computational step is a special case of Graham's convex hull computation
[169]. As a medial sphere is represented in the continuous domain (as a convex
polyhedra), the intersecting polygon also represents an area in the continuous
