G3D/Engine/Drivers/D3D8Drv/GSPAN.CPP

   1 /****************************************************************************************/\r
   2 /*  GSpan.cpp                                                                           */\r
   3 /*                                                                                      */\r
   4 /*  Author: John Pollard                                                                */\r
   5 /*  Description: Front to back span code                                                */\r
   6 /*                                                                                      */\r
   7 /*  The contents of this file are subject to the Genesis3D Public License               */\r
   8 /*  Version 1.01 (the "License"); you may not use this file except in                   */\r
   9 /*  compliance with the License. You may obtain a copy of the License at                */\r
  10 /*  http://www.genesis3d.com                                                            */\r
  11 /*                                                                                      */\r
  12 /*  Software distributed under the License is distributed on an "AS IS"                 */\r
  13 /*  basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See                */\r
  14 /*  the License for the specific language governing rights and limitations              */\r
  15 /*  under the License.                                                                  */\r
  16 /*                                                                                      */\r
  17 /*  The Original Code is Genesis3D, released March 25, 1999.                            */\r
  18 /*Genesis3D Version 1.1 released November 15, 1999                                      */\r
  19 /*  Copyright (C) 1999 WildTangent, Inc. All Rights Reserved                            */\r
  20 /*                                                                                      */\r
  21 /****************************************************************************************/\r
  22 #include <Windows.h>\r
  23 \r
  24 #include "D3DDrv.h"\r
  25 #include "GSpan.h"\r
  26 \r
  27 \r
  28 \r
  29 \r
  30 \r
  31 \r
  32 \r
  33 SPAN            SpanLines[MAX_SPAN_LINES];\r
  34 \r
  35 SPAN_MINMAX     SMinMax[MAX_SPAN_LINES];                        // Linked list of spans for each scanline...\r
  36 SLIST           ScanHash[MAX_SPANS];                            // hash table for SList\r
  37 \r
  38 BOOL            PolyVisible = FALSE;\r
  39 \r
  40 int32                   NumWorldPixels = 0;\r
  41 int32                   NumSpans = 0;\r
  42 int32                   NumSpanPixels[MAX_SPAN_LINES];\r
  43 int32                   PolysRendered = 0;\r
  44 \r
  45 int32                   CurrentSList = 0;\r
  46 \r
  47 const int32 CEIL_FRACT = ( ( 1 << 16)-1);\r
  48 void DRIVERCC EdgeOutNoUV (int32 x1, int32 y1, int32 x2, int32 y2)\r
  49 {\r
  50         int32           Ctmp;\r
  51         int32           y;\r
  52         int32           x,m;\r
  53 \r
  54         int32           ydelta;\r
  55         int32           Dir;\r
  56         int32           Cx1, Cx2, Cy1, Cy2;\r
  57         SPAN    *pSpans;\r
  58 \r
  59         Cx1 = x1;\r
  60         Cx2 = x2;\r
  61         Cy1 = y1;\r
  62         Cy2 = y2;\r
  63 \r
  64         if (Cy2 != Cy1)                                                         // This isn't a horizontal line \r
  65         {                                                               \r
  66                 Dir =0;                                                                 // Left side\r
  67 \r
  68                 if (Cy2 < Cy1)                                                  // Make sure y2 is greater than y1\r
  69                 {\r
  70                         Dir =1;                                                         // Right side\r
  71 \r
  72                         Ctmp = Cx1;\r
  73                         Cx1 = Cx2;\r
  74                         Cx2 = Ctmp;\r
  75 \r
  76                         Ctmp = Cy1;\r
  77                         Cy1 = Cy2;\r
  78                         Cy2 = Ctmp;\r
  79 \r
  80                 }\r
  81 \r
  82                 ydelta = (Cy2 - Cy1);\r
  83 \r
  84                 x = (Cx1 << 16) + CEIL_FRACT;            // Allign on int amounts\r
  85                 m = (((Cx2 - Cx1))<<16) / ydelta;        // How much to increase x each iteration\r
  86 \r
  87                 pSpans = &SpanLines[Cy1];\r
  88 \r
  89                 if (!Dir)\r
  90                 {\r
  91                         for (y = Cy1; y <= Cy2; y++, pSpans++)       \r
  92                         {\r
  93                                 pSpans->x1 = (x>>16);\r
  94                                 x += m;                                                         // Add our constant to x\r
  95                         }\r
  96                 }\r
  97                 else\r
  98                 {\r
  99                         for (y = Cy1; y <= Cy2; y++, pSpans++)       \r
 100                         {\r
 101                                 pSpans->x2 = (x>>16);\r
 102                                 x += m;                                                         // Add our constant to x\r
 103                         }\r
 104                 }   \r
 105         } \r
 106 }\r
 107 \r
 108 void DRIVERCC AddSpanNoUV(int32 x1, int32 x2, int32 y)\r
 109 {\r
 110     int32               i, xx2;\r
 111     SLIST               *LineStart;\r
 112     SLIST               *Current;\r
 113         SPAN_MINMAX *pSList;\r
 114 \r
 115         if (NumSpanPixels[y] >= ClientWindow.Width) \r
 116                 return;\r
 117 \r
 118     if (x1 > x2)                                                                        // Swap all the coordinates so x1 < x2 \r
 119     {\r
 120                 i = x1; \r
 121                 x1 = x2; \r
 122                 x2 = i;\r
 123     }\r
 124 \r
 125     Current = SMinMax[y].First;\r
 126         \r
 127         LineStart = NULL;\r
 128 \r
 129         pSList = &SMinMax[y];\r
 130 \r
 131         // Check to see if there are spans\r
 132         // in the list yet...\r
 133         if (!pSList->First) \r
 134         {       \r
 135                 pSList->First = NewSList();     \r
 136         pSList->First->Last = NULL;\r
 137         pSList->First->Next = NULL;\r
 138         pSList->First->Min = x1;\r
 139         pSList->First->Max = x2;\r
 140     }\r
 141     else while (Current != NULL)\r
 142     {\r
 143                 if (x1 >= Current->Min && x2 <= Current->Max)\r
 144                         return;                                                         // This line totally hidden...\r
 145 \r
 146                 //if falls before the entire min, max\r
 147                 if (LineStart == NULL) \r
 148                 {\r
 149                         if (Current == pSList->First)\r
 150             if (x2 < Current->Min) \r
 151                         {\r
 152                                 SLIST *NewMinMax = NewSList();\r
 153                 NewMinMax->Next = Current;\r
 154                 NewMinMax->Last = NULL;\r
 155                 Current->Last = NewMinMax;\r
 156                 pSList->First = NewMinMax;\r
 157                 NewMinMax->Min = x1;\r
 158                 NewMinMax->Max = x2;\r
 159                 goto WasNull;\r
 160             }\r
 161             // if falls in the middle (but not touching)\r
 162             if (Current->Next != NULL)\r
 163             if (x1 > Current->Max && x2 < (Current->Next)->Min) \r
 164                         {\r
 165                 SLIST *NewMinMax = NewSList();\r
 166                 NewMinMax->Next = Current->Next;\r
 167                 NewMinMax->Last = Current;\r
 168                 Current->Next->Last = NewMinMax;\r
 169                 Current->Next = NewMinMax;\r
 170                 NewMinMax->Min = x1;\r
 171                 NewMinMax->Max = x2;\r
 172                 goto WasNull;\r
 173             }\r
 174             // if it falls to the right of all spans\r
 175             if (Current->Next == NULL)\r
 176             if (x1 > Current->Max) \r
 177                         {\r
 178                 SLIST *NewMinMax = NewSList();\r
 179                 Current->Next = NewMinMax;\r
 180                 NewMinMax->Next = NULL;\r
 181                 NewMinMax->Last = Current;\r
 182                 NewMinMax->Min = x1;\r
 183                 NewMinMax->Max = x2;\r
 184                 goto WasNull;\r
 185             }\r
 186         }\r
 187                 //if we have already started crossing spans, and we find out\r
 188                 // that we are in front of a span, then we can bail out...\r
 189         if (LineStart != NULL)\r
 190                         if (x2 < Current->Min)\r
 191                                 goto WasNull;\r
 192 \r
 193 \r
 194         // We now know that we have not fallen into any empty holes.\r
 195         // We must now check to see what spans, we've crossed...\r
 196 \r
 197         // if split by a min/max\r
 198         if (x1 < Current->Min && x2 > Current->Max) \r
 199                 {\r
 200                         xx2 = Current->Min-1;\r
 201             Current->Min = x1; \r
 202                         \r
 203                         NumWorldPixels += xx2 - x1 + 1; \r
 204                         NumSpanPixels[y] += xx2 - x1 + 1;\r
 205                         \r
 206                         if (!PolyVisible) \r
 207                         { \r
 208                                 PolysRendered++;\r
 209                                 PolyVisible = 1;\r
 210                         }\r
 211             \r
 212             x1 = Current->Max+1;\r
 213             Current->Max = x2;\r
 214             if (LineStart!=NULL) \r
 215                                 LineStart->Max = x2;\r
 216             else\r
 217                                 LineStart = Current;\r
 218             goto next;\r
 219                 }\r
 220 \r
 221                 if (x1 <= Current->Max && x2 > Current->Max) \r
 222                 {\r
 223             x1 = Current->Max+1;\r
 224             Current->Max = x2;\r
 225             LineStart = Current;\r
 226             goto next;\r
 227                 }\r
 228                 if (x1 < Current->Min && x2 >= Current->Min) \r
 229                 {\r
 230             x2 = Current->Min-1;\r
 231             Current->Min = x1;\r
 232             if (LineStart!=NULL) \r
 233                                 LineStart->Max = Current->Max;\r
 234             goto WasNull;\r
 235         }\r
 236                 next:;\r
 237                 Current = Current->Next;\r
 238     }\r
 239         WasNull:;\r
 240 \r
 241         if (!PolyVisible) \r
 242         { \r
 243                 PolysRendered++;\r
 244                 PolyVisible = 1;\r
 245         }\r
 246 \r
 247         NumWorldPixels += x2 - x1 + 1;\r
 248         NumSpanPixels[y] += x2 - x1 + 1;\r
 249 }       \r
 250 \r
 251 void ResetSList(void)\r
 252 {\r
 253         CurrentSList = 0;\r
 254         NumSpans = 0;\r
 255 }\r
 256 \r
 257 SLIST *NewSList(void)\r
 258 {\r
 259 \r
 260         CurrentSList++;\r
 261         NumSpans++;\r
 262 \r
 263         return &ScanHash[CurrentSList-1];\r
 264 \r
 265         return NULL;\r
 266 }\r
 267 \r
 268 void ResetSpans(int32 Rows)\r
 269 { \r
 270         int32           i;\r
 271 \r
 272         for (i=0; i<Rows; i++) \r
 273         {\r
 274                 SMinMax[i].First = NULL;\r
 275                 NumSpanPixels[i] = 0;\r
 276         }\r
 277         ResetSList();\r
 278         NumWorldPixels = 0;\r
 279 }\r