Added an implementation of Lehmer random number generator with Lecuyer constant,...
authorhavoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Sun, 27 Nov 2016 21:45:11 +0000 (21:45 +0000)
committerhavoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Sun, 27 Nov 2016 21:45:11 +0000 (21:45 +0000)
Use the new RNG for bouncegrid traces to hopefully improve the photon distribution compared to lhcheeserandom.

git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@12298 d7cf8633-e32d-0410-b094-e92efae38249

mathlib.c
mathlib.h
r_shadow.c

index 738965a..b228576 100644 (file)
--- a/mathlib.c
+++ b/mathlib.c
@@ -900,3 +900,82 @@ int LoopingFrameNumberFromDouble(double t, int loopframes)
                return (int)t;
 }
 
+static unsigned int mul_Lecuyer[4] = { 0x12e15e35, 0xb500f16e, 0x2e714eb2, 0xb37916a5 };
+
+static void mul128(unsigned int a[], unsigned int b[], unsigned int dest[4])
+{
+       unsigned long long t[4];
+       t[0] = a[0] * b[0];
+       t[1] = a[1] * b[1];
+       t[2] = a[2] * b[2];
+       t[3] = a[3] * b[3];
+
+       // this is complicated because C doesn't have a way to make use of the
+       // cpu status carry flag, so we do it all in reverse order from what
+       // would otherwise make sense, and have to make multiple passes...
+       t[3] += t[2] >> 32; t[2] &= 0xffffffff;
+       t[2] += t[1] >> 32; t[1] &= 0xffffffff;
+       t[1] += t[0] >> 32; t[0] &= 0xffffffff;
+
+       t[3] += t[2] >> 32; t[2] &= 0xffffffff;
+       t[2] += t[1] >> 32; t[1] &= 0xffffffff;
+
+       t[3] += t[2] >> 32; t[2] &= 0xffffffff;
+
+       dest[0] = t[0] & 0xffffffff;
+       dest[1] = t[1] & 0xffffffff;
+       dest[2] = t[2] & 0xffffffff;
+       dest[3] = t[3] & 0xffffffff;
+}
+
+void Math_RandomSeed_Reset(randomseed_t *r)
+{
+       r->s[0] = 1;
+       r->s[1] = 0;
+       r->s[2] = 0;
+       r->s[3] = 0;
+}
+
+void Math_RandomSeed_FromInt(randomseed_t *r, unsigned int n)
+{
+       // if the entire s[] is zero the algorithm would break completely, so make sure it isn't zero by putting a 1 here
+       r->s[0] = 1;
+       r->s[1] = 0;
+       r->s[2] = 0;
+       r->s[3] = n;
+}
+
+unsigned long long Math_rand64(randomseed_t *r)
+{
+       unsigned int o[4];
+       mul128(r->s, mul_Lecuyer, o);
+       r->s[0] = o[0];
+       r->s[1] = o[1];
+       r->s[2] = o[2];
+       r->s[3] = o[3];
+       return ((unsigned long long)o[3] << 32) + o[2];
+}
+
+float Math_randomf(randomseed_t *r)
+{
+       unsigned long long n = Math_rand64(r);
+       return n * (0.25f / 0x80000000 / 0x80000000);
+}
+
+float Math_crandomf(randomseed_t *r)
+{
+       // do this with a signed number and double the result, so we make use of all parts of the cow
+       long long n = (long long)Math_rand64(r);
+       return n * (0.5f / 0x80000000 / 0x80000000);
+}
+
+float Math_randomrangef(randomseed_t *r, float minf, float maxf)
+{
+       return Math_randomf(r) * (maxf - minf) + minf;
+}
+
+int Math_randomrangei(randomseed_t *r, int mini, int maxi)
+{
+       unsigned long long n = Math_rand64(r);
+       return (int)(((n >> 33) * (maxi - mini) + mini) >> 31);
+}
index cb674e5..472d575 100644 (file)
--- a/mathlib.h
+++ b/mathlib.h
@@ -181,9 +181,10 @@ int PointInfrontOfTriangle(const float *p, const float *a, const float *b, const
 }
 #endif
 
