Dual mesh resampling

• US 20040070586A1
• Filed: 10/11/2002
• Published: 04/15/2004
• Est. Priority Date: 10/11/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines SA (International Business Machines Corporation)
• Inventors: Taubin, Gabriel
• Granted Patent: US 6,943,790 B2
• Time in Patent Office: Days
• US Class Current: 345/423
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 17/205 Re-meshing

Abstract

Methods, systems and apparatus which resample a primal mesh signal composed of primal points associated with primal mesh vertices of a primal mesh connectivity of a primal mesh producing a dual mesh signal composed of dual points associated with primal mesh faces of said primal mesh connectivity. The dual points are computed by minimizing a quadratic energy function. The quadratic energy function is composed of a sum of square terms. The invention also constructs a dual mesh from a primal mesh, with the dual mesh signal constructed with the resampling method. It also smoothes a primal mesh signal of a primal mesh. It also constructs a primal-dual mesh from a primal mesh, with the primal-dual mesh connectivity of said primal-dual mesh constructed using a prior art method, and the primal-dual mesh signal constructed by concatenating said primal mesh signal and a dual mesh signal computed with the resampling method.

Claims

1. A method comprising:

obtaining a polygon mesh having at least one primal mesh signal and a polygon mesh connectivity;

resampling said primal mesh signal to produce a dual mesh signal of said polygon mesh, including the steps of;

using said polygon mesh connectivity to define an energy function relating said dual mesh signal with said primal mesh signal; and

minimizing said energy function with respect to said dual mesh signal while keeping said primal mesh signal fixed to provide values for said dual mesh signal.

2. A method as recited in claim 1, wherein the step of obtaining includes at least one of the following steps:

reading an output from a computer program;

reading from a computer memory buffer;

reading from a display screen buffer;

reading a computer file stored in a nonvolatile storage medium;

reading a computer file stored in a magnetic storage device;

reading a computer file stored in an optical storage device;

reading a computer file stored in a computer network;

scanning a document;

multidimensional scanning from a physical object;

drawing with an electronic tablet;

constructing with an interactive modeling system;

constructing with a computer-aided design system;

constructing with a computer animation system;

reconstructing from multiple photographs; and

using a three-dimensional photography system.

3. A method as recited in claim 1, wherein:

said polygon mesh connectivity includes a plurality of polygon mesh vertices, a plurality of polygon mesh faces, and at least one regular edge, each polygon mesh face having at least three e corners, each corner being a particular polygon mesh vertex from among said plurality of polygon mesh vertices, each regular edge being incident to two polygon mesh vertices and two polygon mesh faces;

said primal mesh signal includes a plurality of primal points, each primal point being a point in an N-dimensional space, each primal point corresponding to a particular polygon mesh vertex from among said plurality of polygon mesh vertices of said polygon mesh connectivity;

said dual mesh signal includes a plurality of dual points, each dual point being a point in said N-dimensional space, each dual point corresponding to a particular polygon mesh face from among said plurality of polygon mesh faces of said polygon mesh connectivity; and

the step of using defines the energy function as the sum of a plurality of square terms, each square term corresponding to a particular regular edge of said polygon mesh connectivity, said square term being the square of a difference term, said difference term being computed by subtracting the sum of two dual points from the sum of two primal points, said two dual points corresponding to the two polygon mesh faces to which said regular edge is incident, said two primal points corresponding to the two polygon mesh vertices to which said regular edge is incident.

4. A method as recited in claim 1, wherein the step of minimizing includes at least one step of:

employing a least squares solver; and

employing a dual resampling algorithm.

5. A method as recited in claim 3, further comprising employing a dual resampling algorithm including the steps of:

determining an iteration stopping criterion;

computing a plurality of face barycenters of the polygon mesh, each face barycenter corresponding to a particular polygon mesh face from among said plurality of polygon mesh faces of said polygon mesh connectivity, each face barycenter being the average of the primal points corresponding to the corners of said polygon mesh face;

initializing each of said dual points as equal to a corresponding face barycenter, both each of said dual points and corresponding face barycenter corresponding to the same polygon mesh face;

recomputing each of said dual points as the sum of said corresponding face barycenter plus one half of a dual Laplacian displacement, said dual Laplacian displacement corresponding to said same polygon mesh face, wherein;

