implemented r_subdivisions_ cvars to control q3bsp patches, adaptive LOD based on...
authorhavoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Thu, 4 Mar 2004 06:20:20 +0000 (06:20 +0000)
committerhavoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Thu, 4 Mar 2004 06:20:20 +0000 (06:20 +0000)
git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@3964 d7cf8633-e32d-0410-b094-e92efae38249

curves.c
curves.h
model_brush.c
todo

index 5b19243..8378a4b 100644 (file)
--- a/curves.c
+++ b/curves.c
@@ -4,8 +4,11 @@
 
 // LordHavoc's rant on misuse of the name 'bezier': many people seem to think that bezier is a generic term for splines, but it is not, it is a term for a specific type of spline (minimum of 4 control points, cubic spline).
 
+#include <math.h>
 #include "curves.h"
+#include "zone.h"
 
+#if 0
 void QuadraticSplineSubdivideFloat(int inpoints, int components, const float *in, int instride, float *out, int outstride)
 {
        int s;
@@ -157,5 +160,261 @@ void QuadraticSplinePatchSubdivideFloatBuffer(int cpwidth, int cpheight, int xle
                }
        }
 }
+#elif 1
+void QuadraticSplinePatchSubdivideFloatBuffer(int cpwidth, int cpheight, int xlevel, int ylevel, int components, const float *in, float *out)
+{
+       int c, x, y, outwidth, outheight, halfstep, xstep, ystep;
+       float prev, curr, next;
+       xstep = 1 << xlevel;
+       ystep = 1 << ylevel;
+       outwidth = ((cpwidth - 1) * xstep) + 1;
+       outheight = ((cpheight - 1) * ystep) + 1;
+       for (y = 0;y < cpheight;y++)
+               for (x = 0;x < cpwidth;x++)
+                       for (c = 0;c < components;c++)
+                               out[(y * ystep * outwidth + x * xstep) * components + c] = in[(y * cpwidth + x) * components + c];
+       while (xstep > 1 || ystep > 1)
+       {
+               if (xstep >= ystep)
+               {
+                       // subdivide on X
+                       halfstep = xstep >> 1;
+                       for (y = 0;y < outheight;y += ystep)
+                       {
+                               for (c = 0;c < components;c++)
+                               {
+                                       x = xstep;
+                                       // fetch first two control points 
+                                       prev = out[(y * outwidth + (x - xstep)) * components + c];
+                                       curr = out[(y * outwidth + x) * components + c];
+                                       // create first midpoint
+                                       out[(y * outwidth + (x - halfstep)) * components + c] = (curr + prev) * 0.5f;
+                                       for (;x < outwidth - xstep;x += xstep, prev = curr, curr = next)
+                                       {
+                                               // fetch next control point
+                                               next = out[(y * outwidth + (x + xstep)) * components + c];
+                                               // flatten central control point 
+                                               out[(y * outwidth + x) * components + c] = (curr + (prev + next) * 0.5f) * 0.5f;
+                                               // create following midpoint
+                                               out[(y * outwidth + (x + halfstep)) * components + c] = (curr + next) * 0.5f;
+                                       }
+                               }
+                       }
+                       xstep >>= 1;
+               }
+               else
+               {
+                       // subdivide on Y
+                       halfstep = ystep >> 1;
+                       for (x = 0;x < outwidth;x += xstep)
+                       {
+                               for (c = 0;c < components;c++)
+                               {
+                                       y = ystep;
+                                       // fetch first two control points 
+                                       prev = out[((y - ystep) * outwidth + x) * components + c];
+                                       curr = out[(y * outwidth + x) * components + c];
+                                       // create first midpoint
+                                       out[((y - halfstep) * outwidth + x) * components + c] = (curr + prev) * 0.5f;
+                                       for (;y < outheight - ystep;y += ystep, prev = curr, curr = next)
+                                       {
+                                               // fetch next control point
+                                               next = out[((y + ystep) * outwidth + x) * components + c];
+                                               // flatten central control point 
+                                               out[(y * outwidth + x) * components + c] = (curr + (prev + next) * 0.5f) * 0.5f;;
+                                               // create following midpoint
+                                               out[((y + halfstep) * outwidth + x) * components + c] = (curr + next) * 0.5f;
+                                       }
+                               }
+                       }
+                       ystep >>= 1;
+               }
+       }
+       // flatten control points on X
+       for (y = 0;y < outheight;y += ystep)
+       {
+               for (c = 0;c < components;c++)
+               {
+                       x = xstep;
+                       // fetch first two control points 
+                       prev = out[(y * outwidth + (x - xstep)) * components + c];
+                       curr = out[(y * outwidth + x) * components + c];
+                       for (;x < outwidth - xstep;x += xstep, prev = curr, curr = next)
+                       {
+                               // fetch next control point 
+                               next = out[(y * outwidth + (x + xstep)) * components + c];
+                               // flatten central control point 
+                               out[(y * outwidth + x) * components + c] = (curr + (prev + next) * 0.5f) * 0.5f;;
+                       }
+               }
+       }
+       // flatten control points on Y
+       for (x = 0;x < outwidth;x += xstep)
+       {
+               for (c = 0;c < components;c++)
+               {
+                       y = ystep;
+                       // fetch first two control points 
+                       prev = out[((y - ystep) * outwidth + x) * components + c];
+                       curr = out[(y * outwidth + x) * components + c];
+                       for (;y < outheight - ystep;y += ystep, prev = curr, curr = next)
+                       {
+                               // fetch next control point 
+                               next = out[((y + ystep) * outwidth + x) * components + c];
+                               // flatten central control point 
+                               out[(y * outwidth + x) * components + c] = (curr + (prev + next) * 0.5f) * 0.5f;;
+                       }
+               }
+       }
+
+       /*
+       for (y = ystep;y < outheight - ystep;y += ystep)
+       {
+               for (c = 0;c < components;c++)
+               {
+                       for (x = xstep, outp = out + (y * outwidth + x) * components + c, prev = outp[-xstep * components], curr = outp[0], next = outp[xstep * components];x < outwidth;x += xstep, outp += ystep * outwidth * components, prev = curr, curr = next, next = outp[xstep * components])
+                       {
+                               // midpoint
+                               outp[-halfstep * components] = (prev + curr) * 0.5f;
+                               // flatten control point
+                               outp[0] = (curr + (prev + next) * 0.5f) * 0.5f;
+                               // next midpoint (only needed for end segment)
+                               outp[halfstep * components] = (next + curr) * 0.5f;
+                       }
+               }
+       }
+       */
+}
+#else
+// unfinished code
+void QuadraticSplinePatchSubdivideFloatBuffer(int cpwidth, int cpheight, int xlevel, int ylevel, int components, const float *in, float *out)
+{
+       int outwidth, outheight;
+       outwidth = ((cpwidth - 1) << xlevel) + 1;
+       outheight = ((cpheight - 1) << ylevel) + 1;
+       for (y = 0;y < cpheight;y++)
+       {
+               for (x = 0;x < cpwidth;x++)
+               {
+                       for (c = 0;c < components;c++)
+                       {
+                               inp = in + (y * cpwidth + x) * components + c;
+                               outp = out + ((y<<ylevel) * outwidth + (x<<xlevel)) * components + c;
+                               for (sy = 0;sy < expandy;sy++)
+                               {
+                                       for (sx = 0;sx < expandx;sx++)
+                                       {
+                                               d = a + (b - a) * 2 * t + (a - b + c - b) * t * t;
+                                       }
+                               }
+                       }
+               }
+       }
+}
+#endif
+
+/*
+0.00000 ?.????? ?.????? ?.????? ?.????? ?.????? ?.????? ?.????? 1.00000 ?.????? ?.????? ?.????? ?.????? ?.????? ?.????? ?.????? 0.00000 deviation: 0.5
+0.00000 ?.????? ?.????? ?.????? 0.50000 ?.????? ?.????? ?.????? 0.50000 ?.????? ?.????? ?.????? 0.50000 ?.????? ?.????? ?.????? 0.00000 deviation: 0.125
+0.00000 ?.????? 0.25000 ?.????? 0.37500 ?.????? 0.50000 ?.????? 0.50000 ?.????? 0.50000 ?.????? 0.37500 ?.????? 0.25000 ?.????? 0.00000 deviation: 0.03125
+0.00000 0.12500 0.21875 0.31250 0.37500 0.43750 0.46875 0.50000 0.50000 0.50000 0.46875 0.43750 0.37500 0.31250 0.21875 0.12500 0.00000 deviation: not available
+*/
+
+float QuadraticSplinePatchLargestDeviationOnX(int cpwidth, int cpheight, int components, const float *in)
+{
+       int c, x, y;
+       const float *cp;
+       float deviation, squareddeviation, bestsquareddeviation;
+       bestsquareddeviation = 0;
+       for (y = 0;y < cpheight;y++)
+       {
+               for (x = 1;x < cpwidth-1;x++)
+               {
+                       squareddeviation = 0;
+                       for (c = 0, cp = in + ((y * cpwidth) + x) * components;c < components;c++, cp++)
+                       {
+                               deviation = cp[0] * 0.5f - cp[-components] * 0.25f - cp[components] * 0.25f;
+                               squareddeviation += deviation*deviation;
+                       }
+                       if (bestsquareddeviation < squareddeviation)
+                               bestsquareddeviation = squareddeviation;
+               }
+       }
+       return sqrt(bestsquareddeviation);
+}
+
+float QuadraticSplinePatchLargestDeviationOnY(int cpwidth, int cpheight, int components, const float *in)
+{
+       int c, x, y;
+       const float *cp;
+       float deviation, squareddeviation, bestsquareddeviation;
+       bestsquareddeviation = 0;
+       for (y = 1;y < cpheight-1;y++)
+       {
+               for (x = 0;x < cpwidth;x++)
+               {
+                       squareddeviation = 0;
+                       for (c = 0, cp = in + ((y * cpwidth) + x) * components;c < components;c++, cp++)
+                       {
+                               deviation = cp[0] * 0.5f - cp[-cpwidth * components] * 0.25f - cp[cpwidth * components] * 0.25f;
+                               squareddeviation += deviation*deviation;
+                       }
+                       if (bestsquareddeviation < squareddeviation)
+                               bestsquareddeviation = squareddeviation;
+               }
+       }
+       return sqrt(bestsquareddeviation);
+}
+
+int QuadraticSplinePatchSubdivisionLevelForDeviation(float deviation, float level1tolerance, int levellimit)
+{
+       int level;
+       // count the automatic flatten step which reduces deviation by 50%
+       deviation *= 0.5f;
+       // count the levels to subdivide to come under the tolerance
+       for (level = 0;level < levellimit && deviation > level1tolerance;level++)
+               deviation *= 0.25f;
+       return level;
+}
+
+int QuadraticSplinePatchSubdivisionLevelOnX(int cpwidth, int cpheight, int components, const float *in, float level1tolerance, int levellimit)
+{
+       return QuadraticSplinePatchSubdivisionLevelForDeviation(QuadraticSplinePatchLargestDeviationOnX(cpwidth, cpheight, components, in), level1tolerance, levellimit);
+}
+
+int QuadraticSplinePatchSubdivisionLevelOnY(int cpwidth, int cpheight, int components, const float *in, float level1tolerance, int levellimit)
+{
+       return QuadraticSplinePatchSubdivisionLevelForDeviation(QuadraticSplinePatchLargestDeviationOnY(cpwidth, cpheight, components, in), level1tolerance, levellimit);
+}
 
