1. Sentence: ( 3rd paragraph, 1st line)
This paper described a new algorithm for computing free paths
among the obstacles in a virtual environment.
2. Problem:
Efficient computation of free paths in virtual environment is critical
in computer games and crowd simulation.
Discrete search methods such as A* are robust and simple to implement, but their performance and quality of paths greatly depend on the grid resolution.
No previous work prior to this work, solved the problem of extracting
optimal paths of arbitrary clearance directly from the triangulation.
3. Key Idea:
Introduce a new “local clearance property” which enables the precise
and efficient determination of paths in a triangulated mesh.
4. What this paper lets us do:
Computes the shortest paths of arbitrary clearance in an environment
with obstacles in O(nlog(n) ) time.
5. Additional resources:
Slides, video and source code available at:
http://graphics.ucmerced.edu/projects/10-sca-tripath/
~