said dual Laplacian displacement computed as the average of a plurality of dual point differences, each dual point difference corresponding to a particular regular edge of said polygon mesh connectivity, each dual point difference computed by subtracting said dual point from a neighbor dual point, and

said neighbor dual point corresponding to a neighbor polygon mesh face, said particular regular edge being incident to said same polygon mesh face and said neighbor polygon mesh face; and

repeating the step of recomputing until the iteration stopping criterion is met.

6. A method as recited in claim 1, wherein the primal mesh signal includes at least one signal taken from a group of signals including:

positions of mesh vertices in N-dimensional space;

normal vectors used for shading;

color vectors used for shading; and

texture coordinates used to render textured polygon meshes.

7. A method as recited in claim 1, wherein the energy function measures at least one distance between primal and dual edges.

8. A method as recited in claim 4, wherein said stopping criterion includes at least one stopping criterion taken from a group of stopping criteria including:

maximal error tolerance; and

maximal number of iterations.

9. A method as recited in claim 1, further comprising:

constructing a dual mesh connectivity from said polygon mesh connectivity, wherein said dual mesh connectivity having a plurality of dual mesh vertices, a plurality of dual mesh faces, and a plurality of dual regular edges, each dual mesh vertex corresponding to one said polygon mesh face of said polygon mesh connectivity, each dual mesh face corresponding to one polygon mesh vertex of said polygon mesh connectivity, each dual regular edge corresponding to one particular regular edge of said polygon mesh connectivity; and

combining said dual mesh signal and said dual mesh connectivity in forming a dual mesh.

10. A method as recited in claim 1, further comprising recomputing said primal mesh signal by minimizing said energy function with respect to said primal mesh signal while keeping said dual mesh signal fixed to provide new values for said primal mesh signal.

11. A method as recited in claim 10, further comprising repeating the steps of resampling and recomputing until a smoothing stopping criterion is met.

12. A method as recited in claim 1, further comprising:

constructing a primal-dual mesh signal by concatenating said primal mesh signal with said dual mesh signal;

constructing a primal-dual mesh connectivity from said polygon mesh connectivity, wherein said primal-dual mesh connectivity having a plurality of primal-dual mesh vertices, and a plurality of primal-dual mesh faces, each primal-dual mesh face corresponding to one particular regular edge of said polygon mesh connectivity, each prima-dual mesh vertex corresponding to at least one of a particular polygon mesh vertex and a particular polygon mesh face of the polygon mesh connectivity; and

constructing a primal-dual mesh by combining said primal-dual mesh signal and said primal-dual mesh connectivity.

13. A method as recited in claim 12, further comprising repeating the steps of constructing until a subdivision stopping criterion is met.

14. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing formation of a dual mesh signal, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 1.

15. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for causing formation of a dual mesh signal, said method steps comprising the steps of claim 1.

16. An apparatus comprising:

means for obtaining a polygon mesh having at least one primal mesh signal and a polygon mesh connectivity;

means for resampling said primal mesh signal to produce a dual mesh signal of said polygon mesh;

means for using said polygon mesh connectivity to define an energy function relating said dual mesh signal with said primal mesh signal; and

means for minimizing said energy function with respect to said dual mesh signal while keeping said primal mesh signal fixed to provide values for said dual mesh signal.

17. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing formation of a dual mesh signal, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of claim 16.

18. A method comprising:

obtaining a first polygon mesh;

modifying said first polygon mesh employing a resampling mesh operator to form a second polygon mesh;

replacing said first mesh with said second polygon mesh; and

repeating said steps of modifying and replacing until a stopping criterion is met.

19. A method as recited in claim 18, wherein said resampling mesh operator includes a resampling mesh operator taken from a group of mesh operators including:

a dual mesh operator, a smoothing operator, and a refinement operator.

20. A method comprising:

obtaining a polygon mesh, wherein;

said polygon mesh including a primal mesh signal and a polygon mesh connectivity,

said polygon mesh connectivity including a plurality of polygon mesh vertices, a plurality of polygon mesh faces, and at least one regular edge;

each polygon mesh face having at least three corners, each corner being a particular polygon mesh vertex from among said plurality of polygon mesh vertices, each regular edge being incident to two polygon mesh vertices and two polygon mesh faces; and

