On picking an orthogonal vector (and combing coconuts)

Consider the following problem:

Given a non-zero vector v in 3D space, find a non-zero vector w orthogonal to v (i.e. such that v.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:

$$\mathbf{v} = \begin{bmatrix}x \\ y \\ z \end{bmatrix} \quad \mathbf{w_1} = \begin{bmatrix}-y \\ x \\ 0 \end{bmatrix} \quad \mathbf{v} . \mathbf{w_1} = x * -y + y * x + z * 0 = 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:

$$\mathbf{v} = \begin{bmatrix}x \\ y \\ z \end{bmatrix} \quad \mathbf{w_2} = \begin{bmatrix}0 \\ -z \\ y \end{bmatrix} \quad \mathbf{v} . \mathbf{w_2} = x * 0 + y * -z + z * y = 0 $$

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!

$$\mathbf{v} = \begin{bmatrix}x \\ y \\ z \end{bmatrix} \quad \mathbf{w_3} = \begin{bmatrix}-y \\ x-z \\ y \end{bmatrix} \quad \mathbf{v} . \mathbf{w_3} = x * -y + y * (x-z) + z * y = 0 $$

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:

$$\mathbf{v} = \begin{bmatrix}x \\ y \\ z \end{bmatrix} \quad \mathbf{w} = \begin{bmatrix}-y \\ x- z * f(x,y,z) \\ y * f(x,y,z) \end{bmatrix} \quad \mathbf{v} . \mathbf{w} = \cdots = 0 $$

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:

$$f(x,y,z) = \mathrm{fract}(|x| + \frac{1}{2})$$

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!

  • Posted: 2013-09-21 11:25 (Updated: 2013-09-21 11:34)
  • Author: sam
  • Categories: maths optim

Attachments (4)

Download all attachments as: .zip

Comments

1. b.stolk@gmail.com -- 2013-09-21 17:43

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

  • find smallest |coord| in vector: x,y, or z.
  • cross vector with with unit axis of coord found in step 1.

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: 

#include <immintrin.h>
...
return _mm_blend_ps( zy_solution, yx_solution, x_is_larger );

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.

2. anonymous -- 2014-02-25 09:04

What about the correctness of this function?

Vec3 orthogonal(const Vec3& u, const Vec3& v){

float dt = dot(v, u) / dot(u, u); return Vec3( v - u*dt );

}

3. sam -- 2014-02-25 10:44

@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?

4. samira -- 2014-11-05 22:53

This is interesting, thanks.

5. Bas -- 2015-06-18 23:22

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.

6. sam -- 2015-06-18 23:59

@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].

7. anonymous -- 2017-10-13 08:22

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

8. anonymous -- 2017-11-08 10:38

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.

9. anonymous -- 2017-12-28 14:20

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

10. anonymous -- 2018-01-15 08:39

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

11. anonymous -- 2018-01-15 13:21

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/

12. Thesis Writing Help -- 2018-02-10 10:06

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

13. Online Law Homework Help -- 2018-02-10 10:07

​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.

14. anonymous -- 2018-02-11 20:26

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

15. Autocad Assignment Help -- 2018-02-22 14:06

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

16. Harvard Business Review case analysis -- 2018-02-22 14:08

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/

17. anonymous -- 2018-03-02 15:42

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

18. anonymous -- 2018-03-13 11:42

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/

19. anonymous -- 2018-03-20 11:34

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/

20. anonymous -- 2018-03-28 07:18

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/

21. anonymous -- 2018-04-27 17:47

This article does talk about lot of things in physics which we can see in our academic classrooms teaching. This information can help me to gain more knowledge on this topic. I generally read ​rush my paper writing service blog tutorials and use them as my examination time reference one as additional material.

22. anonymous -- 2018-05-10 11:13

Panda Express is a private subsidiary food service industry that has Chinese cuisine as the genre. ​http://pandaexpress.surveyh.info/ was founded in the year 1983 about 34 years ago at Glendale California United States.

23. dom -- 2018-05-17 08:27

Most of us have probably, at some point, written code resembling this:

Perform velocity damping velocity -= velocity * 0.01f; … or probably the more correct:

Per-second damping coefficient float const D = 10.0f; Damp velocity according to timestep velocity -= velocity * D * delta_time; Per-second damping coefficient float const D = 10.0f; Damp velocity (framerate-independent) velocity *= pow(1.f - D / 60.f, 60.f * delta_time); Per-second damping coefficient float const D = 10.0f; Exponentiation base for velocity damping float const D2 = pow(1.f - D / 60.f, 60.f); Damp velocity (framerate-independent) velocity *= pow(D2, delta_time); /* Build a unit quaternion representing the rotation

  • from u to v. The input vectors need not be normalised. */

