Granted Patent B2

US 9,024,948 · App. 13/685,815 · Granted May 5, 2015

Abstract

Claims (60)

1. A computer-implemented method for generating a representation of an outer layer of a three-dimensional object, the method comprising:

receiving, at a processing device, a data structure defining a three-dimensional object, the data structure including a plurality of triangles that entirely form the three-dimensional object, each triangle being defined by three vertices;

determining, at the processing device, a three-dimensional bounding box having dimensions sufficient to encapsulate the three-dimensional object, the bounding box being comprised of a plurality of voxels;

determining, at the processing device, an intersecting set of voxels from the plurality of voxels, wherein each member of the intersecting set of voxels is intersected by at least one triangle of the plurality of triangles;

determining, at the processing device, an outer set of voxels from the intersecting set of voxels, wherein each member of the outer set of voxels shares a face with a voxel that is not a member of the intersecting set of voxels; and

determining, at the processing device, an outer layer set of triangles from the plurality of triangles to obtain a modified data structure defining only an outer skin of the three-dimensional object, the outer layer set of triangles being comprised of triangles having at least one vertex which intersect the outer set of voxels, wherein the data structure and the modified data structure have the same alternate conventions for defining the three-dimensional object.

2. The computer-implemented method of claim 1 , wherein the data structure is a first tree that includes a first plurality of leaf nodes, each leaf node in the first plurality of leaf nodes representing one of the plurality of triangles, and the modified data structure is a second tree that includes a second plurality of leaf nodes, each leaf node in the second plurality of leaf nodes representing one of the triangles in the outer layer set of triangles and being originally from the first plurality of leaf nodes.

3. The computer-implemented method of claim 2 , wherein determining the outer layer set of triangles includes:

traversing the tree to identify each leaf node of the tree; and

for each leaf node of the tree:

determining whether the three vertices of the triangle represented by the leaf node intersect the outer set of voxels; and

when at least one of the vertices of the triangle does not intersect the outer set of voxels, removing the leaf node representing the triangle from the tree.

4. The computer-implemented method of claim 2 , wherein the tree includes a plurality of shape nodes, each shape node defining a different portion of the three-dimensional object, and wherein each leaf in the tree belongs to one of a plurality of shape nodes.

5. The computer-implemented method of claim 4 , wherein each shape node includes a mathematical expression defining a shape of the portion defined by the shape node, and the triangles of the leaves which belong to the shape node represent the portion of the three-dimensional object.

6. The computer-implemented method of claim 5 , wherein obtaining the modified data structure includes:

traversing the tree to identify each leaf node of the tree; and

for each leaf node of the tree:

determining whether the three vertices of the triangle represented by the leaf node intersect the outer set of voxels; and

when at least one of the vertices of the triangle does not intersect the outer set of voxels, removing the leaf node representing the triangle from the tree.

7. The computer-implemented method of claim 6 , wherein the modified data structure includes the plurality of shape nodes.

8. The computer-implemented method of claim 1 wherein each voxel in the bounding box has a state value associated thereto, the state value of each voxel being initially assigned a default value.

9. The computer-implemented method of claim 8 , wherein determining the intersecting set of voxels includes:

embedding the three-dimensional object into the bounding box; and

changing the state value a particular voxel from the default value to a first value if and only if at least a portion of at least one triangle of the plurality of triangles intersects the particular voxel, wherein the state values of each voxel in the intersecting set of voxels is changed to the first value.

10. The computer-implemented method of claim 9 wherein determining the outer set of voxels includes:

i) determining a non-intersecting set of voxels from the plurality of voxels, wherein the state values of the voxels of the non-intersecting set of voxels are equal to the default value after the intersecting set of voxels is determined; and

ii) setting a state value of any voxel in the intersecting set of voxels to a second value if the voxel shares a face with at least one voxel in the non-intersecting voxels;

wherein the outer set of voxels is comprised of a plurality of voxels that have state values equal to the second value.

11. A system comprising a processing device for generating a representation of an outer layer of a three-dimensional object, the system comprising:

a bounding box determination module that:

receives a data structure defining the three-dimensional object, the data structure including a plurality of triangles entirely forming the three-dimensional object, each triangle being defined by three vertices, and

determines a three-dimensional bounding box having dimensions sufficient to encapsulate the three-dimensional object, the bounding box being comprised of a plurality of voxels;

an object-to-voxel module that determines an intersecting set of voxels from the plurality of voxels, wherein each member of the intersecting set of voxels intersects with at least one triangle of the plurality of triangles; and

an outer layer determination module that:

determines an outer set of voxels from the intersecting set of voxels, wherein each member of the outer set of voxels shares a face with a voxel that is not a member of the intersecting set of voxels, and

determines an outer layer set of triangles from the plurality of triangles to obtain a modified data structure defining only an outer skin of the three-dimensional object, the outer layer set of triangles being comprised of triangles having at least one vertex which intersect the outer set of voxels,

wherein the data structure and the modified data structure have the same alternate conventions for defining the three-dimensional object.

12. The system of claim 11 , wherein the data structure is a first tree that includes a first plurality of leaf nodes, each leaf node in the first plurality of leaf nodes representing one of the plurality of triangles, and the modified data structure is a second tree that includes a second plurality of leaf nodes, each leaf node in the second plurality of leaf nodes representing one of the triangles in the outer layer set of triangles and being originally from the first plurality of leaf nodes.

13. The system of claim 12 , wherein the outer layer determination module is configured to:

traverse the tree to identify each leaf node of the tree; and

for each leaf node of the tree:

determine whether the three vertices of the triangle represented by the leaf node intersect the outer set of voxels; and

remove the leaf node representing the triangle from the tree when none of the vertices of the triangle does not intersect the outer set of voxels.

14. The system of claim 12 , wherein the tree includes a plurality of shape nodes, each shape node defining a different portion of the three-dimensional object, and wherein each leaf in the tree belongs to one of a plurality of shape nodes.

15. The system of claim 14 , wherein each shape node includes a mathematical expression defining a shape of the portion defined by the shape node, and the triangles of the leaves which belong to the shape node represent the portion of the three-dimensional object.

16. The system of claim 15 , wherein the outer layer determination module is configured to:

traverse the tree to identify each leaf node of the tree; and

for each leaf node of the tree:

determine whether the three vertices of the triangle represented by the leaf node intersect the outer set of voxels; and

remove the leaf node representing the triangle from the tree when none of the vertices of the triangle does not intersect the outer set of voxels,

wherein the modified data structure is obtained after each of the leaf nodes that do not intersect the outer set of voxels has been removed from the tree.

17. The system of claim 16 , wherein the modified data structure includes the plurality of shape nodes.

18. The system of claim 11 wherein each voxel in the bounding box has a state value associated thereto, the state value of each voxel being initially assigned a default value.

19. The system of claim 18 , wherein the object-to-voxel module is configured to:

embed the three-dimensional object into the bounding box; and

change the state value a voxel from the default value to a first value if and only if at least a portion of at least one triangle of the plurality of triangles intersects the voxel, wherein the state values of each voxel in the intersecting set of voxels is changed to the first value.

20. The system of claim 19 wherein the outer layer determination module is configured to:

i) determine a non-intersecting set of voxels from the plurality of voxels, wherein the state values of the voxels of the non-intersecting set of voxels are equal to the default value after the intersecting set of voxels is determined; and

ii) set a state value of any voxel in the intersecting set of voxels to a second value if the voxel shares a face with at least one voxel in the non-intersecting voxels;

wherein the outer set of voxels is comprised of a plurality of voxels that have state values equal to the second value.

Assignments (8)