What's a numerically stable, non-branching algorithm for choosing two vectors perpendicular to a given normal?

Question

I have a unit vector $N$ which is the normal to some flat surface. I want to generate two other unit vectors $U$ and $V$ which are mutually perpendicular and lie in this surface, so $(N,U,V)$ will be a set of basis vectors. It does not matter how $U$ and $V$ are rotationally oriented.

In principle I can choose an arbitrary unit vector $M \neq N$ and take cross-products, but this isn't numerically stable in all cases.

Example of something which will not work, choosing $M=N+(1,0,0)^T$, because in the special case that $M=(1,0,0)^T$, the cross products will degenerate.

I can tweak this algorithm with suitable checks, obviously, but this will run on embedded hardware which doesn't handle conditional branches very well and performance is an issue.

Is there a numerically-stable, non-branching algorithm for picking $U$ and $V$ given $N$?

Answer 1

What you want is not possible, otherwise you could construct a continuous unit vector field tangent to the sphere.

A "stable and non-branching" algorithm produces a continuous function. If you apply this to the sphere and its normal and select the first orthogonal vector as the unit vector field, you would get such a continuous tangential field without zeros. However, as is well known, any such vector field has to have at least one singularity, this is the hedgehog or hairy ball theorem.

To avoid producing a singularity you need to cover the unit ball with at least two charts (explicitly or implicitly), which implies branching, and the constructed orthogonal frames are not continuous at the boundary of the charts.