Fixed point Quake

[mankrip]

Is there any Quake engine that doesn't use any floating point data types? How hard would it be to convert the whole engine to use fixed point instead?

The idea is to optimize the Quake engine for processors that doesn't support floating point operations.

[Baker]

Movement and positioning isn't in integer values. I might be standing at 520.6 420.8 28.1 in the Start map atrium. And it only prints like that because the printf statement uses %5.1f or whatever, if you used %5.3f to print it no doubt you'd find it has more precision.

Then you have the angles issue.

Or the fact that all vectors in Quake ... vec3_t is an array of float[0] float [1] and float [2] and is used everywhere for entity positioning and physics.

And vector math and lerping uses floats and the engine abounds in float returning functions (sin, cos, tan, sqrt and friends).

You *could* make the engine use all integer data types by enhancing the precision by using a scale instead of 1, of something like 10,000 and get fairly good precision [this would be a mammoth undertaking].

But then you get to the point that floats are used in the save games formats, the map formats, model formats and you won't be able to avoid float returning functions.

Keep in mind QuakeC uses floats and string and vectors. You have to alter the QuakeC compiler and the progs intepreter stuff too.

In short (you know, the data type ) .. it isn't "impossible impossible". It is the slightly more possible neighbor next door to impossible impossible.

[Lardarse]

It could be feasible if it was using 16.16 fixed point numbers. Or more accurately, 15.16 signed fixed point numbers (so you get +/- 32768 ish). I have a feeling that the Doom engine does something along these lines...

[Spike]

there are far too many floats in quake, yes. even cvars use floats.

you don't have to remove all of them, just the things in performance-critical code. the software renderer, physics code, etc. the rest can generally be emulated automatically using some compiler flags.
qc should generally not be used in performance-critical ways. it shouldn't need extensive logic as most of what its doing is just simple asignments. absmin/absmax are probably a candidate for conversion, but the rest of qc isn't really worth it (if only because you lose mod compatibility, though you may wish to change some store instructions to copy ints instead of floats).

386s and 486s don't always have an fpu, which is why doom uses no floats.

[qbism]

Take a look at the source code of Pocket Quake. It includes many fixed-point conversions. Floats kill performance on many PPC platforms. I've been meaning to try some, especially within the drawspan loop.

http://quake.pocketmatrix.com/

Forum
http://www.pocketmatrix.com/forums/viewforum.php?f=8

[qbism]

OK, here's a fixed-point D_DrawSpans, cut-and-paste. Adapted from PocketQuake. Looks fine at 320x240 but degrades as resolution increases. [edited: forgot to include variables]

Code: Select all

/*==============================================
// Fixed-point D_DrawSpans
//PocketQuake- Dan East
//fixed-point conversion- Jacco Biker
//unrolled- mh, MK, qbism
//============================================*/
static int sdivzorig, sdivzstepv, sdivzstepu, sdivzstepu_fix;
static int tdivzorig, tdivzstepv, tdivzstepu, tdivzstepu_fix;
static int d_zistepu_fxp, d_zistepv_fxp, d_ziorigin_fxp;
static int zistepu_fix;

#define  FIXPOINTDIV 4194304.0f //qbism

//524288.0f is 13.19 fixed point
// 2097152.0f is 11.21
//4194304.0f is 10.22 (this is what PocketQuake used)
//8388608.0f is 9.23

void UpdateFixedPointVars16( int all )
{
   // JB: Store texture transformation matrix in fixed point vars
   if (all)
   {
      sdivzorig = (int)(FIXPOINTDIV * d_sdivzorigin);
      tdivzorig = (int)(FIXPOINTDIV * d_tdivzorigin);
      sdivzstepv = (int)(FIXPOINTDIV * d_sdivzstepv);
      tdivzstepv = (int)(FIXPOINTDIV * d_tdivzstepv);
      sdivzstepu = (int)(FIXPOINTDIV * d_sdivzstepu);
      sdivzstepu_fix = sdivzstepu*16;
      tdivzstepu = (int)(FIXPOINTDIV * d_tdivzstepu);
      tdivzstepu_fix = tdivzstepu*16;


   }
   d_ziorigin_fxp = (int)(FIXPOINTDIV * d_ziorigin);
   d_zistepv_fxp = (int)(FIXPOINTDIV * d_zistepv );
   d_zistepu_fxp = (int)(FIXPOINTDIV * d_zistepu );

   zistepu_fix = d_zistepu_fxp * 16;
}

