System, method, and computer program product for determining a translation vector

1. A method for determining a minimal translation vector (MTV) between a first object and a second object represented in a CAD system, comprising the steps of:

retrieving, in the CAD system, the first object and the second object;

tessellating the first object and second object, by the CAD system, into respective facets;

creating a bounding volume tree of facets, by the CAD system, for each of the first object and the second object;

performing a greedy process on the bounding volume trees, by the CAD system, to produce a initial MTV; and

performing a successive clipping process according to the bounding volume trees and the initial MTV, by the CAD system, to produce a final MTV, wherein the successive clipping process does not process at least a portion of the bounding volume tree based on facets that are outside of a clipping window;

storing the final MTV in a computer readable medium.

2. The method of claim 1 , wherein the greedy process is performed a first time, using a bounding box approximation up to tree level 3 , to determine an estimated MTV, and is performed a second time, using a bounding box approximation and clipping window technique up to tree level 10 , to determine an improved MTV that is output as the initial MTV.

3. The method of claim 1 , wherein the greedy process includes the steps of:

loading initial data;

initializing a tree level and the clipping window;

while the tree level is less than or equal to a maximum tree level, then performing a voxel process using the tree level and the clipping window to determine a revised MTV; and

storing the revised MTV and outputting the revised MTV.

4. The method of claim 3 , wherein the initial data includes one or more of a minimum level, the maximum level, a clipping value, the bounding volume trees, and a current MTV.

5. The method of claim 3 , wherein the voxel process includes the steps of:

loading voxel initial data;

building a voxel model of the clipping window;

computing the Minkowski Difference between the bounding volume trees;

if there is an intersection between the clipping window and the Minkowski Difference, then marking each voxel in the voxel model;

determining at least one candidate voxel from the marked voxels and determining a candidate voxel with a smallest vector from an origin;

outputting the smallest vector from the origin as the revised MTV.

6. The method of claim 5 , wherein the voxel initial data includes one or more of a tree level, a Use Box value, the clipping window, the bounding volume trees, and the current MTV.

7. The method of claim 1 , wherein the successive clipping process includes the steps of:

loading clipping process initial data;

constructing the clipping window so that it contains a current MTV and is closer to an origin than a previous clipping window;

performing a voxel process using the tree level and the clipping window to determine a revised MTV;

if the revised MTV is not within the clipping window, then repeating to the constructing step; and

storing the revised MTV and outputting the revised MTV as a final MTV.

8. A CAD system comprising: a processor and accessible memory, the CAD system particularly configured to perform a process for determining a minimal translation vector (MTV) between a first object and a second object represented in a CAD system, including the steps of:

retrieving the first object and the second object;

tessellating the first object and second object into respective facets;

creating a bounding volume tree of facets for each of the first object and the second object;

performing a greedy process on the bounding volume trees to produce a initial MTV; and

performing a successive clipping process according to the bounding volume trees and the initial MTV to produce a final MTV, wherein the successive clipping process does not process at least a portion of the bounding volume tree based on facets that are outside of a clipping window;

storing the final MTV in a computer readable medium.

9. The CAD system of claim 8 , wherein CAD systems performs the greedy process a first time, using a bounding box approximation up to tree level 3 , to determine an estimated MTV, and a second time, using a bounding box approximation and clipping window technique up to tree level 10 , to determine an improved MTV that is output as the initial MTV.

10. The CAD system of claim 8 , wherein the greedy process performed by the CAD system includes the steps of:

loading initial data;

initializing a tree level and the clipping window;

while the tree level is less than or equal to a maximum tree level, then performing a voxel process using the tree level and the clipping window to determine a revised MTV; and

storing the revised MTV and outputting the revised MTV.

11. The CAD system of claim 10 , wherein the initial data includes one or more of a minimum level, the maximum level, a clipping value, the bounding volume trees, and a current MTV.

12. The CAD system of claim 10 , wherein the voxel process performed by the CAD system includes the steps of:

loading voxel initial data;

building a voxel model of the clipping window;

computing the Minkowski Difference between the bounding volume trees;

if there is an intersection between the clipping window and the Minkowski Difference, then marking each voxel in the voxel model;

determining at least one candidate voxel from the marked voxels and determining a candidate voxel with a smallest vector from an origin;

outputting the smallest vector from the origin as the revised MTV.

13. The CAD system of claim 12 , wherein the voxel initial data includes one or more of a tree level, a Use Box value, the clipping window, the bounding volume trees, and the current MTV.

14. The CAD system of claim 8 , wherein the successive clipping process performed by the CAD system includes the steps of:

loading clipping process initial data;

constructing the clipping window that contains a current MTV and is closer to an origin than a previous clipping window;

performing a voxel process using the tree level and the clipping window to determine a revised MTV;

if the revised MTV is not within the clipping window, then repeating to the constructing step; and

storing the revised MTV and outputting the revised MTV as a final MTV.

15. A non-transitory computer readable medium encoded with computer method instructions that, when executed, cause a CAD system to perform a process for determining a minimal translation vector (MTV) between a first object and a second object represented in the CAD system, including the steps of:

retrieving the first object and the second object;

tessellating the first object and second object into respective facets;

creating a bounding volume tree of facets for each of the first object and the second object;

performing a greedy process on the bounding volume trees to produce a initial MTV; and

performing a successive clipping process according to the bounding volume trees and the initial MTV to produce a final MTV, wherein the successive clipping process does not process at least a portion of the bounding volume tree based on facets that are outside of a clipping window;

storing the final MTV in a computer readable medium.

16. The computer readable medium of claim 15 , wherein the greedy process is performed a first time, using a bounding box approximation up to tree level 3 , to determine an estimated MTV, and is performed a second time, using a bounding box approximation and clipping window technique up to tree level 10 , to determine an improved MTV that is output as the initial MTV.

17. The computer readable medium of claim 15 , wherein the greedy process includes the steps of:

loading initial data;

initializing a tree level and the clipping window;

while the tree level is less than or equal to a maximum tree level, then performing a voxel process using the tree level and the clipping window to determine a revised MTV; and

storing the revised MTV and outputting the revised MTV.

18. The computer readable medium of claim 17 , wherein the initial data includes one or more of a minimum level, the maximum level, a clipping value, the bounding volume trees, and a current MTV.

19. The computer readable medium of claim 17 , wherein the voxel process includes the steps of:

loading voxel initial data;

building a voxel model of the clipping window;

computing the Minkowski Difference between the bounding volume trees;

if there is an intersection between the clipping window and the Minkowski Difference, then marking each voxel in the voxel model;

determining at least one candidate voxel from the marked voxels and determining a candidate voxel with a smallest vector from an origin;

outputting the smallest vector from the origin as the revised MTV.

20. The computer readable medium of claim 19 , wherein the voxel initial data includes one or more of a tree level, a Use Box value, the clipping window, the bounding volume trees, and the current MTV.

21. The computer readable medium of claim 15 , wherein the successive clipping process includes the steps of:

loading clipping process initial data;

constructing the clipping window so that it contains a current MTV and is closer to an origin than a previous clipping window;

performing a voxel process using the tree level and the clipping window to determine a revised MTV;

if the revised MTV is not within the clipping window, then repeating to the constructing step; and

storing the revised MTV and outputting the revised MTV as a final MTV.