测地线算法综述：复杂几何处理的关键技术

需积分: 18 73 浏览量更新于2024-06-30 1 收藏 39.8MB PDF 举报

测地线路径和距离算法综述是一篇针对三维模型中复杂几何问题的研究文章，它探讨了在曲率显著影响下，如何在数字几何处理、科学计算、计算机图形学和计算机视觉等领域进行精确的测地线（即曲线域上最短路径）数值计算以及相关的测地线距离。相比于传统的欧氏距离计算，这些问题的求解更具挑战性，因为曲率的存在会导致最短路径的行为变得难以预测，并且在实际应用中，目标领域的表示往往不是精确的，而是基于近似模型构建。文章指出，尽管面临困难，近年来的研究者们已经开发出了众多先进的算法，使得即使在相对大型的模型上也能实现快速的测地线信息查询。这些方法主要分为几个关键类别： 1. 网格方法：通过将曲面划分为多边形网格，然后在每个网格区域内近似计算局部的测地线路径。这种方法的优点是易于实现，但可能牺牲精度，尤其是在复杂曲率区域。 2. 有限元方法：利用有限元素理论将连续的曲面离散为多个节点，通过解决相应的偏微分方程来找到局部测地线。这种方法提供更精确的结果，但计算成本通常较高。 3. 局部逼近与优化：基于局部特征，如切向量和曲率，采用迭代优化技术寻找最佳路径。这类方法能够在一定程度上保持精度，同时减少全局搜索的复杂性。 4. 数据结构与搜索算法：例如A*搜索算法或者Dijkstra算法的变形，结合启发式信息，可以在大规模空间中高效找到近似测地线路径。这类方法适合实时应用，但可能存在一定的误差。 5. 概率方法：利用随机过程，如布朗运动或随机游走，来模拟测地线行为。虽然可能得到非确定性的结果，但在某些情况下，它们能够提供有用的近似。 6. 深度学习与机器学习：近年来，这些技术也被用于学习测地线路径和距离的模型，通过训练神经网络，可以从大量数据中自动捕捉复杂关系，适用于大数据集和高维度场景。总结来说，测地线路径和距离算法的研究是当前计算机图形学和计算机辅助设计中的一个重要课题，不断有新的思想和技术涌现，以满足日益增长的应用需求。本文通过对各种方法的深入分析，不仅概述了现有成果，还揭示了未来可能的研究方向和挑战。

K. Crane, M. Livesu, E. Puppo, Y. Qin / A Survey of Algorithms for Geodesic Paths and Distances

For each vertex i 2 V, the angle defect is the quantity

:= 2p 

ijk2F

where q

denotes the interior angle at vertex i of triangle ijk, and

the sum is taken over all triangles ijk containing vertex i. Intu-

itively, this quantity captures the “ﬂatness” of the vertex, and is

often viewed as a discrete analogue of the Gaussian curvature. An

important mental image is provided in Fig. 4: imagine that the tri-

angles around a vertex i 2 V are ﬂat pieces of paper glued together

along edges. Depending on the value of W

, these triangles can be

bent into a smooth circular cone, a ﬂat circular disk, or a saddle-

like ﬁgure, all without changing geodesic distance. We will there-

fore refer to vertices with positive, zero, and negative angle defect

as spherical or cone-like, Euclidean, and hyperbolic or saddle-like,

respectively. This local picture nicely encapsulates the intrinsic ge-

ometry of any polyhedron: it is smooth and intrinsically ﬂat away

from the vertices—even the location of edges is irrelevant when it

comes to thinking about geodesics and geodesic distance, since the

edges are effectively invisible to an intrinsic observer. The sign of

W plays an especially important role in the context of polyhedral

geodesics, since shortest geodesics will often pass through vertices

where W

< 0, but can never pass through vertices where W

> 0 (as

will be discussed in Sec. 2.2.1).

Working with polyhedral rather than smooth surfaces has some

interesting geometric consequences. On the one hand, since each

individual triangle is ﬂat, we can study geodesics by “unfolding”

local neighborhoods into the plane, i.e., by ﬁnding an arrange-

ment of vertices in R

that agrees with the intrinsic edge lengths—

several examples are shown in Fig. 4. This picture makes it clear

that, locally, geodesics on polyhedral surfaces can be constructed

by simply drawing line segments in the Euclidean plane. The main

computational challenge, therefore, is answering more global ques-

tions: for example, which sequence of triangles must we unfold to

ﬁnd the shortest such line? An analogous perspective is not gener-

ally not available for smooth surfaces, since any local ﬂattening will

invariably distort lengths (i.e., geodesics are rarely straight lines in

local coordinates). On the other hand, the fact that our surface is no

longer smooth makes the deﬁnition of polyhedral geodesics some-

