System and method related to data structures in the context of a computer graphics system

• US 6,985,143 B2
• Filed: 05/28/2002
• Issued: 01/10/2006
• Est. Priority Date: 04/15/2002
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Pharr, Matthew
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US10/157,579
• Publication Number:
  US 20030193527A1
• Time in Patent Office: 1,323 Days
• Field of Search: 345/419, 345/420, 345/421, 345/422, 345/423, 345/426, 345/611, 345/612, 345/613
• US Class Current: 345/421
• CPC Class Codes: G06T 1/60 Memory management

Abstract

A system and method of maintaining computer graphics data sets in a line tree data structure. A data set is defined by a reference range with endpoint references r0 and r1 and is associated with a segment of a sampling line that analytically represents a part of an object. A data set contains data at the endpoint references r0 and r1 including values for depth, color, transparency, and depth range. Targeted data sets are defined as data sets containing certain reference values and are retrieved using a data set retrieval procedure. After retrieval, a targeted data set is compared to a new data set by a data set update procedure to determine whether the targeted data set remains, the new data set replaces the targeted data set, or modified data sets are required to be created and inserted into the line tree data structure.

Claims

1. A method for maintaining data sets comprising:

storing the data sets in a line tree data structure wherein the line tree data structure includes a root node and a plurality of subordinate nodes, the plurality of subordinate nodes including a plurality of leaf nodes wherein each leaf node stores a data set, the data set containing object parameter values of an associated segment of a sampling line that analytically represents a part of an object;

retrieving targeted data sets using a data set retrieval procedure wherein the targeted data sets are any data sets stored in the line tree data structure meeting a predefined condition; and

updating the line tree data structure using a data set update procedure upon receiving a new data set not already stored in the line tree data structure.

2. The method of claim 1, wherein:

the data set is defined by a reference range with a starting endpoint reference r0 and an ending endpoint reference r1, the reference range corresponding to a parameterized t range spanned by the associated segment, the t range having a starting t value t0 corresponding to the starting endpoint reference r0 and an ending t value t1 corresponding to the ending endpoint reference r1; and

the targeted data sets are any data sets stored in the line tree data structure containing a reference range overlapping a reference range of the new data set.

3. The method of claim 2, wherein the data set stores data at the starting endpoint reference r0 and the ending endpoint reference r1 including data set values for depth, color, and transparency that correspond to object parameter values for depth, color, and transparency of the associated segment and a data set depth range that corresponds to an object depth range of the associated segment, the data set depth range spanning from the data set value for depth at r0 to the data set value for depth at r1.

4. The method of claim 2, wherein each node of the line tree data structure stores the reference range spanned by all its child nodes.

5. The method of claim 4, wherein the data set retrieval procedure comprises:

setting the root node as a current node;

checking each child node of a current node to determine whether the child node contains any targeted data sets;

retrieving a targeted data set from the child node upon determining that the child node contains a targeted data set and that the child node is a leaf node;

resetting the child node as a current node upon determining that the child node contains a targeted data set and that the child node is not a leaf node; and

repeating the checking, retrieving, and resetting for each child node of a current node until all targeted data sets contained in the line tree data structure are retrieved.

6. The method of claim 3, wherein the data set update procedure comprises:

comparing the data set depth range of a targeted data set and the data set depth range of the new data set;

retaining the targeted data set in the line tree data structure and discarding the new data set upon determining that the data set depth range of the targeted data set is less than the data set depth range of the new data set throughout the reference range of the new data set;

replacing the targeted data set with the new data set in the line tree data structure upon determining that the data set depth range of the new data set is less than the data set depth range of the targeted data set throughout the reference range of the targeted data set; and

creating a modified data set or modified data sets to replace the targeted data set in the line tree data structure when the condition for retaining and the condition for replacing are not found.

7. The method of claim 6, wherein the creating comprises:

forming a modified targeted data set by eliminating the portion of the reference range of the targeted data set containing a higher data set depth range than the data set depth range of the new data set in a given reference range;

making a modified new data set by eliminating the portion of the reference range of the new data set that contains a higher data set depth range than the data set depth range of the targeted data set in a given reference range; and

