Tessellation system

• US 5,428,718 A
• Filed: 01/22/1993
• Issued: 06/27/1995
• Est. Priority Date: 01/22/1993
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Taligent, Inc. (HP Inc.)
• Inventors: Peterson, John, Ho, Hsuen C.
• Primary Examiner(s): Zimmerman, Mark K.
• Application Number:
  US08/007,952
• Time in Patent Office: 886 Days
• Field of Search: 395/121, 395/123, 395/126
• US Class Current: 345/423
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A method and apparatus for tessellating a three-dimensional spline surface into shards operates on a surface which can be separated into columns having a series of subpatches. Each column is processed by performing a series of evaluations upon each of the subpatches of the column. Such evaluations include continuity between subpatches, visibility of subpatches and granularity for discretization of the subpatches and the results are stored within caches. Once the evaluations are completed, a grid which holds the discretized points of each subpatch, is computed by dynamic selection of an algorithm. Thereafter, any cracks between subpatches of the column and between columns are removed. Ultimately, the column is rendered for display. Each of the columns is handled in the same manner so as to ultimately render a set of adjacent columns that form the two-dimensional representation.

Claims

1. A computer implemented method for tessellating a surface which is divided into a plurality of columns, each of the plurality of columns being divided into a plurality of subpatches stored in a memory of said computer and displayed on a display attached to said computer, comprising the steps of:

(a) selecting a column of subpatches from the plurality of columns stored in said memory of said computer for display on said display attached to said computer;

(b) selecting a subpatch from the plurality of subpatches comprising the selected column of subpatches stored in said memory of said computer for display on said display attached to said computer;

(c) determining whether the selected subpatch is visible on said display attached to said computer;

(d) computing a grid of discretized points if the selected subpatch is visible on said display attached to said computer;

(e) removing any cracks between the selected subpatch and a previously selected subpatch by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer; and

(f) converting the grid into a plurality of shards stored in said memory of said computer for display upon said display attached to said computer.

2. A method as recited in claim 1, including the steps of:

(a) removing any cracks between the selected subpatch and subpatches in a previously selected column of subpatches by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer; and

(b) rendering a shard in said memory of said computer for display on said display of said computer from the plurality of shards in the previously selected column of subpatches.

3. A computer implemented method for tessellating a surface having a plurality of subpatches organized within a plurality of columns in a memory of said computer and displaying the resultant image on a display attached to said computer, comprising the steps of:

(a) selecting a column from the plurality of columns and selecting a subpatch within the selected column stored in said memory of said computer for display on said display attached to said computer;

(b) determining whether the selected subpatch is visible on said display attached to said computer;

(c) evaluating the selected subpatch stored in said memory of said computer for display on said display attached to said computer to determine a point computation algorithm when the selected subpatch is visible on said display attached to said computer;

(d) using the algorithm determined in step (c) to compute a grid of discretized points for the selected subpatch stored in said memory of said computer for display on said display attached to said computer; and

(e) removing any crack between the selected subpatch and subpatches in the plurality of columns other than the selected column by repositioning selected ones of discretized points stored in said memory of said computer for display on said display attached to said computer.

4. The method as recited in claim 3, including the step of repeating steps (a) through (e) for each subpatch within the selected column to form a computed column of grids.

5. The method as recited in claim 4, including the steps of:

(a) removing any crack between the selected subpatch and a previously selected column of subpatches by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer; and

(b) rendering a plurality of shards in the previously selected column of subpatches stored in said memory of said computer for display on said display attached to said computer.

6. A computer implemented method for tessellating a surface having a plurality of subpatches organized within a plurality of columns, each of the subpatches having a surface with a surface granularity stored in a memory of said computer for display on a display attached to said computer, comprising the steps of:

(a) selecting a column from the plurality of columns and selecting a subpatch within the selected column stored in said memory of said computer for display on said display attached to said computer;

(b) determining whether the selected subpatch is visible on said display attached to said computer;

(c) evaluating the surface granularity of the selected subpatch to determine a point computation algorithm when the selected subpatch is visible on said display attached to said computer;

(d) using the algorithm determined in step (c) to compute a grid of discretized points for the selected subpatch stored in said memory of said computer for display on said display attached to said computer; and

(e) removing any crack between the selected subpatch and subpatches in the plurality of columns other than the selected column by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer.

7. A method as recited in claim 6, including the step of repeating steps (a) through (e) for each subpatch within the selected column stored in said memory of said computer so as to form a computed column of grids for display on said display attached to said computer.

8. The method as recited in claim 7, including the steps of:

(a) removing any crack between the selected subpatch and a previously selected column of subpatches by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer;

(b) using the grid points in the subpatches of a previously selected column of subpatches to generate a plurality of shards stored in said memory of said computer for display on said display attached to said computer; and