what more nuanced—especially in the vicinity of vertices.

2.2.1. Shortest vs. Straightest

In the smooth setting we had two equivalent characterizations of

geodesic curves: they are both straightest (Sec. 2.1.3) and locally

shortest (Sec. 2.1.2). As studied by Polthier & Schmies [PS98],

these two characterizations are no longer equivalent in the poly-

hedral setting. This situation reﬂects a common “no free lunch”

scenario in the discretization of objects from differential geome-

try [CW17], namely that one typically cannot ﬁnd a single deﬁni-

tion (in this case, for discrete geodesics) that exactly captures all

the key properties of the original smooth object (in this case, both

straightest and locally shortest).

Locally, polyhedral geodesics essentially behave the same as in

the smooth setting. Consider for instance a pair of points p,q con-

tained in the same triangle—here geodesics are just ordinary line

segments, which are both shortest and straightest. Likewise, for two

Figure 5: Any pair of adjacent triangles can be unfolded into the

plane without distorting distance (left). A geodesic on a polyhedral

surface is therefore equivalent to a straight line along some planar

triangle strip—so long as it does not pass through any vertices.

points p,q close to a common edge (and away from any vertex) we

can simply unfold the two incident triangles into the plane and con-

nect them by the unique shortest, straightest segment (see Fig. 5,

left). Globally, however, the situation is more complicated due to

non-smooth points at vertices.

Straightest. To ﬁnd the straightest path leaving a point p 2 M in

a direction u 2 T

M, we can simply apply the local observations

made above: inside a given triangle the shortest path is found by

extending a straight ray along u; to continue this path into the next

triangle we can imagine unfolding neighboring triangles into the

plane and extending this ray into the next triangle. The resulting

path corresponds to a straight line along a strip of planar trian-

gles, as depicted in Fig. 5, right. (Note that for very long paths

we may encounter the same triangle more than once, in which case

we would have multiple copies of this triangle in the unfolding.)

This tracing operation effectively deﬁnes a discrete version of the

exponential map discussed in Sec. 2.1.4.

What should we do if our path enters a ver-

tex i 2 V? In particular, which outgoing direc-

tion describes the “straightest” curve? Unless

the angle defect W

is equal to zero, we can-

not simply unfold triangles into the plane. An

idea considered by Polthier & Schmies [PS98]

is to instead pick the outgoing direction such

that there is “equal angle” on either side. More

precisely, let u be the incoming direction; we

can deﬁne the outgoing direction v as the one

such that the total angle between u and v is ex-

actly half the sum Q

ijk

of interior an-

gles q

at vertex i (see inset ﬁgure). Equiva-

lently, one can work in a local polar coordinate system where angles

are normalized to sum to 2p; this viewpoint has been carefully

studied by Troyanov [Tro86], and was later adopted in geometry

processing for problems involving polyhedral geodesics [PS98] and

tangent vector ﬁelds at vertices [ZMTT06]; Sharp et al. [SSC18,

Section 5.2] provides a concise description. As in the smooth case,

this deﬁnition of straightness yields a unique solution to the initial

value problem, even for paths through vertices with nonzero angle

defect.

Shortest. In contrast, the behavior of shortest curves on a polyhe-

dral surface depends critically on the sign of the angle defect W

Consider for instance two points a,b directly opposite a cone-like

vertex (W

> 0), as depicted in Fig. 6. By symmetry, one might ex-

pect that the shortest route between these points is to walk along

 2019 The Author(s)

Computer Graphics Forum

 2019 The Eurographics Association and John Wiley & Sons Ltd.

K. Crane, M. Livesu, E. Puppo, Y. Qin / A Survey of Algorithms for Geodesic Paths and Distances

Figure 6: The triangles around any vertex i with positive angle de-

fect W

> 0 (left) are intrinsically no different from a smooth cone

(center). Therefore, the shortest path between two points a,b on a

polyhedral surface will never pass through a positive vertex: we

can always cut open the cone in a way that lets us draw a straight

line from a to b without passing through i. When i sits directly be-

tween a and b, this path will not even be unique (right).

the straightest possible path g from a to i, then from i to b. How-

ever, one can ﬁnd an even shorter path by walking “around” the

cone—just as one might ﬁnd a shorter path by walking around a

hill, rather than walking over it. In particular, if we cut the cone

from the boundary through the point a and up to the vertex i, then

the straight line segment from b to either copy of a gives us a short-

est path. Hence, straightest curves on a polyhedral surface are not

always shortest. In this case, g is not even locally shortest, since

even in a tiny region around i would can make it slightly shorter by

going around vertex i, instead of through it. In general, it is never

be advantageous (in terms of path length) to pass through a spher-

ical vertex. Therefore, the only shortest geodesics passing through

a positive vertex i are those terminating at i.

