Spatial augmentation of vertices and continuous level of detail transition for smoothly varying terrain polygon density

• US 5,367,615 A
• Filed: 09/02/1993
• Issued: 11/22/1994
• Est. Priority Date: 07/10/1989
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: General Electric Company
• Inventors: Piazza, Thomas A., Pelham, Anthony J., Economy, Richard, Kelly, William A., Quick, Lee T.
• Primary Examiner(s): Zimmerman, Mark K.
• Assistant Examiner(s): SMITH, MICHAEL
• Application Number:
  US08/115,727
• Time in Patent Office: 446 Days
• Field of Search: 395/127-129, 395/123, 395/125, 395/141, 340/729
• US Class Current: 345/441
• CPC Class Codes: G06T 15/50 Lighting effects

Abstract

In a computer image generation system, the number of vertices which define each of a plurality of terrain-defining polygons is augmented in real time for providing finer detail and for effecting substantially continuous smooth level of detail (LOD) transition. Augmented vertices may have components that are statistically derived, in which case it is not necessary to store and/or predefine them. Alternatively, some vertex components may have predetermined values derived from mapping data or from other deterministic sources and may be stored in compact form. Processing polygons, typically triangles defined by selected ones of the sum of the augmented vertices and the original vertices, may be used for displaying the finer detail. Statistically derived finer detail is especially suited for providing non-specific detail to features such as terrain, while deterministic data allows highly accurate representations of specific `real world` locations. The decision to augment vertices is controlled by a predetermined breakup criteria, which may be selected as one, or a combination, of: range from the viewpoint; angle from the viewpoint boresight; desired maximum error; and other defined criteria.

Claims

1. In a computer image generation system wherein object features of a displayed terrain image are formed from vertex data signals each representing one of a plurality of vertices each designating end points of sides of one of a plurality of planar object face polygons, a method for augmenting the total number of polygon vertices so that finer detail for the features may be displayed in any viewable scene while effecting substantially continuous smooth level-of-detail (LOD) transition, comprising the steps of:

(a) storing information describing

(1) vertex descriptors of edges of planar face polygons forming the object features displayable in a scene of lowest LOD,

(2) breakpoint-determination criteria, and

(3) breakpoint geometric attributes;

(b) retrieving from storage information identifying a selected plurality of vertices, and generating therefrom a plurality of corresponding sides interconnecting the vertices, of each of a plurality of planar basis object face polygons each representing a portion of viewable terrain;

(c) locating at least one breakpoint lying on a corresponding side in each of at least one basis polygon selected from the plurality of object face polygons;

(d) combining the at least one breakpoint location information and selected breakpoint geometric attribute information to substantially continuously modify a geometric attribute determining a location of a derived vertex which lies outside the plane of the associated basis polygon by a deviation amount responsive to a preselected function of the location of the associated basis polygon with respect to first and second edges of a range of distances, and with the derived vertex being different from any vertex stored as a descriptor for an object edge, only if the associated basis polygon is within a preselected range of distances from an image observer viewpoint;

(e) selecting desired ones of a set of the unmodified basis polygon vertices and the derived vertices to constitute a set of a plurality of augmented vertices for the associated basis polygon;

(f) forming at least one derived planar polygon by connecting in a predetermined direction at least selected ones of the totality of the augmented set of vertices;

(g) providing the at least one derived polygon as part of the created and displayed terrain image; and

(h) repeating the operation of steps (b)-(g) to incorporate at least one derived polygon in each scene, and cause a succession of scenes to have varying deviation in the derived polygons of that scene to be viewable with substantially continuous smooth LOD transition of increasingly finer feature detail within decreasing ranges of distance to the observer'"'"'s viewpoint.

2. The method of claim 1, wherein each polygon is a triangle.

3. The method of claim 1, wherein the breakpoints and the derived vertices are described in a mutually-orthogonal three-axis system, and step (d) includes the steps of:

(d1) obtaining deviation value data for each breakpoint; and

(d2) combining deviation value data obtained for a particular breakpoint with data for an axis coordinate of the breakpoint to obtain data establishing the actual coordinate of the derived vertex along that same axis.

4. The method of claim 3, wherein the combining step (d2) includes the step of adding an associated deviation data value to each of at least one different one of the three axial data values of the orthogonal three-axis system used to identify breakpoint position.

5. The method of claim 3, wherein the combining step (d2) includes the step of subtracting an associated deviation data value from each of at least one different one of the three axial data values of the orthogonal three-axis system used to identify breakpoint position.

6. The method of claim 3, wherein the deviation value data is selected from the group consisting of:

predetermined constant values;

random values;

predetermined sinusoidal values;

other predetermined periodic values;

terrain geospecific values;

and a combination of these values.

