UNCC College of Computing and Informatics

Graduate Seminar (2009 Fall)

Title: Full 3D Spatial Decomposition for the Generation of Navigation Meshes

Hunter Hale

Ph.D student

Department of Computer Science

University of North Carolina at Charlotte

October 2 at 3:00pm
106 Woodward

Abstract:

We present a novel algorithm developed for decomposing world-space into arbitrary sided high-order polyhedrons for use as navmeshes or other techniques requiring 3D world spatial decomposition. The Volumetric Adaptive Space Filling Volumes (VASFV) algorithm works by seeding world-space with a series of unit cubes. Each cube is then provided with the opportunity to grow to its maximum extent before encountering an obstruction. VASFV implements an automatic subdividing system to convert cubes into higher-order polyhedrons while still maintaining the convex property. This allows for the generation of navigation meshes with high degrees of coverage while still allowing the use of large navigation regions—providing for easier agent navigation in virtual worlds. Compared to the Space-filling Volumes and Automatic Path Node Generation navigation mesh decomposition methods, VASFV provides more complete coverage and a less complex navigation mesh.

Bio:

Hunter Hale is a Ph.D. candidate in the Computer Science Department at the University of North Carolina at Charlotte. His research interests are in artificial intelligence and computational geometry with applications to computer games and simulations. Hunter Hale received his Bachelors Degree from Western Carolina University where he majored in Computer Science. While at Charlotte he has worked in the Charlotte Visualization Center on various Urban Visualization projects and currently works in the Game Intelligence Group where he is researching improvements for navigation mesh generation for agent navigation and assisting with a project to bring agent creation to the layman.

Back