said primal mesh signal including a plurality of primal points, each primal point being a point in an N-dimensional space, each primal point corresponding to a particular polygon mesh vertex from said plurality of polygon mesh vertices, and

resampling the polygon mesh to produce a dual mesh signal, wherein said dual mesh signal including a plurality of dual points, each dual point being a point in said N-dimensional space, each dual point corresponding to a particular polygon mesh face from said plurality of polygon mesh faces;

reading said polygon mesh from an input source;

minimizing an energy function of the primal points and the dual points with respect to the dual points while the primal points are kept fixed, wherein;

said energy function being a sum of a plurality of squares of terms, each square term being associated with a particular regular edge of said polygon mesh connectivity,

said square term being the square of a difference term, said difference term being computed by subtracting the sum of two dual points from the sum of two primal points,

said two dual points corresponding to the two mesh faces to which said regular edge is incident, and

said two primal point corresponding to the two vertices to which said regular edge is incident; and

writing said dual mesh signal to an output source.

21. A method as in claim 20, wherein the input source includes at least one input source from a group of input sources including:

an output from a computer program;

a computer memory buffer;

a display screen buffer;

a computer file stored in a nonvolatile storage medium;

a computer file stored in a magnetic storage device;

a computer file stored in an optical storage device;

a computer file stored in a computer network;

a document scanner;

a three-dimensional scanner;

an electronic tablet;

an interactive modeling system; and

a three-dimensional photography system.

22. A method as in claim 20, further comprising including in said output source at least one output source from a group of output sources including:

an input to a computer program;

a computer memory buffer;

a display screen buffer;

a computer file stored in a nonvolatile storage medium;

a computer file stored in a magnetic storage device;

a computer file stored in an optical storage device;

a computer file stored in a computer network;

a virtual prototyping machine;

a numerically-controlled milling machine;

a computer printer;

an interactive modeling system; and

a three-dimensional photography system.

23. A method as recited in claim 20, where the step of minimizing includes the steps of:

computing a plurality of face barycenters of the polygon mesh, wherein;

each face barycenter corresponds to a particular polygon mesh face from among said plurality of polygon mesh faces of said polygon mesh connectivity, and

each face barycenter being the average of the primal points corresponding to the corners of said polygon mesh face;

initializing each of said dual points to be equal to a corresponding face barycenter, wherein each of said dual points and a corresponding face barycenter correspond to a same polygon mesh face;

recomputing each of said dual points as the sum of said corresponding face barycenter plus one half of a dual Laplacian displacement, wherein;

said dual Laplacian displacement corresponding to said same polygon mesh face,

said dual Laplacian displacement computed as the average of a plurality of dual point differences,

each dual point difference corresponding to a particular regular edge of said polygon mesh connectivity,

each dual point difference computed by subtracting said dual point from a neighbor dual point,

said neighbor dual point corresponding to a neighbor polygon mesh face, and

said particular regular edge being incident to said same polygon mesh face and said neighbor polygon mesh face; and

repeating the steps of computing, initializing, and recomputing until an iteration stopping criterion is met.

24. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing the resampling a primal mesh producing a dual mesh signal, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 20.

25. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for causing the resampling a primal mesh producing a dual mesh signal, said method steps comprising the steps of claim 20.

26. A method comprising:

creating a dual polygon mesh from a polygon mesh, wherein;

said polygon mesh including a primal mesh signal and a polygon mesh connectivity,

said polygon mesh connectivity including a plurality of polygon mesh vertices, a plurality of polygon mesh faces, and at least one regular edge,

each polygon mesh face having at least three corners, each corner being a particular polygon mesh vertex from among said plurality of polygon mesh vertices, each regular edge being incident to two polygon mesh vertices and two polygon mesh faces,

said primal mesh signal including a plurality of primal points, each primal point being a point in an N-dimensional space, each primal point corresponding to a particular polygon mesh vertex from said plurality of polygon mesh vertices,

said dual polygon mesh including a dual mesh signal and a dual mesh connectivity, said dual mesh signal including a plurality of dual points, each dual point being a point in said N-dimensional space, each dual point corresponding to a particular polygon mesh face from said plurality of polygon mesh faces, said dual mesh connectivity having a plurality of dual mesh vertices, and a plurality of dual mesh faces,

