Rendering 3D surfaces through limit surface projections

US 6,525,727 B1
Filed: 10/29/1999
Issued: 02/25/2003
Est. Priority Date: 10/29/1999
Status: Expired due to Term

First Claim

Patent Images

1. A computer-implemented method for use in rendering a 3D surface, the method comprising:

obtaining an initial digital data set that defines a base mesh coarsely approximating the 3D surface, where the base mesh includes vertices connected to form 2D faces;

subdividing the 2D faces of the base mesh one or more times to form one or more subdivision meshes, where each subdivision mesh more closely approximates the 3D surface than each preceding mesh, and where each subdivision mesh includes more vertices than each preceding mesh;

for each subdivision mesh, applying a computer-implemented algorithm to the vertices in the subdivision mesh to project the vertices onto a limit surface that represents the actual shape of the 3D surface, where the projected vertices define a projected surface; and

for each subdivision mesh, rendering an image of the projected surface instead of an image of the subdivision mesh.

View all claims

1 Assignment

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

In rendering a 3D surface, a computer obtains an initial digital data set that defines a base mesh coarsely approximating the 3D surface, where the base mesh includes vertices connected to form 2D faces. The computer subdivides the 2D faces of the base mesh one or more times to form one or more subdivision meshes, where each subdivision mesh more closely approximates the 3D surface than each preceding mesh, and where each subdivision mesh includes more vertices than each preceding mesh. For each subdivision mesh, the computer applies a computer-implemented algorithm to the vertices in the subdivision mesh to project the vertices onto a limit surface that represents the actual shape of the 3D surface, where the projected vertices define a projected surface. The computer then renders an image of the projected surface for the subdivision mesh instead of rendering an image of the subdivision mesh itself.

35 Citations

View as Search Results

30 Claims

1. A computer-implemented method for use in rendering a 3D surface, the method comprising:
- obtaining an initial digital data set that defines a base mesh coarsely approximating the 3D surface, where the base mesh includes vertices connected to form 2D faces;
  
  subdividing the 2D faces of the base mesh one or more times to form one or more subdivision meshes, where each subdivision mesh more closely approximates the 3D surface than each preceding mesh, and where each subdivision mesh includes more vertices than each preceding mesh;
  
  for each subdivision mesh, applying a computer-implemented algorithm to the vertices in the subdivision mesh to project the vertices onto a limit surface that represents the actual shape of the 3D surface, where the projected vertices define a projected surface; and
  
  for each subdivision mesh, rendering an image of the projected surface instead of an image of the subdivision mesh.
- View Dependent Claims (2, 3, 4, 5, 6, 7)
- - 2. The method of claim 1, wherein applying the computer-implemented algorithm includes, for each subdivision mesh, inserting the vertices for the subdivision mesh into a predetermined equation.
  - 3. The method of claim 2, wherein the equation includes a factor that accounts for the projection of the vertices onto the limit surface.
  - 4. The method of claim 1, wherein subdividing includes inserting the vertices from a mesh to be subdivided into a predetermined equation.
  - 5. The method of claim 4, wherein inserting the vertices from the mesh to be subdivided into a predetermined equation includes inserting the vertices into the following equation:
    - $v^{r + 1} = \frac{α (n) v^{r} + v_{1}^{r} + \dots + v_{n}^{r}}{α (n) + n},$
6. The method of claim 4, wherein applying a computer-implemented algorithm to the vertices in a subdivision mesh to project the vertices onto a limit surface includes:
- changing at least one factor in the predetermined equation; and
  
  then inserting the vertices into the predetermined equation.
7. The method of claim 6, wherein changing at least one live factor includes replacing the weighting function α
- (n) with a modified weighting function ε
  
  (n).

8. A computer-implemented method for use in rendering a 3D surface, the method comprising:
- obtaining an initial digital data set that defines a base mesh coarsely approximating the 3D surface, where the base mesh includes vertices connected to form 2D faces;
  
  subdividing the 2D faces of the base mesh one or more times to form one or more subdivision meshes, where each subdivision mesh more closely approximates the 3D surface than each preceding mesh, and where each subdivision mesh includes more vertices than each preceding mesh;
  
  for each subdivision mesh, applying a computer-implemented algorithm to the vertices in the subdivision mesh to project the vertices onto a limit surface that represents the actual shape of the 3D surface, where the projected vertices define a projected surface, and where applying the computer-implemented algorithm includes inserting the vertices in the subdivision mesh into a predetermined equation that includes a factor that accounts for the projection of the vertices onto the limit surface and that is calculated by solving the following equation;
  
  $ɛ (n) = \frac{3 n}{4 a (n)},$ where $a (n) = \frac{5}{8} - \frac{{(3 + 2 \cos (2 π / n))}^{2}}{64},$
  
  and where n represents the number of vertices in a neighborhood surrounding a particular vertex; and
  
  for each subdivision mesh, rendering an image of the projected surface instead of an image of the subdivision mesh.

