# On picking an orthogonal vector (and combing coconuts)

Consider the following problem:

Given a non-zero vector

vin 3D space, find a non-zero vectorworthogonal tov(i.e.such thatv.w= 0).

At first sight, this seems easy. For every possible **v** there are an infinite number of orthogonal vectors lying in a plane:

We just need to pick one. But it’s not as trivial as it may seem.

## First attempts

The following vector satisfies **v.w1** = 0:

Unfortunately that **w1** vector can be zero, for instance when **v** = [0 0 1]. The original problem requires a non-zero vector.

Let’s try another one:

Again, it works most of the time, except in some cases, for instance **v** = [1 0 0].

How about adding them together? Certainly **w1** and **w2** cannot be both zero at the same time!

Alas, this still doesn’t work all the time: it fails with **v** = ![1 0 1].

Should we try harder? Isn’t there a linear combination of these that will work all the time?

Well, no. There isn’t.

## You can’t comb a coconut

Sadly, the hairy ball theorem, a consequence of Brouwer’s fixed-point theorem, states that any continuous function *f* that maps the set of unit vectors to orthogonal vectors takes the value zero somewhere.

Whichever way you look at the sphere of unit vectors, a continuous tangent field will always have a zero point:

Most of the maths operations we usually do (adding, multiplying, taking square roots, etc.) are continuous. Fortunately, we are not limited to them: we can use a simple `if()`

construct to create a discontinuity that will save us.

## A very good implementation

Here is my personal implementation of the orthogonal vector problem. **It is very good. It has excellent numerical stability. It only does one test. It is short. It is beautiful. I really hope you consider using it.**

/* Always works if the input is non-zero. * Doesn’t require the input to be normalised. * Doesn’t normalise the output. */ vec3 orthogonal(vec3 v) { return abs(v.x) > abs(v.z) ? vec3(-v.y, v.x, 0.0) : vec3(0.0, -v.z, v.y); }

Many implementations, such as Ogre3D’s, have additional tests or operations to perform this task, and use epsilons and normalised vectors to avoid singularities.

But our only test is actually enough: if |x|>|z|, it means the largest component in absolute value in **v** is either x or y. So we build a vector using x and y. Otherwise, the largest component in absolute value is either y or z. So we build a vector using y and z. That way, we ensure that the length of our returned vector never, ever comes near zero.

Whether some given code will cause inefficient branching is often unclear. In our case, it is very likely that the ternary operator will actually be branchless, with some help of the compiler and the hardware.

That said, how about we try to get rid of the ternary operator, just for fun?

## Going branchless for fun

Let’s see. We had these two candidate vectors, **w1** and **w2**, which worked almost always except when specific values of **v** caused them to be zero. And whatever the constant *k* we may pick, a vector of the form **w1** + *k* **w2** will eventually take the value zero for some value of **v**, too, because of the hairy ball theorem.

Now here comes the trick. Instead of using a constant *k*, we use a function *f(x,y,z)*. This is what our **w** vector looks like:

From now I shall assume that **v** is a unit vector.

What can cause **w** to be zero, then?

One necessary condition is *y = 0*. When *y ≠ 0* we can chose anything we want for *f(x,y,z)*, it’ll always give us a good orthogonal vector. This restricts the problem to the *y = 0* circle, giving us the useful equality *x² + z² = 1*.

The other condition is *x = z*f(x,y,z)*. So if we manage to build a function *f* such that *f(x,y,z)* never equals *x/z*, we win.

Using *x² + z² = 1* we can plot all the possible values for *x/z* as a function of *x*. It will show us, for a given *x*, the values that *f* **cannot** take:

The almost vertical slopes you see go to infinity upwards and downwards. As expected, this prevents us from using a continuous function: it would obviously cross one of these walls at some point.

Well, let’s try a non-continuous function, then. What are our options?

*fmod**floor*,*ceil*,*round*…*fract*

Here is one that I came up with and which works reasonably well:

