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

• US 7,899,230 B2
• Filed: 12/20/2007
• Issued: 03/01/2011
• Est. Priority Date: 01/08/2007
• Status: Active Grant

• Current Assignee: Siemens Healthineers AG (Siemens AG)
• Original Assignee: Siemens AG
• Inventors: de Roquemaurel, Benoit, Azar, Fred S.
• Primary Examiner(s): Tucker; Wes
• Assistant Examiner(s): Bitar; Nancy
• Application Number:
  US11/960,867
• Publication Number:
  US 20080205720A1
• Time in Patent Office: 1,167 Days
• Field of Search: 382/128, 382/154, 382/241, 382/199, 382/181, 345/419, 345/425, 345/420, 345/428, 345/421
• US Class Current: 382/128
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A method for determining whether a point is contained in a sub-volume of a digitized medical image, includes 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 the 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 the TVM, and wherein if T_i+1 exists, determining whether point M is inside tetrahedron T_i+1.

Claims

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₀ 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

7. The method of claim 6, wherein if H_i−

1H_i^BiCiDi·

N_Bi^AiBiCiDi≧

0 and H<sub>i−

1</sub>H_i^BiCiDi·

N_Ci^AiBiCiDi≧

0 then H_i=H_i^BiCiDi, if H<sub>i−

1</sub>H_i^AiCiDi·

N_Ai^AiBiCiDi≧

0 and H<sub>i−

1</sub>H_i^BiCiDi·

N_Ci^AiBiCiDi≧

0 then H_i=H_i^AiCiDi, or if H<sub>i−

1</sub>H_i^AiBiDi·

N_Ai^AiBiCiDi≧

0 and H<sub>i−

1</sub>H_i^BiCiDi·

N_Bi^AiBiCiDi≧

0 then H_i=H_i^AiBiDi, wherein H<sub>i−

1</sub> 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₀ 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₀ 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

23. The computer readable program storage device of claim 22, wherein if H_i−

1H_i^BiCiDi·

N_Bi^AiBiCiDi≧

0 and H<sub>i−

1</sub>H_i^BiCiDi·

N_Ci^AiBiCiDi≧

0 then H_i=H_i^BiCiDi, if H<sub>i−

1</sub>H_i^AiCiDi·

N_Ai^AiBiCiDi≧

0 and H<sub>i−

1</sub>H_i^BiCiDi·

N_Ci^AiBiCiDi≧

0 then H_i=H_i^AiCiDi, or if H<sub>i−

1</sub>H_i^AiBiDi·

N_Ai^AiBiCiDi≧

0 and H<sub>i−

1</sub>H_i^BiCiDi·

N_Bi^AiBiCiDi≧

0 then H_i=H_i^AiBiDi, wherein H<sub>i−

1</sub> 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.