System and method for efficient real-time technique for point localization in and out of a tetrahedral mesh

1. A method for determining whether a point is contained in a sub-volume of a digitized medical image, comprising the steps of:

providing a digitized image volume, said image volume comprising a plurality of intensities associated with a 3-dimensional grid of voxels;

representing a sub-volume of said image with a tetrahedron volume mesh (TVM);

providing a point M in said image;

finding a vertex P of said TVM that is closest to point M; and

determining whether there exists a tetrahedron T in said TVM that defines a solid angle around point P where point M is located, wherein if no such tetrahedron T exists, then point M is outside said TVM, and wherein if T exists and M is inside T, then M is inside said TVM.

2. The method of claim 1 , wherein if tetrahedron T exists and M is not inside T, further comprising the steps of:

finding a facet F of tetrahedron T through which a line PM connecting points M and P exits T;

determining whether a next tetrahedron T i+1 of said TVM exists along line PM, wherein if no such tetrahedron T i+1 exists, then point M is outside said TVM, and wherein if T i+1 exists, determining whether point M is inside tetrahedron T i+1 .

3. The method of claim 2 , wherein if point M is inside tetrahedron T i+1 , then point M is inside said TVM, and if point M is not inside tetrahedron T i+1 , repeating said steps of finding a facet F of tetrahedron T i+1 through which a line PM exits T i+1 and determining whether another tetrahedron of said TVM exists along line PM.

4. The method of claim 2 , wherein determining whether point M is inside tetrahedron T i+1 , wherein tetrahedron T i+1 has vertices A, B, C, D, comprises testing whether the inequalities

( BM · N A ABCD )·( BA · N A ABCD )≧0,

( CM · N B ABCD )·( CB · N B ABCD )≧0,

( DM · N C ABCD )·( DC · N C ABCD )≧0,

( AM · N D ABCD )·( AD · N D ABCD )≧0,

hold true, wherein N A ABCD , N B ABCD , N C ABCD , and N D ABCD are the normal vectors to the four facets of ABCD, and the subscript corresponds to the opposite vertex of the facet.

5. The method of claim 2 , wherein finding a facet F of tetrahedron T wherein tetrahedron T has vertices A, B, C, P, through which line PM exits T comprises, for a first tetrahedron along line PM, finding facet ABC and the point H 0 in ABC through which line PM exits, and for a subsequent tetrahedron T i along line PM, finding the points of intersection of line PM with the planes containing each of the other facets of tetrahedron T and determining which intersection point is contained within the triangle of a facet of tetrahedron T.

6. The method of claim 5 , wherein finding the points of intersection of line PM with the planes containing each of the other facets of tetrahedron T comprises calculating

OH

i

B

i

⁢

C

i

⁢

D

i

_

=

OP

_

+

N

A

i

A

i

⁢

B

i

⁢

C

i

⁢

D

i

_

·

PA

i

_

N

A

i

A

i

⁢

B

i

⁢

C

i

⁢

D

i

_

·

PM

_

⁢

PM

_

,

OH

i

A

i

⁢

B

i

⁢

D

i

_

=

OP

_

+

N

B

i

A

i

⁢

B

i

⁢

C

i

⁢

D

i

_

·

PB

i

_

N

B

i

A

i

⁢

B

i

⁢

C

i

⁢

D

i

_

·

PM

_

⁢

PM

_

,

OH

i

A

i

⁢

B

i

⁢

C

i

_

=

OP

_

+

N

C

i

A

i

⁢

B

i

⁢

C

i

⁢

D

i

_

·

PC

i

_

N

C

i

A

i

⁢

B

i

⁢

C

i

⁢

D

i

_

·

PM

_

⁢

PM

_

.

wherein point O is the origin of the coordinate system, N A ABCD , N B ABCD , N C ABCD , and N D ABCD are the normal vectors to the four facets of ABCD and the subscript corresponds to the opposite vertex of the facet, and H i B i C i D i , H i A i B i C i , H i A i B i D i , are the points of intersection with the planes of facets B i C i D i , A i B i C i , and A i B i D i of tetrahedron T i .

7. The method of claim 6 , wherein if H i−1 H i B i C i D i · N B i A i B i C i D i ≧0 and H i−1 H i B i C i D i · N C i A i B i C i D i ≧0 then H i =H i B i C i D i , if H i−1 H i A i C i D i · N A i A i B i C i D i ≧0 and H i−1 H i B i C i D i · N C i A i B i C i D i ≧0 then H i =H i A i C i D i , or if H i−1 H i A i B i D i · N A i A i B i C i D i ≧0 and H i−1 H i B i C i D i · N B i A i B i C i D i ≧0 then H i =H i A i B i D i , wherein H i−1 is the intersection point of a previous tetrahedron along line PM.

8. The method of claim 1 , further comprising computing an octree to represent said digital image volume, wherein said vertex P of said TVM that is closest to point M is found by using a nearest point algorithm on said octree.

