Rapid and efficient terrain surface finding system
First Claim
1. In a virtual reality environment, in which a virtual reality scene having a 3D terrain with a surface representing ground is displayed on a computer monitor under control of a computer, a system for quickly finding a point on said terrain representing ground so as to permit the location of a graphical object thereon, comprising:
- means for characterizing said terrain in terms of polygons;
means for defining as said point the intersection of a ray representing the direction of gravity with the surface of one of said polygons, thus to establish a point on said terrain at which said graphical object is to be located if a point on said graphical object is to rest on said ground; and
,means for selecting a subset of said polygons to be examined for the intersection of said ray, thus to eliminate the necessity for examining all polygons making up said terrain, said selecting means including means for rotating said 3D terrain in accordance with a preferred direction and for projecting said rotated terrain into a 2D plane.
2 Assignments
0 Petitions
Accused Products
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.
37 Citations
8 Claims
-
1. In a virtual reality environment, in which a virtual reality scene having a 3D terrain with a surface representing ground is displayed on a computer monitor under control of a computer, a system for quickly finding a point on said terrain representing ground so as to permit the location of a graphical object thereon, comprising:
-
means for characterizing said terrain in terms of polygons; means for defining as said point the intersection of a ray representing the direction of gravity with the surface of one of said polygons, thus to establish a point on said terrain at which said graphical object is to be located if a point on said graphical object is to rest on said ground; and
,means for selecting a subset of said polygons to be examined for the intersection of said ray, thus to eliminate the necessity for examining all polygons making up said terrain, said selecting means including means for rotating said 3D terrain in accordance with a preferred direction and for projecting said rotated terrain into a 2D plane. - View Dependent Claims (2, 3, 4, 5)
-
-
6. In a virtual reality environment, in which a virtual reality scene having a 3D terrain with a surface representing ground is displayed on a computer monitor under control of a computer, a system for quickly finding a point on said terrain representing ground so as to permit the location of a graphical object thereon, comprising:
-
means for characterizing said terrain in terms of polygons; means, for defining as said point the intersection of a ray representing the direction of gravity with the surface of one of said polygons, thus to establish a point on said terrain at which said graphical object is to be located if a point on said graphical object is to rest on said ground; and
,means for selecting a subset of said polygons to be examined for the intersection of said ray, thus to eliminate the necessity for examining all polygons making up said terrain, said selecting means including means for initially providing a quadtree structure including means for loading the polygons representing said terrain into computer memory, means for listing all ground polygons, means for providing a gravity vector as said ray, means for transforming said list of ground polygons until the gravity vector which is transformed the same way is aligned with the -Z axis of a 2D space having an XY plane, means for projecting each transformed polygon on said XY plane, means for building a quadtree structure having leaves defined by a predetermined area, in which leaves of said quadtree contain only polygons whose 2D projection overlaps the area enclosed by the corresponding quadtree leaf and in which each 2D polygon projection is characterized by a bounding box corresponding to the part of the 2D polygon in the corresponding leaf. - View Dependent Claims (7, 8)
-
Specification