Parallel Algorithms for Approximation of Distance Maps on Parametric Surfaces

被引：87

作者：

Weber, Ofir ^{[1
]}

Devir, Yohai S. ^{[1
]}

Bronstein, Alexander M. ^{[1
]}

Bronstein, Michael M. ^{[1
]}

Kimmel, Ron ^{[1
]}

机构：

[1] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel

来源：

ACM TRANSACTIONS ON GRAPHICS | 2008年 / 27卷 / 04期

基金：

美国国家科学基金会;

关键词：

Eikonal equation; geodesic distances; fast marching; geometry image; multiple charts; parallel algorithms; GPU; SIMD;

D O I：

10.1145/1409625.1409626

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present an efficient O(n) numerical algorithm for first-order approximation of geodesic distances on geometry images, where n is the number of points on the surface. The structure of our algorithm allows efficient implementation on parallel architectures. Two implementations on a SIMD processor and on a GPU are discussed. Numerical results demonstrate up to four orders of magnitude improvement in execution time compared to the state-of-the-art algorithms.

引用

页数：16

共 37 条

[1] Finite-element discretization of static Hamilton-Jacobi equations based on a local variational principle [J].

Bornemann, Folkmar ;

Rasch, Christian .

COMPUTING AND VISUALIZATION IN SCIENCE, 2006, 9 (02) :57-69

[2] Generalized multidimensional scaling: A framework for isometry-invariant partial surface matching [J].

Bronstein, AM ;

Bronstein, MM ;

Kimmel, R .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2006, 103 (05) :1168-1172

[3]

BRONSTEIN AM, 2006, IEEE T VISU IN PRESS

[4]

CARR N, P EUR S GEOM PROC

[5]

Chang K.I., 2003, WORKSH MULT US AUTH, P25

[6] EUCLIDEAN DISTANCE MAPPING [J].

DANIELSSON, PE .

COMPUTER GRAPHICS AND IMAGE PROCESSING, 1980, 14 (03) :227-248

[7]

DUPUIS P, 1994, P EUR C COMP VIS ECC, P259

[8]

Elad A, 2001, PROC CVPR IEEE, P168

[9]

FISCHER I, 2005, TR0705 CS HARV U

[10] Modeling by example [J].

Funkhouser, T ;

Kazhdan, M ;

Shilane, P ;

Min, P ;

Kiefer, W ;

Tal, A ;

Rusinkiewicz, S ;

Dobkin, D .

ACM TRANSACTIONS ON GRAPHICS, 2004, 23 (03) :652-663

← 1 2 3 4 →