An Efficient Central Path Algorithm for Virtual Navigation

Abstract

We give an efficient, scalable, and simple algorithm for computation of a central path for navigation in closed virtual environments. The algorithm requires less pre-processing and produces paths of high visual fidelity. The algorithm enables computing paths at multiple resolutions. The algorithm is based on a distance from boundary field computed on a hierarchical subdivision of the free space inside the closed 3D object. We also present a progressive version of our algorithm based on a local search strategy thus giving navigable paths in a localized region of interest.

Results

Click on the thumbnails for larger images.


Path inside the Ogre Mesh	Flythrough Snapshot at the red arrow	Path inside the Heart Mesh	Flythrough Snapshot at the red arrow


Path inside the 3-Holes Mesh	Path inside the 3-Holes Mesh	GUI snapshot: Cross-Section Selection Mode	GUI snapshot: Flythrough Mode