Jump to content

  • Log In with Google      Sign In   
  • Create Account

Generate random perpendicular unit vector


Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.


  • You cannot reply to this topic
6 replies to this topic

#1   Members   

2155
Like
0Likes
Like

Posted 26 January 2013 - 04:33 PM

Hi,

 

I have a unit vector v1 and would like to generate a random perpendicular unit vector v2 with uniform or close to uniform distribution.

 

Potential solution is to generate a random unit vector and cross it with v1 to get v2. Now this has two issues - non uniform distribution and for some inputs it generates degenerate vectors, so it requires running in a loop until a valid vector is returned.

 

My current solution is to generate a random angle. Build a rotation matrix M using v1 and two perpendicular vectors. Those vectors are generated by crossing v1 with axis of it's smallest component and by crossing result with v1. Finally transform vector [ cos(randomAngle), sin(randomAngle), 0 ] using rotation matrix M.

 

It works, but I feel that I'm doing excessive amount of calculations and there is a much simpler way to solve it.


blog | twitter | "Don't have any friends? Still a virgin? Programming is for you!"


#2   Members   

4072
Like
0Likes
Like

Posted 26 January 2013 - 04:43 PM

My current solution is to generate a random angle. Build a rotation matrix M using v1 and two perpendicular vectors. Those vectors are generated by crossing v1 with axis of it's smallest component and by crossing result with v1. Finally transform vector [ cos(randomAngle), sin(randomAngle), 0 ] using rotation matrix M.

If you call your two perpendicular vectors v2 and v3, isn't it equivalent to just do: (v2 * cos(randomAngle)) + (v3 * sin(randomAngle)); ?

Not much less work I suppose, but a little quicker.

Edited by C0lumbo, 27 January 2013 - 02:05 AM.


#3   Senior Moderators   

17826
Like
0Likes
Like

Posted 26 January 2013 - 05:09 PM

There is a fair amount of discussion on the topic in an older thread.


Tristam MacDonald - Software Engineer @ Amazon - [swiftcoding] [GitHub]


#4   Members   

659
Like
0Likes
Like

Posted 27 January 2013 - 05:59 AM

You can avoid sin and cos by generating two random numbers x and y in the range -1 to +1, rejecting if the two are outside the unit circle or both zero, then normalising and multiplying by the perpendicular vectors.

#5   Members   

13102
Like
0Likes
Like

Posted 27 January 2013 - 06:07 AM

You can avoid sin and cos by generating two random numbers x and y in the range -1 to +1, rejecting if the two are outside the unit circle or both zero, then normalising and multiplying by the perpendicular vectors.

 

Rejection sampling will cause you to reject (4 - pi) / 4 = 21% of samples taken, and will thus introduce branching in the computation (as well as an extra normalization). It is probably more efficient to just use sin and cos, depending on your platform.


“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”


#6   Members   

138
Like
1Likes
Like

Posted 27 January 2013 - 08:17 AM

This is what I would do:
http://pastebin.com/fr4aU0cw (needs C++11)

1. Generate a random unit vector
2. Make it orthogonal to your given vector by using the Gram-Schmidt Process (http://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process)

Edit: The snippet does not check, whether v and random u are linearly independent.

Edited by Kepakiano, 27 January 2013 - 08:22 AM.


#7   Members   

659
Like
0Likes
Like

Posted 27 January 2013 - 09:19 AM

You can avoid sin and cos by generating two random numbers x and y in the range -1 to +1, rejecting if the two are outside the unit circle or both zero, then normalising and multiplying by the perpendicular vectors.

 
Rejection sampling will cause you to reject (4 - pi) / 4 = 21% of samples taken, and will thus introduce branching in the computation (as well as an extra normalization). It is probably more efficient to just use sin and cos, depending on your platform.
No doubt it could be made branchless, if running in a loop. If not in a loop, it's unlikely to be a hotspot.

Really, I was just pointing out that it can be done without trig functions. The OP never mentioned a performance issue.




Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.