Method for generating graphical object represented as surface elements

• US 6,498,607 B1
• Filed: 01/29/1999
• Issued: 12/24/2002
• Est. Priority Date: 01/29/1999
• Status: Expired due to Fees

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Pfister, Hanspeter, van Baar, Jeroen, Oosterbaan, Collin E.
• Primary Examiner(s): Zimmerman, Mark
• Assistant Examiner(s): Nguyen, Kimbinh T.
• Application Number:
  US09/240,279
• Time in Patent Office: 1,425 Days
• Field of Search: 345/424, 345/419, 345/422, 345/427, 345/421, 345/426, 345/423, 345/430, 345/431, 345/441, 345/420, 345/425, 345/433, 345/436, 345/619, 345/581, 382/131
• US Class Current: 345/423
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

Provided is a method for representing a graphic object in a memory. A surface of the object is partitioned into a plurality of cells having a grid resolution related to an image plane resolution. Each cell is bounded by eight grid points related to the image plane resolution. A single zero-dimensional surface element is stored in the memory for each cell located on the surface of the object. The surface elements in adjacent cells are connected by links, and attributes of the portion of the object contained in the cell are assigned to each surface element and each link.

Claims

1. A method for generating a representation of a graphic object in a memory, comprising:

partitioning a surface of the object into a plurality of cells having a grid resolution related to a resolution of an image plane;

storing a single zero-dimensional surface element in the memory for each cell located on the surface of the object;

connecting the surface elements in adjacent cells by links;

assigning attributes of the portion of the object contained in the cell to each surface element and each link; and

rendering the attributed surface elements on an output device.

2. The method of claim 1 wherein each cell is bounded by eight grid points related to the image plane resolution.

3. The method of claim 1 wherein the object attributes assigned to each surface element includes a position of the surface element on the surface of the object, a color and opacity of the portion of the object in the corresponding cell, a normal to the surface in the corresponding cell, and offsets to surfels in the adjacent cells.

4. The method of claim 1 wherein the object attributes assigned to each surface element includes a velocity and a mass of the portion of the object in the corresponding cell.

5. The method of claim 1 wherein the object attributes assigned to each link includes a rest length of the distance between two adjacent surface elements connected by the link.

6. The method of claim 1 wherein the object attributes assigned to each cell includes an elastic and damping constant associated with the link.

7. The method of claim 1 wherein six adjacent surface elements are 8-connected.

8. The method of claim 1 wherein each surface element is generated from an analytical function.

9. The method of claim 1 wherein each surface element is generated from polygons representing the surface of the object.

10. The method of claim 9 wherein the generating uses a three-dimensional digital differential analyzer to rasterize the polygons.

11. The method of claim 9 wherein the generating uses a distance map of the surface of the object.

12. The method of claim 1 wherein each surface element is generated from voxels at a surface of a volume data set representing the object.

13. The method of claim 1 wherein each surface element is generated from a particle cloud representing the object.

14. The method of claim 9 wherein the surface elements are a three-dimensional scan conversion of lines parallel to a base edge of each polygon, the lines bounded by guidance-edges of the polygon.

15. The method of claim 9 wherein the polygons are triangles.

16. The method of claim 9 further including generating additional surface elements inside each element to provide 8-connectivity between six adjacent surface elements.

17. The method of claim 11 wherein the distance map stores the shortest distance to the surface of the object for each surface element.

18. The method of claim 11 wherein gradients in the distance map define the direction of surface normals.

19. The method of claim 11 further comprising the steps of:

estimating surface polygons for the object, the surface polygons stored as tri-strips of triangles in the memory;

determining a bounding box for the estimated surface polygons;

defining a grid around the tri-strips, the grid having the image plane resolution, and the grid being larger than the bounding box;

determining a smallest distance to each triangle for each integer grid point position;

adding surface elements to the sequential list for each grid position that has a distance equal or smaller than ½

2.

20. The method of claim 1 including arranging the attributed surface elements and attributed links in a sequential list of the memory.

21. The method of claim 1 including generating a plurality of representations of the graphic object, each of the plurality of representations having a different level of detail.

22. The method of claim 21 further comprising:

combining adjacent surfels into a low resolution surfel to generate a lower level of detail representation from a higher level of detail representation.

23. The method of claim 22 wherein attributes of four adjacent surfels are averaged.

24. A system for generating a representation of a graphic object in a memory, comprising:

means for partitioning a surface of the object into a plurality of cells having a grid resolution related to a resolution of an image plane;

a memory storing a single zero-dimensional surface element for each cell located on the surface of the object;

links for connecting the surface elements in adjacent cells;

means for assigning attributes of the portion of the object contained in the cell to each surface element and each link; and

means for rendering the attributed surface elements on an output device.

25. The system of claim 24 wherein the attributed surface elements and attributed links are stored in the memory as a sequential list.

26. A method for representing a graphic object, comprising:

partitioning a surface of an graphic object into a plurality of grid cells having a grid resolution corresponding to a display resolution;

generating a respective surface element for each of the plurality of grid cells;

assigning attributes of the portion of the graphic object contained in each of the plurality of grid cells to its respective surface element;

representing the graphic object based on the attributed respective surface elements; and

rendering the attributed surface elements on an output device.

27. A method according to claim 26, further comprising:

connecting the respective surface element for each of the plurality cells to each of the respective surface elements for adjacent ones of the plurality of cells.

28. A method according to claim 27, wherein the respective surface element for each of the plurality cells is connected to each of the respective surface elements for the adjacent cells by respective links, and further comprising:

assigning attributes of the portion of the graphic object contained in each of the plurality of cells to the respective links connected to the respective surface element for that cell;

wherein the graphic object is also represented according to the attributed respective links.

29. A method according to claim 26, wherein:

the respective surface element for each of the plurality of cells is a zero-dimensional surface element; and

only one zero-dimensional surface element is generated for each of the plurality of cells.