9. A computer-implemented method for use in rendering a 3D surface, the method comprising:
- obtaining an initial digital data set that defines a base mesh coarsely approximating the 3D surface, where the base mesh includes vertices connected to form 2D faces;
  
  subdividing the 2D faces of the base mesh one or more times to form one or more subdivision meshes, where each subdivision mesh more closely approximates the 3D surface than each preceding mesh, and where each subdivision mesh includes more vertices than each preceding mesh;
  
  for each subdivision mesh, applying a computer-implemented algorithm to the vertices in the subdivision mesh to project the vertices onto a limit surface that represents the actual shape of the 3D surface, where the projected vertices define a projected surface, and where applying the computer-implemented algorithm includes inserting the vertices into the following equation;
  
  $v^{r + 1} = \frac{ɛ (n) v^{r} + v_{1}^{r} + \dots + v_{n}^{r}}{ɛ (n) + n},$
  
  where n represents the number of vertices in a neighborhood surrounding a particular vertex v^r, where r represents the number of subdivisions applied to the bash mesh to derive the subdivision mesh, and where ε
  
  (n) is a weighting function described by the equation;
  
  $ɛ (n) = \frac{3 n}{4 a (n)},$ where $a (n) = \frac{5}{8} - \frac{{(3 + 2 \cos (2 π / n))}^{2}}{64};$
  
  and for each subdivision mesh, rendering an image of the projected surface instead of an image of the subdivision mesh.

10. A computer-implemented method for use in rendering a 3D surface, the method comprising:
- obtaining an initial digital data set that defines a base mesh coarsely approximating the 3D surface, where the base mesh includes vertices connected to form 2D faces;
  
  subdividing the 2D faces of the base mesh one or more times to form one or more subdivision meshes, where each subdivision mesh more closely approximates the 3D surface than each preceding mesh, where each subdivision mesh includes more vertices than each preceding mesh, and where subdividing includes inserting the vertices from a mesh to be subdivided into a predetermined equation;
  
  for each subdivision mesh, applying a computer-implemented algorithm to the vertices in the subdivision mesh to project the vertices onto a limit surface that represents the actual shape of the 3D surface, where the projected vertices define a projected surface, where applying the computer-implemented algorithm includes replacing the weighting function α
  
  (n) in the predetermined equation with a modified weighting function ε
  
  (n) and then inserting the vertices into the predetermined equation, and where the modified weighting function ε
  
  (n) is calculated according to the following equation;
  
  $ɛ (n) = \frac{3 n}{4 a (n)},$ where $a (n) = \frac{5}{8} - \frac{{(3 + 2 \cos (2 π / n))}^{2}}{64};$
  
  and for each subdivision mesh, rendering an image of the projected surface instead of an image of the subdivision mesh.

11. A computer program, residing on a tangible storage medium, for use in rendering a 3D surface, the program comprising executable instructions that enable a computer to:
- obtain an initial digital data set that defines a base mesh coarsely approximating the 3D surface, where the base mesh includes vertices connected to form 2D faces;
  
  subdivide the 2D faces of the base mesh one or more times to form one or more subdivision meshes, where each subdivision mesh more closely approximates the 3D surface than each preceding mesh, and where each subdivision mesh includes more vertices than each preceding mesh;
  
  for each subdivision mesh, apply a computer-implemented algorithm to the vertices in the subdivision mesh to project the vertices onto a limit surface that represents the actual shape of the 3D surface, where the projected vertices define a projected surface; and
  
  for each subdivision mesh, render an image of the projected surface instead of an image of the subdivision mesh.
