Welcome to XIAO HAN's homepage

Research : Fast Marching Method on Triangular Surface Mesh

Introduction

Multi-scale, graph-based topology correction algorithm
Topology-preserving geometric deformable model
Anatomically consistent GM editing
Fast Marching on triangular meshes for sulcal segmentation
Automated WM editing
CRUISE: Cortical reconstruction using implicit surface evolution

IACL Research

The Fast Marching on Triangular Mesh method introduced by Kimmel and Sethian (Computing Geodesic Paths on Manifolds, Proc. Natl. Acad. Sci., vol. 95, 8431-8435, 1998) is an elegant method for the computation of geodesic distance on a triangular surface mesh. It has many important applications including cortical surface segmentation (M.E. Rettmann, X. Han, C. Xu, and J.L. Prince, Automated Sulcal Segmentation Using Watersheds on the Cortical Surface, NeuroImage, Vol. 15, 329-344, 2002).

One non-trivial step in this method that lacks clear explanation (regarding its implementation) is the unfolding of regional surface patches, which is frequently necessary when the surface mesh contains obtuse triangles. Without careful design, this step can largely slow down the computation speed of the overall method.

We have designed a highly efficient scheme for performing the triangle unfolding, which avoids explicit coordinate transformation of any vertex or the evaluation of any trigonometric function or its inverse.

The unfolding algorithm can be found in the appendix of our sulcal segmentation paper (downloadable from my publication page), and is summarized in the following.

Unfolding Algorithm (refer to the figure above):

Initialization: Let vertex X = A, vertex Y = B, vertex U = C. Compute lengths of the line segments XA, XB, XC, YA, YB, YC, and XY directly from the vertex coordinates. Then compute three cosines cosXYA, cosXYB, cosXYC using the cosine theorem as follows, and compute the corresponding sines using

Unfolding: Find the triangle DXY that shares the edge XY with the current triangle XYU. Compute DX and DY from the vertex coordinates, compute cosXYD using the cosine theorem, and compute sinXYD from its cosine. Next, compute the lengths of the virtual edges DA, DB, and DC. For example, These lengths are equal to the distances between the corresponding vertices on the unfolded plane.

Decide: The following computations determine whether D is inside the acute section, and if not, update vertex labels to continue the unfolding. If > then set U = Y, and Y = D, update the lengths YA, YB, YC, and XY, then go to Step 4. If > then set U=X, and X = D, update XA, XB, XC, and XY, and go to step 4. Otherwise, stop unfolding and compute T(C) from the two acute triangles DCA and DCB. The minimum of the two values will be taken as the final distance value at vertex C.

Update: compute the cosines and sines of Step 1 using the updated lengths from the previous step, then go to Step 2.

Home | Education| Research| Publications| Expereinces|Resume|Family|Links

Copyright © 2002 Xiao Han. All Rights Reserved

Last updated: Jan. 28, 2002

		Research : Fast Marching Method on Triangular Surface Mesh

Introduction Multi-scale, graph-based topology correction algorithm Topology-preserving geometric deformable model Anatomically consistent GM editing Fast Marching on triangular meshes for sulcal segmentation Automated WM editing CRUISE: Cortical reconstruction using implicit surface evolution IACL Research		The Fast Marching on Triangular Mesh method introduced by Kimmel and Sethian (Computing Geodesic Paths on Manifolds, Proc. Natl. Acad. Sci., vol. 95, 8431-8435, 1998) is an elegant method for the computation of geodesic distance on a triangular surface mesh. It has many important applications including cortical surface segmentation (M.E. Rettmann, X. Han, C. Xu, and J.L. Prince, *Automated Sulcal Segmentation Using Watersheds on the Cortical Surface, NeuroImage, Vol. 15, 329-344, 2002). One non-trivial step in this method that lacks clear explanation (regarding its implementation) is the unfolding of regional surface patches, which is frequently necessary when the surface mesh contains obtuse triangles. Without careful design, this step can largely slow down the computation speed of the overall method. We have designed a highly efficient scheme for performing the triangle unfolding, which avoids explicit coordinate transformation of any vertex or the evaluation of any trigonometric function or its inverse. The unfolding algorithm can be found in the appendix of our sulcal segmentation paper (downloadable from my publication page), and is summarized in the following. Unfolding Algorithm* (refer to the figure above): Initialization: Let vertex X = A, vertex Y = B, vertex U = C. Compute lengths of the line segments XA, XB, XC, YA, YB, YC, and XY directly from the vertex coordinates. Then compute three cosines cosXYA, cosXYB, cosXYC using the cosine theorem as follows, and compute the corresponding sines using Unfolding: Find the triangle DXY that shares the edge XY with the current triangle XYU. Compute DX and DY from the vertex coordinates, compute cosXYD using the cosine theorem, and compute sinXYD from its cosine. Next, compute the lengths of the virtual edges DA, DB, and DC. For example, These lengths are equal to the distances between the corresponding vertices on the unfolded plane. Decide: The following computations determine whether D is inside the acute section, and if not, update vertex labels to continue the unfolding. If > then set U = Y, and Y = D, update the lengths YA, YB, YC, and XY, then go to Step 4. If > then set U=X, and X = D, update XA, XB, XC, and XY, and go to step 4. Otherwise, stop unfolding and compute T(C) from the two acute triangles DCA and DCB. The minimum of the two values will be taken as the final distance value at vertex C. Update: compute the cosines and sines of Step 1 using the updated lengths from the previous step, then go to Step 2.

	Home \| Education\| Research\| Publications\| Expereinces\|Resume\|Family\|Links
	Copyright © 2002 Xiao Han. All Rights Reserved
	Last updated: Jan. 28, 2002