each dual mesh vertex corresponding to one said polygon mesh face of said polygon mesh connectivity, each dual mesh face corresponding to one polygon mesh vertex of said polygon mesh connectivity;

reading said polygon mesh from an input source;

minimizing an energy function of the primal points and the dual points with respect to the dual points while the primal points are kept fixed, wherein;

said energy function is a sum of a plurality of squares of terms, each square term being associated with a particular regular edge of said polygon mesh connectivity, said square term being the square of a difference term,

said difference term being computed by subtracting the sum of two dual points from the sum of two primal points,

said two dual points corresponding to the two mesh faces to which said regular edge is incident, and

said two primal points corresponding to the two vertices to which said regular edge is incident;

constructing said dual mesh connectivity from said polygon mesh connectivity;

combining said dual mesh signal and said dual mesh connectivity as said dual polygon mesh; and

writing said dual polygon mesh to an output source.

27. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing creation of a dual polygon mesh from a polygon mesh, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 26.

28. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for causing creation of a dual polygon mesh from a polygon mesh, said method steps comprising the steps of claim 26.

29. A method comprising:

smoothing a polygon mesh, wherein;

said polygon mesh includes a primal mesh signal and a polygon mesh connectivity,

said polygon mesh connectivity including a plurality of polygon mesh vertices, a plurality of polygon mesh faces, and at least one regular edge,

each polygon mesh face having at least three corners, each corner being a particular polygon mesh vertex from among said plurality of polygon mesh vertices, each regular edge being incident to two polygon mesh vertices and two polygon mesh faces, and

said primal mesh signal including a plurality of primal points, each primal point being a point in an N-dimensional space, each primal point corresponding to a particular polygon mesh vertex from said plurality of polygon mesh vertices;

reading said polygon mesh from an input source;

creating a temporary dual mesh signal, wherein said temporary dual mesh signal including a plurality of dual points, each dual point being a point in said N-dimensional space, each dual point corresponding to a particular polygon mesh face from said plurality of polygon mesh faces;

minimizing an energy function of the primal points and the dual points with respect to the dual points while the primal points are kept fixed, wherein;

said energy function is a sum of a plurality of squares of terms, each square term being associated with a particular regular edge of said polygon mesh connectivity, said square term being the square of a difference term,

said difference term being computed by subtracting the sum of two dual points from the sum of two primal points, and

said two dual points corresponding to the two mesh faces to which said regular edge is incident, said two primal points corresponding to the two vertices to which said regular edge is incident;

recomputing said primal mesh signal by minimizing said energy function with respect to the primal points while the dual points are kept fixed; and

writing said primal mesh to an output source.

30. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing smoothing of a polygon mesh, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 29.

31. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for causing smoothing of a polygon mesh, said method steps comprising the steps of claim 29.

32. A method comprising:

refining a polygon mesh producing a primal-dual mesh, wherein;

said polygon mesh including a primal mesh signal and a polygon mesh connectivity, said polygon mesh connectivity including a plurality of polygon mesh vertices, a plurality of polygon mesh faces, and at least one regular edge,

each polygon mesh face having at least three corners, each corner being a particular polygon mesh vertex from among said plurality of polygon mesh vertices, each regular edge being incident to two polygon mesh vertices and two polygon mesh faces,

said primal mesh signal including a plurality of primal points, each primal point being a point in an N-dimensional space, each primal point corresponding to a particular polygon mesh vertex from said plurality of polygon mesh vertices; and

reading said polygon mesh from an input source;

creating a temporary dual mesh signal, wherein said temporary dual mesh signal including a plurality of dual points, each dual point being a point in said N-dimensional space, each dual point corresponding to a particular polygon mesh face from said plurality of polygon mesh faces;

minimizing an energy function of the primal points and the dual points with respect to the dual points while the primal points are kept fixed, wherein;

said energy function being a sum of a plurality of squares of terms, each square term being associated with a particular regular edge of said polygon mesh connectivity,

said square term being the square of a difference term, said difference term being computed by subtracting the sum of two dual points from the sum of two primal points, and

said two dual points corresponding to the two mesh faces to which said regular edge is incident, said two primal points corresponding to the two vertices to which said regular edge is incident;

constructing a primal-dual mesh signal by concatenating said primal mesh signal with said dual mesh signal;