void D_DrawSpans16_FP (espan_t *pspan)  //qbism from PocketQuake
{
   int count, spancount, spancountminus1;
   unsigned char *pbase, *pdest;
   fixed16_t s, t;
   int zi, sdivz, tdivz, sstep, tstep;
   int snext, tnext;
   pbase = (unsigned char *)cacheblock;
   //Jacco Biker's fixed point conversion

   // Recalc fixed point values
   UpdateFixedPointVars16( 1 );
   do
   {
      pdest = (unsigned char *)((byte *)d_viewbuffer + (screenwidth * pspan->v) + pspan->u);

      // calculate the initial s/z, t/z, 1/z, s, and t and clamp
      sdivz = sdivzorig + pspan->v * sdivzstepv + pspan->u * sdivzstepu;
      tdivz = tdivzorig + pspan->v * tdivzstepv + pspan->u * tdivzstepu;
      zi = d_ziorigin_fxp + pspan->v * d_zistepv_fxp + pspan->u * d_zistepu_fxp;
      if (zi == 0) zi = 1;
      s = (((sdivz << 8) / zi) << 8) + sadjust;   // 5.27 / 13.19 = 24.8 >> 8 = 16.16
      if (s > bbextents) s = bbextents; else if (s < 0) s = 0;
      t = (((tdivz << 8) / zi) << 8) + tadjust;
      if (t > bbextentt) t = bbextentt; else if (t < 0) t = 0;

      //End Jacco Biker mod

      // Manoel Kasimier - begin
      count = pspan->count >> 4;
      spancount = pspan->count % 16;
      // Manoel Kasimier - end

      while (count-- >0) // Manoel Kasimier
      {
         // calculate s/z, t/z, zi->fixed s and t at far end of span,
         // calculate s and t steps across span by shifting
            sdivz += sdivzstepu_fix;
            tdivz += tdivzstepu_fix;
            zi += zistepu_fix;
            if (!zi) zi = 1;

            snext = (((sdivz<<8)/zi)<<8)+sadjust;
            if (snext > bbextents)
               snext = bbextents;
            else if (snext < 16)
               snext = 16;   // prevent round-off error on <0 steps from causing overstepping & running off the edge of the texture

            tnext = (((tdivz<<8)/zi)<<8) + tadjust;
            if (tnext > bbextentt)
               tnext = bbextentt;
            else if (tnext < 16)
               tnext = 16;   // guard against round-off error on <0 steps

            sstep = (snext - s) >> 4;
            tstep = (tnext - t) >> 4;

         pdest += 16;
         pdest[-16] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
         pdest[-15] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
         pdest[-14] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
         pdest[-13] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
         pdest[-12] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
         pdest[-11] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
         pdest[-10] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
         pdest[ -9] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
         pdest[ -8] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
         pdest[ -7] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
         pdest[ -6] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
         pdest[ -5] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
         pdest[ -4] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
         pdest[ -3] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
         pdest[ -2] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
         pdest[ -1] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
         // Manoel Kasimier - end

         s = snext;
         t = tnext;
         // Manoel Kasimier - begin
      }
      if (spancount > 0)
      {
         // Manoel Kasimier - end
         // calculate s/z, t/z, zi->fixed s and t at last pixel in span (so
         // can't step off polygon), clamp, calculate s and t steps across
         // span by division, biasing steps low so we don't run off the
         // texture

            spancountminus1 = spancount - 1;
            sdivz += sdivzstepu * spancountminus1;
            tdivz += tdivzstepu * spancountminus1;
            zi += d_zistepu_fxp * spancountminus1;
            //if (!zi) zi = 1;
            //z = zi;//(float)0x10000 / zi;   // prescale to 16.16 fixed-point
            snext = (((sdivz<<8) / zi)<<8) + sadjust;
            if (snext > bbextents)
               snext = bbextents;
            else if (snext < 16)
               snext = 16;   // prevent round-off error on <0 steps from causing overstepping & running off the edge of the texture

            tnext = (((tdivz<<8) / zi)<<8) + tadjust;
            if (tnext > bbextentt)
               tnext = bbextentt;
            else if (tnext < 16)
               tnext = 16;   // guard against round-off error on <0 steps

            if (spancount > 1)
            {
               sstep = ((snext - s)) / ((spancount - 1));
               tstep = ((tnext - t)) / ((spancount - 1));
            }


         pdest += spancount;
         switch (spancount)
         {
            case 16: pdest[-16] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
            case 15: pdest[-15] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
            case 14: pdest[-14] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
            case 13: pdest[-13] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
            case 12: pdest[-12] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
            case 11: pdest[-11] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
            case 10: pdest[-10] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
            case  9: pdest[ -9] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
            case  8: pdest[ -8] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
            case  7: pdest[ -7] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
            case  6: pdest[ -6] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
            case  5: pdest[ -5] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
            case  4: pdest[ -4] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
            case  3: pdest[ -3] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
            case  2: pdest[ -2] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
            case  1: pdest[ -1] = pbase[(s >> 16) + (t >> 16) * cachewidth]; s += sstep; t += tstep;
            break;
         }

      }
   } while ((pspan = pspan->pnext) != NULL);
}