Local Geometric Modeling Topics Part 2

Generating Discrete Geodesics

The last section dealt with smooth geodesics and had to do with smooth curves lying in smooth surfaces. What if our surface is not smooth but polygonal? See [KSHS03] for a discussion of two algorithms that generate discrete geodesics given a start point and a start direction. It is obvious how to proceed here except in the case where the geodesic passes through a vertex (we preserve angles when crossing edges just like in the plane). The decision made at a vertex is especially critical if the surface came from a tessellation of a smooth surface and we are trying to approximate a smooth geodesic. One needs to take into account the discrete curvature at the point that could be defined in terms of the sum of angles around the point or the normals to the faces that meet at the point.

In this section we discuss the other and much harder variant of the geodesic problem where we are given two endpoints and we want to find the locally shortest polygonal curves connecting the two points. Before establishing that this is a meaningful question and getting to the main results, we need to introduce some terminology. In particular, we pause to make the definition of a polygonal curve (to be called a piecewise linear curve) more precise. It is hoped that the reader will not despair because of the rather large number of detailed definitions of what may seem like obvious terms, but that is the cross that one has to bear when one tries to be unambiguous. The requirement that piecewise linear curves are defined by a sequence of at least two points is motivated by the fact that other definitions are then less complicated.

Definition. A piecewise linear curve or pwl curve p in Rn is a sequence

of points ofThe length of p, Length(p), is defined using the standard Euclidean metric by

The curve p is said to be closed if The  path  or underlying  space  of    p,    |p|, is

defined by

 

Ifthen    we    say    that    p    is    a    pwl    curve    in    X. The pwl curve p is said to be simple if

(1) all the pointsexcept possibly the first and last, are distinct, and

(2)    no segmentsintersect    unless

(a)in which case they intersect in the pointor

(b)    the curve is closed, i = 0, and j = k – 1, in which case they intersect in the point

Ifthen the pwl curveis    called    an    elementary

subdivision of the pwl curve p and a proper elementary subdivision if q lies in the interior of the segmentA    pwl curve that is obtained from p by a sequence of (proper) elementary subdivisions is called a (proper) subdivision of p.

If we think of pwl curves as defining a path that one walks along, then in the case of a simple pwl curve there is no backtracking or self-intersection. In particular, a simple pwl curve traces out a one-dimensional manifold. (See Lemma 15.3.2.1 below.) Clearly, proper subdivisions of simple curves are again simple.

It is easy to parameterize the path of a pwl curve.

Definition.

be a pwl curve and let

be the standard linear map that, using barycentric coordinates, has the form

The map

where

is called the standard parameterization of the pwl curve p. If s,then define a pwl curve q, called the pwl curve induced by [s,t] with respect to the standard parameterization, as follows:

Lemma. Letbe  a pwl  curve and  p    its   standard parameterization.

 

(1)    The map p is continuous.

