[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: 7692
Joined: May 28, 2005 3:28

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

Postby D.J.Peters » Aug 16, 2016 16:04

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: 9013
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

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

Postby fxm » Aug 16, 2016 16:46

Perhaps work in spherical coordinate system

radial distance = 1
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: 2756
Joined: Jun 02, 2015 16:24

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

Postby Tourist Trap » Aug 16, 2016 18:17

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: 1238
Joined: Jun 04, 2005 9:51

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

Postby dafhi » Aug 17, 2016 6:01

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?

Postby greenink » Aug 17, 2016 12:16

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

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

Postby dodicat » Aug 17, 2016 14:13

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 19
Type pt
    As Single x,y,z
End Type
Dim As Single TwoPi=4*Atn(1)

Dim As Long max=5000000
Redim 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: 2756
Joined: Jun 02, 2015 16:24

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

Postby Tourist Trap » Aug 17, 2016 17:17

Why not slice the sphere?
Image

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 TIMER

dim 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, move3

move1 = int(10*r) mod 2
? !"\nfirst sliced move", move1

move2 = int(100*r) mod 2
? !"\n2nd sliced move", move2

move3 = int(1000*r) mod 2
? !"\n3rd sliced move", move3

'now return the P3D in the space
return arrayOf8000PointOnSphere.X + XsphereCenter
return arrayOf8000PointOnSphere.Y + YsphereCenter
return 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: 7692
Joined: May 28, 2005 3:28

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

Postby D.J.Peters » Aug 17, 2016 21:27

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: 2756
Joined: Jun 02, 2015 16:24

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

Postby Tourist Trap » Aug 17, 2016 22:10

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:
Image
D.J.Peters
Posts: 7692
Joined: May 28, 2005 3:28

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

Postby D.J.Peters » Aug 17, 2016 22:21

Nice but the cone are about the surface :-)

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

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

Postby Tourist Trap » Aug 17, 2016 22:52

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: 223
Joined: Apr 11, 2011 22:22

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

Postby gothon » Aug 17, 2016 23:20

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: 1238
Joined: Jun 04, 2005 9:51

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

Postby dafhi » Aug 18, 2016 0:09

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

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

Postby gothon » Aug 18, 2016 0:56

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: 7692
Joined: May 28, 2005 3:28

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

Postby D.J.Peters » Aug 18, 2016 1:04

@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

Return to “Community Discussion”

Who is online

Users browsing this forum: No registered users and 3 guests