+/*
+       d = a * (1 - 2 * t + t * t) + b * (2 * t - 2 * t * t) + c * t * t;
+       d = a * (1 + t * t + -2 * t) + b * (2 * t + -2 * t * t) + c * t * t;
+       d = a * 1 + a * t * t + a * -2 * t + b * 2 * t + b * -2 * t * t + c * t * t;
+       d = a * 1 + (a * t + a * -2) * t + (b * 2 + b * -2 * t) * t + (c * t) * t;
+       d = a + ((a * t + a * -2) + (b * 2 + b * -2 * t) + (c * t)) * t;
+       d = a + (a * (t - 2) + b * 2 + b * -2 * t + c * t) * t;
+       d = a + (a * (t - 2) + b * 2 + (b * -2 + c) * t) * t;
+       d = a + (a * (t - 2) + b * 2 + (c + b * -2) * t) * t;
+       d = a + a * (t - 2) * t + b * 2 * t + (c + b * -2) * t * t;
+       d = a * (1 + (t - 2) * t) + b * 2 * t + (c + b * -2) * t * t;
+       d = a * (1 + (t - 2) * t) + b * 2 * t + c * t * t + b * -2 * t * t;
+       d = a * 1 + a * (t - 2) * t + b * 2 * t + c * t * t + b * -2 * t * t;
+       d = a * 1 + a * t * t + a * -2 * t + b * 2 * t + c * t * t + b * -2 * t * t;
+       d = a * (1 - 2 * t + t * t) + b * 2 * t + c * t * t + b * -2 * t * t;
+       d = a * (1 - 2 * t) + a * t * t + b * 2 * t + c * t * t + b * -2 * t * t;
+       d = a + a * -2 * t + a * t * t + b * 2 * t + c * t * t + b * -2 * t * t;
+       d = a + a * -2 * t + a * t * t + b * 2 * t + b * -2 * t * t + c * t * t;
+       d = a + a * -2 * t + a * t * t + b * 2 * t + b * -2 * t * t + c * t * t;
+       d = a + a * -2 * t + b * 2 * t + b * -2 * t * t + a * t * t + c * t * t;
+       d = a + a * -2 * t + b * 2 * t + (a + c + b * -2) * t * t;
+       d = a + (a * -2 + b * 2) * t + (a + c + b * -2) * t * t;
+       d = a + ((a * -2 + b * 2) + (a + c + b * -2) * t) * t;
+       d = a + ((b + b - a - a) + (a + c - b - b) * t) * t;
+       d = a + (b + b - a - a) * t + (a + c - b - b) * t * t;
+       d = a + (b - a) * 2 * t + (a + c - b * 2) * t * t;
+       d = a + (b - a) * 2 * t + (a - b + c - b) * t * t;
+       
+       d = in[0] + (in[1] - in[0]) * 2 * t + (in[0] - in[1] + in[2] - in[1]) * t * t;
+*/
 
