Graphics Reference
In-Depth Information
4. DIFFERENTIAL GEOMETRY AND SHAPE ANALYSIS
the network also the connections between vertices that belong to two adjacent triangles and are
opposite with respect to an edge.
Another popular method to solve the single source shortest path problem is the fast march-
ing method [
175
,
176
]. e approach proceeds by solving a discretized version of the Eikonal
equation over a regular grid. e Eikonal equation is a partial differential equation measuring
the first arrival time of a wavefront propagated over the grid, we refer to [
5
] for details. e fast
marching method was extended to triangulated surfaces [
115
], parametric surfaces [
189
], and
regularly sampled parametric surfaces [
210
].
²
4.1.2 CONCEPTS IN ACTION
Geodesic analysis of 3D shapes
e geodesic distance is used to solve many problems of practical
interest such as segmentations using geodesic balls and Voronoi regions, sampling points at regular
geodesic distance or meshing a domain with geodesic Delaunay triangles; for a comprehensive
review we refer to [
29
,
162
]. Among the others, we sketch here the use of the geodesic distance
to derive an intrinsic shape measure.
In general, the geodesic distance between two points can be generalized to the distance from
a point
p
to a set of points
UX
by computing the distance from
p
to its closest point in
X
,
which defines the distance map:
g
X
.p/Dmin
q2X
d
g
.p;q/
, where
d
g
.p;q/
denotes the geodesic
distance between the points
p
and
q
. Being
g
X
defined as a minimum of geodesic distances, this
function is neither differentiable nor smooth and therefore most of the differential geometry tools
are not longer valid.
To be independent of the choice of base points, Hilaga et al. [
102
] introduced the average
of the geodesic distance of the point from all points as an integral function. is assumption
guarantees that the resulting measure is intrinsic. More formally, the value of the function
f
is
given by:
Z
f.p/D
d
g
.p;q/dX
q2X
where
q
varies on
X
.
is function is not invariant to scaling of the object and, in case the space
X
is represented
as a triangulation, it is replaced by its normalized representation defined as:
X
f.p/D
d
g
.p;b
i
/area.b
i
/
i
where
b
i
Db
0
;:::;b
k
are the base vertices for the computation of the geodesic distance which
are scattered almost equally on the surface and
area.b
i
/
is the area of the neighborhood of
b
i
.
e resulting function is theoretically invariant with respect to rotation, translation and
uniform scaling. Figure
4.2
shows the average geodesic distance for three 3D shapes. Besides
²We refer the website of the Numerical Tour Toolbox for Matlab and Scilab:
https://www.ceremade.dauphine.fr/~pe
yre/numerical-tour/
for examples and routines of algorithms for the computation of the shortest path.
Search WWH ::
Custom Search