- View Dependent Claims (12, 13, 14, 15, 16, 17)
- - 12. The program of claim 11, wherein, in applying the computer-implemented algorithm, the computer, for each subdivision mesh, inserts the vertices for the subdivision mesh into a predetermined equation.
  - 13. The program of claim 12, wherein the equation includes a factor that accounts for the projection of the vertices onto the limit surface.
  - 14. The program of claim 11, wherein, in subdividing, the computer inserts the vertices from a mesh to be subdivided into a predetermined equation.
  - 15. The program of claim 14, wherein, in inserting the vertices from the mesh to be subdivided into a predetermined equation, the computer inserts the vertices into the following equation:
    - $v^{r + 1} = \frac{α (n) v^{r} + v_{1}^{r} + \dots + v_{n}^{r}}{α (n) + n},$
16. The program of claim 14, wherein, in applying the computer-implemented algorithm to the vertices in a subdivision mesh to project the vertices onto a limit surface, the computer changes at least one factor in the predetermined equation and then inserts the vertices into the predetermined equation.
17. The program of claim 16, wherein, in changing at least one factor, the computer replaces the weighting function α
- (n) with a modified weighting function ε
  
  (n).

18. A computer program, residing on a tangible storage medium, for use in rendering a 3D surface, the program comprising executable instructions that enable a computer to:
- obtain an initial digital data set that defines a base mesh coarsely approximating the 3D surface, where the base mesh includes vertices connected to form 2D faces;
  
  subdivide the 2D faces of the base mesh one or more times to form one or more subdivision meshes, where each subdivision mesh more closely approximates the 3D surface than each preceding mesh, and where each subdivision mesh includes more vertices than each preceding mesh;
  
  for each subdivision mesh, apply a computer-implemented algorithm to the vertices in the subdivision mesh to project the vertices onto a limit surface that represents the actual shape of the 3D surface, where the projected vertices define a projected surface, and where, in applying the computer-implemented algorithm, the computer inserts the vertices in the subdivision mesh into a predetermined equation that includes a factor that accounts for the projection of the vertices onto the limit surface and that is calculated by solving the following equation;
  
  $ɛ (n) = \frac{3 n}{4 a (n)},$ where $a (n) = \frac{5}{8} - \frac{{(3 + 2 \cos (2 π / n))}^{2}}{64},$
  
  and where n represents the number of vertices in a neighborhood surrounding a particular vertex; and
  
  for each subdivision mesh, render an image of the projected surface instead of an image of the subdivision mesh.

19. A computer program, residing on a tangible storage medium, for use in rendering a 3D surface, the program comprising executable instructions that enable a computer to:
- obtain an initial digital data set that defines a base mesh coarsely approximating the 3D surface, where the base mesh includes vertices connected to form 2D faces;
  
  subdivide the 2D faces of the base mesh one or more times to form one or more subdivision meshes, where each subdivision mesh more closely approximates the 3D surface than each preceding mesh, and where each subdivision mesh includes more vertices than each preceding mesh;
  
  for each subdivision mesh, apply a computer-implemented algorithm to the vertices in the subdivision mesh to project the vertices onto a limit surface that represents the actual shape of the 3D surface, where the projected vertices define a projected surface, and where, in applying the computer-implemented algorithm, the computer inserts the vertices into the following equation;
  
  $v^{r + 1} = \frac{ɛ (n) v^{r} + v_{1}^{r} + \dots + v_{n}^{r}}{ɛ (n) + n},$ where n represents the number of vertices in a neighborhood surrounding a particular vertex v^r, where r represents the number of subdivisions applied to the bash mesh to derive the subdivision mesh, and where ε
  
  (n) is a weighting function described by the equation;
  
  $ɛ (n) = \frac{3 n}{4 a (n)},$ where $a (n) = \frac{5}{8} - \frac{{(3 + 2 \cos (2 π / n))}^{2}}{64};$
  
  and for each subdivision mesh, render an image of the projected surface instead of an image of the subdivision mesh.