quat quat::fromtwovectors(vec3 u, vec3 v) {

float norm_u_norm_v = sqrt(dot(u, u) * dot(v, v)); float real_part = norm_u_norm_v + dot(u, v); vec3 w; if (real_part < 1.e-6f * norm_u_norm_v) {

/* If u and v are exactly opposite, rotate 180 degrees

  • around an arbitrary orthogonal axis. Axis normalisation
  • can happen later, when we normalise the quaternion. */

real_part = 0.0f; w = abs(u.x) > abs(u.z) ? vec3(-u.y, u.x, 0.f)

: vec3(0.f, -u.z, u.y);

} else {

/* Otherwise, build quaternion the standard way. */ w = cross(u, v);

} return normalize(quat(real_part, w.x, w.y, w.z));

​cheap essay writing service uk

25. michaelt.harwell@gmail.com -- 2018-06-05 07:20

Science Channel’s are giving a complete knowledge to its viewers about every thing students write done dissertation on this subjects and show its importance. ​https://paymetodoyourhomework.xyz

26. subhanmahmud76@gmail.com -- 2018-06-05 07:21

I loved the way you discuss the topic great work thanks for the share Your informative post. ​https://pythonassignments.xyz

27. brante.broderick@gmail.com -- 2018-06-05 07:22

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

28. Food -- 2018-06-09 09:59

I was surfing net and fortunately came across this site and found very interesting stuff here. Its really fun to read. I enjoyed a lot. Thanks for sharing this wonderful information. ​Food

29. roberta.gray12@gmail.com -- 2018-06-21 09:09

Thanx For Sharing Such Useful Post Keep It Up :) ​Assignment Help Online

30. Eden Carter -- 2018-06-21 14:07

I’m Really Impressed With Your Article, Such Great & Usefull Knowledge You Mentioned Here ​Case Study Writing Services

31. Cracowcitytours -- 2018-06-29 10:46

It's nice that you create such good quality posts for us. See this webiste: ​guida di cracovi

32. kristinestevart -- 2018-06-30 10:21

Pick an arbitrary vector that is not collinear with the given vector. For "something rigid", you can have a fixed rule.

​help with essay writing - uk essay writing

33. anonymous -- 2018-07-02 07:35

Nice

34. anonymous -- 2018-07-02 07:35

NIce post <a href="​http://www.facebook.com/waleedrajpoot61">Must see</a>

35. anonymous -- 2018-07-02 07:37

