测地线路径和距离算法综述三维模型算法曲率算法_如何计算三维模型的曲率资源-CSDN文库

需积分: 18 94 浏览量 2022-10-09 10:41:12 上传评论 1 收藏 39.8MB PDF 举报

资源推荐

资源详情

资源评论

EUROGRAPHICS 2019

A. Giachetti and H. Rushmeier

(Guest Editors)

Volume 38 (2019), Number 2

STAR – State of The Art Report

A Survey of Algorithms for Geodesic Paths and Distances

Keenan Crane Marco Livesu Enrico Puppo Yipeng Qin

Carnegie Mellon University CNR IMATI University of Genoa KAUST

USA Italy Italy Saudi Arabia

Abstract

Numerical computation of shortest paths or geodesics on curved domains, as well as the associated geodesic distance, arises

in a broad range of applications across digital geometry processing, scientiﬁc computing, computer graphics, and computer

vision. Relative to Euclidean distance computation, these tasks are complicated by the inﬂuence of curvature on the behavior

of shortest paths, as well as the fact that the representation of the domain may itself be approximate. In spite of the difﬁculty

of this problem, recent literature has developed a wide variety of sophisticated methods that enable rapid queries of geodesic

information, even on relatively large models. This survey reviews the major categories of approaches to the computation of

geodesic paths and distances, highlighting common themes and opportunities for future improvement.

CCS Concepts

• Mathematics of computing ! Graphs and surfaces; • Theory of computation ! Computational geometry; • Computing

methodologies ! Shape modeling; Scientiﬁc visualization;

1. Introduction

The ability to rapidly compute shortest paths and/or distances be-

tween pairs or sets of points is a fundamental operation in com-

putational science. This survey considers algorithms for computing

geodesic paths and distances, i.e., paths through curved domains

that arise in a broad range of tasks across digital geometry process-

ing, scientiﬁc computing, computer graphics, and computer vision.

Relative to computing distance on Euclidean domains, this problem

is complicated by the inﬂuence of curvature, as well as the fact that

the domain itself may not be known exactly.

Several problems arise in this context, which have different ap-

plications, and are best tackled with different techniques: from trac-

ing a geodesic line given a starting point and a direction; to com-

puting the shortest path between a pair of points; to computing the

distance function over a whole surface, with respect to a source

point or set; to provide a framework to rapidly extract the shortest

path between any pair of points. Broadly speaking, there are two

major classes of methods: those rooted in computational geome-

try, which view a polyhedral surface as an exact description of the

geometry, and those rooted in scientiﬁc computing, which view a

polyhedron as an approximation of a smooth surface. Neither class

of approaches is universally “better”: each may be best-suited to

a particular task (e.g., ﬁnding geodesics on a CAD model, versus

approximating geodesic distance on a scanned surface), and in a

particular setting, according to a wide variety of trade offs in terms

of accuracy, storage cost, run time performance, and scalability.

In general one might wish to compute geodesics and geodesic

distances on many different data structures (point clouds, voxeliza-

tions, etc.), though in this survey we focus primarily on polyhedral

surfaces, represented as triangle meshes. The survey is organized

according to the different geodesic distance problems and the at-

tendant classes of approaches to their solution (see Table 8 for a

summary). After introducing the basic problems in Sec. 1.1 and

providing the necessary background in Sec. 2, we review major

classes of algorithms in Secs. 3, 4 and 5. In Sec. 6, we examine

the relationship between mesh quality and geodesic computation.

In Sec. 7, we provide a partial evaluation of the reviewed meth-

ods, on the basis of available implementations. Finally, in Sec. 8,

we draw some conclusions and we highlight common themes and

opportunities for future improvement in geodesic algorithms.

Previous surveys. Our focus in this survey is on practical algo-

rithms and their behavior on real-world datasets. A relatively re-

cent survey by Bose et al. [BMSW11] deals primarily with theoret-