(c) rendering the plurality of shards in the previously selected column of subpatches on said display attached to said computer.

9. A computer implemented method for tessellating a surface having a plurality of subpatches organized within a plurality of columns, each of the subpatches having a surface with a surface granularity stored in a memory of said computer for display on a display attached to said computer, comprising the steps of:

(a) selecting a column from the plurality of columns and selecting a subpatch within the selected column stored in said memory of said computer for display on said display attached to said computer;

(b) determining whether the selected subpatch is visible on said display attached to said computer;

(c) evaluating the surface granularity of the selected subpatch to select either a direct evaluation point computation algorithm or a forward differencing point computation algorithm when the selected subpatch is visible on said display attached to said computer;

(d) using the algorithm determined in step (c) to compute a grid of discretized points for the selected subpatch and storing the points in said memory of said computer for display on said display attached to said computer;

(e) removing any crack between the selected subpatch and a previously selected subpatch in the selected column by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer;

(f) repeating steps (a) through (e) for each subpatch within the selected column so as to form a processed column of subpatches stored in said memory of said computer for display on said display attached to said computer;

(g) removing any crack between the processed column of subpatches and a previously processed column of subpatches by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer;

(h) rendering the previously processed column of subpatches stored in said memory, of said computer for display on said display attached to said computer; and

(i) repeating steps (a) through (h) for a column which is adjacent to the selected column but was not previously selected.

10. A computer implemented method for tessellating a surface having a plurality of subpatches organized within a plurality of columns stored in a memory of said computer for display on a display attached to said computer, comprising the steps of:

(a) selecting a column from the plurality of columns and selecting a subpatch within the selected column stored in said memory of said computer for display on said display attached to said computer;

(b) determining whether the selected subpatch is visible on said display attached to said computer;

(c) evaluating the selected subpatch to determine a point computation algorithm when the selected subpatch is visible on said display attached to said computer,

(d) using the algorithm determined in step (c) to compute a grid of discretized points for the selected subpatch stored in said memory of said computer for display on said display attached to said computer;

(e) removing any crack between the selected subpatch and subpatches in the plurality of columns other than the selected column by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer;

(f) repeating steps (a) through (e) for each subpatch within the selected column so as to form a processed column of subpatches stored in said memory of said computer for display on said display attached to said computer;

(g) removing any crack between the processed column of subpatches and a previously selected column of subpatches by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer;

(h) rendering the previously selected column of subpatches stored in said memory of said computer for display on said display attached to said computer; and

(i) repeating steps (a) through (h) for a column which is adjacent to the selected column but that was not previously selected.

11. A computer implemented method for tessellating a surface stored in ad memory of said computer for display on a display attached to said computer having a plurality of subpatches organized within a plurality of columns stored in said memory of said computer for display on said display attached to said computer, comprising the steps of:

(a) selecting a column from the plurality of columns and selecting a subpatch within the selected column stored in said memory of said computer for display on said display attached to said computer;

(b) determining whether the selected subpatch is visible on said display attached to said computer;

(c) evaluating the selected subpatch to determine a point computation algorithm when the selected subpatch is visible on said display attached to said computer;

(d) using the algorithm determined in step (c) to compute a grid of discretized points for the selected subpatch stored in said memory of said computer for display on said display attached to said computer;

(e) removing any crack between the selected subpatch and subpatches in the plurality of columns other than the selected column by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer;

(f) repeating steps (a) through (e) for each subpatch within the selected column so as to form a processed column of subpatches stored in said memory of said computer for display on said display attached to said computer;

(g) removing any crack between the processed column of subpatches and a previously selected column of subpatches by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer;

(h) rendering the previously selected column of subpatches on said display attached to said computer;

(i) storing the processed subpatches for the selected column in said memory of said computer for display on said display attached to said computer; and

(j) repeating steps (a) through (i) for a column which is adjacent to the selected column but that was not previously selected.

12. A computer implemented method for tessellating a surface having a plurality of subpatches stored in a memory of said computer for display on a display attached to said computer organized within a plurality of columns stored in said memory of said computer for display on said display attached to said computer, comprising the steps of:

(a) selecting a column from the plurality of columns and selecting a subpatch within the selected column stored in said memory of said computer for display on said display attached to said computer;

(b) determining whether the selected subpatch is visible on said display attached to said computer;

(c) evaluating the selected subpatch to determine a point computation algorithm when the selected subpatch is visible on said display attached to said computer;

(d) using the algorithm determined in step (c) to compute a grid of discretized points for the selected subpatch stored in said memory of said computer for display, on said display attached to said computer;

(e) removing any crack between the selected subpatch and subpatches in the plurality of columns other than the selected column by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer;

(f) using the grid of discretized points to generate a plurality of shards for display on said display attached to said computer;

