[其它] Constant-Time O(1) All Pairs Geodesic Distance Query On Triangle Meshes

[复制链接]

彬彬

797 主题	1 听众	1万积分

资深设计师

Rank: 7 Rank: 7 Rank: 7

纳金币: 5568
精华: 0

电梯直达

楼主

发表于 2012-1-5 08:25:25 |只看该作者 |倒序浏览

1 Introduction

Geodesic plays an important role in geometric computation and

analysis. Rather than the widely studied single source all des-

tination discrete geodesic problem, very little work has been re-

ported on the all pairs geodesic distance query. So far, the best

known result is due to Cook IV and Wenk [2009], who pre-

computed the pairwise geodesic between any two mesh vertices

in O(n52(n) log n) time complexity and O(n4) space complex-

ity, where n is the number of mesh vertices and α(n) the inverse

Ackermann function. Then the geodesic distance between any pair

of points on the mesh edges can be computed in O(m + log n)

time, wheremis the number of edges crossed by the geodesic path.

Although Cook IV andWenk’s algorithm is able to compute the ex-

act geodesic, the high computational cost limits its applications to

real-world models which usually contain thousands of vertices.

(a) Geodesic distance query(b) Exact result (c) Our result

Figure 1: Our algorithm can approximate the geodesic distance

between arbitrary pair of points in constant time. The user can

control the approximation error by specifying the number of sample

points on the input model. Furthermore, both the geodesic path and

geodesic distance field can be approximated in linear time. With

1000 sample points on the Bunny (n = 72K), the relative root-

mean-square error is less than 0.5%. (a) An example of geodesic

distance query and the corresponding exact (in green) and approx-

imate (in red) geodesic paths. (b) The exact geodesic distance field

by [Xin andWang 2009]. (c) The approximate result by our method.

Cold (resp. warm) colors represent short (resp. long) distances.

This paper presents an efficient algorithm for approximating all-

pairs geodesic distances on triangle meshes (see Fig. 1). Our algo-

rithm consists of two steps. In the preprocessing step, we construct

a geodesic triangulation on m sample points, where m is specified

by the user, usually, between a few hundred and several thousand.

The preprocessing step takes O(mn2 log n) time and outputs an

O(m2 + n)-sized file that encodes 1) the exact geodesic distances

between every pair of sample points and 2) the exact geodesic dis-

tances between a mesh vertex and the three vertices of the enclos-

ing geodesic triangle. Then in the query step, we can approximate

the geodesic distance between any two points (not necessarily mesh

vertices) on the surface in constant time O(1). Experiments on real-

world models demonstrate that our method can generate accurate

results with a reasonable number of sample points and preprocess-

ing time. Furthermore, our method has two by-products. First, the

approximate geodesic path can be computed in O(k) time, where

k is the number of edges crossed by the path. Second, the approxi-

mate geodesic distance field can be computed in linear time.