[url=​http://www.facebook.com/waleedrajpoot61]Must[/url]

36. anonymous -- 2018-07-02 07:39

​https://mailto.space/

37. Deders -- 2018-07-02 07:45

​Mail to my space Pick an arbitrary vector that is not collinear with the given vector. For "something rigid", you can have a fixed rule.

38. Rebbeca -- 2018-07-05 13:11

Wow, Really great article i enjoy it very much here I appreciating your knowledge keep sharing kindly check it out ​pokemon go tutuapp

39. 192.168.1.1 -- 2018-07-05 13:46

Thanks for the valuable information, I enjoy reading your blog and always looking for useful articles and news ​https://192168ll.mobi/ 192.168.1.1

40. anonymous -- 2018-07-11 09:47

This was really an interesting topic and I kinda agree with what you have mentioned here! <a href='​https://pkws.net/'>KFZ</a>

41. anonymous -- 2018-07-11 09:47

This was really an interesting topic and I kinda agree with what you have mentioned here! KFZ ​https://pkws.net/

42. anonymous -- 2018-07-27 12:01

Allassignmenthelp is one of the finest websites I have stumbled upon. It is not only well developed, but has good content as well. It could prove to be an inspiration for many students for their assignments. Assignment Help Online is into assignment writing service sector and helps pupils in completing their academic tasks. ​https://www.allassignmenthelp.com/

43. Best Writers Reviews -- 2018-07-30 13:17

A superior all assignment Help reviews offered by this website with the advantage of online support with high proficiency level based on its latest research and information by professional reviews writers. Wide ranges of subjects are covered with separate writers for each subject. ​http://bestwritersreviews.com/myassignmenthelp-com-reviews

44. anonymous -- 2018-07-30 17:24

I recently found many useful information in your website especially this blog page. Among the lots of comments on your articles. Thanks for sharing. lessons online ​https://acim.biz/

45. anonymous -- 2018-07-31 12:11

i am for the first time here. I found this board and I in finding It truly helpful & it helped me out a lot. I hope to present something back and help others such as you helped me. non duality teachers ​http://www.nonduality.xyz/

46. anonymous -- 2018-07-31 23:02

Which is headquartered in Atlanta Store Support Center, Cobb Country, Georgia, United States and the Home Depot is the largest retailer in the United States. ​http://customersurvey.xyz/homedepot-survey/

47. anonymous -- 2018-08-01 15:59

Thank you very much for writing such an interesting article on this topic. This has really made me think and I hope to read more. ​http://www.cinderconeclaycenter.com ​http://www.cinderconeclaycenter.com

48. Vincent Smith -- 2018-08-04 07:08

App Cloner is an application that will allow you to make exact copies of any app on your smartphone or tablet. ​https://appcloner.xyz/

49. anonymous -- 2018-08-07 18:19

I have read a few of the articles on your website now, and I really like your style of blogging. I added it to my favorites blog site list and will be checking back soon. Please check out my site as well and let me know what you think. suzuki coin ​https://suzukicoin.net/

50. petterson -- 2018-08-13 07:03

Wow what a Great Information about World Day its exceptionally pleasant educational post. a debt of gratitude is in order for the post.  ​https://www.affordable-dissertation.co.uk/dissertation-writing-services-uk/

51. anonymous -- 2018-08-25 13:15

Scholars who find it difficult to manage their assessments on orthogonal vector don't worry. Expertsminds provide them assistance and assignment help services. Get your perfect assignment solutions today as our experts and professionals serve the best assignment help services and homework help services to all the students who find it difficult to manage their assignments by own. ​http://www.expertsminds.com

52. Cranberry -- 2018-08-29 12:09

I wanted to thank you for this great read!! I definitely enjoying every little bit of it I have you bookmarked to check out new stuff you post. ​Cranberry

53. Cranberry Juice -- 2018-08-29 14:11

Mmm.. good to be here in your article or post, whatever, I think I should also work hard for my own website like I see some good and updated working in your site. ​Cranberry Juice

54. Tomatillos -- 2018-08-29 14:17

Much thanks for composing such an intriguing article on this point. This has truly made me think and I plan to peruse more ​Tomatillos

55. Garcinia Cambogia -- 2018-08-29 14:25

All the contents you mentioned in post is too good and can be very useful. I will keep it in mind, thanks for sharing the information keep updating, looking forward for more posts.Thanks ​Garcinia Cambogia

56. Cowpeas -- 2018-08-29 14:25

Thanks for sharing this information. I really like your blog post very much. You have really shared a informative and interesting blog post . ​Cowpeas

57. Green Tea -- 2018-08-29 14:53

Excellent effort to make this blog more wonderful and attractive. ​Green Tea

58. Peppermint Tea -- 2018-08-29 15:24

All the contents you mentioned in post is too good and can be very useful. I will keep it in mind, thanks for sharing the information keep updating, looking forward for more posts.Thanks ​Peppermint Tea

59. Monk Fruit -- 2018-08-29 22:36

This is very educational content and written well for a change. It's nice to see that some people still understand how to write a quality post! ​Monk Fruit

60. Assignment Help -- 2018-08-31 09:10

This post is not just informative but impressive also. The post is so convincing that it created an urge to choose Assignment help services. ​https://www.myassignmenthelpau.com/

61. anonymous -- 2018-09-06 08:29

This really interesting post. Thanks for sharing! spotify web player- ​https://spotify-webplayer.com

62. anonymous -- 2018-09-10 12:38

Is really Vectors which are willing just before each other at 90 degrees are orthogonal vectors?

Regards: Sophia ​Law Essay Writing Services

63. Sophie -- 2018-09-12 10:39

Thank you for the helpful guideline and tutorial! It's very hard but I feel I can solve it after reading your post. ​instagram Hope to see more posts from you.

64. Vulkan -- 2018-09-12 14:12

<a href="​http://itechbeat.com/vulkan-runtime-libraries-should-i-remove-it/">Vulkan Runtime Libraries Should I Remove It?</a> On picking an orthogonal vector (and combing coconuts)

65. anonymous -- 2018-09-20 15:09

<a href="​http://www.Pharma-wisodm.com">Pharma wisdom</a>

Add New Comment