Adaptive Barycentric Contouring

This is a contouring algorithm, the sort used to find a needle in the haystack of a large dataset with as few guesses as possible. It is a general purpose algorithm, also useful for the tree it constructs while searching.

In the case of the demo below, the needle is the surface of a function. In other cases it might be motion, complexity, or similarity to a pre-existing feature.

It begins by checking the 3 pixels at the corners of a triangle covering the entire screen, and from these picks a forth place within the triangle to test (thereby greatly increasing accuracy.)

If the sample is within a certain threshold of the target, the big triangle subdivides into four smaller ones, and the process continues. Triangles are used because they sample the space with less distortion than a version using squares.

The end result contours the information sought with high resolution triangles, while only keeping sparse (big low resolution triangles) for areas with low detail.

This program was extensively debugged with visualizations during it's development, which also make for a nice scifi motif. In practice, it is an invisible process - everything you see in the demos is only for development.




Live Demo with Sourcecode

Early revision using squares (more samples, less accuracy.)

Triangle indexing test.

Comparason of barycentric transforms made during development.

Video of C++ version implemented with the Cinder Lib.