20. A computer program, residing on a tangible storage medium, for use in rendering a 3D surface, the program comprising executable instructions that enable a computer to:
- obtain an initial digital data set that defines a base mesh coarsely approximating the 3D surface, where the base mesh includes vertices connected to form 2D faces;
  
  subdivide the 2D faces of the base mesh one or more times to form one or more subdivision meshes, where each subdivision mesh more closely approximates the 3D surface than each preceding mesh, where each subdivision mesh includes more vertices than each preceding mesh, and where, in subdividing, the computer inserts the vertices from a mesh to be subdivided into a predetermined equation;
  
  for each subdivision mesh, apply a computer-implemented algorithm to the vertices in the subdivision mesh to project the vertices onto a limit surface that represents the actual shape of the 3D surface, where the projected vertices define a projected surface, where, in applying the computer-implemented algorithm, the computer replaces the weighting function α
  
  (n) in the predetermined equation with a modified weighting function ε
  
  (n) and then inserts the vertices into the predetermined equation, and where the modified weighting function ε
  
  (n) is calculated according to the following equation;
  
  $ɛ (n) = \frac{3 n}{4 a (n)},$ where $a (n) = \frac{5}{8} - \frac{{(3 + 2 \cos (2 π / n))}^{2}}{64};$
  
  and for each subdivision mesh, render an image of the projected surface instead of an image of the subdivision mesh.

21. A computer system comprising:
- a processor and a memory device coupled to a system bus;
  
  a display device operable to display rendered images of a 3D surface;
  
  a graphics controller configured to receive data from the system bus and use the data in rendering the 3D surface on the display device; and
  
  a 3D graphics program loaded into the memory device to assist the processor in delivering the data to the graphics controller, the 3D graphics program comprising executable instructions that cause the processor to;
  
  obtain an initial digital data set that defines a base mesh coarsely approximating the 3D surface, where the base mesh includes vertices connected to form 2D faces;
  
  subdivide the 2D faces of the base mesh one or more times to form one or more subdivision meshes, where each subdivision mesh more closely approximates the 3D surface than each preceding mesh, and where each subdivision mesh includes more vertices than each preceding mesh;
  
  for each subdivision mesh, apply a computer-implemented algorithm to the vertices in the subdivision mesh to project the vertices onto a limit surface that represents the actual shape of the 3D surface, where the projected vertices define a projected surface; and
  
  for each subdivision mesh, render an image of the projected surface instead of an image of the subdivision mesh.
- View Dependent Claims (22, 23, 24, 25, 26, 27)
- - 22. The system of claim 21, wherein, in applying the computer-implemented algorithm, the processor, for each subdivision mesh, inserts the vertices for the subdivision mesh into a predetermined equation.
  - 23. The system of claim 22, wherein the equation includes a factor that accounts for the projection of the vertices onto the limit surface.
  - 24. The system of claim 21, wherein, in subdividing, the processor inserts the vertices from a mesh to be subdivided into a predetermined equation.
  - 25. The system of claim 24, wherein, in inserting the vertices from the mesh to be subdivided into a predetermined equation, the processor inserts the vertices into the following equation:
    - $v^{r + 1} = \frac{α (n) v^{r} + v_{1}^{r} + \dots + v_{n}^{r}}{α (n) + n},$
26. The system of claim 24, wherein, in applying the computer-implemented algorithm to the vertices in a subdivision mesh to project the vertices onto a limit surface, the processor changes at least one factor in the predetermined equation and then inserts the vertices into the predetermined equation.
27. The system of claim 26, wherein, in changing at least one factor, the processor replaces the weighting function α
- (n) with a modified weighting function ε
  
  (n).

28. A computer system comprising:
- a processor and a memory device coupled to a system bus;
  
  a display device operable to display rendered images of a 3D surface;
  
  a graphics controller configured to receive data from the system bus and use the data in rendering the 3D surface on the display device; and
  
  a 3D graphics program loaded into the memory device to assist the processor in delivering the data to the graphics controller, the 3D graphics program comprising executable instructions that cause the processor to;
  
  obtain an initial digital data set that defines a base mesh coarsely approximating the 3D surface, where the base mesh includes vertices connected to form 2D faces;
  
  subdivide the 2D faces of the base mesh one or more times to form one or more subdivision meshes, where each subdivision mesh more closely approximates the 3D surface than each preceding mesh, and where each subdivision mesh includes more vertices than each preceding mesh;
  
  for each subdivision mesh, apply a computer-implemented algorithm to the vertices in the subdivision mesh to project the vertices onto a limit surface that represents the actual shape of the 3D surface, where the projected vertices define a projected surface, and where, in applying the computer-implemented algorithm, the processor inserts the vertices in the subdivision mesh into a predetermined equation that includes a factor that accounts for the projection of the vertices onto the limit surface and that is calculated by solving the following equation;
  
  $ɛ (n) = \frac{3 n}{4 a (n)},$ where $a (n) = \frac{5}{8} - \frac{{(3 + 2 \cos (2 π / n))}^{2}}{64},$
  
  and where n represents the number of vertices in a neighborhood surrounding a particular vertex; and
  
  for each subdivision mesh, render an image of the projected surface instead of an image of the subdivision mesh.

