System and method for identifying an aperture in a representation of an object
First Claim
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.
8 Assignments
0 Petitions
Accused Products
Abstract
An iterative process for determining an aperture in a representation of an object is disclosed. The object is received and a bounding box corresponding thereto is determined. The bounding box includes a plurality of initial voxels and the object is embedded therein. An intersecting set of initial voxels is determined, as well as an internal set and an external set of initial voxels. The resolution of the voxels is iteratively decreased until the ratio of internal voxels to external voxels exceeds a predetermined threshold. The voxels corresponding to the final iteration are the final voxels. An internal set of final voxels is determined. A union set of initial voxels is determined indicating an intersection between the external set of initial voxels and the internal set of final voxels. From the union set of initial voxels and the external set of initial voxels, a location of an aperture is determined.
-
Citations
18 Claims
-
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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
-
Specification