9. The method of claim 2 , further comprising:

computing a list L P of all tetrahedra of said TVM;

computing and storing normal vectors of each of the four facets of each tetrahedron in said list; and

computing a table of facets T F corresponding to each normal vector;

searching said list L P to find said tetrahedron Tin said TVM that defines a solid angle around point P in which point M is located; and

searching said facet table T F to find said next tetrahedron T i+1 of said TVM along line PM.

10. The method of claim 9 , further comprising, for a TVM that is not convex, searching said facet table T F to find facets T B with no other corresponding facets, computing a convex envelope of the facets T B and adding facets {tilde over (T)} B corresponding to said envelope to said facets T B , computing connected components C({tilde over (T)} B ) in {tilde over (T)} B , and filling each connected component of C({tilde over (T)} B ) with a tetrahedron labeled as an outside tetrahedron, wherein tetrahedra of said non-convex TVM are labeled as inside tetrahedra, wherein said TVM is converted to a convex sub-volume.

11. The method of claim 10 , wherein point M is inside said TVM if said tetrahedron T is an inside tetrahedron.

12. A method for determining whether a point is contained in a sub-volume of a digitized medical image, comprising the steps of:

providing a tetrahedron volume mesh (TVM) representing a sub-volume of a digital image volume, and a point M;

finding a vertex P of said TVM that is closest to point M;

finding a tetrahedron T i in said TVM that defines a solid angle around point P where point M is located, wherein if M is inside T i , then M is inside said TVM;

if M is not inside T i , finding a facet F of tetrahedron T i through which a line PM connecting points M and P exits T i ; and

determining whether a next tetrahedron T i+1 of said TVM exists along line PM, wherein if no such tetrahedron T i+1 exists, then point M is outside said TVM, and wherein if T i+1 exists, determining whether point M is inside tetrahedron T i+1 .

13. The method of claim 12 , wherein if no such tetrahedron T i in said TVM exists that defines a solid angle around point P where point M is located, then point M is outside said TVM.

14. The method of claim 12 , wherein if point M is inside tetrahedron T i+1 , then point M is inside said TVM, and if point M is not inside tetrahedron T i+1 , repeating said steps of finding a facet F of tetrahedron T i+1 through which a line PM exits T i+1 and determining whether another tetrahedron of said TVM exists along line PM.

15. The method of claim 12 , wherein determining whether point M is inside tetrahedron T i+1 , wherein tetrahedron T i+1 has vertices A, B, C, D, comprises testing whether the inequalities

( BM · N A ABCD )·( BA · N A ABCD )≧0,

( CM · N B ABCD )·( CB · N B ABCD )≧0,

( DM · N C ABCD )·( DC · N C ABCD )≧0,

( AM · N D ABCD )·( AD · N D ABCD )≧0,

hold true, wherein N A ABCD , N B ABCD , N C ABCD , and N D ABCD are the normal vectors to the four facets of ABCD, and the subscript corresponds to the opposite vertex of the facet.

16. The method of claim 12 , wherein finding a facet F of tetrahedron T wherein tetrahedron T has vertices A, B, C, P, through which line PM exits T comprises, for a first tetrahedron along line PM, finding facet ABC and the point H 0 in ABC through which line PM exits, and for a subsequent tetrahedron T i along line PM, finding the points of intersection of line PM with the planes containing each of the other facets of tetrahedron T and determining which intersection point is contained within the triangle of a facet of tetrahedron T.

17. A non-transitory computer readable storage device, tangibly embodying a program of instructions executable by the computer to perform the method steps for determining whether a point is contained in a sub-volume of a digitized medical image, said method comprising the steps of: providing a digitized image volume, said image volume comprising a plurality of intensities associated with a 3-dimensional grid of voxels; representing a sub-volume of said image with a tetrahedron volume mesh (TVM); providing a point M in said image; finding a vertex P of said TVM that is closest to point M; and determining whether there exists a tetrahedron T in said TVM that defines a solid angle around point P where point M is located, wherein if no such tetrahedron T exists, then point M is outside said TVM, and wherein if T exists and M is inside T, then M is inside said TVM.

18. The computer readable program storage device of claim 17 , wherein if tetrahedron T exists and M is not inside T, the method further comprises the steps of:

finding a facet F of tetrahedron T through which a line PM connecting points M and P exits T;

determining whether a next tetrahedron T i+1 of said TVM exists along line PM, wherein if no such tetrahedron T i+1 exists, then point M is outside said TVM, and wherein if T i+1 exists, determining whether point M is inside tetrahedron T i+1 .

19. The computer readable program storage device of claim 18 , wherein if point M is inside tetrahedron T i+1 , then point M is inside said TVM, and if point M is not inside tetrahedron T i+1 , repeating said steps of finding a facet F of tetrahedron T i+1 through which a line PM exits T i+1 and determining whether another tetrahedron of said TVM exists along line PM.

