Transforming polygonal mesh by sub-polychord collapse

• US 9,858,715 B2
• Filed: 08/11/2015
• Issued: 01/02/2018
• Est. Priority Date: 08/11/2015
• Status: Active Grant

• Current Assignee: Electronic Arts Incorporated
• Original Assignee: Electronic Arts Incorporated
• Inventors: Mason, Ashton
• Primary Examiner(s): BROOME, SAID A
• Application Number:
  US14/823,480
• Publication Number:
  US 20170046874A1
• Time in Patent Office: 875 Days
• Field of Search: None
• CPC Class Codes: G06T 17/205 Re-meshing

Abstract

An example method of transforming polygonal meshes by sub-polychord collapse may include identifying, among a plurality of sub-polychords of a given size, a seed sub-polychord having an optimal value of a metric associated with collapsing the respective sub-polychord. The example method may further include identifying a first test value of the metric for a first test sub-polychord comprising the seed sub-polychord and a first adjacent edge, and further identifying a second test value of the metric for a second test sub-polychord comprising the seed sub-polychord and a second adjacent edge. The example method may further include, responsive to determining a minimum of the first test value of the metric and the second test value of the metrics is less than a base value of the metric for the seed sub-polychord, transforming the seed sub-polychord by adding an adjacent edge that produces a test sub-polychord having the minimum test value.

Claims

1. A method, comprising:

identifying, among a plurality of sub-polychords of a given size in a polychord mesh, a seed sub-polychord having a minimal value of a metric associated with collapsing the respective sub-polychord;

identifying, by a processing device, a first test value of the metric for a first test sub-polychord comprising the seed sub-polychord and a first adjacent edge;

identifying a second test value of the metric for a second test sub-polychord comprising the seed sub-polychord and a second adjacent edge;

responsive to determining that a minimum of the first test value of the metric and the second test value of the metrics is less than a base value of the metric for the seed sub-polychord, transforming the seed sub-polychord by adding an adjacent edge that produces a test sub-polychord having the minimum test value; and

utilizing the polychord mesh for creating computer-generated imagery.

2. The method of claim 1, wherein transforming the seed sub-polychord is performed iteratively, until determining that the minimum of the first value of the metric and the second value of the metric exceeds the base value of the metric.

3. The method of claim 1, wherein a sub-polychord of the plurality of sub-polychords comprises one of:

a contiguous sequence of edges of a corresponding polychord or an arbitrary set of edges of the polychord mesh.

4. The method of claim 1, further comprising:

responsive to determining that the minimum of the first value of the metric and the second value of the metric exceeds the base value of the metric, collapsing the seed sub-polychord.

5. The method of claim 1, wherein collapsing the seed sub-polychord comprises at least one of:

replacing a set of edges comprised by the seed sub-polychord with a set of vertices or replacing a quadrangle face at an end of the seed sub-polychord with a triangle.

6. A method, comprising:

identifying, by a processing device, a plurality of sub-polychords in a polychord mesh comprising one or more polychords;

identifying, among the plurality of sub-polychords, a candidate sub-polychord having an optimal value of a metric associated with collapsing the respective sub-polychord, wherein the optimal value is provided by one of;

a maximal value of the metric among a plurality of values of the metric associated with the plurality of sub-polychords or a minimal value of the metric among the plurality of values of the metric associated with the plurality of sub-polychords;

collapsing the candidate sub-polychord by replacing a set of edges comprised by the candidate sub-polychord with a set of vertices, wherein collapsing the candidate sub-polychord further comprises replacing a quadrangle face at an end of the sub-polychord with a triangle; and

utilizing the polychord mesh for creating computer-generated imagery.

7. The method of claim 6, wherein at least one sub-polychord of the plurality of sub-polychords comprises a contiguous sequence of edges of a corresponding polychord.

8. The method of claim 6, wherein at least one sub-polychord of the plurality of sub-polychords comprises an arbitrary set of edges of the polychord mesh.

9. The method of claim 6, wherein the metric represents a loss of mesh fidelity due to collapsing the sub-polychord.

10. The method of claim 6, wherein the metric comprises a quadric error term.

11. The method of claim 6, wherein the metric comprises a sum of quadric error terms associated with two or more vertices comprised by the candidate sub-polychord.

12. The method of claim 6, wherein the metric comprises a weighted sum of two or more terms.

13. The method of claim 6, wherein the metric comprises a valence term reflecting at least one of:

a change of a vertex valence or a change of a face valence.

14. The method of claim 6, wherein the metric is provided by a ratio of a benefit of collapsing the candidate sub-polychord to a loss of mesh fidelity due to collapsing the candidate sub-polychord.

15. The method of claim 14, wherein the benefit of collapsing the candidate sub-polychord reflects at least one of:

a number of edges to be removed from the polychord mesh by collapsing the sub-polychord or a number of vertices to be removed from the polychord mesh by collapsing the candidate sub-polychord.

16. The method of claim 6, wherein identifying the plurality of sub-polychords further comprises:

identifying a seed sub-polychord having a minimal value of the metric among the plurality of sub-polychords of a given size;

identifying a first test value of the metric for a first test sub-polychord comprising the seed sub-polychord and a first adjacent edge;

identifying a second test value of the metric for a second test sub-polychord comprising the seed sub-polychord and a second adjacent edge; and

responsive to determining that a minimum of the first test value of the metric and the second test value of the metrics is less than a base value of the metric for the seed sub-polychord, transforming the seed sub-polychord by adding an adjacent edge that produces a test sub-polychord having the minimum test value.

17. The method of claim 16, wherein adding the adjacent edge is performed iteratively, until determining that the minimum of the first value of the metric and the second value of the metric exceeds the base value of the metric.

18. The method of claim 16, wherein identifying the candidate sub-polychord further comprises:

responsive to determining that the minimum of the first value of the metric and the second value of the metric exceeds the base value of the metric, identifying the candidate sub-polychord as being equal to the seed sub-polychord.

19. A computer-readable non-transitory storage medium comprising executable instructions to cause a processing device to:

identify, by the processing device, a plurality of sub-polychords in a polychord mesh comprising one or more polychords;

identify, among the plurality of sub-polychords, a candidate sub-polychord having an optimal value of a metric associated with collapsing the respective sub-polychord, wherein the optimal value is provided by one of;

a maximal value of the metric among a plurality of values of the metric associated with the plurality of sub-polychords or a minimal value of the metric among the plurality of values of the metric associated with the plurality of sub-polychords;

collapse the candidate sub-polychord by replacing a set of edges comprised by the candidate sub-polychord with a set of vertices, wherein collapsing the candidate sub-polychord further comprises replacing a quadrangle face at an end of the sub-polychord with a triangle; and

utilize the polychord mesh for creating computer-generated imagery.

20. The computer-readable non-transitory storage medium of claim 19, wherein identifying the plurality of sub-polychords further comprises:

identifying a seed sub-polychord having a minimal value of the metric among the plurality of sub-polychords of a given size;

identifying a first test value of the metric for a first test sub-polychord comprising the seed sub-polychord and a first adjacent edge;

identifying a second test value of the metric for a second test sub-polychord comprising the seed sub-polychord and a second adjacent edge; and

responsive to determining that a minimum of the first test value of the metric and the second test value of the metrics is less than a base value of the metric for the seed sub-polychord, transforming the seed sub-polychord by adding an adjacent edge that produces a test sub-polychord having the minimum test value.