ical aspects of one particular problem (the polyhedral shortest path

problem), with a focus on asymptotic time complexity and approx-

imation bounds, as well as special cases such as convex polyhedra.

Less attention is devoted to broader problems (such as geodesic dis-

tance transforms) or issues such as real-world performance, mesh

quality, etc.; in this respect, such a survey is complementary to ours.

Patané [Pat16] provides a detailed survey on the speciﬁc topic of

Laplacian spectral kernels and distances, which is likewise com-

plementary to our account of PDE-based methods. Peyré and col-

leagues [PC09,PPK

⇤

10] provide a nice overview of several aspects

of PDE-based methods, though the last few years have seen major

advancements in PDE-based methods, which we discuss in Sec. 3.

 2019 The Author(s)

Computer Graphics Forum

 2019 The Eurographics Association and John

Wiley & Sons Ltd. Published by John Wiley & Sons Ltd.

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

1.1. Geodesic Queries

Tasks in geometry processing may require a variety of different

queries about geodesics and geodesic distances; though seemingly

similar, these queries must be answered via very different algo-

rithms. We review several important cases here.

Initial Value Problems. Perhaps the simplest type of problem is

the initial value problem, which traces out a geodesic starting at a

given point in a given direction. In the Euclidean case, the solu-

tion is simply a straight ray through space, though in general one

must of course account for the inﬂuence of curvature; in the dis-

crete setting one also encounters some difﬁculty in deﬁning which

ray is most “straight” (see Section 2.2). Computationally this prob-

lem, which we will refer to as Geodesic Tracing (GT), tends to be

among the easiest of geodesic queries; we examine it in detail in

Sec. 5.

Boundary Value Problems. In boundary value problems, a set of

points on the domain is given as input, and one seeks (for instance)

geodesic paths between these points, or geodesic distances to all

these points. This type of problem is generally not as easy as an

initial value problem since, for instance, one cannot simply shoot

a geodesic ray from one point and hope to hit a particular target

point. We consider in particular the following problems:

• Point-to-Point Geodesic Path (PPGP): given two distinct points

p,q, ﬁnd any shortest geodesic g between them. (Note that in

general the solution may not be unique—see Sec. 2.)

• Single Source Geodesic Distance / Shortest Path (SSGD/SSSP):

given a source point p, compute a scalar function j(q) that pro-

vides the length of the shortest path from p to each point q. In

SSGD, only the distance function is provided; in SSSP, the short-

est paths are also explicitly computed.

• Multiple Source Geodesic Distance / Shortest Path

(MSGD/MSSP): in this case the source is no longer just a

single point p, but rather a collection S of points, curves, etc..

The result is a function f(p) which for each point p gives

the distance to the closest point in the set; this query is also

sometimes called a distance transform. In MSSP, paths are also

provided.

• All-Pairs Geodesic Distances / Shortest Paths (APGD/APSP):

given a source set S, compute the shortest distance/paths between

all pairs of points in S.

In Sections 3 and 4, we review the methods for solving these prob-

lems, categorized according to their basic algorithmic approach

they take. Most methods that solve the SSGD/SSSP problems also

provide a solution to PPGP as a byproduct; several easily general-

ize to MSGD/MSSP; only few methods address the APGD/APSP

problems. In Section 4.2, we review some algorithms that are

speciﬁcally developed to solve PPGP.

Note that most methods in the literature assume that initial points

or boundary conditions are speciﬁed at vertices of an input triangu-

lation, though some methods allow direct evaluation of geodesic

queries at arbitrary points of the domain. For algorithms that only

support queries at vertices, a pragmatic approach is to locally reﬁne

the mesh by splitting faces or edges at the query point.

1.2. Polyhedral vs. Smooth Geodesic Problem

When thinking about algorithms for computing geodesics, it is im-

portant to consider what our domain represents: does it exactly rep-

resent the geometry of interest, or is it merely an approximation of

the true domain? The answer to this question depends on context.

