Accelerating Graph-based Path Planning Through Waypoint Clustering (Unknown language)

In: Pacific Graphics Short Papers   ;  59-63  ;  2015

How to get this document?

Download
Commercial Copyright fee: €14.50 Basic fee: €4.00 Total price: €18.50
Academic Copyright fee: €4.50 Basic fee: €2.00 Total price: €6.50

Modern Computer Graphics applications commonly feature very large virtual environments and diverse characters which perform different kinds of motions. To accelerate path planning in such scenario, we propose subregion graph data structure. It consists of subregions, which are clusters of locally connected waypoints inside a region, as well as their connectivities. We also present a fast algorithm to automatically generate subregion graph from enhanced waypoint graph map representation, which also supports various motion types and can be created from large virtual environments. Nevertheless, subregion graph can also be generated from any graph-based map representation. Our experiments showed that subregion graph is very compact relative to the input waypoint graph. By firstly planning subregion path, and then limiting waypoint-level planning to the subregion path, up to 8 times average speedup can be achieved, while average length ratios are maintained at as low as 102.5%.

Table of contents conference proceedings

The tables of contents are generated automatically and are based on the data records of the individual contributions available in the index of the TIB portal. The display of the Tables of Contents may therefore be incomplete.

1
Pairwise Surface Registration Using Local Voxelizer
Song, Peng / Chen, Xiaoping | 2015
7
Robust and GPU-friendly Isotropic Meshing Based on Narrow-banded Euclidean Distance Transformation
Leung, Yuen Shan / Wang, Xiaoning / He, Ying / Liu, Yong-Jin / Wang, Charlie C. L. | 2015
13
Structure-Preserving Image Smoothing via Phase Congruency-aware Weighted Least Square
Yu, Jinze / Sato, Yoichi | 2015
19
Modal Space Subdivision for Physically-plausible 4D Shape Sequence Completion from Sparse Samples
Xia, Qing / Li, Shuai / Qin, Hong / Hao, Aimin | 2015
25
Incomplete 3D Shape Retrieval via Sparse Dictionary Learning
Wan, Lili / Jiang, Jingyu / Zhang, Hao | 2015
31
Complex Modulation Computer-Generated Hologram with Occlusion Effect by a Fast Hybrid Point-source/Wave-field Approach
Gilles, Antonin / Gioia, Patrick / Cozot, Rémi / Morin, Luce | 2015
37
Adaptive Hierarchical Shape Matching
Tian, Yuan / Yang, Yin / Guo, Xiaohu / Prabhakaran, Balakrishnan | 2015
41
Efficient Interactive Image Segmentation with Local and Global Consistency
Li, Hong / Wu, Wen / Wu, Enhua | 2015
47
Simultaneous Stereo Rectification and Distortion Correction with Application to DoF Synthesis
Yeh, Chen Ting / Ho, Tien-Yu / Huang, Szu-Hao / Lai, Shang-Hong | 2015
53
Light-Guided Tree Modeling of Diverse Biomorphs
Yi, Lei / Li, Hongjun / Guo, Jianwei / Deussen, Oliver / Zhang, Xiaopeng | 2015
59
Accelerating Graph-based Path Planning Through Waypoint Clustering
Wardhana, Nicholas Mario / Johan, Henry / Seah, Hock-Soon | 2015
65
Parallel Importing of OBJ Meshes in CUDA
Possemiers, Aidan. L. / Lee, Ickjai | 2015
71
Superpixels Generation of RGB-D Images Based on Geodesic Distance
Pan, Xiao / Zhou, Yuanfeng / Liu, Shuwei / Zhang, Caiming | 2015
77
A Voronoi based Labeling Approach to Curve Reconstruction and Medial Axis Approximation
Peethambaran, Jiju / Parakkat, Amal Dev / Muthuganapathy, Ramanathan | 2015