## [solved]Math Guru II How to make a Normal little bit random FAST?

For other topics related to the FreeBASIC project or its community.
D.J.Peters
Posts: 7943
Joined: May 28, 2005 3:28

### [solved]Math Guru II How to make a Normal little bit random FAST?

random photon directions

A 3d vector normalized (I talk about ~5,000,000 of them per frame)
points in any direction and I need to make this all vectors a little bit random.
(depending on the material roughness of the last surface intersection)

pseudo code:
#define SMALL_RND (rnd()-rnd()) * surface_roughness
n.x += SMALL_RND : n.y += SMALL_RND : n.z += SMALL_RND
var l = n.x*n.x + n.y*n.y + n.z*n.z

Normaly the new vector can't be 0
if it was length 1.0 before and the random offset are small
how ever it's more safe here
while l=0
n.x += SMALL_RND : n.y += SMALL_RND : n.z += SMALL_RND
l = n.x*n.x + n.y*n.y + n.z*n.z
wend

The new direction vector isn't length of 1.0 any more so make it length of 1.0 again.
l=1/sqr(l) : v.x*=l : v.y*=l : v.z*=l

This looks simple and it's Ok BUT normalize = SQR() all this ~5,000,0000 vectors again and again are slow.

Is there any trick to make a normal a litle bit random but the length will be 1.0 same as before ?

The maximum range of x,y and z are -1 to +1 this reminds me on the result of cos() and sin() and so on ...
May be it exist a small random rotation or other trigonometric trick without the need to normalized again.

Don't ask me you are the math guru here :-)

Joshy
Last edited by D.J.Peters on Aug 25, 2016 21:44, edited 1 time in total.
fxm
Posts: 9470
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: Math Guru II How to make a Normal little bit random FAST?

Perhaps work in spherical coordinate system

azimuthal angle: 'teta'
polar angle: 'phi'

