Granted Patent B2

US 9,311,744 · App. 13/735,200 · Granted Apr 12, 2016

Abstract

Claims (43)

1. A method for generating a representation of just an outer layer of a three-dimensional object, the object represented by a plurality of two-dimensional triangles, the method comprising:

receiving the plurality of two-dimensional triangles representing the object;

determining a three-dimensional bounding box having dimensions sufficient to encapsulate the object, the bounding box being comprised of a plurality of voxels, wherein each voxel in the bounding box has a state value associated thereto, wherein the state value of each voxel is initially assigned a default value;

determining 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;

changing the state value of the voxels in the intersecting set of voxels from the default value to a first value;

determining 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;

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;

for each particular voxel having the first value as the state value:

identifying a neighboring voxel that shares a face with the particular voxel; and

changing the state value of the neighboring voxel to a second value if the state value of the neighboring voxel is determined to be equal to the first value and the neighboring voxel shares a face with at least one voxel in the non-intersecting set of voxels; and

isolating the voxels having the second value as the state value and generating the representation of just the outer layer of the three-dimensional objection therefrom.

2. The method of claim 1 wherein the bounding box is comprised of i×j×k voxels, where i is an amount of voxels across the width of the bounding box, j is an amount of voxels across the height of the bounding box, and k is the amount of voxels across the depth of the bounding box.

3. The method of claim 2 wherein determining the three-dimensional bounding box comprises determining a maximum width of the object, a maximum height of the object, and a maximum depth of the object, and wherein i, j, and k, are determined based on the maximum width, the maximum height, and maximum depth, respectively.

4. The method of claim 1 wherein the state values of each voxel in the intersecting set of voxels is assigned the first value.

5. The method of claim 4 wherein the outer set of voxels is comprised of a plurality of voxels that have state values equal to the second value.

6. The method of claim 5 wherein the step of changing the state value of the neighboring voxel to the second value further comprises:

identifying a first non-intersecting voxel from the non-intersecting set of voxels;

inserting the first non-intersecting voxel into a check queue;

iteratively performing the following steps until the check queue is empty:

removing a current voxel from the check queue;

for each face of the current voxel,

determining the state value of the neighboring voxel at the face, and inserting the neighboring voxel into the check queue if the state value of the neighboring voxel is equal to the default value, and

changing the state value of the neighboring voxel to the second value if the state value of the neighboring voxel is determined to be equal to the first value.

7. The method of claim 5 wherein the determining the outer layer set of triangles comprises for each triangle in the object determining whether the three vertices of the triangle are located in at least one of the set of outer voxels, and if so, including the triangle in the outer layer set of triangles.

8. The method of claim 1 wherein a voxel is represented by a data structure containing a reference point of the voxel indicating a location within the bounding box, a state variable, and a neighbor array having six elements, each element pointing to a different neighboring voxel.

9. A system for generating a representation of just an outer layer of a three-dimensional object, the object represented by a plurality of two-dimensional triangles, the system comprising:

a bounding box determination module that receives the plurality of two-dimensional triangles representing the object and that determines a three-dimensional bounding box having dimensions sufficient to encapsulate the object, the bounding box being comprised of a plurality of voxels, wherein each voxel in the bounding box has a state value associated thereto, wherein the state value of each voxel is initially assigned a default value;

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, wherein the object-to-voxel module changes the state value of the voxels in the intersecting set of voxels from the default value to a first value; and

a 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 that determines an outer layer set of triangles from the plurality of triangles, the outer layer set of triangles being comprised of triangles that have at least one vertex that intersect the outer set of voxels, wherein the outer layer determination module determines 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, wherein the outer layer determination module, for each particular voxel having the first value as the state value, identifies a neighboring voxel that shares a face with the particular voxel and changes the state value of the neighboring voxel to a second value if the state value of the neighboring voxel is determined to be equal to the first value and the neighboring voxel shares a face with at least one voxel in the non-intersecting set of voxels, and wherein the outer layer determination module isolates the voxels having the second value as the state value and generates the representation of just the outer layer of the three-dimensional object therefrom.

10. The system of claim 9 wherein the bounding box is comprised of i×j×k voxels, where i is an amount of voxels across the width of the bounding box, j is an amount of voxels across the height of the bounding box, and k is the amount of voxels across the depth of the bounding box.

11. The system of claim 10 wherein the bounding box determination module determines a maximum width of the object, a maximum height of the object, and a maximum depth of the object, and wherein i, j, and k, are determined based on the maximum width, the maximum height, and maximum depth, respectively.

12. The system of claim 9 wherein the state values of each voxel in the intersecting set of voxels is assigned the first value.

13. The system of claim 12 wherein the outer set of voxels is comprised of a plurality of voxels that have state values equal to the second value.

14. The system of claim 13 wherein the outer layer determination module:

identifies a first non-intersecting voxel from the non-intersecting set of voxels;

inserts the first non-intersecting voxel into a check queue; and

iteratively performs the following steps until the check queue is empty:

removing a current voxel from the check queue;

for each face of the current voxel,

determining the state value of the neighboring voxel at the face, and inserting the neighboring voxel into the check queue if the state value of the neighboring voxel is equal to the default value, and

changing to the state value of the neighboring voxel to the second value if the state value of the neighboring voxel is determined to be equal to the first value.

15. The system of claim 13 wherein the outer layer determination module determines the outer layer set of triangles by determining for each triangle in the object whether at least one vertex of the triangle is located in at least one of the set of outer voxels, and if so, including the triangle in an outer skin set of triangles.

16. The system of claim 9 wherein a voxel is represented by a data structure containing a reference point of the voxel indicating a location within the bounding box, a state variable, and a neighbor array having six elements, each element pointing to a different neighboring voxel.

Assignments (8)