constructing a primal-dual mesh connectivity from said polygon mesh connectivity, wherein said primal-dual mesh connectivity has a plurality of primal-dual mesh vertices, and a plurality of primal-dual mesh faces, each primal-dual mesh face corresponding to one particular regular edge of said polygon mesh connectivity, each prima-dual mesh vertex corresponds to one of a particular polygon mesh vertex and a particular polygon mesh face of the polygon mesh connectivity;

constructing said primal-dual mesh by combining said primal-dual mesh signal and said primal-dual mesh connectivity; and

writing said primal-dual mesh to an output source.

33. A system for resampling a primal mesh signal to produce a dual mesh signal comprising:

a computer with operating system, computer memory, input/output interface, and a central processing unit; and

an application program executed by the central processing unit for resampling a primal mesh to produce a dual mesh signal, wherein;

said polygon mesh including a primal mesh signal and a polygon mesh connectivity, said polygon mesh connectivity including a plurality of polygon mesh vertices, a plurality of polygon mesh faces, and at least one regular edge,

each polygon mesh face having at least three corners, each corner being a particular polygon mesh vertex from among said plurality of polygon mesh vertices, each regular edge being incident to two polygon mesh vertices and two polygon mesh faces,

said primal mesh signal including a plurality of primal points, each primal point being a point in an N-dimensional space, each primal point corresponding to a particular polygon mesh vertex from said plurality of polygon mesh vertices,

said dual mesh signal including a plurality of dual points, each dual point being a point in said N-dimensional space, each dual point corresponding to a particular polygon mesh face from said plurality of polygon mesh faces,

said application program comprising the computer implemented steps of;

reading said polygon mesh from one of the computer memory and the peripheral device through the input/output interface; and

minimizing an energy function of the primal points and the dual points with respect to the dual points while the primal points are kept fixed, wherein;

said energy function is a sum of a plurality of squares of terms, each square term being associated with a particular regular edge of said polygon mesh connectivity,

said square term being the square of a difference term, said difference term being computed by subtracting the sum of two dual points from the sum of two primal points,

said two dual points corresponding to the two mesh faces to which said regular edge is incident, and

said two primal points corresponding to the two vertices to which

said regular edge is incident; and

writing said dual mesh signal to computer memory or peripheral device through the input/output interface.

34. A system for resampling a polygon mesh to produce a dual polygon mesh comprising:

a computer with operating system, computer memory, input/output interface, and a central processing unit;

and an application program executed by the central processing unit for resampling a polygon mesh to produce a dual mesh, wherein;

said polygon mesh connectivity includes a plurality of polygon mesh vertices, a plurality of polygon mesh faces, and at least one regular edge,

each polygon mesh face having three or more corners, each corner being a particular polygon mesh vertex from among said plurality of polygon mesh vertices, each regular edge being incident to two polygon mesh vertices and two polygon mesh faces,

said primal mesh signal including a plurality of primal points, each primal point being a point in an N-dimensional space, each primal point corresponding to a particular polygon mesh vertex from said plurality of polygon mesh vertices,

said dual polygon mesh including a dual mesh signal and a dual mesh connectivity, said dual mesh signal including a plurality of dual points, each dual point being a point in said N-dimensional space, each dual point corresponding to a particular polygon mesh face from said plurality of polygon mesh faces, said dual mesh connectivity having a plurality of dual mesh vertices, and a plurality of dual mesh faces, each dual mesh vertex corresponding to one said polygon mesh face of said polygon mesh connectivity, each dual mesh face corresponding to one polygon mesh vertex of said polygon mesh connectivity,

said application program comprising the computer implemented steps of;

reading said polygon mesh from the computer memory or peripheral device through the input/output interface;

minimizing an energy function of the primal points and the dual points with respect to the dual points while the primal points are kept fixed, said energy function being a sum of a plurality of squares of terms, each square term being associated with a particular regular edge of said polygon mesh connectivity, said square term being the square of a difference term, said difference term being computed by subtracting the sum of two dual points from the sum of two primal points, said two dual points corresponding to the two mesh faces to which said regular edge is incident, said two primal points corresponding to the two vertices to which said regular edge is incident;

constructing said dual mesh connectivity from said polygon mesh connectivity;

combining said dual mesh signal and said dual mesh connectivity as said dual polygon mesh; and

