System and method to obtain surface structures of multi-dimensional objects, and to represent those surface structures for animation, transmission and display

• US 20030052875A1
• Filed: 01/07/2002
• Published: 03/20/2003
• Est. Priority Date: 01/05/2001
• Status: Active Grant

• Current Assignee: Interuniversitair Micro-Electronica Centrum VZW (IMEC International), Vrije Universiteit Brussel
• Original Assignee: Interuniversitair Micro-Electronica Centrum VZW (IMEC International), Vrije Universiteit Brussel
• Inventors: Salomie, Ioan Alexandru
• Granted Patent: US 6,982,710 B2
• Time in Patent Office: Days
• US Class Current: 345/419
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

Four related but independent aspects are described: (1) a method and a system to derive mesh surface descriptions (also called connectivity-wireframes) from objects represented as a scalar field (e.g. discrete multi-dimensional data), scalar functions (e.g. implicit surfaces) or any other surface description, (2) a compact, optionally multi-scalable, optionally view-dependent, optionally animation-friendly, multi-dimensional surface representation method and system comprising a combination of a surface mesh description associated with a reference grid, (3) a digital coding and decoding method and system of a combined surface mesh representation with connectivity information and a reference grid, and (4) a method and system for conversion of other surface descriptions to the combined surface mesh representation and reference grid. The presentation of the surface of an object may be transmitted across a communications channel by means of a bit stream.

Claims

1. A method of preparing data for displaying a surface of an n-dimensional body, n being at least 3, the method comprising the steps of:

obtaining an n-dimensional discrete mesh representation of the surface, the mesh representation of the surface comprising a plurality of boundary nodes, each boundary node lying on or adjacent to the surface, each boundary node being associated with connectivity information preferably comprising representations of up to (n−

1) incoming and/or up to (n−

1) outgoing directions towards 2*(n−

1) adjacent boundary nodes adjacent to the said boundary node, the directions being defined in such a way that the cross product of the up to n−

1 incoming or outgoing directions associated with any boundary node represents a further vector which points away from the surface at that boundary node.

2. The method according to claim 1, further comprising:

generating a polygonal representation of the surface of the object from the plurality of boundary nodes and the connectivity information of those boundary nodes.

3. The method according to claim 1, wherein the step of obtaining a discrete mesh representation of the surface comprises obtaining a grid description of the n-dimensional body, the grid being defined by intersection points of n sets of reference surfaces.

4. The method according to claim 3, wherein at least one boundary node is defined by an intersection point of the grid and an offset.

5. The method according to claim 1, further comprising the step of:

obtaining surface primitives from the polygonal representation of the surface.

6. The method according to claim 5, further comprising rendering the surface from the union of the surface primitives.

7. The method according to claim 1, wherein the step of obtaining a mesh representation of the surface comprises the step of:

determining contours of the surface, each contour lying in a reference surface of up to n−

1 lower dimensions.

8. The method according to claim 3, further comprising the step of storing the mesh representation of the surface in a memory as a plurality of boundary node representations, each representation being a definition of an intersection point in the grid and an associated offset.

9. The method according to claim 1, further comprising the step of transmitting the mesh representation of the surface to a remote location.

10. The method according to claim 9, wherein the transmission step comprises the step of:

generating a bit-stream from a representation of at least one boundary node and the connectivity information of a plurality of boundary nodes as a list of directions starting from the at least one boundary node to reach the plurality of other boundary nodes.

25. A computer program product comprising code segments which when executed on a computer carries out any of the methods in accordance with any of claims 1 to 10 or 16 to 22.

26. A computer program product stored on a data carrier, the computer program product comprising code segments which when executed on a computer carry out any of the methods in accordance with any of claims 1 to 10 or 16 to 22.

11. A system for preparing digital data for displaying a surface of an n-dimensional body, n being at least 3, comprising:

means for obtaining an n-dimensional discrete mesh representation of the surface, the mesh representation of the surface comprising a plurality of boundary nodes, each boundary node lying on or adjacent to the surface, each boundary node being associated with connectivity information preferably comprising representations of up to (n−

1) incoming and/or up to (n-1) outgoing directions towards 2*(n−

1) adjacent boundary nodes adjacent to the said boundary node, the directions being defined in such a way that the cross product of the up to n−