For instance, in problems like animation or CAD/CAM, where sur-

faces are designed by artists or engineers, we may have an exact

boundary representation and want to compute exact paths along

this surface. On the other hand, when a mesh is obtained via, say,

3D scanning or numerical simulation, it can only provide an ap-

proximation of the true domain, i.e., the real physical surface of

interest. In this case, the accuracy of geodesic computation is fun-

damentally limited by the accuracy of the domain representation

itself. The choice of application therefore inﬂuences how we talk

about error, and also which algorithms are best suited to a given

task.

In the context of polyhedral surfaces, a

common misconception is that the “correct”

answer is obtained by considering piecewise

linear paths through the domain – though

of course these paths may only be approxi-

mations of true (smooth) geodesic curves. A

simple 1D example is illustrated in the inset.

What is the “correct” distance between the

point a and the point c? If we view the polygon as an exact rep-

resentation of the geometry (i.e., if we wish to compute distance

along the square itself), then the geodesic distance is obtained by

summing the two edge lengths |ab|+ |bc| = 2

2 ⇡ 2.82. On the

other hand, if we view the polygon as an approximation of the

smooth circle, the distance should just be the arc length between

a and c, i.e., p ⇡ 3.14. Not surprisingly, the polygonal geodesic

distance is an underestimate of the smooth geodesic distance, since

each straight segment takes a “short cut” from point to point. This

same phenomenon occurs on triangulated surfaces: the polyhedral

geodesic distance generally underestimates the smooth geodesic

distance (for instance, the distance along a cube provides a poor

approximation of the distance along the circumscribed sphere). To

make the distinction clear in this survey, we therefore distinguish

between two versions of the geodesic problem:

• Polyhedral Geodesic Problem — view a discrete surface as

an exact description of the geometry, and aim to compute exact

geodesics or exact distances along this polyhedral surface.

• Smooth Geodesic Problem — view a discrete surface as an ap-

proximation of the true geometry, and aim to compute the most

accurate possible approximation of geodesics or geodesic dis-

tances.

The polyhedral problem captures the standard viewpoint of com-

putational geometry; the smooth problem encapsulates the standard

viewpoint of scientiﬁc computing. These two problems interact of

course: for instance, one can use the exact polyhedral distance to

approximate the true smooth distance. Surprisingly enough, how-

ever, the best strategy for approximating the smooth geodesic dis-

tance may not be to simply compute the exact polyhedral distance.

For instance, even on a nicely triangulated sphere, the polyhedral

distance gives only an O(h

) approximation of the smooth distance

(Fig. 1); greater accuracy can be achieved by considering the dis-

 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 1: When a polyhedral surface is an approximation of a

smooth surface, the “exact” polyhedral distance still does not re-

cover the true distance of the smooth surface. For instance, even

for very nice triangulations of the smooth sphere, algorithms from

computational geometry improve accuracy by only one order rela-

tive to PDE-based methods (from linear to quadratic).

tance along a spline or subdivision surface that approximates the

same sampling of the domain [DGDMD16, NKP16]. The fact that

one can do better than the exact polyhedral distance should not

come as a surprise: higher-order geometric elements (e.g., spline

or subdivision patches) use a much larger stencil of information

than individual triangles, which correspond to linear elements (con-

sider, for instance, approximating the circle by four Bézier curves

rather than four straight segments). On the other hand, higher-order

interpolation provides no beneﬁt for the polyhedral geodesic prob-

lem, where one is interested in the exact distance along a particular

piecewise linear surface.

2. Background

In this section we provide some basic concepts and deﬁnitions that

will facilitate our discussion of algorithms—for a more thorough

introduction, see [dC76] in the smooth setting (especially Chapter

4, Sections 4–4, 4–6, and 4–7), and [CdGDS13] for the discrete

setting. At a high level, geodesics can be characterized as curves

that are in some sense straightest and (locally) shortest, though one

