Figure 1: Major axes for original (left), swizzle (mid) and perpendicular (right) vectors
Introduction
Two months ago, there was a question (and subsequent discussion) on Twitter as to how to go about generating a perpendicular unit vector, preferably without branching. It seemed about time that I finally post something more complete on the subject, since there are various ways to go about doing this, as well as a few traps awaiting the unwary programmer.
Solution Quartet
Here are four options with various tradeoffs. If you happen to know of any others, by all means let me know and I’ll update this post.
Note: in all of the following approaches, normalisation is left as an optional postprocessing step.
Quick ‘n’ Dirty
A quick hack involves taking the cross product of the original unit vector – let’s call it $\mathbf{u}(x, y, z)$ – with a fixed ‘up’ axis, e.g. $(0, 1, 0)$, and then normalising. A problem here is that if the two vectors are very close – or equally, pointing directly away from each other – then the result will be a degenerate vector. However, it’s still a reasonable approach in the context of a camera, if the view direction can be restricted to guard against this. A general solution in this situation is to fall back to an alternative axis:
1 2 3 4 5 6 7 8 9 

Listing 1: A quick way to generate a perpendicular vector
HughesMöller
In a neat little Journal of Graphics Tools paper [1], Hughes and Möller proposed a more systematic approach to computing a perpendicular vector. Here’s the heart of it:
Or, as the paper also states: “Take the smallest entry (in absolute value) of $\mathbf{u}$ and set it to zero; swap the other two entries and negate the first of them”.
Figure 2: Distribution of v over the sphere
However, there’s a problem with this as written: it doesn’t handle cases where multiple components are the smallest, such as $(0, 0, 1)$! I hit this a few years back when I needed to generate an orthonormal basis for some offline geometry processing, and it’s easily remedied by replacing $<$ with $\leq$. Here’s a corrected version in code form:
1 2 3 4 5 6 7 8 9 10 11 12 

Listing 2: HughesMöller perpendicular vector generation
Stark
More recently, Michael M. Stark suggested some improvements to the HughesMöller approach [2]. Firstly, his choice of permuted vectors is almost the same – differing only in signs – but even easier to remember:
In plain English: the perpendicular vector $\mathbf{\bar{v}}$ is found by taking the cross product of $\mathbf{u}$ with the axis of its smallest component. (Note: the same care is needed when multiple components are the smallest.)
Figure 3 visualises this intermediate ‘swizzle’ vector over the sphere:
Figure 3: Intermediate swizzle vector
Secondly, Michael also provides a branchfree implementation:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 

Listing 3: Branchfree perpendicular vector generation
I know what you’re thinking, there’s a problem here too: it should be zm = 1^(xm  ym)
! Although still robust, the effect of this error is that the nice property of even, symmetrical distribution over the sphere is lost:
Figure 4: Broken symmetry in the perpendicular vector
(that’s 7 years bad luck!)
XNAMath
Finally, another branchfree solution is provided in the form of XMVector3Orthogonal
, which is part of the XNAMath library. Here’s the actual code taken from the DirectX SDK (June 2010):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 

Listing 4: XNAMath’s semivectorised method
Let me save you the trouble of parsing this fully (or consider it an exercise for later); if you boil it down, what you’re effectively left with is:
I’ve failed, thus far, to pinpoint the origin of or thought process behind this approach. That said, some insight can be gained from visualising the resulting vectors:
Figure 5: Covering one’s axis
Their maximum component is in the x axis, except close to the +/ve x poles. Essentially, Microsoft’s solution ensures robustness without concern for distribution, much like the initial ‘quick’ approach.
Performance
I haven’t benchmarked these implementations, since in cases where I’ve needed to generate perpendicular vectors, absolute speed wasn’t important or the call frequency was vanishingly small. Even in performancecritical situations, it really depends on what properties/restrictions you can live with and your target architecture(s). Still, I can’t help but think that XMVector3Orthogonal
is doing a little bit more than it needs to, so maybe there’s cause to revisit this subject at a later date.
Conclusion
I hope you’ve learnt something about generating perpendicular vectors, or that I’ve at least made you aware of some of the minor issues in previous work on the subject. On that note, if you spot any new errors here, please let me know!
References
[1] Hughes, J. F., Möller, T., “Building an Orthonormal Basis from a Unit Vector”, Journal of Graphics Tools 4:4 (1999), 3335.
[2] Stark, M. M., “Efficient Construction of Perpendicular Vectors without Branching”, Journal of Graphics Tools 14:1 (2009), 5561.