Computational geometry is a fascinating domain filled with technical challenges that often seem simple, but equally often turn out to be complicated. For example, suppose you’re given one direction and asked to choose two other directions such that all three are orthogonal (i.e., mutually perpendicular). An intuitive solution is obtained by holding your hand in the shape of the right-hand rule with your thumb pointing in the direction you’re given so the other directions are indicated by your first and middle fingers. You’ll notice that you can rotate your hand freely around your thumb to get many equally valid answers. There seems to be a lot of choice, but does this make the problem easier.. or harder? 🤔
Computing an orthonormal basis
(From here on we assume some vector algebra and programming knowledge).
If we represent directions as unit vectors, our problem amounts to computing an orthonormal basis. A straightforward solution can be derived using basic vector algebra. We’ll call our three directions u, v and w. Given a unit vector u, we first pick an arbitrary vector, say e = (1, 0, 0) and compute the component of e in the direction perpendicular to u, this is known as the rejection vector and denoted in the figure as eᵣ. You may be more familiar with the concept of projection, denoted ep below, rejection is analogous but in the perpendicular direction. Next we normalise eᵣ to obtain the second vector v, and finally we find the last vector by computing a cross product w = u x v.
There are a few problems with this approach. First, note that when u = e the algorithm doesn’t work, and we’ll need to pick a different e. In fact, we can work around the problem with a simple conditional / if statement, but this raises a question — is a conditional / if statement really needed in this context? By interpreting the conditional as a function discontinuity a possible solution presents itself: the branch could be removed by finding a continuous function, v(u) that assigns a unit tangent vector to every point, u, on the surface of a unit sphere. Unfortunately, a classic result known as the Hairy Ball Theorem, proven by Dutch mathematician L. E. J. Brouwer in 1912, demonstrates this is impossible in three dimensions, in fact the theorem actually states this is impossible in all odd dimensions! In two dimensions, for example, it is possible to construct such a function, namely v(u) = (-b, a) with u = (a, b).
A second problem with the naive approach is the cost of the reciprocal square root for vector normalisation. Intuitively, this may appear to be unexpectedly expensive for such a simple task. This second problem is a subject of active research. The first algorithm without normalisation was published by Frisvad in 2012 and a recent improvement was published by Duff et al. in 2017. Currently, this seems to be the best known solution. At CloudNC, we use a variant of Duff’s method.
We’re hiring, come work for us!
Computing an orthonormal basis has many applications important for CNC toolpath generation, including ray-tracing, projection, parameterisation, computing offset curves and surfaces, and determining the relative orientation of points with lines/planes. With this example we’ve hopefully convinced you that one of the most interesting aspects of working on computational geometry is how intuition can trick us into sometimes (often) making difficult or impossible problems look simple at first glance. These interesting surprises really keep the work challenging and fun, if you like this sort of thing check out our hiring page and stay tuned for future blog posts!