On the other hand, if i is a saddle vertex

< 0), one can often ﬁnd much shorter

paths by passing through vertices. Some ba-

sic intuition is provided by Fig. 4, bottom

right: to go from one side of a saddle region

to another, it is much quicker to go straight

through the vertex than to travel across nu-

merous “ripples.” In fact, starting with a

straight line ` from a point p 2 M to a sad-

dle vertex i, there will be inﬁnitely many out-

going directions v that yield a shortest path;

these directions form a wedge-like region of

angle |W

| around the incoming direction u

(see inset ﬁgure). The union of the incoming path ` with the wedge

is sometimes called a funnel, and is the starting point for a large

family of algorithms reviewed in Sec. 4.1. Again the “shortest”

and “straightest” pictures disagree: a straightest geodesic passing

through a saddle vertex must bisect the funnel, whereas a shortest

geodesic can include any from i contained in the funnel.

2.2.2. Discrete Exponential Map

The analysis above has important implications for the exponential

map on a polyhedral surface. Consider for instance tracing straight-

est geodesics in every possible direction from a vertex i 2V. When

paths hit a spherical vertex j, they split into two groups which meet

discontinuously on the opposite side of j. When paths hit a saddle

vertex k, they again split into two groups,

which do not completely cover the funnel

opposite k. In either case, the exponential

map fails to be injective as soon as we hit

any non-ﬂat vertex; in other words, the in-

jectivity radius is simply the distance to the

closest vertex. Moreover, every spherical

vertex of a polyhedral surface is contained

in the cut locus. As explored by Itoh & Sinclair [IS04], this means

that algorithms which exactly compute distance on a polyhedral

surface will (surprisingly enough) do a very poor job of approx-

imating the cut locus of the smooth surface it approximates. For

instance, the cut locus on a polyhedral sphere will contain every

single vertex, whereas the cut locus of a smooth sphere consists of

just a single point.

3. PDE-based Methods

A large number of methods for computing geodesic distance are

based on formulating the problem in terms of partial differen-

tial equations (PDEs) on a smooth manifold, then discretizing

and solving these PDEs via, e.g., ﬁnite element methods (FEM)

or other numerical techniques. These methods are generally suit-

able for computing the single or multiple source geodesic dis-

tance (SSGD/MSGD); explicit geodesic can subsequently be ob-

tained by, e.g., tracing curves through the gradient of the distance

function (though such tracing requires careful consideration in or-

der to achieve accurate results; see Sec. 5). Some of these meth-

ods are also quite attractive for solving all-pairs geodesic distance

problems (APGD), since their solutions are well-approximated

by precomputing a relatively small collection of eigenfunctions

(Sec. 3.3.1). PDE-based methods are attractive because they are

built on top of well-established techniques from scientiﬁc comput-

ing (such as FEM), as opposed to computational geometry methods

(Sec. 4) which must be built “from the ground up.” As a result, such

techniques often come with a clearer picture of, e.g., convergence

rates under reﬁnement, making them particularly well-suited for the

smooth geodesic problem (Section Sec. 1.2). Moreover, they easily

generalize to problems involving multiple or curved sources, and

can often be implemented on data structures beyond triangulations

(as shown in Fig. 7). On the other hand, since these methods com-

pute only the geodesic distance f , additional work must be done if

one wishes to extract geodesic paths, as discussed in Sec. 5.

PDE-based methods can be categorized according to the type

of equation used to characterize geodesic distance. Different start-

ing points will lead to different numerical treatments, which subse-

quently have different computational trade offs (e.g., different mesh

or solver requirements). At a high level there are two basic classes

of methods:

• Wavefront-based. The basic principle behind wavefront-based

methods resembles (in spirit) classical methods like Dijkstra’s

algorithm, or the window-based methods discussed in Section

4: information about distance propagates outward from a given

source point. In the continuous setting, this perspective corre-

sponds to hyperbolic PDEs, i.e., those that describe the evolution

of a wavefront emanating from the source.

 2019 The Author(s)

Computer Graphics Forum

 2019 The Eurographics Association and John Wiley & Sons Ltd.

剩余32页未读，继续阅读

老猿的春天

粉丝: 97
资源: 55

测地线算法综述：复杂几何处理的关键技术

各种算法 包括图论、比较、检索、最短路径等等

三维重建mc算法梯度计算

cloudcompare修复三维模型孔洞

对X射线图像进行三维目标检测的算法有哪些

如何设计一各三维缺陷识别算法

请给我一个三维缺陷识别算法的例子

openmesh补洞算法

逆向工程得到点云数据之后，还需要做哪些操作才能得到法向量以及三维模型

三维点云的目标检测识别

三维点云重建matlab代码

最新资源

各种算法包括图论、比较、检索、最短路径等等