calculating data set values for each endpoint reference of the modified targeted data set and the modified new data set and a data set depth range for the modified targeted data set and the modified new data set.

8. The method of claim 7, wherein constant approximation is applied to the object parameter values and the calculating comprises setting data set values for each endpoint reference of the modified targeted data set and the modified new data set to equal the data set values at the endpoint references of the targeted data set and the new data set, respectively.

9. The method of claim 7, wherein linear approximation is applied to the object parameter values and the calculating comprises computing the data set values at each endpoint reference of the modified targeted data set and the modified new data set using linear interpolation.

10. The method of claim 7, wherein quadratic approximation is applied to the object parameter values and the calculating comprises computing the data set values at each endpoint reference of the modified targeted data set and the modified new data set using quadratic interpolation.

11. The method of claim 7, wherein cubic approximation is applied to the object parameter values and the calculating comprises computing the data set values at each endpoint reference of the modified targeted data set and the modified new data set using cubic interpolation.

12. The method of claim 3, further comprising:

substituting a series of targeted data sets having a contiguous series of reference ranges with a single new data set in the line tree data structure upon detecting that the new data set has a lower data set depth range than the series of the targeted data sets throughout the contiguous series of reference ranges.

13. The method of claim 3, wherein each node of the line tree data structure stores the data set depth range spanned by all its child nodes.

14. The method of claim 13, wherein the data set retrieval procedure comprises:

setting the root node as a current node;

checking the child node to determine whether the child node contains any targeted data sets;

comparing the data set depth range of a child node of the current node to the data set depth range of the new data set;

ending processing of the child node upon determining that the maximum data set value for depth of the child node is less than the minimum data set value for depth of the new data set;

retrieving a targeted data set from the child node upon determining that the child node contains a targeted data set and that the child node is a leaf node;

resetting the child node as a current node upon determining that the child node contains a targeted data set and that the child node is not a leaf node; and

repeating the comparing, ending, checking, retrieving, and resetting for each child node of a current node until all targeted data sets contained in the line tree data structure are retrieved.

15. The method of claim 13, wherein the data set retrieval procedure comprises:

setting the root node as a current node;

checking the child node to determine whether the child node contains any targeted data sets;

comparing the data set depth range of a child node of the current node to the data set depth range of the new data set;

collecting all targeted data sets of the child node upon determining that the maximum data set value for depth of the new data set is less than the minimum data set value for depth of the child node;

retrieving a targeted data set from the child node upon determining that the child node contains a targeted data set and that the child node is a leaf node;

resetting the child node as a current node upon determining that the child node contains a targeted data set and that the child node is not a leaf node; and

repeating the comparing, ending, checking, retrieving, and resetting for each child node of a current node until all targeted data sets contained in the line tree data structure are retrieved.

16. The method of claim 3, wherein the reference range of each data set is uniform in length and the line sample is divided into a fixed number of line sample sub-regions, each line sample sub-region having a fixed starting endpoint and a fixed ending endpoint.

17. The method of claim 16, wherein a data set for a particular line sample sub-region contains data set values at a fixed starting endpoint reference and a fixed ending endpoint reference that correspond to the object parameter values at the fixed starting endpoint and the fixed ending endpoint, respectively, of the particular line sample sub-region.

18. The method of claim 17, wherein the data set contains a fractional overlap value reflecting the proportion of a line sample sub-region that is overlapped by a segment.

19. The method of claim 17, wherein constant approximation is applied to the object parameter values and data set values are contained at only one fixed endpoint reference of the data set.

20. The method of claim 19, wherein the data set values are determined by taking the average of the object parameter values at the fixed starting endpoint and the fixed ending endpoint of the particular line sample sub-region.

21. The method of claim 17, wherein linear approximation is applied to the object parameter values and the data set values at the fixed starting endpoint reference and the fixed ending endpoint reference are computed using linear interpolation.

22. The method of claim 17, wherein quadratic approximation is applied to the object parameter values and the data set values at the fixed starting endpoint reference and the fixed ending endpoint reference are computed using quadratic interpolation.

23. The method of claim 17, wherein cubic approximation is applied to the object parameter values and the data set values at the fixed starting endpoint reference and the fixed ending endpoint reference are computed using cubic interpolation.