Bowyer/Watson algorithm: 3D

by Yi Zhang

3D version implementation of Bowyer/Watson algorithm is almost the same as the 2D. Instead of eliminating lines that belong only to the triangles whose circumcirlce contains the newly added point, in 3D we eliminate the facets that belong only to the tetrahedra whose circumsphere contains the newly added point, then form new tetrahedra by appending new point to those facets’ nodes. Here is an example generated by Mathematica scripts I compiled. Below on the right is tetrahedronization of 200 random points, together with enclosing tetrahedron. On the left is he tetrahedrons generated by first two points.

Advertisements