Graphics Reference
In-Depth Information
to the triangle. For full accuracy, rather than storing the closest point
alongside the distance on the grid, it's better to store the index of the
closest triangle—then when we propagate this to neighboring grid points
they can calculate their own exact distance to the triangle. So far this
only computes the regular distance function without signs. If the mesh
is watertight, then the parity of the number of intersections along a ray
cast out from the grid point (say along an axis for convenience) tells us
inside/outside and therefore the sign of
φ
: an odd number of intersections
indicates inside, an even number outside. However, CG models often come
in the form of triangle soup, with holes, self-intersections, and the like. In
this case, we refer to the slower but more robust test developed by Houston
et al. [Houston et al. 03, Houston et al. 06].
Loop Order.
There are two suggestions given in [Tsai 02], one based on the
fast marching method [Sethian 96, Tsitsiklis 95] and one based on the fast
sweeping method [Zhao 05].
The fast marching method is based on the realization that grid points
should get information about the distance to the surface from points that
are closer, not the other way around. We thus want to loop over the grid
points going from the closest to the furthest. This can be facilitated by
storing unknown grid points in a priority queue (typically implemented as
a heap) keyed by the current estimate of their distance. We initialize the
heap with the neighbors of the known grid points, with their distance values
and closest points estimated from those known grid points. We select the
minimum and remove it from the priority queue, set it as known, and then
update the distance and closest-point information of its unknown neighbors
(possibly adding them to or moving them up in the priority queue). And
then do that again, and again, until the priority queue is empty. This runs
in
O
(
n
log
n
)timefor
n
unknown grid points.
The fast sweeping method approach takes a different tactic from the
fact that information propagates out from closer points to further points.
For any grid point, in the end its closest point information is going to come
to it from one particular direction in the grid—e.g., from (
i
+1
,j,k
), or
maybe from (
i, j
1
,k
), and so on. To ensure that the information can
propagate in the right direction, we thus sweep through the grid points
in all possible loop orders:
i
ascending or descending,
j
ascending or de-
scending,
k
ascending or descending. There are eight combinations in three
dimensions, four in two dimensions. Each time we sweep through the grid,
we include the grid point itself in the list of its neighbors (if the grid point
has had a closest point and distance set from a previous sweep—otherwise
−