(g) rendering the plurality of shards stored in said memory of said computer for display on said display attached to said computer; and

(h) displaying the rendered shards on said display attached to said computer.

13. An apparatus for tessellating a surface on a computer with a memory and a display attached to said computer said surface is divided into a plurality of columns, each of the plurality of columns being divided into a plurality of subpatches stored in said memory of said computer for display on said display attached to said computer, comprising:

(a) processor means for selecting a column of subpatches from the plurality of columns stored in said memory of said computer for display on said display attached to said computer;

(b) processor means for selecting a subpatch from the plurality of subpatches comprising selected column of subpatches stored in said memory of said computer for display on said display attached to said computer;

(c) processor means for determining whether the selected subpatch is visible on said display attached to said computer;

(d) processor means for computing a grid of discretized points if the selected subpatch is visible on said display attached to said computer;

(e) processor means for removing any cracks between the selected subpatch and a previously selected subpatch by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer; and

(f) processor means for converting the grid into a plurality of shards stored in said memory of said computer for display on said display attached to said computer.

14. An apparatus as recited in claim 13, including:

(a) processor means for removing any cracks between the selected subpatch and subpatches in a previously selected column of subpatches by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer; and

(b) processor means for rendering a plurality of shards in the previously selected column of subpatches stored in said memory of said computer for display on said display attached to said computer.

15. An apparatus for tessellating a surface on a computer with a memory and a display attached to said computer, said surface having a plurality of subpatches organized within a plurality of columns stored in said memory of said computer for display on said display attached to said computer, comprising:

(a) processor means for selecting a column from the plurality of columns and selecting a subpatch within the selected column stored in said memory of said computer for display on said display attached to said computer;

(b) processor means for determining whether the selected subpatch is visible on said display attached to said computer;

(c) processor means for evaluating the selected subpatch to determine a point computation algorithm when the selected subpatch is visible on said display attached to said computer;

(d) processor means responsive to the determined point computation algorithm for computing a grid of discretized points for the selected subpatch stored in said memory of said computer for display on said display attached to said computer; and

(e) processor means for removing any crack between the selected subpatch and subpatches in the plurality of columns other than the selected column by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer.

16. The apparatus as recited in claim 15, including means for computing a grid of discretized points for each subpatch within the selected column and means for removing any cracks between adjacent subpatches in the selected column to form a processed column of subpatches by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer.

17. The apparatus as recited in claim 16, including:

(a) processor means for removing any crack between the selected subpatch and a previously selected column of subpatches by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer; and

(b) processor means for rendering a plurality of shards in the previously selected column of subpatches stored in said memory of said computer for display on said display attached to said computer;

18. An apparatus for tessellating a surface on a computer with a memory and a display attached to said computer having a plurality of subpatches organized within a plurality of columns stored in said memory of said computer for display on said display attached to said computer, each of the subpatches having a surface with a surface granularity stored in said memory of said computer for display on said display attached to said computer, comprising:

(a) processor means for selecting a column from the plurality of columns and selecting a subpatch within the selected column stored in said memory of said computer for display on said display attached to said computer;

(b) processor means for determining whether the selected subpatch is visible on said display attached to said computer;

(c) processor means for evaluating the surface granularity of the selected subpatch to determine a point computation algorithm when the selected subpatch is visible on said display attached to said computer;

(d) processor means responsive to the determined point computation algorithm for computing a grid of discretized points for the selected subpatch stored in said memory of said computer for display on said display attached to said computer; and

(e) processor means for removing any crack between the selected subpatch and subpatches in the plurality of columns other than the selected column by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer.

19. An apparatus as recited in claim 18, including means for computing a grid of discretized points for each subpatch within the selected column and means for removing any cracks between adjacent subpatches in the selected column by repositioning selected ones of the discretized points to form a processed column of subpatches stored in said memory of said computer for display on said display attached to said computer.

20. An apparatus as recited in claim 19, including:

(a) processor means for removing any cracks between the selected subpatch and a previously selected column of subpatches by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer; and

(b) processor means for rendering a plurality of shards in the previously selected column of subpatches stored in said memory of said computer for display on said display attached to said computer.

21. An apparatus for tessellating a surface on a computer with a memory and a display attached to said computer having a plurality of subpatches organized within a plurality of columns stored in said memory of said computer for display on said display attached to said computer, each of the subpatches having a surface with a surface granularity stored in said memory of said computer for display on said display attached to said computer, comprising:

(a) processor means for selecting a column from the plurality of columns and selecting a subpatch within the selected column stored in said memory of said computer for display on said display attached to said computer;

(b) processor means for determining whether the selected subpatch is visible on said display attached to said computer;

(c) processor means for evaluating the surface granularity of the selected subpatch to determine a point computation algorithm when the selected subpatch is visible on said display attached to said computer;