index 72567dd..0b46103 100644 (file)
--- a/curves.h
+++ b/curves.h
@@ -4,6 +4,11 @@
 
 void QuadraticSplineSubdivideFloat(int inpoints, int components, const float *in, int instride, float *out, int outstride);
 void QuadraticSplinePatchSubdivideFloatBuffer(int cpwidth, int cpheight, int xlevel, int ylevel, int components, const float *in, float *out);
+float QuadraticSplinePatchLargestDeviationOnX(int cpwidth, int cpheight, int components, const float *in);
+float QuadraticSplinePatchLargestDeviationOnY(int cpwidth, int cpheight, int components, const float *in);
+int QuadraticSplinePatchSubdivisionLevelForDeviation(float deviation, float level1tolerance, int levellimit);
+int QuadraticSplinePatchSubdivisionLevelOnX(int cpwidth, int cpheight, int components, const float *in, float level1tolerance, int levellimit);
+int QuadraticSplinePatchSubdivisionLevelOnY(int cpwidth, int cpheight, int components, const float *in, float level1tolerance, int levellimit);
 
 #endif
 
index f923c3f..1d87204 100644 (file)
@@ -34,7 +34,10 @@ cvar_t r_novis = {0, "r_novis", "0"};
 cvar_t r_miplightmaps = {CVAR_SAVE, "r_miplightmaps", "0"};
 cvar_t r_lightmaprgba = {0, "r_lightmaprgba", "1"};
 cvar_t r_nosurftextures = {0, "r_nosurftextures", "0"};
