Jump to content

View more

Image of the Day

The night is still, but the invasion brings chaos. #screenshotsaturday #hanako #indiegame #gameart #ue4 #samurai https://t.co/cgILXuokoS
IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.


Sign up now

Generate random perpendicular unit vector

4: Adsense

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 knarkowicz   Members   

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



#2 C0lumbo   Members   

4365
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 swiftcoder   Senior Moderators   

18216
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 EWClay   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 Bacterius   Members   

13164
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 Kepakiano   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 EWClay   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.