Tiling Algorithm Used in Skandha3

Jeff Prothero

(From an email message received 4/3/01)
The basic tiling algorithm is just recursive divide and conquer:

Given two point sequences A and B to tile together,
find the midpoint M of A, find the closest point in B to M,
connect the two, then recursively tile the left and right
halves of A and B to each other the same way.

Very simple, and works very well on the sort of data we have.
Especially important, it's fast enough to be effectively
instant in interactive use. (With today's faster hardware,
maybe some of the O(N^3) algorithms are more practical, I dunno.)

One important wrinkle is, before you start, assuming A and B
are closed curves (which they usually are in our applications)
to center the centroids (center of area -- easy to compute by
the naive calculus method) of the two closed curves on top of
each other.

This makes the method work much better in cases where, say,
some tube-like structure has been sliced at a sharp angle, so
that successive contours appear to be moving rapidly across
the field of view.

Another wrinkle is to, as Jim mentioned, allow the user to
specify certain points which must be tiled to each other.
This allows bad behavior to be overridden.

This is typically used when a sharp point on one contour "obviously"
corresponds to a matching sharp point on the other contour. The
above naive algorithm will not detect such matches. Neither will
most of the academically published algorithms, which are based on
minimizing surface area or such, which usually isn't what we want
in practice, although it makes for a nice paper.

A typical example of where this is needed is in getting the sulci
on the brain to tile properly together.

I've experimented a bit with trying to automate the point-to-point
matching process by finding points of high curvature and rewarding
the algorithm for matching them. I never got anything practical,
but had limited time, and there was limited interest in the result
here, plus we had very limited compute power at the time (e.g.,
1-5 MIPs and no floating point hardware). I think this could be
done if one wanted to spend 1-4 months on it. Offhand, if I were
to start on it today, I'd parameterize the curves somehow to
expose curvature explicitly, then do wavelet decomposition on
the result to produce a reasonably explicit representation of
major shapes features on the curves, then try to match up really
"obvious" corresponding shapes, and feed the result as hints into
the standard tile-with-advice algorithm.

None of this properly handles forking and rejoining of structures.
We've always totally faked this by hand, with no assistance whatever
from the software or datastructures. It would be clearly possible
to automate some simple cases. For the general cases, one needs to
more or less abandon the contour-by-contour view of the world and
start over thinking of tiling a pointcloud, I think, or at least
solving the pointcloud case and using it to guide the contour-by-
contour tiling process later.

Ping me if there's anything more useful I can say.

-- Jeff