-#define lhcheeserand() (seed = (seed * 987211u) ^ (seed >> 13u) ^ 914867)
-#define lhcheeserandom(MIN,MAX) ((double)(lhcheeserand() + 0.5) / ((double)4096.0*1024.0*1024.0) * ((MAX)-(MIN)) + (MIN))
-#define VectorCheeseRandom(v) do{(v)[0] = lhcheeserandom(-1, 1);(v)[1] = lhcheeserandom(-1, 1);(v)[2] = lhcheeserandom(-1, 1);}while(DotProduct(v, v) > 1)
+#define lhcheeserand(seed) ((seed) = ((seed) * 987211u) ^ ((seed) >> 13u) ^ 914867)
+#define lhcheeserandom(seed,MIN,MAX) ((double)(lhcheeserand(seed) + 0.5) / ((double)4096.0*1024.0*1024.0) * ((MAX)-(MIN)) + (MIN))
+#define VectorCheeseRandom(seed,v) do{(v)[0] = lhcheeserandom(seed,-1, 1);(v)[1] = lhcheeserandom(seed,-1, 1);(v)[2] = lhcheeserandom(seed,-1, 1);}while(DotProduct(v, v) > 1)
+#define VectorLehmerRandom(seed,v) do{(v)[0] = Math_crandomf(seed);(v)[1] = Math_crandomf(seed);(v)[2] = Math_crandomf(seed);}while(DotProduct(v, v) > 1)
 
 /*
 // LordHavoc: quaternion math, untested, don't know if these are correct,
@@ -301,6 +302,22 @@ void BoxFromPoints(vec3_t mins, vec3_t maxs, int numpoints, vec_t *point3f);
 
 int LoopingFrameNumberFromDouble(double t, int loopframes);
 
+// implementation of 128bit Lehmer Random Number Generator with 2^126 period
+// https://en.wikipedia.org/Lehmer_random_number_generator
+typedef struct randomseed_s
+{
+       unsigned int s[4];
+}
+randomseed_t;
+
+void Math_RandomSeed_Reset(randomseed_t *r);
+void Math_RandomSeed_FromInt(randomseed_t *r, unsigned int n);
+unsigned long long Math_rand64(randomseed_t *r);
+float Math_randomf(randomseed_t *r);
+float Math_crandomf(randomseed_t *r);
+float Math_randomrangef(randomseed_t *r, float minf, float maxf);
+int Math_randomrangei(randomseed_t *r, int mini, int maxi);
+
 void Mathlib_Init(void);
 
 #endif
index dd57afb..4ad0996 100644 (file)
@@ -3188,6 +3188,7 @@ static void R_Shadow_BounceGrid_ConvertPixelsAndUpload(void)
 
 static void R_Shadow_BounceGrid_TracePhotons(r_shadow_bouncegrid_settings_t settings, unsigned int range, unsigned int range1, unsigned int range2, float photonscaling, int flag)
 {
+       vec3_t bouncerandom[10];
        dlight_t *light;
        int bouncecount;
        int hitsupercontentsmask;
@@ -3200,6 +3201,7 @@ static void R_Shadow_BounceGrid_TracePhotons(r_shadow_bouncegrid_settings_t sett
        //trace_t cliptrace3;
        unsigned int lightindex;
        unsigned int seed = (unsigned int)(realtime * 1000.0f);
+       randomseed_t randomseed;
        vec3_t shotcolor;
        vec3_t baseshotcolor;
        vec3_t surfcolor;
@@ -3210,7 +3212,8 @@ static void R_Shadow_BounceGrid_TracePhotons(r_shadow_bouncegrid_settings_t sett
        vec_t s;
        rtlight_t *rtlight;
 
-       // we'll need somewhere to store these
+       Math_RandomSeed_FromInt(&randomseed, seed);
+
        r_shadow_bouncegrid_state.numsplatpaths = 0;
        r_shadow_bouncegrid_state.splatpaths = (r_shadow_bouncegrid_splatpath_t *)R_FrameData_Alloc(sizeof(r_shadow_bouncegrid_splatpath_t) * r_shadow_bouncegrid_state.maxsplatpaths);
 
@@ -3245,25 +3248,68 @@ static void R_Shadow_BounceGrid_TracePhotons(r_shadow_bouncegrid_settings_t sett
                VectorScale(rtlight->photoncolor, s, baseshotcolor);
                r_refdef.stats[r_stat_bouncegrid_lights]++;
                r_refdef.stats[r_stat_bouncegrid_particles] += shootparticles;
+               switch (settings.stablerandom)
+               {
+               default:
+                       break;
+               case 1:
+                       Math_RandomSeed_FromInt(&randomseed, lightindex * 11937);
+                       // prime the random number generator a bit
+                       Math_crandomf(&randomseed);
+                       break;
+               case 2:
+                       seed = lightindex * 11937;
+                       // prime the random number generator a bit
+                       lhcheeserand(seed);
+                       break;
+               }
                for (shotparticles = 0;shotparticles < shootparticles;shotparticles++)
                {
-                       if (settings.stablerandom > 0)
-                               seed = lightindex * 11937 + shotparticles;
                        VectorCopy(baseshotcolor, shotcolor);
                        VectorCopy(rtlight->shadoworigin, clipstart);
-                       if (settings.stablerandom < 0)
+                       switch (settings.stablerandom)
+                       {
+                       default:
+                       case 0:
                                VectorRandom(clipend);
-                       else
-                               VectorCheeseRandom(clipend);
+                               if (settings.bounceanglediffuse)
+                               {
+                                       // we want random to be stable, so we still have to do all the random we would have done
+                                       for (bouncecount = 0; bouncecount < maxbounce; bouncecount++)
+                                               VectorRandom(bouncerandom[bouncecount]);
+                               }
+                               break;
+                       case -1:
+                       case 1:
+                               VectorLehmerRandom(&randomseed, clipend);
+                               if (settings.bounceanglediffuse)
+                               {
+                                       // we want random to be stable, so we still have to do all the random we would have done
+                                       for (bouncecount = 0; bouncecount < maxbounce; bouncecount++)
+                                               VectorLehmerRandom(&randomseed, bouncerandom[bouncecount]);
+                               }
+                               break;
+                       case -2:
+                       case 2:
+                               VectorCheeseRandom(seed, clipend);
+                               if (settings.bounceanglediffuse)
+                               {
+                                       // we want random to be stable, so we still have to do all the random we would have done
+                                       for (bouncecount = 0; bouncecount < maxbounce; bouncecount++)
+                                               VectorCheeseRandom(seed, bouncerandom[bouncecount]);
+                               }
+                               break;
+                       }
                        VectorMA(clipstart, radius, clipend, clipend);
                        for (bouncecount = 0;;bouncecount++)
                        {
                                r_refdef.stats[r_stat_bouncegrid_traces]++;
                                //r_refdef.scene.worldmodel->TraceLineAgainstSurfaces(r_refdef.scene.worldmodel, NULL, NULL, &cliptrace, clipstart, clipend, hitsupercontentsmask);
                                //r_refdef.scene.worldmodel->TraceLine(r_refdef.scene.worldmodel, NULL, NULL, &cliptrace2, clipstart, clipend, hitsupercontentsmask);
-                               if (settings.staticmode)
+                               if (settings.staticmode || settings.stablerandom <= 0)
                                {
                                        // static mode fires a LOT of rays but none of them are identical, so they are not cached
+                                       // non-stable random in dynamic mode also never reuses a direction, so there's no reason to cache it
                                        cliptrace = CL_TraceLine(clipstart, clipend, settings.staticmode ? MOVE_WORLDONLY : (settings.hitmodels ? MOVE_HITMODEL : MOVE_NOMONSTERS), NULL, hitsupercontentsmask, skipsupercontentsmask, collision_extendmovelength.value, true, false, NULL, true, true);
                                }
                                else
@@ -3300,11 +3346,7 @@ static void R_Shadow_BounceGrid_TracePhotons(r_shadow_bouncegrid_settings_t sett
                                {
                                        // random direction, primarily along plane normal
                                        s = VectorDistance(cliptrace.endpos, clipend);
-                                       if (settings.stablerandom < 0)
-                                               VectorRandom(clipend);
-                                       else
-                                               VectorCheeseRandom(clipend);
-                                       VectorMA(cliptrace.plane.normal, 0.95f, clipend, clipend);
+                                       VectorMA(cliptrace.plane.normal, 0.95f, bouncerandom[bouncecount], clipend);
                                        VectorNormalize(clipend);
                                        VectorScale(clipend, s, clipend);
                                }