Low-poly mesh generation for three-dimensional models

Patent metadata

Field	Value
Publication number	US-12333653-B2
Application number	US-202318112445-A
Country	US
Kind code	B2
Filing date	Feb 21, 2023
Priority date	Feb 21, 2023
Publication date	Jun 17, 2025
Grant date	Jun 17, 2025

Abstract

According to an aspect of the disclosure, a method of generating a low-poly mesh for a three-dimensional (3D) model is provided. In the method, an edge-collapse operation is performed on each of a plurality of edges of an input mesh to generate a simplified mesh in which a number of faces of the input mesh is reduced by the edge-collapse operation. A position of at least one vertex of the simplified mesh is updated to generate an updated mesh in which a distance between the simplified mesh and the input mesh is reduced. The low-poly mesh is generated based on an aligned mesh in which positions of vertices of the updated mesh are optimized by minimizing a shape difference between the simplified mesh and the updated mesh.

First claim

What is claimed is:

1. A method of generating a low-poly mesh for a three-dimensional (3D) model, the method comprising:
performing an edge-collapse operation on each of a plurality of edges of an input mesh to generate a simplified mesh in which a number of faces of the input mesh are reduced by the edge-collapse operations;
updating a position of at least one vertex of the simplified mesh to generate an updated mesh in which a distance between the simplified mesh and the input mesh is reduced, wherein a position of a first vertex of the at least one vertex of the simplified mesh is updated based on vector information and the position of the first vertex, the vector information indicating a difference between a position of a target vertex in the input mesh and the position of the first vertex over a first constant value, the target vertex in the input mesh being a closest vertex of the first vertex of the simplified mesh; and
generating the low-poly mesh based on an aligned mesh in which positions of vertices of the updated mesh are optimized by minimizing a shape difference between the simplified mesh and the updated mesh.

2. The method of claim 1 , wherein the input mesh is an iso-surface mesh that is generated based on a plurality of iso-surfaces in a plurality of voxels of the 3D model, the plurality of iso-surfaces being determined based on an iso-value.

3. The method of claim 1 , wherein the performing the edge-collapse operation further comprises:
performing the edge-collapse operation on a first edge of the plurality of edges of the input mesh to generate the simplified mesh;
determining whether the simplified mesh meets a topology consistency based on whether the simplified mesh is manifold and watertight, and has a same genus and a same number of components as the input mesh;
in response to the simplified mesh meeting the topology consistency, determining whether the simplified mesh is free of self-intersection;
in response to the simplified mesh being free of self-intersection, determining whether a first distance between a sub-mesh of the input mesh and a sub-mesh of the simplified mesh is larger than an iso-value, the sub-mesh of the input mesh including faces adjacent to the first edge before the edge-collapse operation, the sub-mesh of the simplified mesh including faces associated with the first edge after the edge-collapse operation; and
in response to the first distance being less than the iso-value, determining whether a second distance between the sub-mesh of the input mesh and a reference mesh is less than a third distance between the sub-mesh of the simplified mesh and the reference mesh.

4. The method of claim 3 , wherein the determining whether the simplified mesh is free of self-intersection further comprises:
determining a first sub-mesh in the simplified mesh that includes at least one first face, each of the at least one first face being in contact with a vertex that is determined when the edge-collapse operation is applied on the first edge;
determining a second sub-mesh in the simplified mesh, the second sub-mesh including a plurality of second faces, each of the plurality of second faces sharing at least one vertex of the first sub-mesh;
determining a third sub-mesh in the simplified mesh, the third sub-mesh including a plurality of third faces that are not included in the first sub-mesh and the second sub-mesh;
constructing a bounding volume hierarchy (BVH) tree data structure of the third sub-mesh based on a BVHTree type;
for each of the at least one first face of the first sub-mesh, determining a closest face of the respective first face in the third sub-mesh; and
verifying whether each of the at least one first face of the first sub-mesh intersects the closest face of the respective first face.

5. The method of claim 1 , wherein the updating the first vertex further comprises:
updating the position of the first vertex as a sum of (i) the position of the first vertex and (ii) a product of a second constant value and a vector indicated by the vector information;
determining whether a first face of the simplified mesh that includes the first vertex intersects at least one neighboring face in the simplified mesh;
in response to the first face intersecting the at least one neighboring face, updating the position of the first vertex as a sum of (i) the position of the first vertex and (ii) a product of a third constant value, a half of the second constant value, and the vector; and
in response to the first face not intersecting the at least one neighboring face, updating the position of the first vertex as a sum of (i) the position of the first vertex and (ii) a product of the third constant value, the second constant value, and the vector.

6. The method of claim 5 , wherein the first constant value is 8, the second constant value is 1, and the third constant value is 0.95.

7. The method of claim 1 , wherein the generating further comprises:
determining an unnormalized face normal of a first face of a face union that includes faces in the updated mesh and contacts the first vertex of the updated mesh;
setting a normal constant based on a magnitude of the unnormalized face normal of the first face;
determining a unnormalized face normal of a corresponding face to the first face in the simplified mesh; and
determining the optimized position of the first vertex that minimizes an unconstrained quadratic function.

8. The method of claim 7 , wherein the determining the unnormalized face normal of the first face further comprises:
determining the unnormalized face normal of the first face as a cross product of two face edges of the first face.

9. The method of claim 8 , wherein the determining the unnormalized face normal of the corresponding face to the first face further comprises:
determining the unnormalized face normal of the corresponding face to the first face as a cross product of two face edges of the corresponding face to the first face.

10. The method of claim 9 , wherein the unconstrained quadratic function comprises:

E
⁡
(
v
)

:=

Σ

f
∈

N
⁡
(
v
)

⁢



n
⁡
(
f
)

c
n

-

n
~

(
f
)



n
~

(
f

Assignees

• Tencent America LLC

Inventors

• Gao Xifeng
• Chen Zhen
• Pan Zherong
• Wu Kui

Classifications

• G06T19/20

  Editing of three-dimensional [3D] images, e.g. changing shapes or colours, aligning objects or positioning parts · CPC title

• G06T17/005

  Tree description, e.g. octree, quadtree · CPC title

• G06T2219/2004

  Aligning objects, relative positioning of parts · CPC title

• G06T17/205 Primary

  Re-meshing · CPC title

• G06T17/20 Primary

  Finite element generation, e.g. wire-frame surface description, {tesselation} · CPC title