Rapid and efficient terrain surface finding system
US5990896A · kind A · utility
Assignee
Inventor
Key dates
| Filing date | Sep 30, 1996 |
| Grant date | Nov 23, 1999 |
| Priority date | — |
| Expiry date | Sep 30, 2016 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06T15/10
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.