Perpendicular Possibilities

Figure 1: Major axes for original (left), swizzle (mid) and perpendicular (right) vectors


This is a companion discussion topic for the original entry at http://blog.selfshadow.com/2011/10/17/perp-vectors/

Wow! Never thought a tweet of mine would inspire a nice blog post like this!

Being illiterate on the 3D math I always use the Quick n' Dirty version, but had the problem of getting the degenerate vector, now I know how to fix/avoid it.

Many thanks for this very illustrative and informative post, more please ;-)

Hey Steve,

Nice blog! The idea behind the XNAMath construction is the following:

The task is to find a vector \mathbf{w} which is not parallel to \mathbf{v}, since then \mathbf{w} \times \mathbf{v} will be orthogonal to \mathbf{v}.

Clearly, any parameter-family not contained in the line \mathbb{R} \mathbf{v} will contain such a vector (this is just rephrasing the condition of being not parallel). Therefore, if we manage to find a one-parameter family which is not contained in any line through the origin then this construction will work for arbitrary vectors \mathbf{v}.

The simplest such construction is to simply fix two of the three components of \mathbf{w} with at least one of them non-zero (i.e., to choose as your one-parameter family a one-dimensional affine space which does not contain the origin), e.g.,

\mathbf{w} = \begin{pmatrix}0\\w\\1\end{pmatrix}.

Then given a specific vector \mathbf{v} we only need to choose w in such a way that the last two components of \mathbf{w} are not parallel to those of \mathbf{v}. Suppose that we have failed to do so and the two 2-vectors are in fact parallel. Then

\mathrm{sign}(yz) = \mathrm{sign}(w).

It follows that we can simply choose

w = -\mathrm{sign}(yz)

to ensure that the two vectors \mathbf{v} and \mathbf{w} are non-parallel (this also works for yz = 0 as long as one defines \mathrm{sign}(0) = 1).

Thanks Keith. I actually had most of the material figured out soon after the initial Twitter chatter, but it took me this long to get around to buffing it up! It was a good opportunity to improve my diagram-making skills. :)

Thanks! More hopefully on the way soon!

Awesome reply Michael! Thanks for the complete picture.

Yes, I should have defined \mathrm{sign}() properly. I’ll update the post later and also replace -\mathrm{sign}(y)\mathrm{sign}(z) with the simpler -\mathrm{sign}(yz).

Edit: Oh, thanks for teaching me about \mathrm{} as well. :slight_smile:

Hey Steve, just wondering how you cooked up those diagrams? Is it a MAX scene? Using a funky shader or a texture you prepared offline?

I'm guessing that every time you call these functions, you probably intend to build a rotation matrix. Is there any time when you wouldn't?

I used Mathematica – both for convenience and as a learning exercise – with the texture generated first and then mapped to a sphere (well, ParametricPlot3D). I would have liked to have embedded WebGL, but WordPress.com hosting makes that difficult (security reasons apparently). If I eventually get around to moving to self-hosting then I might go back and update posts like this, although I rather like the high quality anti-aliasing that comes from heavy supersampling.

I assume the graph is showing, for any input vector, the color of the axis vector that is cross-producted against the input to yield the final vector. That there is such an axis vector isn't necessarily immediately obvious, e.g. with Hughes and Moller (although if you're familiar with the cross-product matrix form it's pretty obvious from the code). Labelling the graph "Distribution of v over the sphere" isn't very clear either since you certainly never define an axis vector v, you just jump straight to the perpendicular vector v-bar (and so it's easy to look at the graph and think it's supposed to be showing Distribution of v-bar, except I don't even know what that would colorize as which is why I'm assuming not).

One can also imagine hypothetical algorithms that don't even go through such a step, which is another reason why it may not be immediately intuitive what the graph is showing.

In all cases, the colour indicates the component with the largest magnitude. This was mentioned in Figure 1, but not anywhere in the body of the article, so I agree it's pretty unclear. In fact, I was already planning to address that after a discussion at work today. Sorry about that!

Not long ago I did displacement with noise in vertex shader. To facilitate normal calculation I needed some sort of a local frame - I did the following:

vec3 minAxis(vec3 v){ return step(v, v.yxx) * step(v, v.zzy); }
vec3 maxAxis(vec3 v){ return step(v.yxx, v) * step(v.zzy, v); } // not used here...

vec3 N0 = _normal;
vec3 Bt = minAxis(N0);
vec3 T  = normalize(cross(Bt, N0));
Bt = cross(N0, T);

The minAxis() is basically MinAxis from here.

Neat! I've used similar tricks in the past for branchless selections in shaders. One question though: don't you need an abs() somewhere? (Preferably inside minAxis().)

Funnily enough, I was planning to add a note about building a basis and then I remembered an old ShaderX article that generated one in the vertex shader for specular lighting. I'll have to compare that against your approach.

(By the way, I hope you don't mind, but I reformatted your comment a little.)

Your observation about need of abs() is correct. My original C# code has it, so I guess you found a bug. Thanks also for fixing the formatting :-)

"Note: in all of the following approaches, normalisation is left as an optional post-processing step."

Would you mind making that note red, bold and double-sized? :)
*three-hour-bug*

also: excellent article!

Italic wasn't enough for you? :) I had meant to do a proper second pass on the post by now – partly prompted by Sean's feedback – and also add a short note about normalising and building a basis. Unfortunately I've been too busy lately, but I'll get on that soon. Cheers!

One important property, which only the Quick and Dirty method has, is stability. In other words, as long as you don't hit the singularity, a small change in u will give a small change in v.

This issue has come up for me when generating a dynamic "tubular" mesh, which is constrained to follow a curve in space. The geometry shouldn't suddenly "twist" around by 180 degrees between one cross-section and the next. So the cross-sectional orientation is arbitrary, but the choice must be stable along the length of the curve.

Incidentally, a completely stable solution is impossible because of the "hairy ball theorem": http://en.wikipedia.org/wiki/H...

Indeed! When I wrote this, I'd forgotten about a situation in the past where I'd needed this property. Funnily enough, it came up again recently in another application. :)

I'd thought about mentioning the "hairy ball"/Brouwer fixed point problem, but I figured I would be repeating too much of Stark's paper, which at the time was available online. It looks as though T&F have stuck that back behind a paywall now though, so it's tempting to update the post with a brief mention. Thanks for the Wikipedia link!

Upcoming in Journal of Graphics Tools 2012

"Code for Building an Orthonormal Basis from a 3D Unit Vector Without Normalization"
http://www2.imm.dtu.dk/pubdb/v...

Yes, I saw (and cached) your tweet about this. I was planning a followup post, but I didn't get around to emailing the author yet – thanks for reminding me!