29. A computer system comprising:
- a processor and a memory device coupled to a system bus;
  
  a display device operable to display rendered images of a 3D surface;
  
  a graphics controller configured to receive data from the system bus and use the data in rendering the 3D surface on the display device; and
  
  a 3D graphics program loaded into the memory device to assist the processor in delivering the data to the graphics controller, the 3D graphics program comprising executable instructions that cause the processor to;
  
  obtain an initial digital data set that defines a base mesh coarsely approximating the 3D surface, where the base mesh includes vertices connected to form 2D faces;
  
  subdivide the 2D faces of the base mesh one or more times to form one or more subdivision meshes, where each subdivision mesh more closely approximates the 3D surface than each preceding mesh, and where each subdivision mesh includes more vertices than each preceding mesh;
  
  for each subdivision mesh, apply a computer-implemented algorithm to the vertices in the subdivision mesh to project the vertices onto a limit surface that represents the actual shape of the 3D surface, where the projected vertices define a projected surface, and where, in applying the computer-implemented algorithm, the processor inserts the vertices into the following equation;
  
  $v^{r + 1} = \frac{ɛ (n) v^{r} + v_{1}^{r} + \dots + v_{n}^{r}}{ɛ (n) + n},$ where n represents the number of vertices in a neighborhood surrounding a particular vertex v^r, where r represents the number of subdivisions applied to the bash mesh to derive the subdivision mesh, and where ε
  
  (n) is a weighting function described by the equation;
  
  $ɛ (n) = \frac{3 n}{4 a (n)},$ where $a (n) = \frac{5}{8} - \frac{{(3 + 2 \cos (2 π / n))}^{2}}{64};$
  
  for each subdivision mesh, render an image of the projected surface instead of an image of the subdivision mesh.

30. A computer system comprising:
- a processor and a memory device coupled to a system bus;
  
  a display device operable to display rendered images of a 3D surface;
  
  a graphics controller configured to receive data from the system bus and use the data in rendering the 3D surface on the display device; and
  
  a 3D graphics program loaded into the memory device to assist the processor in delivering the data to the graphics controller, the 3D graphics program comprising executable instructions that cause the processor to;
  
  obtain an initial digital data set that defines a base mesh coarsely approximating the 3D surface, where the base mesh includes vertices connected to form 2D faces;
  
  subdivide the 2D faces of the base mesh one or more times to form one or more subdivision meshes, where each subdivision mesh more closely approximates the 3D surface than each preceding mesh, where each subdivision mesh includes more vertices than each preceding mesh, and where, in subdividing, the processor inserts the vertices from a mesh to be subdivided into a predetermined equation;
  
  for each subdivision mesh, apply a computer-implemented algorithm to the vertices in the subdivision mesh to project the vertices onto a limit surface that represents the actual shape of the 3D surface, where the projected vertices define a projected surface, where, in applying the computer-implemented algorithm, the processor replaces the weighting function α
  
  (n) in the predetermined equation with a modified weighting function ε
  
  (n) and then inserts the vertices into the predetermined equation, and where the modified weighting function ε
  
  (n) is calculated according to the following equation;
  
  $ɛ (n) = \frac{3 n}{4 a (n)},$ where $a (n) = \frac{5}{8} - \frac{{(3 + 2 \cos (2 π / n))}^{2}}{64};$
  
  and for each subdivision mesh, render an image of the projected surface instead of an image of the subdivision mesh.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
Intel Corporation
Original Assignee
Intel Corporation
Inventors
Lake, Adam T., Junkins, Stephen
Primary Examiner(s)
Padmanabhan, Mano

Application Number

US09/430,621
Time in Patent Office

1,215 Days
Field of Search

345/419, 345/420, 345/421, 345/423, 345/427, 345/428, 345/441-443, 345/582, 345/606, 345/611
US Class Current

345/423
CPC Class Codes

G06T 17/20 Finite element generation, ...

Rendering 3D surfaces through limit surface projections

First Claim

1 Assignment

0 Petitions

Accused Products

Abstract

35 Citations

30 Claims

Specification

Solutions

Use Cases

Quick Links

Rendering 3D surfaces through limit surface projections

First Claim

1 Assignment

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

35 Citations

30 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links