nrnr / readme.md

Peter Shinners f3f322d 

Peter Shinners 7589732 
Peter Shinners f3f322d 
Peter Shinners 7589732 
Peter Shinners f3f322d 
Peter Shinners 7589732 
Peter Shinners f3f322d 









NrNr
====

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.
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.