-cvar_t mod_q3bsp_curves_subdivide_level = {0, "mod_q3bsp_curves_subdivide_level", "2"};
+cvar_t r_subdivisions_tolerance = {0, "r_subdivisions_tolerance", "4"};
+cvar_t r_subdivisions_minlevel = {0, "r_subdivisions_minlevel", "0"};
+cvar_t r_subdivisions_maxlevel = {0, "r_subdivisions_maxlevel", "4"};
+cvar_t r_subdivisions_maxvertices = {0, "r_subdivisions_maxvertices", "65536"};
 cvar_t mod_q3bsp_curves_collisions = {0, "mod_q3bsp_curves_collisions", "1"};
 cvar_t mod_q3bsp_optimizedtraceline = {0, "mod_q3bsp_optimizedtraceline", "1"};
 cvar_t mod_q3bsp_debugtracebrush = {0, "mod_q3bsp_debugtracebrush", "0"};
@@ -48,7 +51,10 @@ void Mod_BrushInit(void)
        Cvar_RegisterVariable(&r_miplightmaps);
        Cvar_RegisterVariable(&r_lightmaprgba);
        Cvar_RegisterVariable(&r_nosurftextures);
-       Cvar_RegisterVariable(&mod_q3bsp_curves_subdivide_level);
+       Cvar_RegisterVariable(&r_subdivisions_tolerance);
+       Cvar_RegisterVariable(&r_subdivisions_minlevel);
+       Cvar_RegisterVariable(&r_subdivisions_maxlevel);
+       Cvar_RegisterVariable(&r_subdivisions_maxvertices);
        Cvar_RegisterVariable(&mod_q3bsp_curves_collisions);
        Cvar_RegisterVariable(&mod_q3bsp_optimizedtraceline);
        Cvar_RegisterVariable(&mod_q3bsp_debugtracebrush);
