author havoc Sun, 27 Nov 2016 21:45:11 +0000 (21:45 +0000) committer havoc 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 patch | blob | history mathlib.h patch | blob | history r_shadow.c patch | blob | history

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 = { 0x12e15e35, 0xb500f16e, 0x2e714eb2, 0xb37916a5 };
+
+static void mul128(unsigned int a[], unsigned int b[], unsigned int dest)
+{
+       unsigned long long t;
+       t = a * b;
+       t = a * b;
+       t = a * b;
+       t = a * b;
+
+       // 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 += t >> 32; t &= 0xffffffff;
+       t += t >> 32; t &= 0xffffffff;
+       t += t >> 32; t &= 0xffffffff;
+
+       t += t >> 32; t &= 0xffffffff;
+       t += t >> 32; t &= 0xffffffff;
+
+       t += t >> 32; t &= 0xffffffff;
+
+       dest = t & 0xffffffff;
+       dest = t & 0xffffffff;
+       dest = t & 0xffffffff;
+       dest = t & 0xffffffff;
+}
+
+void Math_RandomSeed_Reset(randomseed_t *r)
+{
+       r->s = 1;
+       r->s = 0;
+       r->s = 0;
+       r->s = 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 = 1;
+       r->s = 0;
+       r->s = 0;
+       r->s = n;
+}
+
+unsigned long long Math_rand64(randomseed_t *r)
+{
+       unsigned int o;
+       mul128(r->s, mul_Lecuyer, o);
+       r->s = o;
+       r->s = o;
+       r->s = o;
+       r->s = o;
+       return ((unsigned long long)o << 32) + o;
+}
+
+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) = lhcheeserandom(-1, 1);(v) = lhcheeserandom(-1, 1);(v) = 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) = lhcheeserandom(seed,-1, 1);(v) = lhcheeserandom(seed,-1, 1);(v) = lhcheeserandom(seed,-1, 1);}while(DotProduct(v, v) > 1)
+#define VectorLehmerRandom(seed,v) do{(v) = Math_crandomf(seed);(v) = Math_crandomf(seed);(v) = 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);

+// 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;
+}
+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

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;
dlight_t *light;
int bouncecount;
//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;
vec_t s;
rtlight_t *rtlight;

-       // we'll need somewhere to store these
+       Math_RandomSeed_FromInt(&randomseed, seed);
+

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);
-                       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;
+                       }
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