(2)    If p is simple, then p|(0,1) is a homeomorphism between (0,1) and |p| – {p0,pkl· If p is simple and not closed, then p is a homeomorphism between [0,1] and |p|.

Proof. Easy.

Definition. Let p be a pwl curve and p its standard parameterization. Let p and q be two points in the path of p. Choose s and t, so that s < t, p = p(s), and q = p(t). The set p([s,t]) is called the part of the path of p from p to q.

The part of a path of a pwl curve is not well-defined in general because there may be many choices for the parameters s and t (the curve may backtrack on itself, for example). However, for simple curves it is well-defined unless the curve is closed and one of the points is the first or last point of the curve.

After these preliminary definitions, we come to the first basic fact about shortest curves, namely, that they exist.

Theorem. Let S be a connected compact polygonal surface.

(1)    Any two points of S can be connected by a shortest pwl curve, meaning that any other pwl curve between the points will have a length that is larger than or equal to the length of that curve. In fact, a shortest pwl curve between two points will have length less than or equal to the length of any rectifiable curve between those two points, not just pwl curves.

(2)    Every shortest pwl curve between two points of S is a simple curve but there may be more than one shortest curve between two points.

(3)    There is a δ > 0, so that, for any two points p and q in S with |pq| < δ, there is a unique shortest pwl curve from p to q.

Proof. By cutting along edges one can flatten the whole surface out in the plane, so that one can study curves on the surface by studying curves in planar polygons. It is a well-known fact that the shortest parametric curve between two points in the plane traces out the segment between the points.

Just like in the smooth case, shortest pwl curves are a special case of a more general type of pwl curve.

Definition. A pwl curve p in a polygonal surface S is called a discrete geodesic if it is locally the shortest pwl curve. More precisely, there is a δ > 0, so that, for any s, t e [0,1], s < t, with |s – t| < δ, the pwl curve induced by [s,t] with respect to the standard parameterization p of p is a shortest pwl curve between p(s) and p(t).

Intuitively, a discrete geodesic has the property that if two points p and q in its path are sufficiently close, then the part of the path from p to q is the path of a shortest pwl curve from p to q. Just like in the smooth case, geodesics are not necessarily the shortest curves between points. For example, on a cube a geodesic between two points may pass those points more than once as it wraps around the cube multiple times. On the other hand, it is obvious that every shortest pwl curve is a discrete geodesic.

The discrete geodesic problem: Given two points p and q on a polygonal surface S, find a shortest pwl curve in S from p to q.

In the rest of this section we shall assume the following:

(1)    All surfaces S will be compact, connected, triangulated, and without boundary.

(2)    All pwl curves in a surface S will have the property that if they meet a vertex of S, then that vertex is a vertex for the curve.

(3)    All pwl curves are assumed to be simple. All subdivisions will be proper.

Surfaces are assumed to be triangulated because triangular faces simplify arguments. Fortunately, a polygon with v vertices and no holes or self-intersections can always be triangulated in time O(v) (see Section 17.6). Furthermore, if a surface has e edges, then it will have O(e) edges after triangulation. However, there is one point that needs to be kept in mind with respect to the triangulation hypothesis. The number of faces may have increased substantially. Therefore, if the big-O complexity of an algorithm depends on the number of faces, then the triangulation has to be taken into account.

Surfaces are not allowed to have a boundary because, like in the last section, the boundary would cause problems that will not be addressed here. A typical surface would therefore be the surface of a polyhedron in R3. The assumption about pwl curves being simple is justified by the fact that our goal is to find shortest curves and these are all simple. Finally, note that subdividing either a curve or the surface has no effect on the length of the curves or the geodesics in the surface.

The O(n2) solution to the discrete geodesic problem for polygonal surfaces with n edges presented by Chen and Han in [CheH90] is too complicated to describe in its entirety here, but we shall sketch the main steps for the convex case. Whether or not a surface is convex has a great influence on the complexity of a shortest curve algorithm. When a surface is not convex, one has to handle some complicating special cases although the basic idea is the same as in the convex case.

The specific shortest path problem that we address is the “single source” shortest path problem, namely, we seek an algorithm for finding a shortest pwl curve from a fixed “start” point s of the surface S to all other points of S. We shall assume that s is a vertex of the triangulation of S. The Chen and Han algorithm is actually not the most efficient solution to the problem. Kapoor ([Kapo99]) has described an O(nlog2 n) algorithm, but it is more complicated to describe. A number of other papers prepared the ground for these algorithms. In particular, [MiMP87] is worthwhile reading because it helps one see what the problems are when one is looking for shortest paths. Other references can be found in that paper and in [CheH90]. The solution in [MiMP87], which is not as efficient, is based on an argument that is similar to Dijkstra’s single-source shortest path algorithm for graphs.

Definition. Two faces of S are edge-adjacent if they meet in a common edge. An edge-adjacent sequence of faces is a sequence F = (f1,f2, . . . ,fk) of faces £ with f edge-adjacent to fj+1. If ej is the common edge of £ and fj+1, then the sequence E = (e1,e2, . . . ,ek-1) is called the edge sequence defined by the sequence F. The sequences F or E are said to be simple if no face or edge, respectively, appears more than once in the sequence. Let qi be a point in the interior of the edge ej. The pwl curve q = (q1,q2, . . . ,qk-1) is said to connect the edge sequence E. A pwl curve q in S of the form (qo,q1,q2, . . . ,qk-1,qk), where qo and qk are arbitrary points in f1 and fk, respectively, is said to define the edge sequence E.

Figure 15.3. An edge-adjacent sequence of faces.

Figure 15.4. Unfolding a curve.

Figure 15.3 shows an edge-adjacent sequence of faces for k = 6 and its associated edge sequence. Given an edge adjacent sequence of faces,    it is clear that

such a sequence can be “unfolded” into the plane determined by the last face. One simply successively rotates the plane of fi about ei into the plane of k – 1, so that the image of fj under this rotation R; of R3 and fi+1 lie on opposite sides of the edge ei. Define motions M; by

and define a map

by.    The    triangle  f[ is just the image in the plane of fk of the face fi under this “unfolding.” See Figure 15.4.

Definition. The sequence of trianglesIf X is any subset of the union of the facesthen the set v(X) is called the unfolding of X and the map

v is called the unfolding map with respect to the sequence

In Figure 15.4, the pwl curve (A,B,C,D) unfolds to (A’,B/,C’,D/). The unfolding map v is clearly one-to-one on each face fi but may not be globally one-to-one because the faces may wrap around each other. The next two lemmas state some interesting properties of geodesics and their unfoldings.

Lemma. A geodesic pwl curve that connects the edge sequence of an edge-adjacent sequence of faces unfolds to a straight line with respect to that sequence.

Figure 15.5. Shortest curves on nonconvex surfaces.

Figure 15.6. The angle at a vertex.

Proof. See [MiMP87]. The fact that the curve intersects the edges in the edge sequence in their interior is needed here.

If our surface is convex, then one can show that, except for possibly its first and last point, a discrete geodesic will not go through any vertices of the surface. Unfortunately, things get more complicated in the nonconvex case. See Figure 15.5. However, a discrete geodesic that passes through a vertex has to satisfy an interesting geometric condition there.

Definition. The angle of a face at one of its vertices v is the angle between the two edges of the face that meet in v.

Suppose that a simple pwl curve goes through a vertex v. Let e and e’ be the two distinct adjacent edges of the curve that meet in v. By momentarily dividing a face into two, if necessary, we may assume that both e and e’ lie in edges of faces that meet in v. Clearly, we can now divide the faces that meet in v into two edge-adjacent sequences whose first and last faces meet in edges containing e and e’. For each of these two sequences add up the angles of their faces at v.

Definition. The smaller of the two sums is called the angle that the curve makes at v.

In Figure 15.6, Θ is the angle of the curve at v. The reader should not assume that the faces adjacent to a vertex can be flattened out in the plane. Figure 15.5(a) shows an example where this would not be possible.

Figure 15.7. Regions with the same edge sequence.

Figure 15.8. Impossible and possible edge sequences for shortest curves.

Lemma

(1)    A discrete geodesic is a curve that alternates between vertices and (possibly empty) edge sequences such that the unfolded path along any edge sequence is a straight line segment. If the curve passes through any surface vertex, then the angle that the curve makes at that vertex is greater than or equal to p.

(2)    If a discrete geodesic between two points is actually the shortest curve between those points, then no edge can appear in more than one edge sequence and each edge sequence must be simple.

Proof. See [MiMP87]. Figure 15.5(b) shows how a sequence of vertices could be part of a geodesic.

The basic idea that will lead to our main theorem (Theorem 15.3.2.6) is to divide the surface into regions, so that the shortest pwl curves from the start point s to all the points within a region define the same edge sequence. See the shaded region in Figure 15.7.

Definition. If p is a shortest pwl curve from s to a point p that defines an edge sequence, then that edge sequence will be called a shortest edge sequence for p.

Not every edge sequences is a shortest edge sequence. For example, if we are dealing with a convex surface in Figure 15.8(a), then the unfolded edge sequence e1, e2, e3, e4, e5 cannot possibly come from a shortest edge sequence. (It could be without the hypothesis of convexity as one can see from Figure 15.5(b).) In the next stage of our discussion we shall assume that surfaces are convex. The following facts hold in that case:

Lemma. Assume that S is a convex surface with n faces.

(1)   A shortest path cannot traverse more than n faces.

(2)   Two shortest paths from the start point s can only intersect in s and their endpoint.

We now look for a criterion that rejects edge-adjacent sequences of faces that cannot possibly come from a shortest curve.

Definition. Given a point p and a set X, define infCone(p,X), the infinite cone on X from p, by

Definition. Given a point p and sets X and Y, define proj(p,X,Y), the projection of X on Y from p, by

Now letbe  an  edge-adjacent sequence  of  faces  in  S with

associated edge sequenceand    unfolding    map    vk. Recall that vk maps all faces fi into the plane ofAssume that the start point s is the vertex of f1 opposite the edgeLetbe    the    unfolding    of    s    and    ei with respect to vk, respectively.

Definition. Define the subsetsrecursively    as    follows:

Call projs,i a shadow of the start point s on edge ei. We shall calla face shadowed by the edge ei with respect to the sequence F;.

Figure 15.8(b) shows what the shadow projs5 would look like. Because our surface is convex, we could stop our edge-adjacent sequence of faces at that point since e6 cannot belong to a shortest edge sequence. In fact, projs,6 would be the empty set. Basically, projs,i defines a cone from s in which all shortest paths with edge sequence (e1,e2,e3,e4,e5) would have to lie. The algorithm for finding shortest paths for convex surfaces uses these shadows to control the search that one has to perform. Algorithm 15.3.2.1 is an outline of an algorithm for finding shortest edge sequences. One builds a tree whose nodes, other than the root, consist of quadruples of the form where e is an edge of the face f in the surface S, p is a point in the plane of f that is an unfolding of s, that is, p = v(s) where v is an unfolding map to the plane of f, and is a subset of e that is a shadow of s.

Note that a face can be shadowed by each of its three edges.

Definition. The setis    called    the shadow of s in N.

Algorithm 15.3.2.1. A convex surface edge sequence algorithm.

The tree built by Algorithm 15.3.2.1 is called the edge sequence tree for S with respect to the start point s. The reason for the name is that every path from the root to a node in the tree defines an edge sequence for geodesics from s to a point p in the node’s shadow of s. These geodesics are not necessarily shortest paths but there is a unique geodesic with that edge sequence from s to every point in the node’s shadow of s. To find the shortest path from s to an arbitrary point p in S one would first find all the nodes N in the tree, so that p is in the shadow of s in N. These nodes would define unique geodesics to p. We would simply select the shortest of those and that would be the shortest path from s to p.

We now have a correct algorithm for finding shortest paths. The only problem is that the edge sequence tree might be exponential in size. Figure 15.9(a) shows how shadows can cover angles opposite an edge and this would give rise to two children to a node.

Figure 15.9. Limiting the number of children of a node.

However, our task was to find shortest paths and not all geodesics. Because of this it turns out that the initial edge sequence tree can be pruned. The key observation is that at most one node whose shadows cover the angle needs to be given two children if one is only looking for shortest paths. See Figure 15.9(b). In the figure nodes N1 and N2 with the same edge BC gave rise to unfolded start points p1 and p2 with respect to face ABC. If |p1A| < |p2A|, then the shorter paths to s from points on edges AB and AC sufficiently close to A come from the edge sequence defined by N1. This means that only N1 needs to be given two children. If |p1A| = |p2A|, then both N1 and N2 need only one child. Using this “one angle, one split” criterion leads to a new edge sequence tree generation algorithm that produces a tree with O(n) leaves at each stage. One can reduce the total space used to O(n) by the following trick: if a leaf in the current tree generates only one child, we delete that node and replace it with the child. One can also show that the new tree can be generated in time O(n2). Once the tree is built, one can find shortest paths in time O(n). To do better, one needs to make some more improvements.

It turns out that the essential information one needs to store is the shortest paths to vertices. Therefore, the authors in [CheH90] create additional “vertex nodes” while they build the edge sequence tree. This can also be done using O(n) space and, given the nature of the tree, one can now find the shortest path to a vertex in time O(k), where k is the number of edges in the path.

Now the edge sequence tree certainly has to be built once. This takes time O(n2). However, after that, what slows down answering shortest path queries to O(n) is finding path information in the tree. By storing that information more efficiently one can speed up multiple queries. An appropriate Voronoi diagram and the subdivision it induces on the surface turns out to do the trick.

First, one cuts the surface along the shortest paths to its vertices. The cut surface can be flattened out into the plane (there may be overlaps). The authors in [CheH90] call the layout one gets the inward layout to distinguish it from the one used in [ShaS86]. The start point s will map to O(n) vertices s(. A Voronoi diagram is built with respect to these image points in the plane and this induces a subdivision of the layout with the property that points that belong to the same region, say the one associated to si, are closer to sj than to any other sj, i π j, and their shortest paths have the same edge sequence. This leaves the question of the complexity of building the Voronoi diagram. Lemma 15.3.2.5(2) implies that all vertices other than the start point can be listed in a circular order based on the angle that a shortest path to that vertex makes with a fixed line at the start point. Using such an order, connect the flattened vertices by edges in the order in which they are listed. This generates a circular loop called the equator that cuts the flattened surface into two regions called the arctic region (the one containing the start point) and the antarctic region. One can show that the Voronoi diagram is a tree with O(n) edges. Therefore, it can be built in time O(nlogn) and space O(n). The subdivision of the surface induced by the subdivision of the layout can be built in time O(n2).

This completes the sketch of how one finds shortest paths in convex surfaces. If the surface is not convex, the steps in the algorithm have to be modified but fortunately the complexity of the steps does not change in the end. The final result for surfaces, convex or not, is stated below.

Theorem. Let S be an arbitrary polygonal surface with n edges and let p be a fixed point on S. After a preprocessing time of O(n2) and using space O(n2), the Chen and Han algorithm answers any query about the shortest distance from a point q on S to p in time O(logn) and the shortest path from p to q can be generated in time O(k + logn), where k is the number of edges intersected by the path. 

The Chen and Han algorithm improved on the one in [MiMP87], which was an O(n2logn) algorithm, but it and the better O(nlog2n) Kapoor algorithm are too complicated and slow to be practical if one wants accurate answers since one would have to represent computations with a number of bits that is an exponential function of the number of bits in the coordinates of a vertex. For that reason, algorithms have been developed that only give an approximate answer but which are much more efficient. See, for example, the paper by Agarwal et al. ([AgHK00]).