Granted Patent B2

US 8,923,606 · App. 13/735,199 · Granted Dec 30, 2014

Abstract

Claims (50)

1. A method for identifying an aperture in a three-dimensional (3D) representation of an object, the method comprising:

receiving a plurality of two-dimensional (2D) triangles representing the object;

determining a 3D bounding box having dimensions sufficient to encapsulate the object, the 3D bounding box including a plurality of initial voxels for the 3D bounding box, wherein initial voxels of the plurality each have equal initial dimensions;

determining an intersecting set of initial voxels from the plurality of initial voxels, wherein each initial voxel of the intersecting set of initial voxels intersects with at least one of the plurality of 2D triangles;

determining an external set of initial voxels from the plurality of initial voxels, the external set of initial voxels being exclusive from the intersecting set of initial voxels and not wholly encapsulated by voxels from the intersecting set of initial voxels;

determining a plurality of final voxels corresponding to the bounding box, wherein each of the plurality of final voxels have equal final dimensions;

determining an intersecting set of final voxels from the plurality of final voxels, wherein each final voxel of the intersecting set of final voxels intersects with at least one of the plurality of 2D triangles;

determining an internal set of final voxels from the plurality of final voxels, the internal set of final voxels being exclusive from the final intersecting set of final voxels and wherein each final voxel of the internal set of final voxels is wholly encapsulated by the final voxels of the intersecting set of final voxels;

determining a union set of initial voxels from the plurality of initial voxels based on the external set of initial voxels and the internal set of final voxels, wherein an initial voxel of the union set of initial voxels intersects a final voxel of the internal set of final voxels; and

determining a location of the aperture by identifying initial voxels of the union set of initial voxels that share at least one face with at least one initial voxel of the external set of initial voxels.

2. The method of claim 1 further comprising generating a cover sufficient to seal the aperture based on the location of the aperture and the identified initial voxels in the union set of initial voxels that share at least one face with at least one initial voxel in the external set of initial voxels.

3. The method of claim 2 wherein the cover is generated by generating at least two triangles based on a face that is shared by an identified initial voxel of the union set of initial voxels and an initial voxel of the external set of initial voxels and including the at least two triangles in the plurality of triangles.

4. The method of claim 1 further comprising determining an internal set of initial voxels from the plurality of initial voxels, the internal set of initial voxels being exclusive from the intersecting set of initial voxels and wherein each initial voxel of the internal set of initial voxels is wholly encapsulated by the initial voxels in the intersecting set of initial voxels.

5. The method of claim 4 wherein the external set of initial voxels, the internal set of initial voxels, and the intersecting set of initial voxels are mutually exclusive.

6. The method of claim 1 further comprising determining an external set of final voxels from the plurality of final voxels, the external set of final voxels being exclusive from the intersecting set of final voxels and the internal set of final voxels.

7. The method of claim 6 wherein the plurality of final voxels is determined by iteratively performing the following steps:

i) determining a plurality of new voxels wherein each of the plurality of new voxels have equal new dimensions, wherein the new dimensions are greater than previous dimensions;

ii) determining a new external set of new voxels and a new internal set of new voxels;

iii) determining a first value corresponding to a first amount of new voxels in the new external set of new voxels;

iv) determining a second value corresponding to a second amount of new voxels in the new internal set of new voxels;

v) determining a ratio based on the first value and the second value; and

vi) comparing the ratio with a predetermined threshold;

wherein the steps i) through vi) are iteratively performed until the ratio exceeds the predetermined threshold.

8. The method of claim 7 wherein the ratio is determined by dividing the second value by the first value.

9. The method of claim 7 wherein the final plurality of final voxels, the internal set of final voxels and the external set of final voxels are equal to the new plurality of new voxels, the new internal set of new voxels and the new external set of new voxels, respectively, after a final iteration is performed.

10. A system for identifying an aperture in a three-dimensional (3D) representation of an object, the system comprising:

a bounding box determination module that receives a plurality of two-dimensional (2D) triangles representing the object, and that determines a 3D bounding box having dimensions sufficient to encapsulate the object, the 3D bounding box including a plurality of initial voxels, wherein initial voxels of the plurality each have equal initial dimensions;

a union set determination module that:

i) determines an intersecting set of initial voxels from the plurality of initial voxels, wherein each initial voxel of the intersecting set of initial voxels intersects with at least one of the plurality of 2D triangles,

ii) determines an external set of initial voxels from the plurality of initial voxels, the external set of initial voxels being exclusive from the intersecting set of initial voxels and not wholly encapsulated by voxels from the intersecting set of initial voxels,

iii) determines a plurality of final voxels corresponding to the 3D bounding box, wherein final voxels of the plurality of final voxels each have equal final dimensions,

iv) determines an intersecting set of final voxels from the plurality of final voxels, wherein each final voxel of the intersecting set of final voxels intersects with at least one of the plurality of 2D triangles,

v) determines an internal set of final voxels from the plurality of final voxels, the internal set of final voxels being exclusive from the intersecting set of final voxels and wherein each final voxel of the internal set of final voxels is wholly encapsulated by the final voxels of the intersecting set of final voxels, and

vi) determines a union set of initial voxels from the plurality of initial voxels based on the external set of initial voxels and the internal set of final voxels, wherein an initial voxel of the union set of initial voxels intersects a final voxel of the internal set of final voxels; and

an aperture location determination module that determines a location of the aperture by identifying initial voxels of the union set of initial voxels that share at least one face with at least one initial voxel of the external set of initial voxels.

11. The system of claim 10 further comprising an aperture cover generation module that generates a cover sufficient to seal the aperture based on the location of the aperture and the identified initial voxels of the union set of initial voxels that share at least one face with at least one initial voxel of the external set of initial voxels.

12. The system of claim 11 wherein the aperture cover generation module generates the cover by generating at least two triangles based on a face that is shared by an identified initial voxel of the union set of initial voxels and an initial voxel of the external set of initial voxels and including the at least two triangles in the plurality of triangles.

13. The system of claim 10 wherein the union set determination module further determines an internal set of initial voxels from the plurality of initial voxels, the internal set of initial voxels being exclusive from the intersecting set of initial voxels and wherein each initial voxel of the internal set of initial voxels is wholly encapsulated by the initial voxels in the intersecting set of initial voxels.

14. The system of claim 13 wherein the external set of initial voxels, the internal set of initial voxels, and the intersecting set of initial voxels are mutually exclusive.

15. The system of claim 10 further comprising determining an external set of final voxels from the plurality of final voxels, the external set of final voxels being exclusive from the intersecting set of final voxels and the internal set of final voxels.

16. The system of claim 15 wherein the union set determination module determines the plurality of final voxels by iteratively performing the following steps:

i) determining a plurality of new voxels wherein each of the plurality of new voxels have equal new dimensions, wherein the new dimensions are greater than previous dimensions;

ii) determining a new external set of new voxels and a new internal set of new voxels;

iii) determining a first value corresponding to a first amount of new voxels in the new external set of new voxels;

iv) determining a second value corresponding to a second amount of new voxels in the new internal set of new voxels;

v) determining a ratio based on the first value and the second value; and

vi) comparing the ratio with a predetermined threshold;

wherein the steps i) through vi) are iteratively performed until the ratio exceeds the predetermined threshold.

17. The system of claim 16 wherein the ratio is determined by dividing the second value by the first value.

18. The system of claim 16 wherein the plurality of final voxels, the internal set of final voxels and the external set of final voxels are equal to the new plurality of new voxels, the new internal set of new voxels and the new external set of new voxels, respectively, after a final iteration is performed.

Assignments (7)