Spatial patches for graphics rendering

• US 20020171644A1
• Filed: 03/31/2001
• Published: 11/21/2002
• Est. Priority Date: 03/31/2001
• Status: Active Grant

• Current Assignee: Intel Corporation, Moscow State University (Moscow State University Lomonosov)
• Original Assignee: Moscow State University (Moscow State University Lomonosov)
• Inventors: Reshetov, Alexander V., Yakovlev, Alexander N., Ivanov, Denis V., Kuzmin, Yevgeniy P.
• Granted Patent: US 7,102,636 B2
• Time in Patent Office: Days
• US Class Current: 345/420
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

Described are a novel graphical element known as a spatial patch and a system and method for rendering the spatial patch to create computer graphics. The spatial patch may include appearance data and displacement data for each of a plurality of nodes that together specify the color and geometry for typically a small portion of a surface of an object. The appearance and displacement data may be independent and irregular for each of the nodes in order to represent complexly colored and structured objects. The spatial patch may be processed independently and may have internal topology or structure to facilitate parallel processing. Accordingly, the spatial patch offers many quality and processing advantages over polygon mesh representations that have previously been used to create three-dimensional computer graphics.

Claims

1. A method comprising:

accessing graphical data for a plurality of nodes that represent a portion of a surface of a three-dimensional object, the graphical data including coordinate system data that indicates a coordinate system for the plurality of nodes, appearance data that indicates an appearance for each of the plurality of nodes, and displacement data that indicates a displacement for each of the plurality of nodes;

creating a computer graphics representation of the portion of the surface of the three-dimensional object by rendering the graphical data for the plurality of nodes; and

presenting the computer graphics representation on a presentation device.

2. The method of claim 1, wherein accessing the graphical data includes accessing appearance data that indicates an independent color for each of the plurality of nodes and displacement data that indicates an independent displacement for each of the plurality of nodes.

3. The method of claim 1, wherein accessing the graphical data includes accessing coordinate system data that indicates a coordinate system that is local to the plurality of nodes.

4. The method of claim 1:

wherein accessing the graphical data includes accessing node coordinate data for each of the plurality of nodes and accessing coordinate system data that implicitly creates a structural arrangement for the plurality of nodes; and

wherein creating includes using the node coordinate data to determine coordinates for each of the plurality of nodes in the structural arrangement.

5. The method of claim 4, further comprising determining coordinates for a displaced node by applying a displacement indicated in the displacement data to one of the plurality of nodes with a determined position.

6. The method of claim 1, wherein creating comprises:

determining coordinates for a displaced node by combining a displacement associated with the displacement data with coordinates of a node of the plurality of nodes indicated by the graphical data; and

projecting the coordinates of the displaced node to a two-dimensional plane corresponding to a viewing surface of the presentation device.

7. The method of claim 1, wherein creating comprises determining whether at least a portion of the plurality of nodes lie within a view volume by performing visibility processing including:

generating a bounding solid that completely contains the plurality of nodes;

rejecting the plurality of nodes if all extents of the bounding solid lie outside of extents of a view volume that is used to test for visibility; and

accepting the plurality of nodes if at least some of the extents of the bounding solid lie inside of extents of the view volume.

8. The method of claim 1, wherein creating includes removing a node of the plurality of nodes if the node lies outside of a view volume that distinguishes a portion that is represented in the computer graphics representation from another portion that is not represented in the computer graphics representation by clipping the portion.

9. The method of claim 1, wherein creating includes modifying the color value based on lighting calculations evaluated for the spatial patch, the lighting calculations including calculating a normal vector by forming a vector product of tangents associated with neighboring nodes.

10. The method of claim 1, wherein creating further comprises:

determining four pixels of a quadrilateral that correspond to four nodes of the plurality of nodes, the quadrilateral having a quadrilateral dimension;

determining an inner pixel contained within the quadrilateral by comparing the quadrilateral dimension with a pixel dimension; and

interpolating a value for the inner pixel by using values for at least one of the four pixels.

11. The method of claim 1, wherein accessing graphical data includes accessing a spatial patch having a total number of nodes that is a multiple of 2^Λ

k+1, where k is a positive integer.

13. The machine-readable medium of claim 12, wherein the instructions to access further comprise instructions causing the machine to access a spatial patch having the graphical data, the spatial patch containing graphical data for a total number of nodes that is a multiple of 2^Λ

k+1 nodes, where k is a positive integer.

14. The machine-readable medium of claim 12, wherein the instructions to access graphical data further comprise instructions causing the machine to access appearance data that indicates an independent color for each of at least nine nodes and displacement data that indicates an independent displacement for each of the at least nine nodes.

16. The machine-readable data structure of claim 15, wherein the machine-readable data structure comprises displacement data for each of at least nine points, the displacement data indicating independent and irregular displacements that vary in both magnitude and gradient for each of the at least nine points.

17. The machine-readable data structure of claim 15, wherein the coordinate system data indicates a plane and wherein the displacement data indicates a displacement distance that is relative to the plane.

19. The system of claim 18, further comprising:

a second spatial patch; and

a second spatial patch rendering unit to create computer graphics by rendering the second spatial patch simultaneously with the rendering of the spatial patch.

20. The system of claim 18, wherein the spatial patch comprises color data that indicates a color value for each of a plurality of nodes associated with a surface portion of a graphical object, and wherein the displacement data indicates an independent and irregular displacement distance that varies in both magnitude and gradient for each of the plurality of nodes.

21. The system of claim 18, wherein the spatial patch comprises color data and displacement data for each of a total plurality of nodes, the total plurality of nodes having a total number of nodes that is a multiple of 2^Λ

k+1, where k is a positive integer.

22. The system of claim 18, wherein the spatial patch rendering unit comprises a combination of hardware and software.

12. A machine-readable medium having stored thereon data representing sequences of instructions that when executed cause a machine to:

access graphical data for a plurality of nodes that represent a portion of a surface of a three-dimensional object, the graphical data including coordinate system data that indicates a coordinate system for the plurality of nodes, appearance data that indicates an appearance for each of the plurality of nodes, and displacement data that indicates a displacement for each of the plurality of nodes;

determine a plurality of presentation device coordinates that correspond to the plurality of nodes by processing the graphical data including determining coordinates of a displaced node by combining coordinates for a node with a displacement corresponding to the node; and

store the plurality of presention device coordinates in a memory.

15. A machine-readable data structure stored on a machine-readable medium, comprising:

color data that indicates color values of a plurality of nodes associated with a portion of a surface of an object;

displacement data that indicates a displacement distance for each of the plurality of nodes; and

coordinate system data that indicates a coordinate system of the plurality of nodes.

18. A system comprising:

a memory having a spatial patch stored thereon, the spatial patch comprising color data that indicates a color value associated with at least a portion of the spatial patch, displacement data that indicates a displacement distance for at least a portion of the spatial patch, and coordinate system data that indicates a coordinate system for the spatial patch;

a spatial patch rendering unit to create computer graphics by rendering the spatial patch; and

a display device to display at least the computer graphics.