7. The method of claim 1, wherein step (c) includes the step of designating each different breakpoint to be at a predetermined distance along a different preselected side extending from an associated preselected vertex c,f the basis polygon.

8. The method of claim 7, wherein the predetermined distance is selected from the group consisting of:

one-half the length of the corresponding side;

a predetermined constant distance;

a random distance;

and a combination of these distances.

9. The method of claim 1, wherein

step (c) further includes the step (c'"'"') of processing the total data to determine other breakpoints, each other breakpoint lying on a corresponding side of the derived polygon;

step (d) further includes the step (d'"'"') of substantially continuously modifying data for at least one of the other breakpoints to form data designating another derived vertex which lies outside the plane of both the derived polygon and the basis polygon; and

step (e) further includes the step (e'"'"') of including the other derived vertex data in the augmented vertex data to be processed in step (f).

10. The method of claim 9, wherein

step (c) is performed only when the basis polygon is within a first predetermined distance from the viewpoint;

and the

step (c'"'"') of processing data to determine other breakpoints is performed only when the involved polygon is within a second predetermined distance, closer to the viewpoint than the first predetermined distance.

11. The method of claim 1, wherein step (c) is performed only when the basis polygon is within a predetermined distance from the viewpoint.

12. The method of claim 1, wherein

step (c) further includes the step of determining said at least one breakpoint only when an angle between a boresight of a view window and a view ray to the involved polygon, both with respect to the viewpoint, is within a predetermined limit.

13. In a computer image generation system wherein object features of a display image are formed by first planar polygons, each having a plurality of first vertices each designating one end point of each side of one of the first polygons, a method for achieving substantially continuous smooth level of detail transition, comprising the steps of:

(a) retrieving from storage data determining each of the first vertices of each of the first polygons;

(b) separating each of at least some of the first polygons into a plurality of planar second polygons, each smaller than the associated first polygon, with each second polygon having at least one second vertex which is located at a juncture formed by two sides of that second polygon and with each second vertex being different from any one of the first vertices;

(c) locating, for at least one selected one of the second vertices, a corresponding derived third vertex lying some deviational amount outside the common plane of the associated first and second polygons and different from any of the stored first vertices;

(d) displaying at least one derived planar polygon, each defined by a different combination of one of a third vertex determined in step (c) and associated ones of the first and second vertices, to create and display at least some of a sequence of scenes of a viewable image; and

(e) varying the deviational amount in a manner to display scenes having an increasing level of detail as a viewpoint nears a polygon location, and with a substantially continuous smooth level of detail transition.

14. The method of claim 13, wherein each second vertex has an elevation component associated therewith, and step (c) includes the step of locating at least one of the third vertices such that the elevation data component of that third vertex is different from the elevation data component of its associated second vertex.

15. The method of claim 14, wherein the elevation data component of the selected third vertex is greater than the elevation data component of its associated second vertex.

16. The method of claim 14, wherein the elevation data component of the selected third vertex is less than the elevation data component of its associated second vertex.

17. The method of claim 13, wherein step (b) includes the step of breaking up at least some of the first polygons into second polygons only when an angle, between an image viewpoint and both a boresight of a view window and a view ray to that one of the first polygons, is within a predetermined limit.

18. In a computer image generation system wherein object features of an image to be displayed are represented by planar basis polygons having vertices designating end points of each of a plurality of sides of the basis polygons, a method for augmenting a total number of vertices to cause an increased number of total polygons, each with finer detail for the object features, to be displayed with substantially continuous smooth level of detail transition in viewable scenes created by the system, comprising the steps of:

(a) retrieving from storage vertex data defining each of a plurality of the basis polygons;

(b) selecting a point lying within each of at least one selected one of the basis polygons and different from any vertex of the associated basis polygon;

(c) locating a derived vertex lying at a deviation distance outside the plane of the associated basis polygon at the selected point and different from any of the stored basis polygon vertices;

(d) forming at least one derived polygon determined by the derived vertex and at least two adjacent vertices of the associated basis polygon, responsive to the location of the associated basis polygon nearing an observer viewpoint in the image; and

(e) displaying the derived polygon as part of the viewable image of a scene having finer feature detail along with substantially continuous smooth level of detail transition as the polygon location distance to the viewpoint decreases.

19. The method of claim 18, wherein step (e) includes the steps of:

forming a plurality of derived polygons each including the derived vertex and a side of the associated basis polygon, with the plurality of derived polygons equal in number to the number of sides of the basis polygon;

and displaying the plurality of derived polygons to obtain the display image.

20. The method of claim 18, wherein step (b) further includes the step of selecting each basis polygon point only when an angle, formed between the image viewpoint and both a boresight of a view window and a view ray to the basis polygon, is within a predetermined limit.