Look how it nicely avoids *x/z*:

And finally, our resulting branchless code:

/* Requires the input to be normalised. * Doesn’t normalise the output. */ vec3 orthogonal(vec3 v) { float k = fract(abs(v.x) + 0.5); return vec3(-v.y, v.x - k * v.z, k * v.y); }

I find it highly unlikely that this second version will perform better than the branching one. However, I haven’t put much thought into it and maybe someone will come up with a much better solution using the ideas presented here. Have fun!

### Attachments (4)

- math-vector-ortho.png (14.3 KB) - added by 5 years ago.
- math-hairy-ball.png (23.8 KB) - added by 5 years ago.
- plot-1.png (12.8 KB) - added by 5 years ago.
- plot-2.png (15.8 KB) - added by 5 years ago.

Download all attachments as: .zip

## Comments

That seems pretty efficient. What I used to do was much more involved:

which is slower due to two tests.

About your version: you can easily take out the branch by simply computing both vectors and blending. In x86 SSE this would look like:

PS: I used the branchless selection a lot when programming the Cell's SPU. That thing would execute code at such an insane ridiculous speed as long as you avoid branching and used SoA. In the CPU's case, you would use the spu_sel() intrinsic.

What about the correctness of this function?

@anonymous This function will work, but it requires you to provide a vector

`v`

that is not collinear with`u`

. Which brings you back to square one: given`u`

, how do you pick`v`

?This is interesting, thanks.

I've thought about this lately and wouldn't it work to do this?

cross(v, v.zxy * (-1,1,-1))

It's so simple there has to be something wrong with it, but I can't think of any case that would make it fail.

@Bas: Yes, there is necessarily something wrong, since the fixed-point theorem applies to this function. In this case, a simple counterexample is`v = [1 1 -1]`

.The prospect that two randomly picked vectors are orthogonal to each other is precisely zero for any sensible probability distribution on a vector space. So it sounds like you're disappeared some relevant situation here.http://www.aoneassignments.com

Play sonic games free online from this webpage http://sonicgames.xyz and play online sonic games. For play these sonic games there are no need to download anything.

As per my sight the Orthogonal vector is a vector uprooted by 90° regarding a given vector !!!!!! their convergence makes a point of 90°. Assignment Writing Service

You have posted a great tutorial which i like it a lot. I must say students should read this article so that they can learn from it. Purchase grass mats from http://www.grassmatsuk.com

Very good information about the On picking an orthogonal vector which practically makes it work. I am very happy to see this post. Thanks. To get gym mats Click here http://www.rubbergymmats.co.uk/

https://www.dissertationwriting.uk/ I’m really impressed with your article, such great & usefull knowledge you mentioned here

https://lawassignmentshelp.com/ I am so happy to read this. This is the kind of manual that needs to be given and not the random misinformation that's at the other blogs.

It is interesting how you combine the maths with coconuts! Pretty good stuff, we like it. www.derbydrivewaypros.co.uk

Dissertation Guidance Provides Quality Online Dissertation Help For Students. http://www.autocadhelp.net/

This A Good Way To Appreciate The Teacher As They Put Their Efforts To Train Students. UK Dissertation Writers Appreciates The Teachers. http://casegurus.com/

A great example of how a competent post should be made, thanks, others should learn from your blog http://19216811-admin.com/ 192.168.1.1

Windows 10 turns on Bluetooth on your computer system or tool as well as starts looking for tools it could link to. When you see your Bluetooth mouse in the checklist of devices, tap on it. For how to take screen shot in windows 10 go to https://windowsclassroom.com/how-to-take-screenshot-on-windows-8/

Informative post. There are very practical points shared in this post. These points are very helpful in out practical life. Thanks for it. Carry on it. To get heavy duty shelving Click here http://ukheavydutyshelving.uk/

What a great informative post. I like it and appreciate your writing skills. You have done good job. Keep it up.Get online epdm rubber roofing click this http://epdmrubberroofinguk.co.uk/