[Yt-dev] Contour finding

[Matthew Turk]

Hi guys,

I have implemented a new contour finding algorithm.  This new
algorithm is based on what I can remember from a paper I discussed
with Dave and Britton some time ago, but since I can't find the paper
anymore, it's not necessarily a full implementation.  The new strong
points are that while the initial identification *may* be slower
(although actually, I'm *not* sure it is!) you can essentially scroll
over the contours instantly; pulling out level sets at arbitrary
densities is *very* cheap, so doing dendograms and other level set
identification should be basically free -- in fact, pulling out trees
with exact values of density for the splits/joins should be trivial.
(This assumes that there are no duplicate values; in the paper I
recall they suggest jittering by random values of order float-epsilon
to ensure this.)

I've placed the diff for the Cython code here:

http://paste.enzotools.org/show/327

and the test script that performs the contouring and the verification here:

http://paste.enzotools.org/show/326

(you can also download these with yt_lodgeit.py --download=...)

You'll have to re-cythonize after you apply the patch.  (I've already
done this on Triton, and the LCA dev group install should have these
functions.)

Right now it's still slightly raw.  Note that the Cython function for
getting the contours out, extract_identified_contours, accepts and
index rather than a density.  This will probably change, and I'd also
like to change it such that it will actually pull out a tree rather
than the indices -- which shouldn't be too hard.  The index fed in
here is the index in the *sorted* system, because as you'll note the
densities (or whatever other field there is) must be fed in sorted
such that the joins proceed outward from the lowest-index values.

Let me know what you think.  I'm going to conduct some more tests and
wrap it in the familiar contour interface, with additional wrapping
layers for holding the full set of topology rather than the explicitly
pulled-out contours.   I believe this algorithm can be parallelized
relatively easily, and that will be a final step after cleaning it up.

Matt