Orthogonal-projection-based texture atlas packing of three-dimensional meshes

1. A method of atlas packing for computer graphics performed by one or more computer processors, the method comprising:

receiving a three-dimensional (3D) mesh including a plurality of triangles representing surfaces of one or more objects, each triangle having a respective texture;

for each respective triangle of the plurality of triangles:

determining a normal of the respective triangle; and

categorizing the respective triangle into one of six directions along positive and negative of x-, y-, and z-directions according a predominant component of the normal;

categorizing triangles in each respective direction of the six directions into one or more layers orthogonal to the respective direction;

for each respective layer in a respective direction:

identifying one or more connected components, each connected component comprises a plurality of connected triangles;

projecting each respective connected component onto a plane orthogonal to the respective direction to obtain a corresponding projected two-dimensional (2D) connected component; and

cutting the projected 2D connected component into one or more sub-components, each sub-component contained within a respective rectangular bounding box;

packing the bounding boxes of all sub-components of all projected 2D connected components in all layers in all directions into one or more atlases;

for each respective triangle of each sub-component in each atlas, copying a texture of a corresponding triangle of the 3D mesh to the respective triangle; and

storing the one or more atlases in a computer memory.

2. The method of claim 1 , further comprising, before categorizing the triangles:

identifying one or more major surfaces of the 3D mesh; and

rotating the 3D mesh to align normals of the one or more major surfaces with one or more of x-, y-, and z-directions.

3. The method of claim 1 wherein categorizing the triangles in each respective direction into the one or more layers comprises:

dividing a space in the respective direction by a plurality of planes orthogonal to the respective direction; and

categorizing triangles lying between two adjacent planes into one layer.

4. The method of claim 1 wherein cutting the projected 2D connected component into the one or more sub-components minimizes a sum of areas of the bounding boxes for the one or more sub-components.

5. The method of claim 4 wherein each sub-component has substantially a rectangular shape.

6. The method of claim 4 wherein cutting the projected 2D connected component comprises:

identifying an edge of the projected 2D connected component in a horizontal direction or a vertical direction; and

cutting the projected 2D connected component along a straight horizontal line or a straight vertical line at the identified edge to divide the projected 2D connected component into two or more sub-components.

7. The method of claim 6 wherein cutting the projected 2D connected component further comprises, before identifying the edge:

rotating the projected 2D connected component to minimize an area of a rectangular bounding box containing the projected 2D connected component.

8. The method of claim 1 wherein packing the bounding boxes of all sub-components comprises:

sorting the bounding boxes for all sub-components in a descending order by lengths of their longer edges;

picking a first unpacked bounding box;

searching for an available space in all current atlases that the first unpacked bounding box can fit into; and

packing the first unpacked bounding box in the available space.

9. The method of claim 1 further comprising, before storing the one or more atlases:

dividing each atlas into a plurality of blocks, each block including a plurality of pixels; and

for each block that includes both textured pixels and dark pixels, filling dark pixels with colors from textured pixels;

wherein storing the one or more atlases uses a compression standard.

10. The method of claim 1 further comprising, before storing the one or more atlases:

dividing each atlas into a plurality of blocks, each block including a plurality of pixels;

for each block that includes both textured pixels and dark pixels, filling dark pixels with colors from textured pixels; and

filling each block that includes only dark pixels with colors from a neighboring textured block;

wherein storing the one or more atlases uses a compression standard.

11. A non-transitory computer-readable storage medium comprising a plurality of computer-readable instructions tangibly embodied on the computer-readable storage medium, which, when executed by a computer processor, perform atlas packing for computer graphics, the plurality of instructions comprising:

instructions that cause the computer processor to receive a three-dimensional (3D) mesh including a plurality of triangles representing surfaces of one or more objects, each triangle having a respective texture;

instructions that cause the computer processor to, for each respective triangle of the plurality of triangles:

determine a normal of the respective triangle; and