must be careful about the relationship between these two character-

izations (Sec. 4.1), especially on polyhedra where they may lead

to different discrete deﬁnitions [PS98]. We ﬁrst give some standard

background in the smooth setting (Sec. 2.1), followed by a discus-

sion of geodesics on polyhedral surfaces (Sec. 2.2).

2.1. Smooth Setting

Intrinsic vs. Extrinsic Geometry. When studying geodesics, how

should we describe the shape of the domain? An important feature

of geodesics is that they depend only on distances along the surface,

and not at all how the surface sits in space. As a concrete example,

consider a piece of paper rolled up into a tube (Fig. 2): a straight

line `

drawn between two nearby points p and q on the ﬂat piece

of paper is still a shortest curve on the tube (see Fig. 2). One can

ﬁnd an even shorter path by drawing a straight line through space,

but this line is no longer a path along the surface. Likewise, there

are many other ways we could bend the tube without changing the

Figure 2: A geodesic is any “straight” curve between two points

p and q, and are a feature of the intrinsic geometry of the surface:

they do not change if we bend the surface, so long as there is no

stretching, shearing, or ripping. Though the shortest path will al-

ways be a geodesic (here, `

), a geodesic is not necessarily the

shortest path (consider `

shape or length of shortest paths—for this reason, when studying

geodesics we really want to ignore the extrinsic geometry of the

surface (how it sits in space), and focus purely on its intrinsic ge-

ometry (only those things that can be measured by walking along

the surface). The desire to compute shortest intrinsic (rather than

extrinsic) paths is of course quite natural: for instance, the “short-

est” route between two cities is the one that best avoids mountains

and valleys—not the one that tunnels straight through the Earth!

Shortest vs. Straightest Curves. The tube example also helps to

illustrate another feature of geodesics: shortest implies straight, but

straight does not necessarily imply shortest. Consider, for instance,

a long straight line `

from p that “goes off the edge of the map”

before returning to q. This curve is still a geodesic, but it is not a

shortest geodesic—in particular, it is not as short as `

. Finally, the

word “shortest” does not imply that there is a unique geodesic of

minimal length. For instance, there may be two equally short ways

to go around a hill; in fact, there may be inﬁnitely many shortest

paths between two given points, such as the north and south pole of

a sphere.

Unfortunately, ﬁnding geodesics is not as simple as just “un-

rolling” a smooth surface into the plane and ﬁnding straight lines

(as we did with the tube), since most surfaces cannot be ﬂattened

without distorting distances. Consider for instance the many dif-

ferent map projections used by cartographers (Mercator, Robinson,

etc.), none of which preserve geodesic distances. However, we can

nonetheless reason about shortness and straightness of curves: for

instance, a curve on an embedded surface is “straight” if there is

no acceleration as we travel along the curve, except in the nor-

mal direction—in other words, if we only turn by the bare mini-

mum amount needed to remain on the surface. Alternatively, we

can adopt the perspective of Riemannian geometry, which allows

one to reason about intrinsic geometry without thinking about how

it is embedded in space.

2.1.1. Smooth Surfaces

In the intrinsic picture, our main object of study is a smooth sur-

face M with Riemannian metric g. The fact that M is smooth im-

plies that at each point p 2 M we have a tangent space T

M, where

each tangent vector X 2 T

M speciﬁes a vector pointing “along”

the surface, i.e., all possible directions we can travel away from p.

 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

Since we have no information about how the surface sits in space,

the one and only way to measure lengths and angles of tangent vec-

tors is via the Riemannian metric, which for tangent space T

provides a positive-deﬁnite inner product g

: T

M ⇥T

M ! R

0

For instance, the length of any tangent vector X 2 T

M is given

by |X| :=

(X,X); the angle between any two tangent vectors

X,Y 2 T

M is given by arccos(g

(X,Y)/|X||Y|), just as in ordi-

nary Euclidean R

. In fact, whenever the surface M is sitting in

space, the Riemannian metric and Euclidean inner product coin-

cide. When the meaning is understood from context, or when work-

ing with a vector ﬁeld X (i.e., a choice of vector in each tangent

space), we can drop the subscript p.

2.1.2. Shortest Curves

The Riemannian metric enables us to easily deﬁne geodesic curves

in terms of conditions on length. In particular, consider any differ-

entiable map g from an interval [a, b] of the real line into the surface

M, and let

g(t) :=

g(t); we say that g is arc-length parameterized

if |

g(t)|= 1 for all t 2[a,b]. We can express the length of any curve

g as

L(g) :=

g(t)| dt =

g(t)

(

g(t),

g(t)) dt.

The geodesic distance f (p, q) between any two points p,q 2 M

is the inﬁmum of length over all curves g such that g(a)=p

and g(b)=q. An arc-length parameterized curve g is a shortest

geodesic if it achieves this inﬁmal length. An arc-length parame-

terized curve g is a geodesic if it is “locally shortest,” i.e., if there

is some d > 0 such that g is a shortest geodesic when restricted to

any interval [t

] ⇢ [a,b] such that t

t

d . Intuitively, a short-

est geodesic is a curve that cannot be made any shorter (without

moving its endpoints); a geodesic is a curve that cannot be made

shorter by adjusting any small piece of it.

2.1.3. Straightest Curves

We can also characterize geodesics in terms of straightness rather

than shortness. This perspective is best understood from a dynamic

point of view: imagine we are driving along a road at constant

speed, and never turn our wheel left or right. Although we may

encounter hills and valleys along the way, our trajectory is in some

sense as straight as it possibly could be. In the extrinsic setting the

only acceleration we experience is in the direction normal to the

surface, i.e., the minimal possible acceleration needed to keep our

vehicle on the ground. In the intrinsic setting, we do not need to

worry about this normal acceleration since our surface is not sitting

in space—instead, we just say that a geodesic is a curve of zero

acceleration.

How can we measure the acceleration of a curve g(t) in a surface

M? In the Euclidean plane, we can just take the second derivative of

g with respect to t. In the Riemannian setting, however, the velocity

vectors g

) and g

) at two different times t

will in general

belong to two different tangent spaces T

g(t

)

M,T

g(t

)

M, and hence

cannot be compared directly. Instead, we can use the Levi-Civita

connection or covariant derivative —

Y, which (intuitively) uses

the metric g to measure how much Y is turning as we move along

the direction X. In particular, a curve g is a geodesic if its tangent

Figure 3: Extrinsically, the curvature of a curve

g can be decom-

posed into the normal and geodesic curvatures k

, which mea-

sure the change in the tangent in the direction of the surface normal

N and the curve normal n, respectively (left). A “wiggly” but planar

curve will have zero normal curvature and nonzero geodesic cur-

vature (center), whereas a great arc on a sphere has zero geodesic

curvature but nonzero normal curvature (right).

g exhibits zero turning as we move along the tangent direction, i.e.,

—

g(t)

g(t)=0

at all times t 2 [a,b]. (Since the covariant derivative is local, it does

not help us deﬁne shortest geodesics.) More generally, for any arc-

length parameterized curve g we have

—

g(t)

g(t)=k

(t)N(t),

where for each time t, the vector N(t) 2 T

g(t)

M is the unit normal

to the curve (i.e., a unit vector orthogonal to the tangent), and the

scalar k

(t) 2R is the geodesic curvature, which measures the rate

at which the curve is bending. A geodesic is then a curve with zero

geodesic curvature.

We can also understand geodesic curvature from an extrinsic

point of view. Suppose we have a map f : M ! R

assigning each

point of the surface M a location in space, and let N : M !S

⇢R

be the corresponding Gauss map giving the unit normal at each

point. A curve g : [a,b] ! M on the surface can now be realized

as a curve

g := f g in Euclidean space. Assuming

g is parameter-

ized by its arc-length s, its unit tangent is given by

T(s) :=

g(t);

we will use n := T ⇥N to denote the normal to the curve (as op-

posed to the normal N of the surface). The derivative of T in turn

describes the curvature of the curve, which can be decomposed into

two scalar components:

:= hn,

Ti,

:= hN,

Ti.

Note that there is no derivative in the T direction, since

g is arc-

length parameterized and hence its tangent doesn’t change length.

In other words, the geodesic curvature k

describes how much the

curve g is bending “in plane”; the normal curvature k

describes

how much g is bending “out of plane.” Geodesics are again curves

of zero geodesic curvature, i.e., those that go straight along the sur-

face (and bend purely to remain on the surface). An illustration is

provided in Fig. 3.

 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

2.1.4. Exponential Map

At any point p 2 M and any unit vector X 2 T

M, there is a unique

geodesic traveling away from p in the direction X, i.e., such that

g = X (this perspective leads to the tracing algorithms discussed

in Sec. 5). More generally, the exponential map exp

: T

M ! M

takes any tangent vector X at p to the point q of M reached by walk-

ing in the direction X/|X| a distance |X|. In general, however, this

map is not invertible: there can be distinct points q

6= q

that are

reached by starting at p and walking along geodesics in different

directions (or for different distances). Any neighborhood U of p

over which exp

is invertible is called a normal neighborhood of

p; on any such neighborhood, the inverse of the exponential map

deﬁnes the logarithmic map log

: U !T

M. The logarithmic map

provides local coordinates around p called normal coordinates, by

effectively “ﬂattening out” a small patch of the surface onto its tan-

gent space. Polar coordinates on the tangent space are sometimes

called geodesic polar coordinates; here, geodesics can be charac-

terized (locally) as lines of constant angle. Circles in this tangent

plane are mapped by the exponential map to geodesic circles, which

orthogonally intersect geodesic rays from p (Gauss’ lemma).

Away from a normal neighborhood, geodesics may start behav-

ing in less intuitive and undesirable ways. We review some global

aspects of geodesics in Sec. 4.1.

2.1.5. Geodesic Distance

Many of the algorithms discussed in this survey aim not to com-

pute individual geodesic curves, but rather the geodesic distance

function f : M ⇥ M ! R over the entire surface. In particular,

for any two points x,y 2 M, f (x,y) is the smallest length of any

geodesic between x and y. This function satisﬁes all the properties

of a distance metric, i.e., nonnegativity (f (x,y)  0), nondegen-

eracy (f(x, y)=0 () x = y), symmetry (f(x,y)=f (y,x)) and

triangle inequality (f (x,y)+f(y, z) f(x, z)); these properties will

be important to keep in mind when studying numerical approxima-

tions of geodesic distance. A geodesic ball B

(r) is the set of all

points q 2 M such that f (p,q) < r.

Cut locus. For a given point p, the injectivity radius is the radius

r > 0 of the largest geodesic ball B

(r) such that there is a unique

shortest path from any point q 2 B

(r) back to p. Outside this ra-

dius, there are points q with two or more shortest paths to p. The

collection of all such points is called the cut locus. More generally,

for any source set W (e.g., a collection of isolated points, or a net-

work of curves, surfaces, etc.) the cut locus is the set of points q for

which there is not a unique shortest path to some point in W. The

geodesic distance function f (x , y) is smooth away from the cut lo-

cus. In most situations, it is not particularly important that geodesic

distance algorithms accurately reconstruct the cut locus: only that

the distance values or paths computed at each point are accurate.

However, some applications (e.g., computing the medial axis of a

shape) may require an accurate cut locus.

2.2. Polyhedral Setting

Geodesics on polyhedral surfaces behave somewhat differently

from geodesics on smooth surfaces—especially in the vicinity of

vertices, where the surface fails to be smooth. Methods coming

from computational geometry (Sec. 4) must therefore carefully

consider the speciﬁc behavior of polyhedral geodesic paths; meth-

ods based on the ﬁnite element viewport (Sec. 3) largely side-step

these questions by approaching geodesic computation from the per-

spective of function approximation rather than explicit path tracing.

A polyhedral surface is, roughly speak-

ing, a collection of Euclidean (planar)

polygons glued together to form a surface.

Since any planar polygon can be triangu-

lated (and the choice of triangulation has

no effect on geodesics), we will assume

that the combinatorics of any polyhedron

are encoded by a simplicial complex M with vertices V, edges E,

and faces F. For simplicity we also assume that this complex is

manifold, i.e., the link Lk(i) of every vertex i 2 V interior vertex is

a single closed loop; the link of every boundary vertex is a single

path (see inset ﬁgure).

The geometry of a polyhedral surface can be speciﬁed in one of

two ways: either extrinsically, using vertex coordinates f : V !R

which are linearly interpolated over each triangle, or intrinsically,

by specifying positive edge lengths ` : E ! R

that satisfy the

triangle inequality in each face: `

+ `

 `

for all ijk2 F. Of

course, one can always obtain edge lengths from vertex coordi-

nates (`

:= |f

 f

|), though the vast majority of geodesic algo-