writing said dual polygon mesh to the computer memory or peripheral device through the input/output interface.

35. A system for smoothing a polygon mesh to produce a smoothed polygon mesh comprising:

a computer with operating system, computer memory, input/output interface, and a central processing unit; and

an application program executed by the central processing unit for smoothing a polygon mesh to produce a smoothed polygon mesh signal, wherein;

said polygon mesh including a primal mesh signal and a polygon mesh connectivity, said polygon mesh connectivity including a plurality of polygon mesh vertices, a plurality of polygon mesh faces, and at least one regular edge,

each polygon mesh face having three or more corners, each corner being a particular polygon mesh vertex from among said plurality of polygon mesh vertices, each regular edge being incident to two polygon mesh vertices and two polygon mesh faces,

said primal mesh signal including a plurality of primal points, each primal point being a point in an N-dimensional space, each primal point corresponding to a particular polygon mesh vertex from said plurality of polygon mesh vertices, comprising the computer implemented steps of;

reading said polygon mesh from the computer memory or peripheral device through the input/output interface;

creating a temporary dual mesh signal, said temporary dual mesh signal including a plurality of dual points, each dual point being a point in said N-dimensional space, each dual point corresponding to a particular polygon mesh face from said plurality of polygon mesh faces;

minimizing an energy function of the primal points and the dual points with respect to the dual points while the primal points are kept fixed, said energy function being a sum of a plurality of squares of terms, each square term being associated with a particular regular edge of said polygon mesh connectivity, said square term being the square of a difference term, said difference term being computed by subtracting the sum of two dual points from the sum of two primal points, said two dual points corresponding to the two mesh faces to which said regular edge is incident, said two primal points corresponding to the two vertices to which said regular edge is incident; and

recomputing said primal mesh signal by minimizing said energy function with respect to the primal points while the dual points are kept fixed; and

writing said smoothed polygon mesh to the computer memory or peripheral device through the input/output interface.

36. A system for refining a polygon mesh to produce a primal-dual mesh comprising:

a computer with operating system, computer memory, input/output interface, and a central processing unit; and

an application program executed by the central processing unit for refining a polygon mesh to produce a primal-dual mesh comprising, wherein;

said polygon mesh including a primal mesh signal and a polygon mesh connectivity, said polygon mesh connectivity including a plurality of polygon mesh vertices, a plurality of polygon mesh faces, and at least one regular edge,

each polygon mesh face having three or more corners, each corner being a particular polygon mesh vertex from among said plurality of polygon mesh vertices, each regular edge being incident to two polygon mesh vertices and two polygon mesh faces,

said primal mesh signal including a plurality of primal points, each primal point being a point in an N-dimensional space, each primal point corresponding to a particular polygon mesh vertex from said plurality of polygon mesh vertices, comprising the computer implemented steps of;

reading said polygon mesh from the computer memory or peripheral device through the input/output interface;

creating a temporary dual mesh signal, said temporary dual mesh signal including a plurality of dual points, each dual point being a point in said N-dimensional space, each dual point corresponding to a particular polygon mesh face from said plurality of polygon mesh faces;

minimizing an energy function of the primal points and the dual points with respect to the dual points while the primal points are kept fixed, said energy function being a sum of a plurality of squares of terms, each square term being associated with a particular regular edge of said polygon mesh connectivity, said square term being the square of a difference term, said difference term being computed by subtracting the sum of two dual points from the sum of two primal points, said two dual points corresponding to the two mesh faces to which said regular edge is incident, said two primal points corresponding to the two vertices to which said regular edge is incident; and

constructing a primal-dual mesh signal by concatenating said primal mesh signal with said dual mesh signal;

constructing a primal-dual mesh connectivity from said polygon mesh connectivity, said primal-dual mesh connectivity having a plurality of primal-dual mesh vertices, and a plurality of primal-dual mesh faces, each primal-dual mesh face corresponding to one particular regular edge of said polygon mesh connectivity, each prima-dual mesh vertex corresponding to either one particular polygon mesh vertex or one particular polygon mesh face of the polygon mesh connectivity;

constructing said primal-dual mesh by combining said primal-dual mesh signal and said primal-dual mesh connectivity; and

writing said primal-dual mesh to the computer memory or peripheral device through the input/output interface.