Please use this identifier to cite or link to this item:
Title: Nagivation Mesh Construction and Path-Finding for Architecture Environment
Authors: MAO LEI
Keywords: Navigation Mesh, Path Finding, Architecture Model, Algorithm, Computer Graphics
Issue Date: 6-Aug-2010
Citation: MAO LEI (2010-08-06). Nagivation Mesh Construction and Path-Finding for Architecture Environment. ScholarBank@NUS Repository.
Abstract: With the fast development of computer science technology, path finding is kept a hot topic in research area; especially it plays an important role in game industry, video and film industry, and large model simulation. However, these approaches and underlying data structure construction are not suitable for all the situations. In this thesis, we present an approach to semi-automatically construct an underlying structure (Navigation Mesh) in the pre-computing phase, and use a two-level path-finding algorithm during the real searching time for an architecture environment. There are many path-finding algorithm approaches with their underlying data structure which represents the real walkable world for game, video and film. However, the problem arises in architecture environment is very different with these situations. In a large hospital, hotel or airports, we need to more concentrate on those small obstacles as tables, chairs, or beds, rather than the un-smooth walkable surface in games or videos. The number of these obstacles is enormous in architecture environment so that we must be careful to choose the underlying data structure construction and also the relative path-finding. In our approach, we construct a navigation mesh data structure for the underlying walkable surface with only relatively large obstacles and leave enormous number of small obstacles in the two-level path-finding phase. We will show that the real searching time will be faster in two-level path-finding approach instead of normal path-finding approach but with bigger number of navigation meshes as we must sub-divide large navigation mesh into lots of small pieces with the enormous number of small obstacles.
Appears in Collections:Master's Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
Master Thesis_MAOLEI_G071020E.pdf1.58 MBAdobe PDF



Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.