1 incoming or outgoing directions associated with any boundary node represents a further vector which points away from the surface at that boundary node; and

means for generating a polygonal representation of the surface of the object from the plurality of boundary nodes and the connectivity information of those boundary nodes.

12. The system according to claim 11, wherein the means for obtaining a discrete mesh representation of the surface comprises

means for obtaining a grid description of the n-dimensional body, the grid being defined by the intersection points of n sets of reference surfaces.

13. The system according to claim 11, further comprising:

means for generating a bit-stream from a representation of at least one boundary node and the connectivity information of a plurality of boundary nodes as a list of directions starting from the at least one boundary node to reach the plurality of other boundary nodes.

14. A decoder for receiving a data bit-stream representing a surface of an n-dimensional body, n being at least 3, comprising:

means for receiving the bit-stream comprising a representation of at least one boundary node, and connectivity information as a list of directions starting from the at least one boundary node to reach a plurality of other boundary nodes of the surface to be represented,

means for initializing an n-dimensional mesh at a first resolution;

means for reading the representation of the at least one boundary node;

means for reading the connectivity information of a first number of boundary nodes and for initializing nodes of the mesh in accordance with the connectivity information.

15. The decoder according to claim 14, further comprising:

means for receiving connectivity information of a second number of boundary nodes; and

means for initializing a further set of boundary nodes in the mesh to allow a higher resolution display of the surface.

16. A method of decoding a data bit-stream representing a surface of an n-dimensional body, n being at least 3, comprising:

receiving a bit-stream comprising a representation of at least one boundary node, and connectivity information as a list of directions starting from the at least one boundary node to reach a plurality of other boundary nodes of the surface to be represented,

initializing a grid at a first resolution;

reading the representation of the at least one boundary node;

reading the connectivity information of a first number of boundary nodes and initializing boundary nodes within the grid in accordance with the connectivity information.

17. The method according to claim 16, further comprising the step of receiving connectivity information of a second number of boundary nodes;

and initializing a further set of boundary nodes in the grid to allow a higher resolution display of the surface.

18. The method according to claim 16, further comprising generating a polygonal representation of the surface of the object from the plurality of boundary nodes and the connectivity information of those boundary nodes.

19. The method according to claim 18, further comprising the step of obtaining surface primitives from the polygonal representation of the surface.

20. The method according to claim 19, further comprising the step of rendering the surface from the union of the surface primitives.

21. The method according to claim 16, further comprising the step of:

receiving in the bit-stream for at least one node a precision definition; and

modifying the position of the at least one boundary node in the grid in accordance with at least a part of the precision definition.

22. The method according to claim 16, further comprising generating a mesh description of the surface, the mesh description comprising a set of boundary nodes defined by intersection points in the grid and offsets from this grid.

23. A coder for preparing data for displaying a surface of an n-dimensional body, n being at least 3, the coder comprising:

means for generating an n-dimensional discrete mesh representation of the surface, the mesh representation of the surface comprising a plurality of boundary nodes, each boundary node lying on or adjacent to the surface, each boundary node being associated with connectivity information preferably comprising representations of up to (n−

1) incoming and/or up to (n−

1) outgoing directions towards 2*(n−

1) adjacent boundary nodes adjacent to the said boundary node, the directions being defined in such a way that the cross product of the up to n−

1 incoming or outgoing directions associated with any boundary node represents a further vector which points away from the surface at that boundary node.

24. A bit-stream coding an n-dimensional discrete mesh representation of a surface, the mesh representation of the surface comprising a plurality of boundary nodes, each boundary node lying on or adjacent to the surface, each boundary node being associated with connectivity information preferably comprising representations of up to (n−

1) incoming and/or up to (n−

1) outgoing directions towards 2*(n−

1) adjacent boundary nodes adjacent to the said boundary node, the directions being defined in such a way that the cross product of the up to n−

1 incoming or outgoing directions associated with any boundary node represents a further vector which points away from the surface at that boundary node;

the bit-stream comprising;

a representation of at least one boundary node and the connectivity information of a plurality of boundary nodes as a list of directions starting from the at least one boundary node to reach the plurality of other boundary nodes.