Accelerating Line-of-Sight Computations in Large OneSAF Terrains with Dynamic Events
Christian Lauterbach, Ming C. Lin, Dinesh Manocha, Steve Borkman, E. LaFave, G. Peele, Maria Bauer · 2008
We describe novel algorithms to accelerate the performance of line-of-sight (LOS) computations in large terrains with dynamic entities and events. The underlying approach can handle all kinds of dynamic environments with large number of moving entities, modifiable and dense urban features and may include environmental elements such as terrain skin and features (trees, roads, buildings) an entities such as smoke, clouds, etc. Our algorithm makes use of dynamic bounding volume hierarchies (D-BVHs), which are represented in terms of axis-aligned-bounding-boxes (AABBs). We describe efficient algorithms to compute the D-BHVs by using a combination of refitting and restructuring techniques and perform fast intersection tests between AABBs and the LOS to improve the runtime performance. We have integrated our algorithm with the OneSAF Objective System (Versions 1.1 and 1.5) and created an LOS services library inside of the OneSAF Environment Runtime Component (ERC). We have measured the LOS performance of the existing OneSAF algorithm and our novel D-BVH algorithm on many test suites including JNTC and JRTC databases. Our new integrated LOS algorithm executes the query in 18 microseconds per call on a current desktop PC within high-resolution, urban exercises. In practice, our D-BVH algorithm is about 3X faster than the current OneSAF v1.5 LOS routines and about 10X faster than OneSAF v1.1 LOS routines. To the best of our knowledge, this is the first efficient approach to accelerate LOS computations in large terrains with dynamic entities and events. Our formulation can also be used to accelerate route planning, collision detection and physics-based simulations in dynamic terrains.