Perpendicular Possibilities

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!

Hi. I would like to humbly point to this article, featuring both branching and branchless implementations that I believe improve on both Hughes—Möller and Stark. http://lolengine.net/blog/2013...

Yes, I'd seen that – nice work Sam!

I've been meaning to do a followup post to cover the paper Mikkel mentioned and the point David raised about stability. I'll include your method there too. Thanks for giving me the extra motivation!

Sorry I’m a bit late to the party, but is there any reason why crossing a vector with a swizzled version of itself with one component negated wouldn’t work? Eg:

cross(v, float3(v.y, -v.z, v.x))

Sorry for the delay in replying! In any formulation like this, there will be points of degeneracy (see Sam’s post that he links to in an earlier comment, which covers the Hairy Ball Theorem). For instance, in this case, if v is (-1, 1, 1) or (1, -1, -1), the cross product will give (0, 0, 0).

No need to apologise - I assumed you may not be paying much attention to a 6 year old post!

I completely missed that case; thanks for pointing out my error.

[edited to add]

Although I do wonder if there is any merit to the idea of trying to detect the singularity case after it has happened, rather than trying to predict it. Since the singularity is such a rare exception, it should be quite friendly to the GPU branch predictor.

Singularities are not the only concern, since there can be precision issues as the length of the vector goes to zero. This recent paper goes into depth on the topic and provides a numerically robust implementation, plus a branchless variant.