Today is the release of version 1.0 of bfs, a fully-compatible* drop-in replacement for the UNIX find command. I thought this would be a good occasion to write more about its implementation. This post will talk about how I parse the command line. Continue reading bfs from the ground up, part 2: parsing
Category Archives: Computer Science
The Approximating and Eliminating Search Algorithm
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.
Continue reading The Approximating and Eliminating Search Algorithm
Fast, Branchless Ray/Bounding Box Intersections, Part 2: NaNs
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 [1], and the implementation was fleshed out by Amy Williams. et al. in [2].
Continue reading Fast, Branchless Ray/Bounding Box Intersections, Part 2: NaNs
Exact Bounding Boxes for Spheres/Ellipsoids
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.
Continue reading Exact Bounding Boxes for Spheres/Ellipsoids
A Beautiful Ray/Mesh Intersection Algorithm
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.
Continue reading A Beautiful Ray/Mesh Intersection Algorithm
A Beautiful Ray/Triangle Intersection Method
3D ray/triangle intersections are obviously an important part of much of computer graphics. The Möller–Trumbore algorithm, for example, computes these intersections very quickly. But there is another method that I believe is more elegant, and in some cases allows you to compute the intersection for “free.”
Continue reading A Beautiful Ray/Triangle Intersection Method
k-d Forests
Recently I saw an interesting Code Golf problem: create an image using all possible RGB colours. The top ranked submission, by József Fejes, contained some truly beautiful images, but they took an immense amount of time to generate.
Specifying Types
C specifies types like this:
int integer; int array[2]; int *pointer; int function(int); |
The clever rule C follows is that declarations and expressions look the same. So int *pointer can be read as, "from now on, *pointer is an int." Similarly, function(0) is an int, and array[0] is an int. Continue reading Specifying Types
Fair and Square, or How to Count to a Googol
Fair and Square is a problem from the qualification round of Google Code Jam 2013. The gist of the problem is to find out how many integers in a given range are both a palindrome, and the square of a palindrome. Such numbers are called "fair and square." A number is a palindrome iff its value is the same when written forwards or backwards, in base 10. Continue reading Fair and Square, or How to Count to a Googol
Iterating Over Binary Trees
Binary trees are great. If you ever have to implement one yourself though, you're probably either using C or you need to look at the documentation for your language's standard library more closely. Even POSIX C has the tsearch family of functions from <search.h>. Continue reading Iterating Over Binary Trees