rithms can in principle be implemented without reference to vertex

coordinates—reﬂecting the fact that geodesics are a purely intrinsic

object. Instead, quantities like triangle areas A

ijk

and interior angles

at triangle corners can be computed directly from edge lengths

(using expressions like Heron’s formula and the law of cosines).

This fact is especially useful given that in some geometric problems

(e.g., manifold learning) one may have distances between points,

but not an explicit embedding in R

Figure 4: Intrinsically, a vertex i of a polyhedral surface looks like

either a circular cone, a ﬂat disk, or a saddle, depending on the

sign of the angle defect W

 2019 The Author(s)

Computer Graphics Forum

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

剩余32页未读，继续阅读

评论收藏

内容反馈

老猿的春天

粉丝: 74
资源: 55

测地线路径和距离算法综述 三维模型算法 曲率算法

三维模型上两点之间的测地线距离 Geodesic Distance

三维CAD曲面模型距离-曲率形状分布检索算法.pdf

基于双距离场的三维中心路径提取算法

基于曲率约束的三维模型凹区域分割线提取算法

分享规则网格数字高程模型中使用距离与坡度的路径规划算法.pdf

matlab算法——计算三维散乱点云的曲率，包括主曲率，高斯曲率和平均曲率）

curve.rar_三维曲率_三维模型 MATLAB

