Delaunay Tessellation

Now we have a set of contour stacks which represent the three-dimensional surfaces of LV over time. At any time instant, we want to triangulate the contour stack to infer a 3-D representation of the LV which will allow the analysis of the geometrical parameters of the surface, will allow the provision of a nice surface display, and will also allow the embedding of local smoothness constraints on shape and motion.

While our previous minimum span tessellation[1] is adequate under certain conditions, it may produce some odd-shaped triangles, and is not appropriate when there are major differences in shape or position between successive contours.

Meanwhile, for a set V of N points in 3D, Delaunay triangulation(for definition and other properties, see [40][8] etc) is a 3-connected graph on V embedded in , which defines a symmetrical and isotropic neighborhood relationship between the points, and is closely related to the metric of the surface[9]. It takes into account the discrete nature of the problem, uses a global data structure that will allow the extraction of a minimal representation of the shape, and can be computed efficiently.

Computing the entire Delaunay triangulation consists of finding the neighbors of the N vertices or, equivalently, of computing N convex hulls, which can be done in O(NlogN) time. We use the algorithms proposed by Watson[40], which is based on incremental point insertion into a pre-existing Delaunay triangulation, and by Boissonnat[9], which efficiently computes the Delaunay triangulation between two adjacent contours, two by two, and uses only two-dimensional operations. Then, we get rid of all the triangles inside the triangulated volume, while keeping all the facets on the outside boundary to form a tessellated surface representation, which will become the embedding of the curvature estimation and motion vector field tracking processes. Meanwhile, we also compute the rough estimate of the outward normal vector of each vertex point, which will be useful in the curvature estimation process.