Determination of vertices of triangular grids for three-dimensional object representations

Patent metadata

Field	Value
Publication number	US-11587289-B2
Application number	US-201817296827-A
Country	US
Kind code	B2
Filing date	Dec 11, 2018
Priority date	Dec 11, 2018
Publication date	Feb 21, 2023
Grant date	Feb 21, 2023

Abstract

An example of a non-transitory computer-readable medium storing machine-readable instructions. The instructions may cause the processor to receive a three-dimensional (3D) object representation and subdivide it into a triangular grid. Curved triangles may be calculated for triangles in the triangular grid. The triangles may be subdivided and differences calculated between corresponding sections of the curved triangles and the received 3D object representation.

First claim

What is claimed is:

1. A non-transitory computer-readable medium to store machine-readable instructions that, when executed by a processor, cause the processor to:
receive a three-dimensional (3D) object representation;
subdivide a parametric space of the 3D object representation into a first triangular grid, the first triangular grid comprising a first set of grid lines and a first set of vertices where grid lines in the first set of grid lines intersect;
calculate a first curved triangle for a first triangle in the first triangular grid, the first curved triangle corresponding to the 3D object representation for the first triangle;
subdivide the first triangle into at least a first subdivision and a second subdivision;
calculate a first difference between a first point on the 3D object representation and a corresponding first point on the first curved triangle, the first point on the 3D object representation corresponding to a point within the first subdivision;
in response to the first difference exceeding a predetermined error threshold,
subdivide the first subdivision into at least a third subdivision and a fourth subdivision;

calculate a second difference between a second point of the 3D object representation and a corresponding second point on the first curved triangle, the second point on the 3D object representation corresponding to a point within the third subdivision; and
in response to the second difference exceeding the predetermined error threshold, combine the point within the first subdivision and the point within the third subdivision with the first set of vertices to create a second set of vertices.

2. The computer-readable medium of claim 1 , wherein the 3D object representation comprises a non-uniform rational basis spline (NURBS) format.

3. The computer-readable medium of claim 1 , wherein the first triangular grid includes a uniform triangular grid.

4. The computer-readable medium of claim 1 , wherein the first subdivision and the second subdivision are equivalent shapes.

5. The computer-readable medium of claim 1 , wherein execution of the machine-readable instructions by the processor causes the processor to further:
calculate a first intersection between the second curved triangle and a plane in Euclidean space.

6. The computer-readable medium of claim 1 , wherein execution of the machine-readable instructions by the processor causes the processor to further:
subdivide the parametric space into a second triangular grid, the second triangular grid comprising a second set of grid lines between the second set of vertices;
calculate a second curved triangle for a second triangle in the second triangular grid; and
print a 3D object based on the second curved triangle.

7. A non-transitory computer-readable medium to store machine-readable instructions that, when executed by a processor, cause the processor to:
partition a parametric space of a 3D object representation into a uniform triangular grid comprising a first set of vertices;
create a first curved triangle for a first triangle in the uniform triangular grid, the first curved triangle corresponding to the 3D object representation for the first triangle;
partition the first triangle into a set of shapes, the set of shapes including a first shape and a second shape;
calculate a first difference between a first point on the 3D object representation and a corresponding first point on the first curved triangle, the first point on the 3D object representation corresponding to a point within the first shape;
determine that the first difference is greater than a first predetermined error threshold;
in response to the determination that the first difference is greater than the first predetermined error threshold, partition the first shape into a set of sub-shapes, the set of sub-shapes including a first sub-shape and a second sub-shape;
calculate a second difference between a second point on the 3D object representation and a corresponding second point on the first curved triangle, the second point on the 3D object representation corresponding to a point within the first sub-shape;
determine that the second difference is greater than a second predetermined error threshold;
in response to the determination that the second difference is greater than the second predetermined error threshold, combining the point within the first shape and the point within the second sub-shape with the first set of vertices to create a second set of vertices.

8. The computer-readable medium of claim 7 , wherein the set of shapes includes a third shape, and wherein the first, second, and third shapes are quadrilaterals.

9. The computer-readable medium of claim 8 , wherein the set of sub-shapes includes a third sub-shape and a fourth sub-shape, and wherein the first, second, third, and fourth sub-shapes are quadrilaterals.

10. The computer-readable medium of claim 7 , wherein the calculation of a first difference includes calculation of a chordal error of the barycenter of the first shape.

11. The computer-readable medium of claim 7 , wherein the first predetermined error threshold is the same as the second predetermined error threshold.

12. The computer-readable medium of claim 7 , wherein execution of the machine-readable instructions by the processor causes the processor to further:
partitioning the parameter space into a non-uniform triangular grid comprising the second set of vertices;
calculate a second curved triangle for a second triangle in the non-uniform triangular grid; and
printing a 3D object based on the second curved triangle.

13. A method comprising:
splitting a parametric space of a three-dimensional (3D) object representation into a first triangular grid having a first set of vertices;
determining a first curved triangle for a first triangle in the first triangular grid, the first curved triangle corresponding to the 3D object representation for the triangle;
subdividing the first triangle into at least a first subdivision and a second subdivision;
calculating a first difference between a first point on the 3D object representation and a corresponding first point on the first curved triangle, the first point on the 3D object representation corresponding to a point within the first subdivision;
in response to the first difference exceeding a predetermined error threshold, subdividing the first subdivision into at least a third subdivision and a fourth subdivision;
calculating a second difference between a second point of the 3D object representation and a corresponding second point on the first curved triangle, the second point on the 3D object representation corresponding to a point within the third subdivision; and
in response to the second difference exceeding the predetermined error threshold, combining the point within the first subdivision and the point within the third subdivision with the first set of vertices to create a second set of vertices.

14. The method of claim 13 , wherein the first, second, third, and fourth subdivisions are each a triangle.

15. The method of claim 14 , wherein the first subdivision and the second subdivision are equivalent shapes.

16. The method of claim 13 , wherein the first triangular grid is uniform.

17. The method of claim 13 , further comprising:
splitting the parametric space into a second triangular grid comprising the second set of vertices;
calculating a second curved triangle for a second triangle in the second triangular grid; and
printing a 3D object based on the second curved triangle.

Assignees

• Hewlett Packard Development Co
• Univ Pernambuco Federal

Inventors

• Henriques Diogo
• Simoes Francisco
• Melo Silvio
• Silva Andre
• Chaves Thiago
• Charamba Gustavo
• Teixeira Joao
• Teichrieb Veronica
• Barros Gutenberg
• Correia Walter
• Domingues Thiago
• Castilho Vinicius
• Riss Marcelo
• White Scott A

Classifications

• G06T19/00

  Manipulating three-dimensional [3D] models or images for computer graphics · CPC title

• G06T17/20 Primary

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

• G06T17/205 Primary

  Re-meshing · CPC title