source: golgotha/src/i4/poly/polydraw.hh @ 608

Last change on this file since 608 was 80, checked in by Sam Hocevar, 15 years ago
  • Adding the Golgotha source code. Not sure what's going to be interesting in there, but since it's all public domain, there's certainly stuff to pick up.
File size: 24.3 KB
Line 
1/********************************************************************** <BR>
2  This file is part of Crack dot Com's free source code release of
3  Golgotha. <a href="http://www.crack.com/golgotha_release"> <BR> for
4  information about compiling & licensing issues visit this URL</a>
5  <PRE> If that doesn't help, contact Jonathan Clark at
6  golgotha_source@usa.net (Subject should have "GOLG" in it)
7***********************************************************************/
8
9#include "poly/poly.hh"
10/*
11
12  Ussage notes :
13   
14g1_poly_draw is a template function for drawing a polygon. You pass in
15a class which has the needed components not defined here depending on
16how these components are defined you can get the different poly drawing
17behavior.  Here are a few :
18
19solid color, gouraud shaded, colored shading, texture mapped, z buffering
20
21g1_poly_draw assumes vertices are already clipped and projected
22
23functions need int class_with_needed_functions (modified for asm)
24*/
25
26enum
27{
28  I4_DO_W=1,                 // do you want w value for each pixel write? (1/z)
29  I4_DO_ST=2,                // do you want texture coordinates?
30  I4_DO_WHITE_LIGHT=4,
31  I4_DO_COLOR_LIGHT=8,
32  I4_DO_PERSPECTIVE=16,
33  I4_FAVOR_LARGE_POLYS=32,    // unroll loops
34  I4_DO_ALPHA=64
35};
36       
37
38/*
39
40a class_with_needed_functions should have a subclass called screen_pointer with the
41following members
42
43move_to(int x, int y);
44+=
45next_line()
46write(int s, int t, int w, float r, float g, float b);
47
48*/
49
50//step modifiers are only needed for values interpolated
51//over Z.  Typically vertex light values and alpha are not.
52template <class class_with_needed_functions>
53class i4_poly_draw_gradient_class
54{
55  w32 order[i4_polygon_class::V_BUF_SIZE];
56  sw32 top, bot, cw, ccw, y_count;
57  i4_float aOneOverZ[i4_polygon_class::V_BUF_SIZE],
58    aUOverZ[i4_polygon_class::V_BUF_SIZE],
59    aVOverZ[i4_polygon_class::V_BUF_SIZE];
60  typedef sw32 fixed28_4;
61  fixed28_4 fixedX[i4_polygon_class::V_BUF_SIZE];
62  fixed28_4 fixedY[i4_polygon_class::V_BUF_SIZE];
63
64  struct edge
65  { //edge stepping info
66    sw32 X, XStep, Numerator, Denominator;          //DDA info
67    sw32 ErrorTerm, Y, Height;                      //current y and vertical count
68    i4_float r,g,b,a, rs,bs,gs,as;                  //color and alpha
69    i4_float OneOverZ, OneOverZStep, OneOverZStepExtra;  //edge 1/z
70    i4_float UOverZ, UOverZStep, UOverZStepExtra;    //edge u/z
71    i4_float VOverZ, VOverZStep, VOverZStepExtra;    //edge v/z
72    void step(class_with_needed_functions &c)
73    {
74      X+=XStep;  Y++;  Height--;
75      if(c.feature(I4_DO_ST))
76      {
77        UOverZ+=UOverZStep;
78        VOverZ+=VOverZStep;
79      }
80      OneOverZ += OneOverZStep;
81      if(c.feature(I4_DO_WHITE_LIGHT)) r+=rs;
82      else if(c.feature(I4_DO_COLOR_LIGHT))
83      {
84        r+=rs;  g+=gs;  b+=bs;
85      }
86      if(c.feature(I4_DO_ALPHA)) a+=as;
87
88      ErrorTerm+=Numerator;
89      if(ErrorTerm >= Denominator)
90      {
91        X++;
92        ErrorTerm-=Denominator;
93        OneOverZ+=OneOverZStepExtra;
94        if(c.feature(I4_DO_ST))
95        {
96          UOverZ+=UOverZStepExtra;
97          VOverZ+=VOverZStepExtra;
98        }
99      }
100    }
101  } left, right;
102
103  struct gradients
104  { //polygon gradients
105    i4_float dOneOverZdX, dOneOverZdX8;             //normal and scaled 1/z step in polygon x
106    i4_float dOneOverZdY;                           //1/z step in polygon y
107    i4_float dUOverZdX, dUOverZdX8, dUOverZdY;      //normal and scaled u/z step
108    i4_float dVOverZdX, dVOverZdX8, dVOverZdY;      //normal and scaled v/z step
109    sw32 dUdXModifier, dVdXModifier;                //fixed 16.16 fixup
110  } grads;
111
112  //this stuff doesn't look too fast...
113  fixed28_4 FloatToFixed28_4(i4_float Value) { return i4_f_to_i(Value * 16.f); }
114  i4_float Fixed28_4ToFloat(fixed28_4 Value) { return Value / 16.0; }
115  fixed28_4 Fixed28_4Mul(fixed28_4 A, fixed28_4 B) { return (A * B) / 16; }
116
117  fixed28_4 Ceil28_4(fixed28_4 Value)
118  {
119    sw32 ReturnValue;
120    sw32 Numerator = Value - 1 + 16;
121    if(Numerator >= 0) ReturnValue = Numerator/16;
122    else
123    { // deal with negative numerators correctly
124      ReturnValue = -((-Numerator)/16);
125      ReturnValue -= ((-Numerator) % 16) ? 1 : 0;
126    }
127    return ReturnValue;
128  }
129
130  void FloorDivMod(sw32 Numerator, sw32 Denominator, sw32 &Floor, sw32 &Mod)
131  {
132    I4_ASSERT(Denominator > 0, "FloorDivMod d<=0");
133    if(Numerator >= 0)
134    { // positive case, C is okay
135      Floor = Numerator / Denominator;
136      Mod = Numerator % Denominator;
137    }
138    else
139    { // Numerator is negative, do the right thing
140      Floor = -((-Numerator) / Denominator);
141      Mod = (-Numerator) % Denominator;
142      if(Mod)
143      { // there is a remainder
144        Floor--;
145        Mod = Denominator - Mod;
146      }
147    }
148  }
149
150  void sort(i4_polygon_class &poly)
151  {
152    int i, swap, mod;
153
154    for (i=0 ; i<poly.t_verts; i++) order[i]=i;
155
156    /* bubble sort the draworder corners */
157    for (mod=1; mod;)
158    {
159      mod = 0;
160      for (i=0 ; i<poly.t_verts-1 ; i++)
161      {
162        if (poly.vert[order[i]].py > poly.vert[order[i+1]].py)
163        {
164          swap = order[i];
165          order[i] = order[i+1];
166          order[i+1] = swap;
167          mod = 1;
168        }
169      }
170    }
171  }
172 
173  sw32 FloatToFixed16_16(float Value) { return (sw32)(Value * 65536); }
174  int next_cw(int i, int t)
175  {
176    i--;
177    if (i<0)
178      return t-1;
179    else return i;     
180  }
181
182  int next_ccw(int i, int t)
183  {
184    i++;
185    if (i==t)
186      return 0;
187    else return i;
188  }
189
190  void rasterize_parallelogram(i4_polygon_class &poly, class_with_needed_functions &c)
191  {
192    int p_starty = Ceil28_4(fixedY[top]);
193    int ycount = y_count;
194
195    enum { f_shift=16 };
196    typename class_with_needed_functions::screen_pointer line_on, pixel_on;
197    line_on.move_to(0, p_starty, c);
198   
199    while (ycount--)
200    {
201      pixel_on=line_on;
202      pixel_on.add(left.X, c);
203      if(right.X-left.X>0)
204        draw_scanline_default(c, &pixel_on);
205      left.step(c);
206      right.step(c);
207      line_on.next_line(c);
208    }
209  }
210
211  void setup_edge(i4_polygon_class &poly, struct edge &edge, int end, class_with_needed_functions &c)
212  { 
213    i4_vertex_class *top_v=poly.vert+top;
214    i4_vertex_class *end_v=poly.vert+end;
215
216    edge.Y=Ceil28_4(fixedY[top]);
217    sw32 YEnd=Ceil28_4(fixedY[end]);
218    edge.Height=YEnd - edge.Y;
219//    i4_float yd=(edge.Height>0)? 1.0/(i4_float)edge.Height : 1.0;
220
221    if(edge.Height > 0)
222    {
223      i4_float yd=1.0/(i4_float)edge.Height;
224      sw32 dN=fixedY[end] - fixedY[top];
225      sw32 dM=fixedX[end] - fixedX[top];
226
227      sw32 InitialNumerator = dM*16*edge.Y - dM*fixedY[top] +
228        dN*fixedX[top] - 1 + dN*16;
229
230      FloorDivMod(InitialNumerator,dN*16,edge.X,edge.ErrorTerm);
231      FloorDivMod(dM*16,dN*16,edge.XStep,edge.Numerator);
232      edge.Denominator = dN*16;
233
234      i4_float YPrestep=Fixed28_4ToFloat(edge.Y*16 - fixedY[top]);
235      i4_float XPrestep=Fixed28_4ToFloat(edge.X*16 - fixedX[top]);
236
237      edge.OneOverZ=aOneOverZ[top] + YPrestep * grads.dOneOverZdY
238        + XPrestep * grads.dOneOverZdX;
239      edge.OneOverZStep=edge.XStep * grads.dOneOverZdX + grads.dOneOverZdY;
240      edge.OneOverZStepExtra=grads.dOneOverZdX;
241
242      if(c.feature(I4_DO_ST))
243      {
244        edge.UOverZ=aUOverZ[top] + YPrestep * grads.dUOverZdY
245          + XPrestep * grads.dUOverZdX;
246        edge.UOverZStep=edge.XStep * grads.dUOverZdX + grads.dUOverZdY;
247        edge.UOverZStepExtra=grads.dUOverZdX;
248
249        edge.VOverZ = aVOverZ[top] + YPrestep * grads.dVOverZdY
250          + XPrestep * grads.dVOverZdX;
251        edge.VOverZStep=edge.XStep * grads.dVOverZdX + grads.dVOverZdY;
252        edge.VOverZStepExtra=grads.dVOverZdX;
253      }
254      if(c.feature(I4_DO_WHITE_LIGHT))
255      {
256        edge.r=top_v->r;
257        edge.rs=(end_v->r - top_v->r) * yd;
258      }
259      else if (c.feature(I4_DO_COLOR_LIGHT))
260      {
261        edge.r=top_v->r;
262        edge.rs=(end_v->r - top_v->r) * yd;
263
264        edge.g=top_v->g;
265        edge.gs=(end_v->g - top_v->g) * yd;
266
267        edge.b=top_v->b;
268        edge.bs=(end_v->b - top_v->b) * yd;
269      }
270      if (c.feature(I4_DO_ALPHA))
271      {
272        edge.a=top_v->a;
273        edge.as=(end_v->a - top_v->a) * yd;
274      }
275    }
276  }
277
278public:
279
280  i4_poly_draw_gradient_class(class_with_needed_functions &c,
281                     i4_polygon_class &poly)
282  {
283    i4_float X1Y0=(poly.vert[1].px - poly.vert[2].px)*(poly.vert[0].py - poly.vert[2].py);
284    i4_float X0Y1=(poly.vert[0].px - poly.vert[2].px)*(poly.vert[1].py - poly.vert[2].py);
285
286    i4_float OneOverdX=1.0/(X1Y0 - X0Y1);
287    i4_float OneOverdY=-OneOverdX;
288
289    int i;
290
291    for(i=0;i<poly.t_verts;i++)
292    {
293      i4_float const OneOverZ = poly.vert[i].w;
294      aOneOverZ[i]=OneOverZ;
295      if(c.feature(I4_DO_ST))
296      {
297        aUOverZ[i]=poly.vert[i].s * OneOverZ;
298        aVOverZ[i]=poly.vert[i].t * OneOverZ;
299      }
300      fixedX[i]=FloatToFixed28_4(poly.vert[i].px);
301      fixedY[i]=FloatToFixed28_4(poly.vert[i].py);
302    }
303
304    grads.dOneOverZdX=OneOverdX*(((aOneOverZ[1] - aOneOverZ[2]) *
305      (poly.vert[0].py - poly.vert[2].py)) -
306      ((aOneOverZ[0] - aOneOverZ[2]) * (poly.vert[1].py - poly.vert[2].py)));
307
308    grads.dOneOverZdY=OneOverdY*(((aOneOverZ[1] - aOneOverZ[2]) *
309      (poly.vert[0].px - poly.vert[2].px)) -
310      ((aOneOverZ[0] - aOneOverZ[2]) * (poly.vert[1].px - poly.vert[2].px)));
311    grads.dOneOverZdX8=grads.dOneOverZdX*8.0;
312
313    if(c.feature(I4_DO_ST))
314    {
315      grads.dUOverZdX=OneOverdX*(((aUOverZ[1] - aUOverZ[2])*
316        (poly.vert[0].py - poly.vert[2].py))-((aUOverZ[0] - aUOverZ[2])*
317        (poly.vert[1].py - poly.vert[2].py)));
318
319      grads.dUOverZdY=OneOverdY*(((aUOverZ[1] - aUOverZ[2]) *
320        (poly.vert[0].px - poly.vert[2].px))-((aUOverZ[0] - aUOverZ[2])*
321        (poly.vert[1].px - poly.vert[2].px)));
322
323      grads.dVOverZdX=OneOverdX*(((aVOverZ[1] - aVOverZ[2]) *
324        (poly.vert[0].py - poly.vert[2].py))-((aVOverZ[0] - aVOverZ[2])*
325        (poly.vert[1].py - poly.vert[2].py)));
326
327      grads.dVOverZdY=OneOverdY*(((aVOverZ[1] - aVOverZ[2]) *
328        (poly.vert[0].px - poly.vert[2].px))-((aVOverZ[0] - aVOverZ[2])*
329        (poly.vert[1].px - poly.vert[2].px)));
330
331      grads.dUOverZdX8=grads.dUOverZdX*8.0;
332      grads.dVOverZdX8=grads.dVOverZdX*8.0;
333    }
334
335    w32 const Half = 0x8000;
336    w32 const PosModifier = Half;
337    w32 const NegModifier = Half - 1;
338
339    i4_float dUdXIndicator=grads.dUOverZdX*aOneOverZ[0]-aUOverZ[0]*grads.dOneOverZdX;
340    if(dUdXIndicator > 0)
341      grads.dUdXModifier = PosModifier;
342    else if(dUdXIndicator < 0)
343      grads.dUdXModifier = NegModifier;
344    else
345    {
346      // dUdX == 0
347      i4_float dUdYIndicator=grads.dUOverZdY*aOneOverZ[0]-aUOverZ[0]*grads.dOneOverZdY;
348      if(dUdYIndicator >= 0)
349        grads.dUdXModifier = PosModifier;
350      else
351        grads.dUdXModifier = NegModifier;
352    }
353    i4_float dVdXIndicator=grads.dVOverZdX*aOneOverZ[0]-aVOverZ[0]*grads.dOneOverZdX;
354    if(dVdXIndicator > 0)
355      grads.dVdXModifier = PosModifier;
356    else if(dVdXIndicator < 0)
357      grads.dVdXModifier = NegModifier;
358    else
359    {
360      // dVdX == 0
361      float dVdYIndicator=grads.dVOverZdY*aOneOverZ[0]-aVOverZ[0]*grads.dOneOverZdY;
362      if(dVdYIndicator >= 0)
363        grads.dVdXModifier = PosModifier;
364      else
365        grads.dVdXModifier = NegModifier;
366    }
367    // sort the vertices by y   
368    sort(poly);
369
370    top=order[0];
371    bot=order[1];
372
373    cw = next_cw(top, poly.t_verts);
374    ccw = next_ccw(top, poly.t_verts);
375
376    setup_edge(poly, left, ccw, c);
377    setup_edge(poly, right, cw, c);
378
379    y_count =Ceil28_4(fixedY[bot]) - Ceil28_4(fixedY[top]);
380    rasterize_parallelogram(poly, c);
381
382    for (i=1; i<poly.t_verts-1; i++)
383    {
384      top=order[i];
385      bot=order[i+1];
386
387      y_count =Ceil28_4(fixedY[bot]) - Ceil28_4(fixedY[top]);
388
389      if (top==ccw)
390      {
391        ccw=next_ccw(top, poly.t_verts);
392        setup_edge(poly, left, ccw, c);
393      }
394      else if (top == cw)
395      {
396        cw=next_cw(top, poly.t_verts);
397        setup_edge(poly, right, cw, c);
398      }
399      rasterize_parallelogram(poly, c);
400    }
401  } 
402
403  void draw_scanline_default(class_with_needed_functions &c, typename class_with_needed_functions::screen_pointer * pon)
404  {
405    int XStart=left.X;
406    int Width=right.X-XStart;
407
408    float wd=1.0/(float)Width;
409    float r,g,b,a,w, rstep,gstep,bstep,astep,wstep;
410
411    if(c.feature(I4_DO_WHITE_LIGHT))
412    {
413      r=left.r;
414      rstep=(right.r-left.r)*wd;
415    }
416    else if(c.feature(I4_DO_COLOR_LIGHT))
417    {
418      rstep=(right.r-left.r)*wd;
419      gstep=(right.g-left.g)*wd;
420      bstep=(right.b-left.b)*wd;
421    }
422    if(c.feature(I4_DO_ALPHA)) astep=(right.a-left.a)*wd;
423    if(c.feature(I4_DO_W))
424    {
425      w=left.OneOverZ;
426      wstep=grads.dOneOverZdX;
427    }
428
429    float OneOverZLeft = left.OneOverZ;
430    float UOverZLeft = left.UOverZ;
431    float VOverZLeft = left.VOverZ;
432
433    float dOneOverZdXAff = grads.dOneOverZdX8;
434    float dUOverZdXAff = grads.dUOverZdX8;
435    float dVOverZdXAff = grads.dVOverZdX8;
436
437    float OneOverZRight = OneOverZLeft + dOneOverZdXAff;
438    float UOverZRight, VOverZRight;
439    if(c.feature(I4_DO_ST))
440    {
441      UOverZRight = UOverZLeft + dUOverZdXAff;
442      VOverZRight = VOverZLeft + dVOverZdXAff;
443    }
444
445    float ZLeft = 1/OneOverZLeft, ULeft, VLeft, URight, VRight, ZRight;
446    sw32 U, V, DeltaU, DeltaV;
447    if(c.feature(I4_DO_ST))
448    {
449      ULeft = ZLeft * UOverZLeft;
450      VLeft = ZLeft * VOverZLeft;
451    }
452
453    if(Width > 0)
454    {
455      int Subdivisions = Width>>3;
456      int WidthModLength = Width % 8;
457
458      if(!WidthModLength)
459      {
460        Subdivisions--;
461        WidthModLength = 8;
462      }
463
464      while(Subdivisions-- > 0)
465      {
466        ZRight = 1/OneOverZRight;
467        if(c.feature(I4_DO_ST))
468        {
469          URight = ZRight * UOverZRight;
470          VRight = ZRight * VOverZRight;
471
472          U = FloatToFixed16_16(ULeft) + grads.dUdXModifier;
473          V = FloatToFixed16_16(VLeft) + grads.dVdXModifier;
474          DeltaU = FloatToFixed16_16(URight - ULeft) / 8;
475          DeltaV = FloatToFixed16_16(VRight - VLeft) / 8;
476        }
477        for(int Counter = 0;Counter < 8;Counter++)
478        {
479          sw32 UInt, VInt;
480          if(c.feature(I4_DO_ST))
481          {
482            UInt = U>>16;
483            VInt = V>>16;
484          }
485          pon->write(UInt, VInt, w, r, g, b, a, c);
486          pon->add(1,c);
487
488          if(c.feature(I4_DO_ST))
489          {
490            U += DeltaU;
491            V += DeltaV;
492          }
493          if(c.feature(I4_DO_WHITE_LIGHT)) r += rstep;
494          else if(c.feature(I4_DO_COLOR_LIGHT))
495          {
496            r+=rstep;  g+=gstep;  b+=bstep;
497          }
498          if(c.feature(I4_DO_ALPHA)) a+=astep;
499        }
500        ZLeft = ZRight;
501        ULeft = URight;
502        VLeft = VRight;
503
504        OneOverZRight += dOneOverZdXAff;
505        if(c.feature(I4_DO_ST))
506        {
507          UOverZRight += dUOverZdXAff;
508          VOverZRight += dVOverZdXAff;
509        }
510      }
511
512      if(WidthModLength)
513      {
514        ZRight = 1.0/(right.OneOverZ - grads.dOneOverZdX);
515        if(c.feature(I4_DO_ST))
516        {
517          URight = ZRight * (right.UOverZ - grads.dUOverZdX);
518          VRight = ZRight * (right.VOverZ - grads.dVOverZdX);
519
520          U = FloatToFixed16_16(ULeft) + grads.dUdXModifier;
521          V = FloatToFixed16_16(VLeft) + grads.dVdXModifier;
522        }
523        if(--WidthModLength)
524        {
525          // guard against div-by-0 for 1 pixel lines
526          if(c.feature(I4_DO_ST))
527          {
528            DeltaU = FloatToFixed16_16(URight - ULeft) / WidthModLength;
529            DeltaV = FloatToFixed16_16(VRight - VLeft) / WidthModLength;
530          }
531        }
532
533        for(int Counter = 0;Counter <= WidthModLength;Counter++)
534        {
535          sw32 UInt, VInt;
536          if(c.feature(I4_DO_ST))
537          {
538            UInt = U>>16;
539            VInt = V>>16;
540          }
541          pon->write(UInt, VInt, w, r, g, b, a, c);
542          pon->add(1,c);
543
544          if(c.feature(I4_DO_ST))
545          {
546            U += DeltaU;
547            V += DeltaV;
548          }
549          if(c.feature(I4_DO_WHITE_LIGHT)) r += rstep;
550          else if(c.feature(I4_DO_COLOR_LIGHT))
551          {
552            r+=rstep;  g+=gstep;  b+=bstep;
553          }
554          if(c.feature(I4_DO_ALPHA)) a+=astep;
555        }
556      }
557    }
558  }
559};
560
561//for polygons that need no gradient calculated
562template <class class_with_needed_functions>
563class i4_poly_draw_class
564{
565  w32 order[i4_polygon_class::V_BUF_SIZE];
566  sw32 top, bot, cw, ccw, y_count;
567  i4_float aOneOverZ[i4_polygon_class::V_BUF_SIZE];
568
569  typedef sw32 fixed28_4;
570  fixed28_4 fixedX[i4_polygon_class::V_BUF_SIZE];
571  fixed28_4 fixedY[i4_polygon_class::V_BUF_SIZE];
572
573  struct edge
574  { //edge stepping info
575    sw32 X, XStep, Numerator, Denominator;          //DDA info
576    sw32 ErrorTerm, Y, Height;                      //current y and vertical count
577    i4_float r,g,b,a, rs,bs,gs,as;                  //color and alpha
578    i4_float w,s,t, ws,ss,ts;                       //texture and w
579    void step(class_with_needed_functions &c)
580    {
581      X+=XStep;  Y++;  Height--;
582      if(c.feature(I4_DO_ST))
583      {
584        s+=ss;  t+=ts;
585      }
586      if(c.feature(I4_DO_W)) w+=ws;
587      if(c.feature(I4_DO_WHITE_LIGHT)) r+=rs;
588      else if(c.feature(I4_DO_COLOR_LIGHT))
589      {
590        r+=rs;  g+=gs;  b+=bs;
591      }
592      if(c.feature(I4_DO_ALPHA)) a += as;
593
594      ErrorTerm+=Numerator;
595      if(ErrorTerm >= Denominator)
596      {
597        X++;
598        ErrorTerm-=Denominator;
599      }
600    }
601  } left, right;
602
603  //this stuff doesn't look too fast...
604  fixed28_4 FloatToFixed28_4(i4_float Value) { return (fixed28_4)(Value * 16); }
605  i4_float Fixed28_4ToFloat(fixed28_4 Value) { return Value / 16.0; }
606  fixed28_4 Fixed28_4Mul(fixed28_4 A, fixed28_4 B) { return (A * B) / 16; }
607
608  fixed28_4 Ceil28_4(fixed28_4 Value)
609  {
610    sw32 ReturnValue;
611    sw32 Numerator = Value - 1 + 16;
612    if(Numerator >= 0) ReturnValue = Numerator/16;
613    else
614    { // deal with negative numerators correctly
615      ReturnValue = -((-Numerator)/16);
616      ReturnValue -= ((-Numerator) % 16) ? 1 : 0;
617    }
618    return ReturnValue;
619  }
620
621  void FloorDivMod(sw32 Numerator, sw32 Denominator, sw32 &Floor, sw32 &Mod)
622  {
623    I4_ASSERT(Denominator > 0, "FloorDivMod d<=0");
624    if(Numerator >= 0)
625    { // positive case, C is okay
626      Floor = Numerator / Denominator;
627      Mod = Numerator % Denominator;
628    }
629    else
630    { // Numerator is negative, do the right thing
631      Floor = -((-Numerator) / Denominator);
632      Mod = (-Numerator) % Denominator;
633      if(Mod)
634      { // there is a remainder
635        Floor--;
636        Mod = Denominator - Mod;
637      }
638    }
639  }
640
641  void sort(i4_polygon_class &poly)
642  {
643    int i, swap, mod;
644
645    for (i=0 ; i<poly.t_verts; i++) order[i]=i;
646
647    /* bubble sort the draworder corners */
648    for (mod=1; mod;)
649    {
650      mod = 0;
651      for (i=0 ; i<poly.t_verts-1 ; i++)
652      {
653        if (poly.vert[order[i]].py > poly.vert[order[i+1]].py)
654        {
655          swap = order[i];
656          order[i] = order[i+1];
657          order[i+1] = swap;
658          mod = 1;
659        }
660      }
661    }
662  }
663
664  int next_cw(int i, int t)
665  {
666    i--;
667    if (i<0)
668      return t-1;
669    else return i;     
670  }
671
672  int next_ccw(int i, int t)
673  {
674    i++;
675    if (i==t)
676      return 0;
677    else return i;
678  }
679
680  void rasterize_parallelogram(i4_polygon_class &poly, class_with_needed_functions &c)
681  {
682//    int p_starty = (int)poly.vert[top].py;
683    int p_starty = left.Y;
684    int ycount = y_count;
685
686    enum { f_shift=16 };
687    typename class_with_needed_functions::screen_pointer line_on, pixel_on;
688    line_on.move_to(0, p_starty, c);
689   
690    while (ycount--)
691    {
692      pixel_on=line_on;
693      pixel_on.add(left.X, c);
694      if(right.X-left.X>0)
695        draw_scanline_default(c, &pixel_on);
696      left.step(c);
697      right.step(c);
698      line_on.next_line(c);
699    }
700  }
701
702  void setup_edge(i4_polygon_class &poly, struct edge &edge, int end, class_with_needed_functions &c)
703  { 
704    i4_vertex_class *top_v=poly.vert+top;
705    i4_vertex_class *end_v=poly.vert+end;
706
707    edge.Y=Ceil28_4(fixedY[top]);
708    sw32 YEnd=Ceil28_4(fixedY[end]);
709    edge.Height=YEnd - edge.Y;
710
711    if(edge.Height > 0)
712    {
713      i4_float yd=1.0/(i4_float)edge.Height;
714
715      sw32 dN=fixedY[end] - fixedY[top];
716      sw32 dM=fixedX[end] - fixedX[top];
717
718      sw32 InitialNumerator = dM*16*edge.Y - dM*fixedY[top] +
719        dN*fixedX[top] - 1 + dN*16;
720
721      FloorDivMod(InitialNumerator,dN*16,edge.X,edge.ErrorTerm);
722      FloorDivMod(dM*16,dN*16,edge.XStep,edge.Numerator);
723      edge.Denominator = dN*16;
724
725      i4_float YPrestep=Fixed28_4ToFloat(edge.Y*16 - fixedY[top]);
726      i4_float XPrestep=Fixed28_4ToFloat(edge.X*16 - fixedX[top]);
727
728      if(c.feature(I4_DO_W))
729      {
730        edge.w=aOneOverZ[top];
731        edge.ws=(aOneOverZ[end]-edge.w)*yd;
732      }
733      if(c.feature(I4_DO_ST))
734      {
735        edge.s=top_v->s;
736        edge.ss=(end_v->s - top_v->s)*yd;
737
738        edge.t=top_v->t;
739        edge.ts=(end_v->t - top_v->t)*yd;
740      }
741      if(c.feature(I4_DO_WHITE_LIGHT))
742      {
743        edge.r=top_v->r;
744        edge.rs=(end_v->r - top_v->r) * yd;
745      }
746      else if (c.feature(I4_DO_COLOR_LIGHT))
747      {
748        edge.r=top_v->r;
749        edge.rs=(end_v->r - top_v->r) * yd;
750
751        edge.g=top_v->g;
752        edge.gs=(end_v->g - top_v->g) * yd;
753
754        edge.b=top_v->b;
755        edge.bs=(end_v->b - top_v->b) * yd;
756      }
757      if (c.feature(I4_DO_ALPHA))
758      {
759        edge.a=top_v->a;
760        edge.as=(end_v->a - top_v->a) * yd;
761      }
762    }
763  }
764
765public:
766
767  i4_poly_draw_class(class_with_needed_functions &c,
768                     i4_polygon_class &poly)
769  {
770    int i;
771
772    for(i=0;i<poly.t_verts;i++)
773    {
774      if(c.feature(I4_DO_W)) aOneOverZ[i]=poly.vert[i].w;
775      fixedX[i]=i4_f_to_i(poly.vert[i].px * 16.f);//FloatToFixed28_4(poly.vert[i].px);
776      fixedY[i]=i4_f_to_i(poly.vert[i].py * 16.f);//FloatToFixed28_4(poly.vert[i].py);
777    }
778
779    // sort the vertices by y   
780    sort(poly);
781
782    top=order[0];
783    bot=order[1];
784
785    cw = next_cw(top, poly.t_verts);
786    ccw = next_ccw(top, poly.t_verts);
787
788    setup_edge(poly, left, ccw, c);
789    setup_edge(poly, right, cw, c);
790
791    y_count =Ceil28_4(fixedY[bot]) - Ceil28_4(fixedY[top]);
792    rasterize_parallelogram(poly, c);
793
794    for (i=1; i<poly.t_verts-1; i++)
795    {
796      top=order[i];
797      bot=order[i+1];
798
799      y_count =Ceil28_4(fixedY[bot]) - Ceil28_4(fixedY[top]);
800
801      if (top==ccw)
802      {
803        ccw=next_ccw(top, poly.t_verts);
804        setup_edge(poly, left, ccw, c);
805      }
806      else if (top == cw)
807      {
808        cw=next_cw(top, poly.t_verts);
809        setup_edge(poly, right, cw, c);
810      }
811      rasterize_parallelogram(poly, c);
812    }
813  }
814
815  void draw_scanline_default(class_with_needed_functions &c, typename class_with_needed_functions::screen_pointer * pon)
816  {
817    int XStart=left.X;
818    int Width=right.X-XStart;
819
820    float wd=1.0/(float)Width;
821    float r,g,b,a,w,s,t, rstep,gstep,bstep,astep,wstep,sstep,tstep;
822
823    if(c.feature(I4_DO_WHITE_LIGHT))
824    {
825      r=left.r;
826      rstep=(right.r-left.r)*wd;
827    }
828    else if(c.feature(I4_DO_COLOR_LIGHT))
829    {
830      r=left.r;  b=left.b;  g=left.g;
831      rstep=(right.r-left.r)*wd;
832      gstep=(right.g-left.g)*wd;
833      bstep=(right.b-left.b)*wd;
834    }
835    if(c.feature(I4_DO_ALPHA))
836    {
837      a=left.a;
838      astep=(right.a-left.a)*wd;
839    }
840    if(c.feature(I4_DO_W))
841    {
842      w=left.w;
843      wstep=(right.w-left.w)*wd;
844    }
845    if(c.feature(I4_DO_ST))
846    {
847      s=left.s;
848      sstep=(right.s-s)*wd;
849      t=left.t;
850      tstep=(right.t-t)*wd;
851    }
852    if(Width > 0)
853    {
854      while(Width--)
855      {
856        pon->write((int)s, (int)t, w, r, g, b, a, c);
857        pon->add(1,c);
858
859        if(c.feature(I4_DO_ST))
860        {
861          s+=sstep;
862          t+=tstep;
863        }
864
865        if(c.feature(I4_DO_W)) w+=wstep;
866        if(c.feature(I4_DO_WHITE_LIGHT)) r+=rstep;
867        else if(c.feature(I4_DO_COLOR_LIGHT))
868        {
869          r+=rstep;  g+=gstep;  b+=bstep;
870        }
871        if(c.feature(I4_DO_ALPHA)) a+=astep;
872      }
873    }
874  }
875};
Note: See TracBrowser for help on using the repository browser.