20. The computer readable program storage device of claim 18 , wherein determining whether point M is inside tetrahedron T i+1 , wherein tetrahedron T i+1 has vertices A, B, C, D, comprises testing whether the inequalities

( BM · N A ABCD )·( BA · N A ABCD )≧0,

( CM · N B ABCD )·( CB · N B ABCD )≧0,

( DM · N C ABCD )·( DC · N C ABCD )≧0,

( AM · N D ABCD )·( AD · N D ABCD )≧0,

hold true, wherein N A ABCD , N B ABCD , N C ABCD , and N D ABCD are the normal vectors to the four facets of ABCD, and the subscript corresponds to the opposite vertex of the facet.

21. The computer readable program storage device of claim 18 , wherein finding a facet F of tetrahedron T wherein tetrahedron T has vertices A, B, C, P, through which line PM exits T comprises, for a first tetrahedron along line PM, finding facet ABC and the point H 0 in ABC through which line PM exits, and for a subsequent tetrahedron T i along line PM, finding the points of intersection of line PM with the planes containing each of the other facets of tetrahedron T and determining which intersection point is contained within the triangle of a facet of tetrahedron T.

22. The computer readable program storage device of claim 21 , wherein finding the points of intersection of line PM with the planes containing each of the other facets of tetrahedron T comprises calculating

OH

i

B

i

⁢

C

i

⁢

D

i

_

=

OP

_

+

N

A

i

A

i

⁢

B

i

⁢

C

i

⁢

D

i

_

·

PA

i

_

N

A

i

A

i

⁢

B

i

⁢

C

i

⁢

D

i

_

·

PM

_

⁢

PM

_

,

OH

i

A

i

⁢

B

i

⁢

D

i

_

=

OP

_

+

N

B

i

A

i

⁢

B

i

⁢

C

i

⁢

D

i

_

·

PB

i

_

N

B

i

A

i

⁢

B

i

⁢

C

i

⁢

D

i

_

·

PM

_

⁢

PM

_

,

OH

i

A

i

⁢

B

i

⁢

C

i

_

=

OP

_

+

N

C

i

A

i

⁢

B

i

⁢

C

i

⁢

D

i

_

·

PC

i

_

N

C

i

A

i

⁢

B

i

⁢

C

i

⁢

D

i

_

·

PM

_

⁢

PM

_

.

wherein point O is the origin of the coordinate system, N A ABCD , N B ABCD , N C ABCD , and N D ABCD are the normal vectors to the four facets of ABCD and the subscript corresponds to the opposite vertex of the facet, and H i B i C i D i , H i A i B i C i , H i A i B i D i are the points of intersection with the planes of facets B i C i D i , A i B i C i , and A i B i D i of tetrahedron T i .

23. The computer readable program storage device of claim 22 , wherein if H i−1 H i B i C i D i · N B i A i B i C i D i ≧0 and H i−1 H i B i C i D i · N C i A i B i C i D i ≧0 then H i =H i B i C i D i , if H i−1 H i A i C i D i · N A i A i B i C i D i ≧0 and H i−1 H i B i C i D i · N C i A i B i C i D i ≧0 then H i =H i A i C i D i , or if H i−1 H i A i B i D i · N A i A i B i C i D i ≧0 and H i−1 H i B i C i D i · N B i A i B i C i D i ≧0 then H i =H i A i B i D i , wherein H i−1 is the intersection point of a previous tetrahedron along line PM.

24. The computer readable program storage device of claim 17 , the method further comprising computing an octree to represent said digital image volume, wherein said vertex P of said TVM that is closest to point M is found by using a nearest point algorithm on said octree.

25. The computer readable program storage device of claim 18 , the method further comprising:

computing a list L P of all tetrahedra of said TVM;

computing and storing normal vectors of each of the four facets of each tetrahedron in said list; and

computing a table of facets T F corresponding to each normal vector;

searching said list L P to find said tetrahedron Tin said TVM that defines a solid angle around point P in which point M is located; and

searching said facet table T F to find said next tetrahedron T i+1 of said TVM along line PM.

26. The computer readable program storage device of claim 25 , the method further comprising, for a TVM that is not convex, searching said facet table T F to find facets T B with no other corresponding facets, computing a convex envelope of the facets T B and adding facets {tilde over (T)} B corresponding to said envelope to said facets T B , computing connected components C({tilde over (T)} B ) in {tilde over (T)} B , and filling each connected component of C({tilde over (T)} B ) with a tetrahedron labeled as an outside tetrahedron, wherein tetrahedra of said non-convex TVM are labeled as inside tetrahedra, wherein said TVM is converted to a convex sub-volume.

27. The computer readable program storage device of claim 26 , wherein point M is inside said TVM if said tetrahedron T is an inside tetrahedron.