纳金网

标题: Constant-Time O(1) All Pairs Geodesic Distance Query On Triangle Meshes [打印本页]

作者: 彬彬 时间: 2012-1-5 08:25
标题: Constant-Time O(1) All Pairs Geodesic Distance Query On Triangle Meshes
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.

作者: C.R.CAN 时间: 2012-2-8 23:32
顶!学习了!阅!

作者: C.R.CAN 时间: 2012-3-1 23:28
路过……

作者: 菜刀吻电线 时间: 2012-3-7 23:18
百度的叫度娘，网易的叫易娘，新浪内部还在为是叫新娘还是浪娘而争论不休！……不管你们是企鹅的额娘，豆瓣的伴娘，还是华为的伪娘，都要记得，淘宝才是你们的亲娘啊！亲！！

作者: 菜刀吻电线 时间: 2012-3-15 23:18
呵呵，很好，方便罗。

作者: C.R.CAN 时间: 2012-4-7 23:24
我是老实人,我来也!

作者: 菜刀吻电线 时间: 2012-4-27 23:22
长了不少见识

作者: C.R.CAN 时间: 2012-8-25 23:54
好铁多多发，感激分享

作者: 晃晃 时间: 2012-9-5 23:27
其实楼主所说的这些，俺支很少用！

作者: 铁锹 时间: 2012-9-6 09:54
3D人体地图：人人都可以学解剖

松下展出业界最大的裸眼3D电视

3D打印火热_国内外试水企业颇多

美科研机构投资3D打印技术_意在重振制造业

作者: 菜刀吻电线 时间: 2012-10-3 23:18
好铁多多发，感激分享

作者: tc 时间: 2012-10-31 23:29
其实楼主所说的这些，俺支很少用！

作者: 菜刀吻电线 时间: 2013-3-15 23:29
先顶上去，偶要高亮加精鸟！

欢迎光临纳金网 (http://go.narkii.com/club/)