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