(d) processor means responsive to the determined point computation algorithm for computing a grid of discretized points for the selected subpatch stored in said memory of said computer for display on said display attached to said computer;

(e) processor means for removing any crack between the selected subpatch and subpatches in the plurality of columns other than the selected column by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer;

(f) processor means for sequentially processing each subpatch within the selected column so as to form a processed column of subpatches stored in said memory of said computer for display on said display attached to said computer;

(g) processor means for removing any crack between the processed column of subpatches and a previously selected column of subpatches stored in said memory of said computer for display on said display attached to said computer;

(h) processor means for rendering the previously selected column of subpatches stored in said memory of said computer for display on said display attached to said computer; and

(i) processor means for sequentially rendering a column of subpatches stored in said memory of said computer for display on said display attached to said computer which is adjacent to a selected column but that was not previously selected.

22. An apparatus for tessellating a surface on a computer with a memory and a display attached to said computer having a plurality of subpatches organized within a plurality of columns stored in said memory of said computer for display of said display attached to said computer, comprising:

(a) processor means for selecting a column from the plurality of columns and selecting a subpatch within the selected column stored in said memory of said computer for display on said display attached to said computer;

(b) processor means for determining whether the selected subpatch is visible on said display attached to said computer;

(c) processor means for evaluating the selected subpatch to determine a point computation algorithm when the selected subpatch is visible on said display attached to said computer;

(d) processor means responsive to the determined point computation algorithm for computing a grid of discretized points for the selected subpatch stored in said memory of said computer for display on said display attached to said computer;

(e) processor means for removing any crack between the selected subpatch and subpatches in the plurality of columns other than the selected column by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer;

(f) processor means for sequentially processing each subpatch within the selected column so as to form a processed column of subpatches stored in said memory of said computer for display on said display attached to said computer;

(g) processor means for removing any crack between the processed column of subpatches and a previously selected column of subpatches by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer;

(h) processor means for rendering the previously selected column of subpatches on said display attached to said computer; and

(i) processor means for sequentially rendering a column of subpatches stored in said memory of said computer for display on said display attached to said computer which is adjacent to a selected column but that was not previously selected.

23. An apparatus for tessellating a surface on a computer with a memory and a display attached to said computer having a plurality of subpatches organized within a plurality of columns stored in said memory of said computer for display on said display attached to said computer comprising:

(a) processor means for selecting a column from the plurality of columns and selecting a subpatch within the selected column stored in said memory of said computer for display on said display attached to said computer;

(b) processor means for determining whether the selected subpatch is visible on said display attached to said computer;

(c) processor means for evaluating the selected subpatch to determine a point computation algorithm when the selected subpatch is visible on said display attached to said computer;

(d) processor means responsive to the determined point computation algorithm for computing a grid of discretized points for the selected subpatch stored in said memory of said computer for display on said display attached to said computer;

(e) processor means for removing any crack between the selected subpatch and subpatches in the plurality of columns other than the selected column by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer;

(f) processor means for sequentially processing each subpatch within the selected column so as to form a processed column of subpatches stored in said memory of said computer for display on said display attached to said computer;

(g) processor means for removing any crack between the processed column of subpatches and a previously selected column of subpatches by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer;

(h) processor means for rendering the previously selected column of subpatches stored in said memory of said computer for display on said display attached to said computer;

(i) storage means for maintaining the processed subpatches for the selected column in said memory of said computer for display on said display attached to said computer; and

(j) processor means for sequentially rendering a column of subpatches stored in said memory of said computer for display on said display attached to said computer which is adjacent to a selected column but that was not previously selected.

24. An apparatus for tessellating a surface on a computer with a memory and a display attached to said computer having a plurality of subpatches organized within a plurality of columns stored in said memory of said computer for display on said display attached to said computer, comprising:

(a) processor means for selecting a column from the plurality of columns and selecting a subpatch within the selected column stored in said memory of said computer for display on said display attached to said computer;

(b) processor means for determining whether the selected subpatch is visible on said display attached to said computer;

(c) processor means for evaluating the selected subpatch to determine a point computation algorithm when the selected subpatch is visible on said display attached to said computer;

(d) processor means responsive to the determined point computation algorithm for computing a grid of discretized points for the selected subpatch stored in said memory of said computer for display on said display attached to said computer;

(e) processor means for removing any crack between the selected subpatch and subpatches in the plurality of columns other than the selected column by repositioning selected ones of the discretized points stored in said memory of said computer for display on said display attached to said computer;

(f) processor means responsive to the grid of discretized points for generating a plurality of shards stored in said memory of said computer for display on said display attached to said computer;

(g) processor means for rendering the plurality of shards on said display attached to said compute; and

(h) processor means for displaying the rendered shards on said display attached to said computer.