bfs is a tool I've been writing for about a year, with the goal of being a drop-in replacement for the UNIX
find command. This series of posts will be deep technical explorations of its implementation, starting from the lower levels all the way up to the user interface.
bfs is small (only about 3,500 lines of C code), which makes it possible to do a fairly complete analysis. But the codebase is fairly clean and highly optimized, which should make the analysis interesting. Continue reading bfs from the ground up, part 1: traversal
Nearest neighbour search is a very natural problem: given a target point and a set of candidates, find the closest candidate to the target. For points in the standard k-dimensional Euclidean space, k-d trees and related data structures offer a good solution. But we're not always so lucky.
In part 1, I outlined an algorithm for computing intersections between rays and axis-aligned bounding boxes. The idea to eliminate branches by relying on IEEE 754 floating point properties goes back to Brian Smits in , and the implementation was fleshed out by Amy Williams. et al. in .
It's surprisingly difficult to find a good code snippet for this on Google, so here's an efficient computation of integer powers in C, using binary exponentiation:
Clang is known for its great error messages, but I did manage to horribly confuse it:
The visitor pattern is tremendously useful when working with certain kinds of information like abstract syntax trees. It's basically a poor man's version of sum types for languages that don't natively support them. Unfortunately, they take advantage of function overloading, something which duck-typed languages like Python lack.
Finding the tightest axis-aligned bounding box for a sphere is trivial: the box extends from the center by the radius in all dimensions. But once the sphere is transformed, finding the minimal bounding box becomes trickier. Rotating a sphere, for example, shouldn't change its bounding box, but naïvely rotating the bounding box will expand it unnecessarily. Luckily there's a trick to computing minimal bounding boxes by representing the transformed sphere as a quadric surface.
In my last post, I talked about a beautiful method for computing ray/triangle intersections. In this post, I will extend it to computing intersections with triangle fans. Since meshes are often stored in a corner table, which is simply an array of triangle fans, this gives an efficient algorithm for ray tracing triangle meshes.