@@ -4079,13 +4085,6 @@ static void Mod_Q3BSP_LoadFaces(lump_t *l)
                                out->type = 0; // error
                                continue;
                        }
-                       // convert patch to Q3FACETYPE_MESH
-                       xlevel = mod_q3bsp_curves_subdivide_level.integer;
-                       ylevel = mod_q3bsp_curves_subdivide_level.integer;
-                       finalwidth = ((patchsize[0] - 1) << xlevel) + 1;
-                       finalheight = ((patchsize[1] - 1) << ylevel) + 1;
-                       finalvertices = finalwidth * finalheight;
-                       finaltriangles = (finalwidth - 1) * (finalheight - 1) * 2;
                        originalvertex3f = loadmodel->brushq3.data_vertex3f + out->firstvertex * 3;
                        //originalsvector3f = loadmodel->brushq3.data_svector3f + out->firstvertex * 3;
                        //originaltvector3f = loadmodel->brushq3.data_tvector3f + out->firstvertex * 3;
@@ -4106,6 +4105,27 @@ static void Mod_Q3BSP_LoadFaces(lump_t *l)
                        //originalelement3i = out->data_element3i;
                        //originalneighbor3i = out->data_neighbor3i;
                        */
+                       // convert patch to Q3FACETYPE_MESH
+                       xlevel = QuadraticSplinePatchSubdivisionLevelOnX(patchsize[0], patchsize[1], 3, originalvertex3f, r_subdivisions_tolerance.value, 10);
+                       ylevel = QuadraticSplinePatchSubdivisionLevelOnY(patchsize[0], patchsize[1], 3, originalvertex3f, r_subdivisions_tolerance.value, 10);
+                       // bound to user settings
+                       xlevel = bound(r_subdivisions_minlevel.integer, xlevel, r_subdivisions_maxlevel.integer);
+                       ylevel = bound(r_subdivisions_minlevel.integer, ylevel, r_subdivisions_maxlevel.integer);
+                       // bound to sanity settings
+                       xlevel = bound(0, xlevel, 10);
+                       ylevel = bound(0, ylevel, 10);
+                       // bound to user limit on vertices
+                       while ((xlevel > 0 || ylevel > 0) && (((patchsize[0] - 1) << xlevel) + 1) * (((patchsize[1] - 1) << ylevel) + 1) > min(r_subdivisions_maxvertices.integer, 262144))
+                       {
+                               if (xlevel > ylevel)
+                                       xlevel--;
+                               else
+                                       ylevel--;
+                       }
+                       finalwidth = ((patchsize[0] - 1) << xlevel) + 1;
+                       finalheight = ((patchsize[1] - 1) << ylevel) + 1;
+                       finalvertices = finalwidth * finalheight;
+                       finaltriangles = (finalwidth - 1) * (finalheight - 1) * 2;
                        out->data_vertex3f = Mem_Alloc(loadmodel->mempool, sizeof(float[20]) * finalvertices);
                        out->data_svector3f = out->data_vertex3f + finalvertices * 3;
                        out->data_tvector3f = out->data_svector3f + finalvertices * 3;