categorize the respective triangle into one of six directions along positive and negative of x-, y-, and z-directions according a predominant component of the normal;

instructions that cause the computer processor to categorize triangles in each respective direction of the six directions into one or more layers orthogonal to the respective direction;

instructions that cause the computer processor to, for each respective layer in a respective direction:

identify one or more connected components, each connected component comprises a plurality of connected triangles;

project each respective connected component onto a plane orthogonal to the respective direction to obtain a corresponding projected two-dimensional (2D) connected component; and

cut the projected 2D connected component into one or more sub-components, each sub-component contained within a respective rectangular bounding box;

instructions that cause the computer processor to pack the bounding boxes of all sub-components of all projected 2D connected components in all layers in all directions into one or more atlases;

instructions that cause the computer processor to, for each respective triangle of each sub-component in each atlas, copy a texture of a corresponding triangle of the 3D mesh to the respective triangle; and

instructions that cause the computer processor to store the one or more atlases in a computer memory.

12. The non-transitory computer-readable storage medium of claim 11 wherein the plurality of instructions further comprising instructions that cause the computer processor to, before categorizing the triangles:

identify one or more major surfaces of the 3D mesh; and

rotate the 3D mesh to align normals of the one or more major surfaces with one or more of x-, y-, and z-directions.

13. The non-transitory computer-readable storage medium of claim 11 wherein the instructions that cause the computer processor to categorize triangles in each respective direction into the one or more layers includes:

instructions that cause the computer processor to divide a space in the respective direction by a plurality of planes orthogonal to the respective direction; and

instructions that cause the computer processor to categorize triangles lying between two adjacent planes into one layer.

14. The non-transitory computer-readable storage medium of claim 11 wherein cutting the projected 2D connected component into the one or more sub-components minimizes a sum of areas of the bounding boxes for the one or more sub-components.

15. The non-transitory computer-readable storage medium of claim 14 wherein each sub-component has substantially a rectangular shape.

16. The non-transitory computer-readable storage medium of claim 14 wherein the instructions that cause the computer processor to cut the projected 2D connected component comprises:

instructions that cause the computer processor to identify an edge of the projected 2D connected component in a horizontal direction or a vertical direction; and

instructions that cause the computer processor to cut the projected 2D connected component along a straight horizontal line or a straight vertical line at the identified edge to divide the projected 2D connected component into two or more sub-components.

17. The non-transitory computer-readable storage medium of claim 16 wherein the instructions that cause the computer processor to cut the projected 2D connected component further comprises:

instructions that cause the computer processor to, before identifying the edge, rotate the projected 2D connected component to minimize an area of a rectangular bounding box containing the projected 2D connected component.

18. The non-transitory computer-readable storage medium of claim 16 wherein the instructions that cause the computer processor to pack the bounding boxes of all sub-components comprises:

instructions that cause the computer processor to sort the bounding boxes for all sub-components in a descending order by lengths of their longer edges;

instructions that cause the computer processor to pick a first unpacked bounding box;

instructions that cause the computer processor to search for an available space in all current atlases that the first unpacked bounding box can fit into; and

instructions that cause the computer processor to pack the first unpacked bounding box in the available space.

19. The non-transitory computer-readable storage medium of claim 11 wherein the plurality of instructions further comprising:

instructions that cause the computer processor to, before storing the one or more atlases:

divide each atlas into a plurality of blocks, each block including a plurality of pixels; and

for each block that includes both textured pixels and dark pixels, fill dark pixels with colors from textured pixels;

wherein storing the one or more atlases uses a compression standard.

20. The non-transitory computer-readable storage medium of claim 11 wherein the plurality of instructions further comprising:

instructions that cause the computer processor to, before storing the one or more atlases:

divide each atlas into a plurality of blocks, each block including a plurality of pixels;

for each block that includes both textured pixels and dark pixels, fill dark pixels with colors from textured pixels; and

fill each block that includes only dark pixels with colors from a neighboring textured block;

wherein storing the one or more atlases uses a compression standard.