Importance

Loading Importance Indicators...

Abstract

A system for quickly finding a point in a virtual environment 'on the gro' or beneath another point involves finding the intersection of a 'ground' polygon representing the terrain with a single ray representing the direction of gravity emanating from the original point. After appropriate polygons are selected, they are intersected with the gravity vector to determine which ones are just under the point in question, with the closest point being returned as the ground point. Polygons are sorted into a variable depth quadtree structure, where the leaves contain a predetermined maximum number of polygons, with each quadtree node being subdivided based on a polygon vertex located inside the current quadtree node. A planar space subdivision of each quadtree node is created using the edges of the polygons that overlap that node. The system for rapid ground point determination intersects lines of a predetermined orientation, e.g., gravity, with a terrain model and uses a preprocessing step that reduces the 3D terrain to a 2D projection and then sorts terrain polygons into a quadtree, followed by adding bounding boxes and polygon edge parameters to speed up polygon containment checking.

Loading the Abstract Image...

First Claim