论文研究-基于区域离散曲率的三维网格分水岭分割.pdf

论文研究-基于三维点云模型的特征线提取算法.pdf

基于距离-夹角形状分布的三维CAD模型检索算法.pdf

基于三维点云模型的特征线提取算法 (2013年)

一种基于顶点曲率的三维实体表面模型加密算法 (2005年)

论文研究-三维模型孔洞修补方法的研究.pdf

三维离散曲线曲率挠率的微中心差分算法.pdf

论文研究-序列图像三维重构中点云精简算法的研究与改进.pdf

三维模型特征笔画的风格化绘制 (2008年)

论文研究-基于离散曲率的点云光顺算法.pdf

基于matlab计算三维散乱点云的曲率，包括主曲率，高斯曲率和平均曲率.zip

基于曲率图的三维点云数据配准

基于激光三维点云分割地铁隧道壁表面物体

第十五届蓝桥杯大赛软件赛省赛C++B组题目

C/C++中文参考手册离线最新版

代码随想录-八股文 pdf

第十五届蓝桥杯大赛软件赛省赛-C++A组题目

编译器（gcc、g++）

Qt5.9 C++开发指南.pdf 及示例源码

Qt （高仿Visio）流程图组件开发，源码分享

mingw-w64-install.exe

最新资源

测地线路径和距离算法综述三维模型算法曲率算法