GEOMETRIC MODELING USING POINT CLOUDS 303Also, the point cloud for a prismatic object is different from that of a free form object and so the
aforementioned treatment would be different for the two point clouds.
10.6.1 Segmentation and Surface Fitting for Prismatic Objects
There are two different methods, edge-based and face-based, for segmentation and surface fitting of
prismatic surfaces. In edge-based methods, we try to determine possible patches by determining their
boundaries, and later patches are inferred from the implicit segmentation provided by these boundary
curves. Sharp edges are locations where the first difference (derivative) estimated from the point
cloud changes rapidly, for example, two intersecting orthogonal planes. For smooth edges on the
other hand, we look for sites where the second difference (surface curvature) has discontinuity.
A procedure to estimate curvature from a point set may be as follows. For each point in the set, a
local neighborhood is defined based on a limiting distance. Then a local quadratic surface is fit using
least square minimization. A quadratic surface in algebraic form is given by
f(x,y,z) = a 1 x^2 + a 2 y^2 + a 3 z^2 + a 4 xy + a 5 xz + a 6 yz + a 7 x + a 8 y + a 9 z + a 10 = 0 (10.1)The surface curvatures (principle curvatures) and the slope directions can be computed from this
locally approximated surface. By inspecting the magnitude (very large) of the principle curvatures,
or the change in their sign, we may identify edge points. After all the edge points are determined from
the point cloud, they are linked to form the closed boundaries.
In the segmentation stage, to partition the digitized points to regions, all points are tested for
belonging to each boundary loops using the scan line algorithm (Chapter 9) as shown in Figure 10.10
with an example point cloud showing one quarter of a cylinder in the first quadrant (Figure 10.10a).
Cloud curvature can be estimated and the points are identified where curvature extremes occur as
shown in Figure 10.10 (b). The detected edge points and the boundary loops joining them are shown
in Figure 10.10 (c).
(a) (b) (c)Figure 10.10 Edge detection using cloud curvature: (a) point cloud of an object, (b) edge points on the
cloud are colored; identified (darkened) on curvature estimation from points and (c) the
edge loop detected
The edge-based methods have the following limitations.
(a) Sensor data, particularly from optical scanners, are often unreliable near sharp edges.