diff --git a/todo b/todo
index 2179f2d..d2b7a6f 100644 (file)
--- a/todo
+++ b/todo
@@ -37,6 +37,10 @@ d darkplaces: revert noclip movement to match nq for compatibility with mods tha
 d darkplaces: make light_lev dlights from qc require PFLAGS_FULLDYNAMIC flag
 d darkplaces: improve tenebrae compatibility by handling EF_FULLDYNAMIC flag in tenebrae mode, also make all sprites render additive
 d darkplaces: add r_showtris cvar (Riot)
+0 darkplaces: figure out why dlights are flashing on/off in TEU, particularly test the flashlight (Electro)
+0 darkplaces: fix r_editlights_edit origin not working (romi)
+0 darkplaces: make players step down stairs rather than just flying off (Riot) 
+0 darkplaces: add DP_EF_NOSHADOW extension (Urre)
 0 darkplaces: fix model lighting with r_shadow_realtime_world_lightmaps mode, it seems to be adding dlights to vertices? (Mitchell)
 3 darkplaces: figure out BoxOnPlaneSide crash that happens in dpmod dpdm2 deathmatch 7 occasionally
 2 darkplaces: add q2 sprite support sometime
@@ -156,7 +160,7 @@ d darkplaces: figure out and fix win32 networking problems
 0 darkplaces: add back cl_particles_lighting cvar and add back the particle lighting (romi)
 5 darkplaces: lightshader files (probably loaded by the cubemap field already present in rtlights handling), these would indicate what attenuation textures to use for the light, what cubemap filter, whether to have a corona and so on (romi)
 1 darkplaces: shadow volumes from q3bsp brush models are broken, maybe inverted or something (Vermeulen)
-2 darkplaces: decal clipping (romi)
+2 darkplaces: decal clipping (romi, Sajt)
 7 darkplaces: shadow volume clipping (romi)
 0 dpmod: make run animation play back according to movement speed (along v_forward), instead of just playing a continuous loop based on time (Urre)
 1 darkplaces: q1bsp: parse submodels before leafs, so that the pvs can be allocated smaller (only enough for the world model's visleafs count) (Vic) 
@@ -460,7 +464,7 @@ d darkplaces: figure out what is causing invalid entity numbers in TouchAreaGrid
 ? dpmod: apparently can't fire in start.bsp? (scar3crow)
 resolvedbug darkplaces: Zerstorer: riot shotgun rotates even as a view model: need to ignore that model flag when a view model
 resolvedbug darkplaces: collision: 'wall stuttering' collision bugs: getting stuck and nudged out constantly when sliding along certain walls
-bug darkplaces: collision: q3bsp curve problems: comparing nudged impacts causes player to hit edges of triangles in a q3bsp curve closer than the surface
+resolvedbug darkplaces: collision: q3bsp curve problems: comparing nudged impacts causes player to hit edges of triangles in a q3bsp curve closer than the surface
 bug darkplaces: physics: rotating MOVETYPE_PUSH code calls blocked when it's just a touch, it isn't even trying to push (SeienAbunae)
 d darkplaces: (goodvsbad2) increase chase_stevie height to 2048 (yummyluv)
 d darkplaces: .skin loading for models (override skins - not exactly shaders, but adequate, missing replacements are nodraw, this allows q3 player models with optional accessories) (Electro)