nrnr /

Full commit


A simple C library for finding nearest neighbors of positions in 3D space.

The code on its own is mostly ignorable. Likely, with some additional discussion it provides something of value.

The Creation of Nrnr, Part 1

Several weeks ago I had some ideas on how to find nearest neighbors in a collection of points in 3D space. For many visual effects studios this means using something like a kdtree.

A long, long time ago I was working at a place where we need to combine all points in the same position into the same point. We had written the straightforward approach of comparing all points with each other. This turned out to be slow. At the time we were using a piece of commercial software, Prisms from Side Effects Software, that had the same operation, but ran orders of magnitude faster than our own. The wise +Mark Elendt explained the secret; Prisms would sort the points along the first dimension.

Driving in to work recently, I remembered these interactions and wondered what if you were to do the same thing across all three axis. Hopeful, but cautious, I began creating some experiments that would, at best, end the interest and use of kdtree structures for all time.

The end result is a cleaned up codebase I named "nrnr" for nearest neighbor searching. Unfortunately, this is not appear to revolutionize anything. There are some cool highlights. I learned a lot along the way, which was my main motivation for packaging up the final code and writing a series of posts that descrive the journey.