The 2 independent random variables are 'teta' and 'phi' each in [0 , 2*pi[

x = cos(teta) * cos(phi)
y = sin(teta) * cos(phi)
z = sin(phi)
Tourist Trap
Posts: 2792
Joined: Jun 02, 2015 16:24

### Re: Math Guru II How to make a Normal little bit random FAST?

D.J.Peters wrote:random photon directions

Add some random noise to your image, it's the same effect ;-)
No I really don't know, looks that we'll have to wait for the clever people.
dafhi
Posts: 1324
Joined: Jun 04, 2005 9:51

### Re: Math Guru II How to make a Normal little bit random FAST?

fxm code looks simple enough. I use sampling sphere

Code: Select all

`  var axis_x_angle = rnd * TwoPi  var cosa = 2 * (rnd - 0.5)  var sina = sqr(1 - cosa*cosa)  x = cosa  y = sina * sin(axis_x_angle)  z = sina * cos(axis_x_angle)`
greenink
Posts: 200
Joined: Jan 28, 2016 15:45

### Re: Math Guru II How to make a Normal little bit random FAST?

Rob from Peter to pay Paul. Ie. Take from x to give to y etc.
dodicat
Posts: 6155
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: Math Guru II How to make a Normal little bit random FAST?

I cannot think of an ingenious method at the moment.
fxm/Dafhi method is sound.
The y values must be given +ve and -ve in Dafhi's code.
I have compared the bog standard method for unit vectors and the spherical-co-ordinate method.
The trig method probably lends itself better to straight asm, but I have not done that here.

Code: Select all

`Screen 19Type pt    As Single x,y,zEnd TypeDim As Single TwoPi=4*Atn(1)Dim As Long max=5000000Redim As pt p(1 To max)Do    'Spherical method    #Define k IIf(Rnd>.5,1,-1) 'needed for the y values    Dim As Double t=Timer        For n As Long=1 To max        Var axis_x_angle = Rnd * TwoPi        Var cosa = 2 * (Rnd - 0.5)        Var sina = Sqr(1 - cosa*cosa)        p(n)=Type(cosa, k*sina * Sin(axis_x_angle),sina * Cos(axis_x_angle))    Next        Print Timer-t,"Spherical co-ordinated"        Circle(400,300),100,4    Dim As Long ctrx,ctry,ctrz    For z As Long=Lbound(p) To Ubound(p)        Pset(400+100*p(z).x,300+100*p(z).y)        If p(z).x>0 Then ctrx+=1        If p(z).y>0 Then ctry+=1        If p(z).z>0 Then ctrz+=1    Next    Print max/2,"Expected"    Print ctrx,ctry,ctrz    Print    '========================  Standard ==========================    #define _p rnd-rnd    t=Timer    For n As Long=1 To max        p(n)=Type(_p,_p,_p)        Var L=Sqr(p(n).x*p(n).x+p(n).y*p(n).y+p(n).z*p(n).z)        p(n)=Type(p(n).x/L,p(n).y/L,p(n).z/L)    Next n    Print Timer-t,"Standard method"        Circle(400+200,300+200),100,4    ctrx=0:ctry=0:ctrz=0    For z As Long=Lbound(p) To Ubound(p)        Pset(400+200+100*p(z).x,300+200+100*p(z).y)        If p(z).x>0 Then ctrx+=1        If p(z).y>0 Then ctry+=1        If p(z).z>0 Then ctrz+=1    Next    Print max/2,"Expected"    Print ctrx,ctry,ctrz    Sleep    Cls    Loop Until Inkey=Chr(27) `
Tourist Trap
Posts: 2792
Joined: Jun 02, 2015 16:24

### Re: Math Guru II How to make a Normal little bit random FAST?

Why not slice the sphere? It's just some principle. You first slice a circle in Z axis, then the X axis. You get a point on the sphere. The step for slicing (for apply random selection on axis) should be discrete I think. But seems to be bound to some screen resolution and sphere dimensions, I don't know...

Code: Select all

`randomize TIMERdim as P3D  arrayOf8000PointOnSphere(0 to 20, 0 to 20, 0 to 20)dim as single r = rnd()? !"\nrandom number", r''a bit silly idea, just cut the sphere in 4, and choose with choosers the sides you go. Then depending on the binary stuff ''obtained, deduce a coordinate for the 1/4 sphere array... So get more coordinates for cheap???''.......dim as integer chooser, move1, move2, move3move1 = int(10*r) mod 2? !"\nfirst sliced move", move1move2 = int(100*r) mod 2? !"\n2nd sliced move", move2move3 = int(1000*r) mod 2? !"\n3rd sliced move", move3'now return the P3D in the spacereturn arrayOf8000PointOnSphere.X + XsphereCenterreturn arrayOf8000PointOnSphere.Y + YsphereCenterreturn arrayOf8000PointOnSphere.Z + ZsphereCenter'(eof)`

Something like that in pseudo code. No sinus, no cosinus, no sqr, or only to build the first array, once for all.
D.J.Peters
Posts: 7943
Joined: May 28, 2005 3:28

### Re: Math Guru II How to make a Normal little bit random FAST?

First all small random vectors around a given normal is a kind cone.
Looks like one inverse sqr() and three mul's to normlize the new random vector
are faster then rotating any precalculated vectors around 3 axis to fit the cone.
And also faster as all sin() and cos() needed to transform the old normal
to spherical coords make it random and transform it back as new normal.

But thank you all for the nice ideas.

Joshy
Tourist Trap
Posts: 2792
Joined: Jun 02, 2015 16:24

### Re: Math Guru II How to make a Normal little bit random FAST?

D.J.Peters wrote:First all small random vectors around a given normal is a kind cone.

I see better now.
So last for illustrate this: D.J.Peters
Posts: 7943
Joined: May 28, 2005 3:28

### Re: Math Guru II How to make a Normal little bit random FAST?

Nice but the cone are about the surface :-)

Joshy Last edited by D.J.Peters on Sep 25, 2017 21:38, edited 1 time in total.
Tourist Trap
Posts: 2792
Joined: Jun 02, 2015 16:24

### Re: Math Guru II How to make a Normal little bit random FAST?

If your angle is meant to be very small, maybe you can also apply sin(angle)=angle and cos(angle)=1 - angle^2/2. At least you can choose to use those after testing the angle?
gothon
Posts: 224
Joined: Apr 11, 2011 22:22

### Re: Math Guru II How to make a Normal little bit random FAST?

D.J.Peters wrote:May be it exist a small random rotation or other trigonometric trick without the need to normalized again.

D.J.Peters wrote:First all small random vectors around a given normal is a kind cone.
Looks like one inverse sqr() and three mul's to normlize the new random vector
are faster then rotating any precalculated vectors around 3 axis to fit the cone.
And also faster as all sin() and cos() needed to transform the old normal
to spherical coords make it random and transform it back as new normal.

Why not pre-compute a bunch of small angle rotation matrices? Offline you would use trig functions to make the matrices, but online you would only need to multiply them. Applying a 3x3 matrix is 9 multiplications and 6 additions, but avoids the inverse sqr function and the 3 multiplications in the renormalization. Because of floating point error, you aught to re-normalize the vectors properly every now and then, but you can probably get away with doing that only once in 1000 rotations or so.

Also, you probably only really need a small number of precomputed matrices, because you can reuse them by indexing them randomly or semi randomly. Ken Perlin got away with only using 256 precomputed random numbers to build his noise functions. If all you are going for is the illusion of randomness, you can probably do the same.
dafhi
Posts: 1324
Joined: Jun 04, 2005 9:51

### Re: Math Guru II How to make a Normal little bit random FAST?

Similarly to what gothon suggests, you could store some points, choose one and rotate it
gothon
Posts: 224
Joined: Apr 11, 2011 22:22

### Re: Math Guru II How to make a Normal little bit random FAST?

Another trick you might use is to replace the sqr() function directly. Since all your vectors are already nearly unit length when you re-normalize them, you can approximate sqr(x) or 1/sqr(x) at x = 1 by using the tailor series expansion. Depending on the number of terms you use it could be faster than using the built in sqr() function.

eg:
sqr(1+x) = 1 + 1/2 x - 1/8 x^2 + 1/16 x^3 - 5/128 x^4 + 7 / 256 x^5 - 21/1024 x^6 + ...

You can compute this 6th order polynomial using only 6 multiplications by parenthesizing it the efficient way:

sqr(1+x) ~= 1 + x*(1/2 + x*(-1/8 + x*(1/16 + x*(-5/128 + x*(7/256 + x*-21/1024))))) (near x = 0)

Of course you probably want to find the series for 1/sqr(1+x), that way you avoid the division too. And you also want to figure out how many terms will give sufficient precision. Since the series gets more accurate the closer you are to the expansion point, repeatedly normalizing by the approximation should converge rapidly to the correct vector.
Last edited by gothon on Aug 18, 2016 1:07, edited 1 time in total.
D.J.Peters
Posts: 7943
Joined: May 28, 2005 3:28

### Re: Math Guru II How to make a Normal little bit random FAST?

@dafhi @gothon first you think it's clever but in practice it looks different.

If you get any surface normal (it points in any direction)

1) how you would select a precalculated random vector ?
(as a minimum you have to get the right qudrant from sphere to chose one)

2) more important how to rotate any new random vector does it fits the cone ?
(I think a hour about it but I don't get it)

Show me the code if you like please

Joshy