GTestAndEngine: triangle.h Source File

00001 /****************************************************************************************/
00002 /*  Triangle.h                                                                          */
00003 /*                                                                                      */
00004 /*  Author: Mike Sandige                                                                    */
00005 /*  Description:  Edge and Gradient calculations for triangle rasterizater              */
00006 /*                                                                                      */
00007 /*  Code fragments from Chris Hecker's texture mapping articles used with               */
00008 /*  permission.  http://www.d6.com/users/checker                                        */
00009 /*                                                                                      */
00010 /*  The contents of this file are subject to the Genesis3D Public License               */
00011 /*  Version 1.01 (the "License"); you may not use this file except in                   */
00012 /*  compliance with the License. You may obtain a copy of the License at                */
00013 /*  http://www.genesis3d.com                                                            */
00014 /*                                                                                      */
00015 /*  Software distributed under the License is distributed on an "AS IS"                 */
00016 /*  basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See                */
00017 /*  the License for the specific language governing rights and limitations              */
00018 /*  under the License.                                                                  */
00019 /*                                                                                      */
00020 /*  The Original Code is Genesis3D, released March 25, 1999.                            */
00021 /*  Genesis3D Version 1.1 released November 15, 1999                                 */
00022 /*  Copyright (C) 1999 WildTangent, Inc. All Rights Reserved           */
00023 /*                                                                                      */
00024 /****************************************************************************************/
00025 
00026 
00027 #ifndef TRIANGLE_H
00028 #define TRIANGLE_H
00029 
00030 #include "basetype.h"
00031 #include "swthandle.h"                  // geRDriver_THandle
00032 
00033 #ifdef __cplusplus
00034 extern "C" {
00035 #endif
00036 
00037 
00038 
00039 //#define NOISE_FILTER
00040 
00041 #define USE_FIXED_POINT 
00042 
00043 
00044 
00045 #define OOZ_NUMERATOR_SHIFTER  (32)
00046 #define OOZ_NUMERATOR     0xFFFFFFFF
00047 /* oz 20 ooz 30 divprec 16 oozmulprec 8 ozmulprec 8  good. */
00048 /* oz 20 ooz 26 divprec 16 oozmulprec 10 ozmulprec 6  good. */
00049 /* oz 20 ooz 26 divprec 18 oozmulprec 12 ozmulprec 4  good. (small textures suffer a little)*/
00050 
00051 //                                                       32
00052 #define OZ_FXP_SHIFTER /*________________   *     */  (20)                                                              
00053 #define OOZ_FXP_SHIFTER       (26)                                                                                      
00054 
00055 #define OOZ_DIV_PRECISION_BITS (18)
00056 
00057 #define OOZ_MULTIPLY_PRECISION_BITS   (12)
00058 #define OZ_MULTIPLY_PRECISION_BITS    (4)                               // affects the accuracy to the nearest texel 
00059 
00060 #define OOZ_DIV_PREP_RSHIFT    (OOZ_FXP_SHIFTER - OOZ_DIV_PRECISION_BITS)                               
00061 
00062 #define RGB_FXP_SHIFTER (15)    
00063 #define Z_FXP_SHIFTER (8)
00064 
00065 #define Z_FXP_MULTIPLIER   ((geFloat)( 1 <<   Z_FXP_SHIFTER ))  
00066 #define OOZ_FXP_MULTIPLIER ((geFloat)( 1 << OOZ_FXP_SHIFTER ))  
00067 #define OZ_FXP_MULTIPLIER  ((geFloat)( 1 <<  OZ_FXP_SHIFTER )) 
00068 #define RGB_FXP_MULTIPLIER ((geFloat)( 1 << RGB_FXP_SHIFTER ))
00069 
00070 #define OOZ_MUL_PREP_RSHIFT  (OOZ_NUMERATOR_SHIFTER - OOZ_FXP_SHIFTER + OOZ_DIV_PREP_RSHIFT - OOZ_MULTIPLY_PRECISION_BITS)              
00071 #define  OZ_MUL_PREP_RSHIFT  (OZ_FXP_SHIFTER - OZ_MULTIPLY_PRECISION_BITS)                                                                      
00072 /* fixed point is used for the edge and span iterators.   
00073 
00074                 The 1/z (OOZ) iterator is stored with 6.26 precision.
00075                 The other 1/U iterators are stored with 12.20 precision.
00076                 (These were experimentially determined by minimizing the visible errors.)
00077 
00078                 (OOZ_NUMERATOR is ~= 0.32)
00079 
00080                 so, to compute a 16.16 fixed point U from 1/z and U/z
00081 
00082                  U  ={[(2^OZ_FXP_SHIFTER)/((1/z * 2^OOZ_FXP_SHIFTER)>>OOZ_DIV_PRE_RSHIFT)]>>OOZ_MUL_PREP_RSHIFT} * {[U/z * 2^OZ_FXP_SHIFTER]>>OZ_MUL_PRE_PRSHIFT}
00083 
00084                  U  ={[(2^32)/((1/z * 2^26)>>8)]>>2} * {[U/z * 2^20]>>16}
00085                     ={[(2^32)/(   1/z * 2^18   ]>>2} * {   U/z * 2^4    }
00086                     ={[       z * 2^14         ]>>2} * {   U/z * 2^4    }
00087                         ={        z * 2^12             } * {   U/z * 2^4    }
00088                         =                        (z*U/z) * 2^16
00089                         =                              U * 2^16
00090 
00091 
00092 
00093 */
00094 
00095 
00096 #if OOZ_DIV_PREP_RSHIFT > 0
00097         #define OOZ_DIV_PREP(OOZ)   ((OOZ)>>OOZ_DIV_PREP_RSHIFT)
00098 #else
00099         #define OOZ_DIV_PREP(OOZ)   ((OOZ)<<(-OOZ_DIV_PREP_RSHIFT))
00100 #endif
00101 
00102 #if OZ_MUL_PREP_RSHIFT > 0
00103         #define OZ_MUL_PREP(OZ)         ((OZ)>>OZ_MUL_PREP_RSHIFT)   
00104 #else
00105         #define OZ_MUL_PREP(OZ)         ((OZ)<<(-OZ_MUL_PREP_RSHIFT))   
00106 #endif
00107 
00108 #if OOZ_MUL_PREP_RSHIFT > 0
00109         #define OOZ_MUL_PREP(OZ)        ((OZ)>>OOZ_MUL_PREP_RSHIFT)   
00110 #else
00111         #define OOZ_MUL_PREP(OZ)        ((OZ)<<(-OOZ_MUL_PREP_RSHIFT))   
00112 #endif
00113 
00114 #if (OOZ_MULTIPLY_PRECISION_BITS > 8)
00115         #define OOZ_MUL_Z(OOZ,Z)  ( ((OOZ)>>(OOZ_MULTIPLY_PRECISION_BITS-8)) * (Z) )
00116 #else
00117         #define OOZ_MUL_Z(OOZ,Z)  ( ((OOZ)<<(8-OOZ_MULTIPLY_PRECISION_BITS)) * (Z) )
00118 #endif
00119 
00120 #if (OOZ_MULTIPLY_PRECISION_BITS > 8)
00121         #define GRADIENT_OOZ_MUL_Z(OOZ,Z)  ( ((OOZ)>>(OOZ_FXPMULTIPLY_PRECISION_BITS-8)) * (Z) )
00122 #else
00123         #define GRADIENT_OOZ_MUL_Z(OOZ,Z)  ( ((OOZ)<<(8-OOZ_MULTIPLY_PRECISION_BITS)) * (Z) )
00124 #endif
00125 
00126 #if (OZ_MULTIPLY_SHIFTER <0) || (OOZ_MULTIPLY_SHIFTER<0)
00127         error.  
00128 #endif
00129 
00130 #define USE_FIXED_POINT 
00131 #define DEST16BIT
00132 
00133 #ifdef USE_FIXED_POINT
00134 #define FXFL int32
00135 #define FXFL_OOZ(XXX)   ((int32)((XXX) * OOZ_FXP_MULTIPLIER))
00136 #define FXFL_OZ(XXX)    ((int32)((XXX) *  OZ_FXP_MULTIPLIER))
00137 #define FXFL_RGB(XXX)   ((int32)((XXX) * RGB_FXP_MULTIPLIER))
00138 #define FXFL_Z(XXX)     ((int32)((XXX) *   Z_FXP_MULTIPLIER))
00139 #define OOZ_FXP_TO_16_16(XXX)  ( (XXX)>>(OOZ_FXP_SHIFTER-16) )
00140 #define  OZ_FXP_TO_16_16(XXX)  ( (XXX)>>(OZ_FXP_SHIFTER-16)  )
00141 #define     Z_FXP_TO_INT(XXX)  ( (XXX)>>Z_FXP_SHIFTER        )
00142 #define RGB_FXP_TO_16_16(XXX)  (XXX)
00143 #else
00144         error.
00145 #endif
00146 
00147 
00148 #define TEXTUREPIXEL    unsigned char 
00149 #define LIGHTMAPPIXEL   unsigned char
00150 #ifdef DEST16BIT
00151         #define DESTPIXEL       unsigned short
00152 #else
00153         #define DESTPIXEL       unsigned char
00154 #endif
00155 #define ZMAPPIXEL               unsigned short
00156 #define ALPHAMAPPIXEL   unsigned short
00157 
00158 #define DESTPIXEL_SHIFTER (sizeof(DESTPIXEL)/2)
00159 #ifdef USE_DIBS
00160 #define TOPDOWN_OR_BOTTOMUP(XXX) (-(XXX))  // + for TOPDOWN, - for BOTTOMUP.
00161 #else
00162 #define TOPDOWN_OR_BOTTOMUP(XXX) ((XXX))  // + for TOPDOWN, - for BOTTOMUP.
00163 #endif
00164 
00165 // ROP FLAGS
00166 #define TMAP            0x1
00167 #define LSHADE          0x2
00168 #define LFLAT           0x4
00169 #define LMAP        0x8
00170 #define AFLAT           0x10
00171 #define AMAP            0x20
00172 #define ZSET            0x40
00173 #define ZTEST           0x80
00174 #define ZBUF            0x100           // any zbuffering
00175 #define SBUF            0x200
00176 #define D565            0x200           // not really a rop flag, but used in generating spans
00177 
00178 
00179 
00180 #define TRASTER_SMALL_DIVIDE_TABLESIZE 129
00181 
00182 
00183 
00184 typedef struct Triangle_Gradients 
00185 {
00186         geFloat OneOverZ[3];                    // 1/Z per vtx  (if Affine Z per vtx)  Normalized!
00187                                                                 // all Z's stored here are normalized to [0..1]  see FZScale below
00188         geFloat UOverZ[3];                      // U/Z per vtx  (if Affine U per vtx)  
00189         geFloat VOverZ[3];                      // V/Z per vtx  (if Affine V per vtx)  
00190         geFloat FdOneOverZdX;                   // d(1/Z)/dX    (if Affine dZ/dX )
00191         geFloat dOneOverZdY;                    // d(1/Z)/dY    (if Affine dZ/dY )
00192         geFloat FdUOverZdX;                     // d(U/Z)/dX    (if Affine dU/dX )
00193         geFloat dUOverZdY;                      // d(U/Z)/dY    (if Affine dU/dY )
00194         geFloat FdVOverZdX;                     // d(V/Z)/dX    (if Affine dV/dX )
00195         geFloat dVOverZdY;                      // d(V/Z)/dY    (if Affine dV/dY )
00196 
00197         int SubSpanWidth;                       // maximum affine subdivision width for this poly (power of 2)
00198         int SubSpanShift;                       //   shift to divide by SubSpanLength   1<<SubSpanShift == SubSpanWidth
00199         int Affine;                                     // flag:  if true, then all gradients are NOT 1/Z, just Z
00200 
00201         // lighting interpolation is always affine
00202         geFloat FdRdX;                          // dR/dX (the F means geFloat, since there is a fixed point version of this also)
00203         geFloat  dRdY;                          // dR/dY  
00204         geFloat FdGdX;                          // dG/dX (the F means geFloat, since there is a fixed point version of this also)
00205         geFloat  dGdY;                          // dG/dY  
00206         geFloat FdBdX;                          // dB/dX (the F means geFloat, since there is a fixed point version of this also)
00207         geFloat  dBdY;                          // dB/dY  
00208 
00209         FXFL dOneOverZdX;                       // fixed point FdOneOverZdX (FXFL_OOZ)           see precision comments
00210         FXFL dUOverZdX;                         // fixed point FdUOverZdX   (FXFL_OZ)
00211         FXFL dVOverZdX;                         // fixed point FdVOverZdX   (FXFL_OZ)
00212         FXFL dRdX;                                      // fixed point FdRdX        (FXFL_RGB)
00213         FXFL dGdX;                                      // fixed point FdGdX        (FXFL_RGB)
00214         FXFL dBdX;                                      // fixed point FdBdX        (FXFL_RGB)
00215 
00216         geFloat FZScale;                                // Z is normalized to a max Z of 1.0.  so Normalized_Z = Z/FZScale;
00217         FXFL  ZScale;                           // fixed point FZScale      (FXFL_Z)
00218 } Triangle_Gradients;
00219 
00220 
00221 typedef struct Triangle_Edge
00222 {
00223         int32 X;                                        // current X of edge pixel 
00224         int32 XStep;                            // X + XStep = X for next edge point
00225         uint32 Dest;                            // current address into destination bits for edge pixel
00226         int32 DestStep;                         // Dest + DestStep = Dest for next edge point
00227         int32 Numerator, Denominator;// DDA fraction
00228         int32 ErrorTerm;                                // DDA error
00229 
00230         FXFL OneOverZ;                          // current 1/Z   (if Gradients.Affine: Z)
00231         FXFL OneOverZStep;                      // OneOverZ + OneOverZStep = 1/Z for next edge point
00232         FXFL UOverZ;                            // current U/Z   (if Gradients.Affine: U)
00233         FXFL UOverZStep;                        // UOneOverZ + UOverZStep = U/Z for next edge point
00234         FXFL VOverZ;                            // V/Z and step     (if Gradients.Affine: V )
00235         FXFL VOverZStep;                        // VOneOverZ + VOverZStep = V/Z for next edge point
00236         FXFL R;                                         // current R
00237         FXFL RStep;                                     // R + RStep = R for next edge point
00238         FXFL G;                                         // current G
00239         FXFL GStep;                                     // G + GStep = G for next edge point
00240         FXFL B;                                         // B
00241         FXFL BStep;                                     // B + BStep = B for next edge point
00242         
00243         // (these are copied from Gradients) 
00244         FXFL dOneOverZdX;       
00245         FXFL dUOverZdX;         
00246         FXFL dVOverZdX;         
00247         FXFL dRdX;                      
00248         FXFL dGdX;                      
00249         FXFL dBdX;                      
00250         //--------
00251 
00252         int Y;                                          // current Y of edge pixel
00253         int Height;                                     // number of vertical pixels in this edge
00254 
00255 } Triangle_Edge;
00256 
00257 
00258 #define Triangle_PaletteEntry uint32
00259 
00260 typedef struct Triangle_Triangle
00261 {
00262         int ROPFlags;                                           // bit flags for rop.
00263         Triangle_Gradients Gradients;           // Changes across the triangle with respect to the screen
00264         Triangle_Edge Left;                                     // current left edge of currently drawing triangle
00265         Triangle_Edge Right;                            // current right edge of currently drawing triangle
00266         
00267         DESTPIXEL *DestBits;                            // pointer into destination bits at left edge of span to draw
00268         TEXTUREPIXEL *TextureBits;                      // pointer to first scan line of texture bits
00269         Triangle_PaletteEntry *Palette;         // pointer to texture palette
00270         int MipIndex;                                           // mip level; index 0 is highest detail
00271         int StrideShift;                                        // Texture is always a power of two width.  This is the power.
00272 
00273         int   SpanWidth;                                        // Width in pixels of current span
00274 
00275         int UMask;                                                      // Mask U by this for tiling
00276         int VMask;                                                      // Mask V by this for tiling
00277         
00278         LIGHTMAPPIXEL *LightMapBits;            // pointer to first scan line of light map bits as supplied by engine
00279                                                                                 // scale a U or V down into the lightmap
00280         int LightMapWidth;                                      // in lightmap pixels (luxels)
00281         int LightMapStride;                                     // in bytes
00282         int LightMapHeight;                                     // in lightmap pixels (luxels)
00283         int LightMapMaxU;                                       // maximum lightmap U (in 16:16 fixed point)
00284         int LightMapMaxV;                                       // maximum lightmap V (in 16:16 fixed point)
00285         int32 LightMapShiftU;                                           // 16:16 shift such that LMU = (u-LightMapShiftU)*LightMapScaleU
00286         int32 LightMapScaleU;                                           // 8:8 multiplication such that LMU = (u-LightMapShiftU)*LightMapScaleU
00287         int32 LightMapShiftV;                                           // 16:16 shift such that LMV = (v-LightMapShiftV)*LightMapScaleV
00288         int32 LightMapScaleV;                                           // 8:8 multiplication such that LMV = (v-LightMapShiftV)*LightMapScaleV
00289 
00290         ZMAPPIXEL *ZMapBits;                            // pointer into zmap bits at left edge of span to draw.
00291         geRDriver_THandle *ZMap;                        // reference to currently selected zmap
00292         geRDriver_THandle *DestMap;                     // reference to currently selected destination bitmap
00293         int ZBufferAddressDelta;                        // Destination bitmap bits + ZBufferAddressDelta = Zbuffer bits
00294 
00295         int SmallDivideTable[TRASTER_SMALL_DIVIDE_TABLESIZE];   // for quick divides by 1..TRASTER_SMALL_DIVIDE_TABLESIZE
00296 
00297         geFloat MaxAffineSize;                          // if triangle is smaller than this, the rasterizer reverts to affine.
00298 
00299         geBoolean IsLightMapSetup;                      // GE_TRUE if light map is already set up. 
00300         void (*LightMapSetup)();                        // called to set up lightmap 
00301 
00302         #ifdef NOISE_FILTER             
00303         int RandomIndex;                                        // experimental: to reduce 16bit banding                        
00304         int RandomTable[256];
00305         unsigned char RandomTableIndex=0;
00306         #endif
00307 } Triangle_Triangle;
00308 
00309 // Global used by span routines.  Not in Triangle for simplified asm addressing.
00310 
00311 int32 OneOverZ,UOverZ,VOverZ;                   // Current 1/Z, U/Z, V/Z for left edge of span (and subspans)
00312 int32 R,G,B;                                                    // Current R,G,B,A for left edge of span (and subspans) 
00313                                                                                 //  R = Red Channel, G = Green Channel, B = Blue Channel
00314 int32 A,OneMinusA;                                              //  A = Alpha Channel   A is 0..16    OneMinusA is 16..0
00315 
00316 Triangle_Triangle Triangle;
00317 
00318         // computes gradients for triangle.  
00319         // Doesn't set any global variables (Triangle), but may reference them for mode info (sorry)
00320 geBoolean GENESISCC Triangle_GradientsCompute( 
00321                                         Triangle_Gradients *G,                  // Gradients to compute (yeah, this is also global)
00322                                         const DRV_TLVertex *pVertices,  // vertex corners of triangle (U,V,R,G,B,etc are [0..1])
00323                                         geFloat TextureWidth,                           // Width of texture in pixels  (scale U up to [0..Width])
00324                                         geFloat TextureHeight);                 // Height of texture in pixels (scale V up to [0..Height])
00325 
00326 
00327         //      computes gradients for an edge of the triangle.
00328         //  Doesn't set or reference any global variables (Triangle).
00329 void GENESISCC Triangle_EdgeCompute( 
00330                 Triangle_Edge *E,                                                       // Edge to compute
00331                 const Triangle_Gradients *Gradients,            // Gradients to use (yeah, this is also global)
00332                 const DRV_TLVertex *pVertices,                          // vertex corners of triangle (U,V,R,G,B,etc are [0..1])
00333                 int Top,                                                                        // Index into pVertices for 'top' (smallest y) vertex 
00334                 int Bottom,                                                                     // Index into pVertices for 'bottom' (greatest y) vertex
00335                 int IsLeftEdge);                                                        // Flag:  is this on the left side of the triangle
00336                                                                                                         //   only x is computed for the right side
00337 
00338 #ifdef __cplusplus
00339 }
00340 #endif
00341 
00342 
00343 
00344 #endif