home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Mac Game Programming Gurus / TricksOfTheMacGameProgrammingGurus.iso / More Source / C⁄C++ / Peter's Final Project / src / scan.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-10  |  37.3 KB  |  1,970 lines  |  [TEXT/KAHL]
  1. /*
  2.  *  Peter's Final Project -- A texture mapping demonstration
  3.  *  © 1995, Peter Mattis
  4.  *
  5.  *  E-mail:
  6.  *  petm@soda.csua.berkeley.edu
  7.  *
  8.  *  Snail-mail:
  9.  *   Peter Mattis
  10.  *   557 Fort Laramie Dr.
  11.  *   Sunnyvale, CA 94087
  12.  *
  13.  *  Avaible from:
  14.  *  http://www.csua.berkeley.edu/~petm/final.html
  15.  *
  16.  *  This program is free software; you can redistribute it and/or modify
  17.  *  it under the terms of the GNU General Public License as published by
  18.  *  the Free Software Foundation; either version 2 of the License, or
  19.  *  (at your option) any later version.
  20.  *
  21.  *  This program is distributed in the hope that it will be useful,
  22.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  23.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  24.  *  GNU General Public License for more details.
  25.  *
  26.  *  You should have received a copy of the GNU General Public License
  27.  *  along with this program; if not, write to the Free Software
  28.  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  29.  */
  30.  
  31. #include <assert.h>
  32. #include <math.h>
  33. #include <stdio.h>
  34.  
  35. #include "fixed.h"
  36. #include "list.h"
  37. #include "sys.stuff.h"
  38. #include "scan.h"
  39. #include "utils.h"
  40.  
  41. /*
  42.  * Defines that affect rendering.
  43.  * Increasing INTENSITY_MULT makes the depth falloff more dramatic.
  44.  * Increasing SHADING_MULT makes the psuedo-Gourad effect less dramatic.
  45.  * Both defines are only used in the texture scan conversion routines.
  46.  */
  47.  
  48. #define INTENSITY_MULT  15
  49. #define SHADE_MULT      50
  50.  
  51. /*
  52.  * Define the number of spans to allocate when growing the span pool.
  53.  */
  54.  
  55. #define SPAN_POOL_CHUNK   30000
  56.  
  57. /*
  58.  * Define the SPAN type.
  59.  * This type is used to keep track of which parts of the frame
  60.  *  have been drawn.
  61.  */
  62.  
  63. typedef struct _SPAN _SPAN, *SPAN;
  64. struct _SPAN {
  65.     short start;
  66.     short end;
  67.     SPAN next;
  68. };
  69.  
  70. /*
  71.  * Define the Z_LINE type.
  72.  * This type is used in texture mapping walls.
  73.  */
  74.  
  75. typedef struct Z_LINE Z_LINE;
  76. struct Z_LINE {
  77.     long u, v;
  78.     long du, dv;
  79.     unsigned char *table;
  80.     BOOLEAN ready;
  81. };
  82.  
  83. /*
  84.  * Declare the private functions.
  85.  */
  86.  
  87. static void scan_calc_texture (VECTOR, VECTOR, VECTOR);
  88. static void scan_texture_points (POINTS);
  89. static void scan_shade_points (POINTS, NUM, NUM, NUM);
  90. static void scan_texture_horizontal8 (long, long);
  91. static void scan_texture_vertical8 (long, long);
  92. static void scan_shade8 (long, long, long);
  93. static void scan_texture_horizontal24 (long, long);
  94. static void scan_texture_vertical24 (long, long);
  95. static void scan_shade24 (long, long, long, long, long);
  96. static POINTS scan_calc_y_extrema (POINTS, long *, long *);
  97. static POINTS scan_calc_x_extrema (POINTS, long *, long *);
  98. static long *scan_calc_edge (long *, long, long, long, long);
  99. static long *scan_calc_color (long *, long, long, long);
  100.  
  101. static void make_span_buffer (void);
  102. static void reset_span_buffer (void);
  103.  
  104. static void make_span_pool (void);
  105. static void grow_span_pool (void);
  106. static void reset_span_pool (void);
  107. static SPAN make_span (short, short);
  108. static short span_trivial_reject (long, long);
  109. static SPAN span_add (long, long, long);
  110. static SPAN span_valid (SPAN, long, long);
  111. static SPAN span_remove (SPAN, long, long);
  112.  
  113. /*
  114.  * Keep local copies of the width and height of the frame.
  115.  */
  116. static long width, height;
  117.  
  118. /*
  119.  * The "span_buffer" contains the spans of filled pixels in the frame.
  120.  * The "span_pool" is a collection of spans that can be allocated.
  121.  */
  122. static SPAN *span_buffer;
  123. static _SPAN *span_pool;
  124.  
  125. /*
  126.  * Need something to keep track of which spans are full.
  127.  */
  128. static BOOLEAN *span_full;
  129.  
  130. /*
  131.  * "span_pool_size" is the size of the span pool.
  132.  * "span_pool_index" is the index of the next span that can be allocated.
  133.  */
  134. static long span_pool_size;
  135. static long span_pool_index;
  136.  
  137. /*
  138.  * The left and right edges of the polygon being drawn.
  139.  * Note: Since polygons are guaranteed to be convex, only 2 edges
  140.  *       can ever exist on a given scanline.
  141.  */
  142. static long *left_edges;
  143. static long *right_edges;
  144.  
  145. /*
  146.  * The left and right colors for usage in Gourad shading.
  147.  */
  148. static long *left_colors;
  149. static long *right_colors;
  150.  
  151. /*
  152.  * A table of intensity values.
  153.  * The table is set up so that the first index is the intensity
  154.  *  and the second index is a color value at that intensity.
  155.  */
  156. static unsigned char **intensity_table;
  157.  
  158. /*
  159.  * The current texture and its size.
  160.  */
  161. static TEXTURE texture;
  162. static long s;
  163.  
  164. /*
  165.  * The vectors defining the current texture mapping.
  166.  */
  167. static VECTOR B, U, V;
  168.  
  169. static long plane_a;
  170. static long plane_b;
  171. static long plane_c;
  172. static long plane_d;
  173.  
  174. /*
  175.  * The "magic" texture mapping values.
  176.  */
  177. static long v1x, v1y, v1z;
  178. static long v2x, v2y, v2z;
  179. static long v3x, v3y, v3z;
  180.  
  181. /*
  182.  * Different increment values.
  183.  */
  184. static long axi, bxi, cxi;
  185. static long ayi, byi, cyi;
  186. static long xi, yi;
  187.  
  188. /*
  189.  * An array of z_lines needed for texture mapping walls.
  190.  */
  191. static Z_LINE *z_lines;
  192.  
  193. /*
  194.  * Initialize the scan converter.
  195.  */
  196.  
  197. void
  198. scan_init ()
  199. {
  200.     short i, j;
  201.  
  202.     /*
  203.      * Get the frame buffer width and height.
  204.      * (Guaranteed not to change).
  205.      */
  206.     width = get_frame_buffer_width ();
  207.     height = get_frame_buffer_height ();
  208.  
  209.     /*
  210.      * Allocate the edge arrays.
  211.      */
  212.     left_edges = (long *) ALLOC (sizeof (long) * height);
  213.     right_edges = (long *) ALLOC (sizeof (long) * height);
  214.  
  215.     /*
  216.      * Allocate the color arrays.
  217.      */
  218.     left_colors = (long *) ALLOC (sizeof (long) * height);
  219.     right_colors = (long *) ALLOC (sizeof (long) * height);
  220.  
  221.     /*
  222.      * Allocate the intensity table.
  223.      */
  224.     intensity_table = (unsigned char **) ALLOC (sizeof (unsigned char *) * 256);
  225.  
  226.     /*
  227.      * The intensity table is used to modify the value of a pixel in
  228.      *  a regular manner. The table is set up so that the ith subtable
  229.      *  contains values such that each value has been multiplied by (i / 255).
  230.      *  This means that the 255th subtable contains values between 0 and 255.
  231.      *  The 128th subtable contains values between 0 and 128. Evenly distributed
  232.      *  among the 256 entries in each subtable.
  233.      */
  234.     for (i = 0; i < 256; i++)
  235.     {
  236.         intensity_table[i] = (unsigned char *) ALLOC (sizeof (unsigned char) * 256);
  237.  
  238.         for (j = 0; j < 256; j++)
  239.         {
  240.             intensity_table[i][j] = (i * (j + 1)) >> 8;
  241.             if (intensity_table[i][j] == 0)
  242.                 intensity_table[i][j] = 1;
  243.         }
  244.     }
  245.  
  246.     /*
  247.      * Allocate the array used to keep track of constant z lines.
  248.      */
  249.     z_lines = (Z_LINE *) ALLOC (sizeof (Z_LINE) * width);
  250.  
  251.     /*
  252.      * Make the span pool and span buffer.
  253.      */
  254.     make_span_pool ();
  255.     make_span_buffer ();
  256. }
  257.  
  258. /*
  259.  * Reset the scan converter.
  260.  */
  261.  
  262. void
  263. scan_reset ()
  264. {
  265.     /*
  266.      * Reset the span pool and span buffer.
  267.      */
  268.     reset_span_pool ();
  269.     reset_span_buffer ();
  270. }
  271.  
  272. /*
  273.  * Finish scan conversion.
  274.  */
  275.  
  276. void
  277. scan_finish ()
  278. {
  279.     /*
  280.      * Nothing is done here at the present time,
  281.      *  but we could fill in the remaining spans
  282.      *  to black, or some other background color.
  283.      */
  284. }
  285.  
  286. /*
  287.  * Is scan conversion complete?
  288.  */
  289.  
  290. short
  291. scan_complete ()
  292. {
  293.     short dy;
  294.     BOOLEAN *full_spans;
  295.     
  296.     /*
  297.      * Decide if the frame buffer is full by detemining
  298.      *  if every span is full.
  299.      */
  300.  
  301.     full_spans = &span_full[0];
  302.     dy = height;
  303.  
  304.     if (dy > 0)
  305.         while (dy--)
  306.             if (!(*full_spans++))
  307.                 return FALSE;
  308.  
  309.     return TRUE;
  310. }
  311.  
  312. /*
  313.  * Scan convert a textured face.
  314.  */
  315.  
  316. void
  317. scan_texture (pts, n, to, tu, tv, t)
  318.     POINTS pts;
  319.     VECTOR n, to, tu, tv;
  320.     TEXTURE t;
  321. {
  322.     /*
  323.      * Scan convert a polygon.
  324.      * The plane variables are needed to determine
  325.      *  the z value for a given screen point.
  326.      * "scan_calc_texture" calculates the "magic"
  327.      *  texture values.
  328.      * "scan_points" calculates the horizontal spans
  329.      *  this polygon contains and calls the appropriate
  330.      *  drawing routine based on the polygons orientation.
  331.      *  (ie Is it a wall or a floor).
  332.      */
  333.  
  334.     plane_a = my_num_to_fix (vector_x (n));
  335.     plane_b = my_num_to_fix (vector_y (n));
  336.     plane_c = my_num_to_fix (vector_z (n));
  337.     plane_d = my_num_to_fix (vector_dot (n, to));
  338.  
  339.     texture = t;
  340.     scan_calc_texture (to, tu, tv);
  341.     scan_texture_points (pts);
  342. }
  343.  
  344. /*
  345.  * Scan convert a shaded face.
  346.  */
  347.  
  348. void
  349. scan_shade (pts, r, g, b)
  350.     POINTS pts;
  351.     NUM r, g, b;
  352. {
  353.     scan_shade_points (pts, r, g, b);
  354. }
  355.  
  356. /*
  357.  * Calculate the "magic" texture values.
  358.  */
  359.  
  360. void
  361. scan_calc_texture (to, tu, tv)
  362.     VECTOR to, tu, tv;
  363. {
  364.     VECTOR V1, V2, V3;
  365.  
  366.     vector_copy (to, B);
  367.     vector_copy (tu, U);
  368.     vector_copy (tv, V);
  369.  
  370.     vector_cross (tu, tv, V1);
  371.     vector_cross (to, tu, V2);
  372.     vector_cross (tv, to, V3);
  373.  
  374.     v1x = my_num_to_fix (vector_x (V1));
  375.     v1y = my_num_to_fix (vector_y (V1));
  376.     v1z = my_num_to_fix (vector_z (V1));
  377.  
  378.     v2x = my_num_to_fix (vector_x (V2));
  379.     v2y = my_num_to_fix (vector_y (V2));
  380.     v2z = my_num_to_fix (vector_z (V2));
  381.  
  382.     v3x = my_num_to_fix (vector_x (V3));
  383.     v3y = my_num_to_fix (vector_y (V3));
  384.     v3z = my_num_to_fix (vector_z (V3));
  385.  
  386.     xi = float_to_fix (-2.0 /width);
  387.     yi = float_to_fix (-2.0 /height);
  388.  
  389.     s = texture_size (texture);
  390.  
  391.     axi = fix_mul (v1x, xi);
  392.     bxi = fix_mul (v2x, xi) * s;
  393.     cxi = fix_mul (v3x, xi) * s;
  394.  
  395.     ayi = fix_mul (v1y, yi);
  396.     byi = fix_mul (v2y, yi) * s;
  397.     cyi = fix_mul (v3y, yi) * s;
  398. }
  399.  
  400. /*
  401.  * Scan convert a polygon for texturing.
  402.  */
  403.  
  404. static void
  405. scan_texture_points (pts)
  406.     POINTS pts;
  407. {
  408.     POINTS last_pt = points_last (pts);
  409.     POINTS y_min_pt, tmp_pts;
  410.     POINT cur_pt, next_pt, prev_pt;
  411.     long y_min, y_max;
  412.     long x_min, x_max;
  413.     long *temp_edge;
  414.     long dy;
  415.  
  416.     /*
  417.      * Calculate the x extrema and do a trivial
  418.      *  rejection if this polygon degenerates into
  419.      *  a vertical line.
  420.      */
  421.     scan_calc_x_extrema (pts, &x_min, &x_max);
  422.     if (x_min == x_max)
  423.         return;
  424.  
  425.     /*
  426.      * Calculate the y extrema and do a trivial
  427.      *  rejection if this polygon degenerates into
  428.      *  a horizontal line.
  429.      */
  430.     y_min_pt = scan_calc_y_extrema (pts, &y_min, &y_max);
  431.     if (y_min == y_max)
  432.         return;
  433.  
  434.     /*
  435.      * Check to see that this polygon has some visible
  436.      *  portion.
  437.      */
  438.     if (span_trivial_reject (y_min, y_max))
  439.         return;
  440.  
  441.     /*
  442.      * Make the points list circular.
  443.      */
  444.     set_points_rest (last_pt, pts);
  445.     set_points_prev (pts, last_pt);
  446.  
  447.     /*
  448.      * Calculate the "left_edges" for this polygon.
  449.      * This is done by using a modified line drawing
  450.      *  algorithm to determine the x-coordinate for
  451.      *  every y-coordinate on the line.
  452.      * Note: Because it is unknown whether or not
  453.      *       the points are specified clockwise or
  454.      *       counter-clockwise in the "pts" list, the
  455.      *       "left_edges" calculated here may in fact
  456.      *       be the "right_edges" of the polygon. This
  457.      *       is something to keep in mind.
  458.      */
  459.  
  460.     tmp_pts = y_min_pt;
  461.     temp_edge = left_edges;
  462.     while (points_prev (tmp_pts) != y_min_pt)
  463.     {
  464.         cur_pt = points_first (tmp_pts);
  465.         prev_pt = points_first (points_prev (tmp_pts));
  466.         tmp_pts = points_prev (tmp_pts);
  467.  
  468.         dy = point_y (prev_pt) - point_y (cur_pt);
  469.         if (dy < 0)
  470.             break;
  471.  
  472.         if (dy > 0)
  473.         {
  474.             temp_edge = scan_calc_edge (temp_edge, point_x (cur_pt), point_x (prev_pt),
  475.                 point_y (cur_pt), point_y (prev_pt));
  476.         }
  477.     }
  478.  
  479.     /*
  480.      * Calculate the "right_edges" for this polygon.
  481.      */
  482.  
  483.     tmp_pts = y_min_pt;
  484.     temp_edge = right_edges;
  485.     while (points_rest (tmp_pts) != y_min_pt)
  486.     {
  487.         cur_pt = points_first (tmp_pts);
  488.         next_pt = points_first (points_rest (tmp_pts));
  489.         tmp_pts = points_rest (tmp_pts);
  490.  
  491.         dy = point_y (next_pt) - point_y (cur_pt);
  492.         if (dy < 0)
  493.             break;
  494.  
  495.         if (dy > 0)
  496.         {
  497.             temp_edge = scan_calc_edge (temp_edge, point_x (cur_pt), point_x (next_pt),
  498.                 point_y (cur_pt), point_y (next_pt));
  499.         }
  500.     }
  501.  
  502.     /*
  503.      * Call the appropriate drawing routine based on two
  504.      *  considerations.
  505.      * 1. What is the depth of the screen?
  506.      * 2. What is the orientation of the polygon?
  507.      * Walls are drawn by the scan_texture_vertical routines
  508.      *  and floor and ceilings are drawn by the
  509.      *  scan_texture_horizontal routines.
  510.      */
  511.     switch (get_frame_buffer_pixel ())
  512.     {
  513.     case 1:
  514.         if (v1x == 0)
  515.             scan_texture_horizontal8 (y_min, y_max);
  516.         else if (v1y == 0)
  517.             scan_texture_vertical8 (y_min, y_max);
  518.         break;
  519.     case 4:
  520.         if (v1x == 0)
  521.             scan_texture_horizontal24 (y_min, y_max);
  522.         else if (v1y == 0)
  523.             scan_texture_vertical24 (y_min, y_max);
  524.         break;
  525.     }
  526.  
  527.     /*
  528.      * Make the points list non-circular.
  529.      * This is needed so that disposal of the list
  530.      *  works properly.
  531.      */
  532.     set_points_rest (last_pt, NULL);
  533.     set_points_prev (pts, NULL);
  534. }
  535.  
  536. /*
  537.  * Scan convert a polygon for shading.
  538.  */
  539.  
  540. static void
  541. scan_shade_points (pts, r, g, b)
  542.     POINTS pts;
  543.     NUM r, g, b;
  544. {
  545.     POINTS last_pt = points_last (pts);
  546.     POINTS y_min_pt, tmp_pts;
  547.     POINT cur_pt, next_pt, prev_pt;
  548.     long y_min, y_max;
  549.     long x_min, x_max;
  550.     long *temp_edge;
  551.     long *temp_color;
  552.     long dy;
  553.  
  554.     /*
  555.      * Calculate the x extrema and do a trivial
  556.      *  rejection if this polygon degenerates into
  557.      *  a vertical line.
  558.      */
  559.     scan_calc_x_extrema (pts, &x_min, &x_max);
  560.     if (x_min == x_max)
  561.         return;
  562.  
  563.     /*
  564.      * Calculate the y extrema and do a trivial
  565.      *  rejection if this polygon degenerates into
  566.      *  a horizontal line.
  567.      */
  568.     y_min_pt = scan_calc_y_extrema (pts, &y_min, &y_max);
  569.     if (y_min == y_max)
  570.         return;
  571.  
  572.     /*
  573.      * Check to see that this polygon has some visible
  574.      *  portion.
  575.      */
  576.     if (span_trivial_reject (y_min, y_max))
  577.         return;
  578.  
  579.     /*
  580.      * Make the points list circular.
  581.      */
  582.     set_points_rest (last_pt, pts);
  583.     set_points_prev (pts, last_pt);
  584.  
  585.     /*
  586.      * Calculate the "left_edges" for this polygon.
  587.      * This is done by using a modified line drawing
  588.      *  algorithm to determine the x-coordinate for
  589.      *  every y-coordinate on the line.
  590.      * Note: Because it is unknown whether or not
  591.      *       the points are specified clockwise or
  592.      *       counter-clockwise in the "pts" list, the
  593.      *       "left_edges" calculated here may in fact
  594.      *       be the "right_edges" of the polygon. This
  595.      *       is something to keep in mind.
  596.      *
  597.      * The difference between this and the texture scan
  598.      *  converter is that we also keep track off intensity
  599.      *  values along edges.
  600.      */
  601.  
  602.     tmp_pts = y_min_pt;
  603.     temp_edge = left_edges;
  604.     temp_color = left_colors;
  605.     while (points_prev (tmp_pts) != y_min_pt)
  606.     {
  607.         cur_pt = points_first (tmp_pts);
  608.         prev_pt = points_first (points_prev (tmp_pts));
  609.         tmp_pts = points_prev (tmp_pts);
  610.  
  611.         dy = point_y (prev_pt) - point_y (cur_pt);
  612.         if (dy < 0)
  613.             break;
  614.  
  615.         if (dy > 0)
  616.         {
  617.             temp_edge = scan_calc_edge (temp_edge, point_x (cur_pt), point_x (prev_pt),
  618.                 point_y (cur_pt), point_y (prev_pt));
  619.             
  620.             temp_color = scan_calc_color (temp_color, 
  621.                 my_num_to_fix (my_mul (point_intensity (cur_pt),
  622.                                        my_float_to_num (255.0))),
  623.                 my_num_to_fix (my_mul (point_intensity (prev_pt),
  624.                                        my_float_to_num (255.0))),
  625.                 dy);
  626.         }
  627.     }
  628.  
  629.     /*
  630.      * Calculate the "right_edges" for this polygon.
  631.      */
  632.  
  633.     tmp_pts = y_min_pt;
  634.     temp_edge = right_edges;
  635.     temp_color = right_colors;
  636.     while (points_rest (tmp_pts) != y_min_pt)
  637.     {
  638.         cur_pt = points_first (tmp_pts);
  639.         next_pt = points_first (points_rest (tmp_pts));
  640.         tmp_pts = points_rest (tmp_pts);
  641.  
  642.         dy = point_y (next_pt) - point_y (cur_pt);
  643.         if (dy < 0)
  644.             break;
  645.  
  646.         if (dy > 0)
  647.         {
  648.             temp_edge = scan_calc_edge (temp_edge, point_x (cur_pt), point_x (next_pt),
  649.                 point_y (cur_pt), point_y (next_pt));
  650.             
  651.             temp_color = scan_calc_color (temp_color, 
  652.                 my_num_to_fix (my_mul (point_intensity (cur_pt),
  653.                                        my_float_to_num (255.0))),
  654.                 my_num_to_fix (my_mul (point_intensity (next_pt),
  655.                                        my_float_to_num (255.0))),
  656.                 dy);
  657.         }
  658.     }
  659.  
  660.     /*
  661.      * Call the appropriate drawing routine based on the depth.
  662.      */
  663.     switch (get_frame_buffer_pixel ())
  664.     {
  665.     case 1:
  666.         scan_shade8 (y_min, y_max, 65536);
  667.     case 4:
  668.         scan_shade24 (y_min, y_max, 
  669.             my_num_to_fix (r), 
  670.             my_num_to_fix (g),
  671.             my_num_to_fix (b));
  672.         break;
  673.     }
  674.  
  675.     /*
  676.      * Make the points list non-circular.
  677.      * This is needed so that disposal of the list
  678.      *  works properly.
  679.      */
  680.     set_points_rest (last_pt, NULL);
  681.     set_points_prev (pts, NULL);
  682. }
  683.  
  684. /*
  685.  * Scan a "horizontal" polygon for texturing.
  686.  */
  687.  
  688. static void
  689. scan_texture_horizontal8 (y_min, y_max)
  690.     long y_min, y_max;
  691. {
  692.     PIXEL8 *p, *t;
  693.     PIXEL8 *ta;
  694.     SPAN cur_span;
  695.     SPAN next_span;
  696.     unsigned char *table;
  697.     long ts, mask;
  698.     long dx, dy;
  699.     long *left, *right;
  700.     long a, b, c;
  701.     long bi, ci;
  702.     long u, v;
  703.     long x, y;
  704.     long intensity;
  705.  
  706.     /*
  707.      * Get the frame buffer address and offset to
  708.      *  the first scanline.
  709.      */
  710.     p = get_frame_buffer_address ();
  711.     p += y_min * width;
  712.  
  713.     /*
  714.      * Check the "middle" of the polygon to see which
  715.      *  edges are which. We can't know ahead of time!
  716.      */
  717.     dy = (y_max - y_min) >> 1;
  718.     if (left_edges[dy] < right_edges[dy])
  719.     {
  720.         left = left_edges;
  721.         right = right_edges;
  722.     }
  723.     else
  724.     {
  725.         left = right_edges;
  726.         right = left_edges;
  727.     }
  728.  
  729.     /*
  730.      * Get the texture address and its size log 2.
  731.      * Also, a mask is used to speed up overflow handling.
  732.      */
  733.     ta = texture_address (texture);
  734.     ts = texture_size_log2 (texture);
  735.     mask = texture_size (texture) - 1;
  736.  
  737.     /*
  738.      * Need to keep track of y.
  739.      */
  740.     y = float_to_fix (1 - (y_min * 2.0) / height);
  741.  
  742.     /*
  743.      * For each scanline...
  744.      */
  745.     dy = y_max - y_min;
  746.     while (dy--)
  747.     {
  748.         /*
  749.          * Get a pointer to the start of the line and
  750.          *  increment to the start of the next line.
  751.          */
  752.         t = p + *left;
  753.         p += width;
  754.  
  755.         /*
  756.          * Find the width of the span on the current line.
  757.          * This should never be less than 0. (Though stranger
  758.          *  things have happened.) It may be 0, though.
  759.          */
  760.         dx = *right - *left;
  761.         if (dx > 0)
  762.         {
  763.             /*
  764.              * Add the span to the given span buffer. The span
  765.              *  that is returned is the areas we are allowed to
  766.              *  draw in.
  767.              */
  768.             cur_span = span_add (*left, *right, y_max - dy - 1);
  769.  
  770.             /*
  771.              * If something was returned...
  772.              */
  773.             if (cur_span)
  774.             {
  775.                 /*
  776.                  * Calculate texture values for this line.
  777.                  */
  778.                 x = float_to_fix (1 - (*left * 2.0) /width);
  779.                 a = fix_mul (v1x, x) + fix_mul (v1y, y) + v1z;
  780.                 b = (fix_mul (v2x, x) + fix_mul (v2y, y) + v2z) * s;
  781.                 c = (fix_mul (v3x, x) + fix_mul (v3y, y) + v3z) * s;
  782.  
  783.                 /*
  784.                  * The polygon is "horizontal" so z is constant
  785.                  *  across a scanline. (ie "ai" is 0). This means
  786.                  *  we can do the costly divides outside the inner
  787.                  *  loop.
  788.                  */
  789.                 b = fix_div (b, a);
  790.                 c = fix_div (c, a);
  791.  
  792.                 bi = fix_div (bxi, a);
  793.                 ci = fix_div (cxi, a);
  794.  
  795.                 /*
  796.                  * Calculate the z distance this scanline is from the viewer.
  797.                  * It'll be the same for the whole scanline.
  798.                  */
  799.                 intensity = fix_mul (plane_a, x) + fix_mul (plane_b, y) - plane_c;
  800.                 intensity = fix_div (plane_d, intensity);
  801.  
  802.                 /*
  803.                  * This is a little hack, that makes it look nice.
  804.                  * Clamp the value between 0 and 255.
  805.                  */
  806.                 intensity = fix_to_int (intensity * INTENSITY_MULT);
  807.                 if (intensity < 0)
  808.                     intensity = -intensity;
  809.                 if (intensity > 255)
  810.                     intensity = 255;
  811.  
  812.                 /*
  813.                  * The farther something is away, the darker it gets, so...
  814.                  */
  815.                 table = intensity_table[255 - intensity];
  816.  
  817.                 /*
  818.                  * This is just something I noticed. (It's the psuedo-
  819.                  *  Gouraud shading).
  820.                  * "a" depends on the orientation of the polygon
  821.                  *  with respect to the viewer. That is, if the
  822.                  *  polygon is nearly on edge, "a" gets smaller.
  823.                  *  Conversely, if the polygon is viewed straight
  824.                  *  on "a" get larger.
  825.                  */
  826.                 a = fix_to_int (a * SHADE_MULT);
  827.                 if (a < 0)
  828.                     a = -a;
  829.                 if (a > 255)
  830.                     a = 255;
  831.  
  832.                 /*
  833.                  * Use the previous depth table to find a new table
  834.                  *  based on the value of "a".
  835.                  */
  836.                 table = intensity_table[table[a]];
  837.  
  838.                 /*
  839.                  * "t" points to the beginning of the original
  840.                  *  span for this scanline. We need to increment
  841.                  *  it and the texture values to get to the
  842.                  *  start of the first span we can draw into.
  843.                  */
  844.                 if (cur_span->next)
  845.                     dx = 0;
  846.                 dx = cur_span->start - *left;
  847.                 
  848.                 t += dx;
  849.                 b += bi * dx;
  850.                 c += ci * dx;
  851.  
  852.                 /*
  853.                  * While there are more spans...
  854.                  */
  855.                 while (cur_span)
  856.                 {
  857.                     dx = cur_span->end - cur_span->start;
  858.                     if (dx < 0)
  859.                         dx = 0;
  860.  
  861.                     /*
  862.                      * For the width of this span calculate
  863.                      *  the u and v texture vals and use the
  864.                      *  table chosen above to modify the
  865.                      *  texture color.
  866.                      * Remember to increment.
  867.                      */
  868.                     while (dx--)
  869.                     {
  870.                         u = fix_to_int (b) & mask;
  871.                         v = fix_to_int (c) & mask;
  872.  
  873.                         *t++ = table[*(ta + (u << ts) + v)];
  874.  
  875.                         b += bi;
  876.                         c += ci;
  877.                     }
  878.  
  879.                     /*
  880.                      * There is probably (almost definately)
  881.                      *  some distance between the end of the
  882.                      *  current span and the start of the next.
  883.                      *  This means we have to increment the
  884.                      *  texture vals appropriately.
  885.                      */
  886.                     next_span = cur_span->next;
  887.                     if (next_span)
  888.                         dx = next_span->start - cur_span->end;
  889.                     else
  890.                         dx = *right - cur_span->end;
  891.  
  892.                     cur_span = next_span;
  893.  
  894.                     if (dx < 0)
  895.                         dx = 0;
  896.                     
  897.                     t += dx;
  898.                     b += bi * dx;
  899.                     c += ci * dx;
  900.                 }
  901.             }
  902.         }
  903.  
  904.         /*
  905.          * Increment the left and right edge pointers.
  906.          */
  907.         left++;
  908.         right++;
  909.  
  910.         /*
  911.          * Increment y.
  912.          */
  913.         y += yi;
  914.     }
  915. }
  916.  
  917. static void
  918. scan_texture_vertical8 (y_min, y_max)
  919.     long y_min, y_max;
  920. {
  921.     PIXEL8 *p, *t;
  922.     PIXEL8 *ta;
  923.     Z_LINE *cols;
  924.     SPAN cur_span;
  925.     SPAN next_span;
  926.     long dx, dy;
  927.     long *left, *right;
  928.     long ts, mask;
  929.     long a, b, c;
  930.     long x, y;
  931.     long u, v;
  932.     long intensity;
  933.  
  934.     /*
  935.      * Get the frame buffer address and offset to
  936.      *  the first scanline.
  937.      */
  938.     p = get_frame_buffer_address ();
  939.     p += y_min * width;
  940.  
  941.     /*
  942.      * Check the "middle" of the polygon to see which
  943.      *  edges are which. We can't know ahead of time!
  944.      */
  945.     dy = (y_max - y_min) >> 1;
  946.     if (left_edges[dy] < right_edges[dy])
  947.     {
  948.         left = left_edges;
  949.         right = right_edges;
  950.     }
  951.     else
  952.     {
  953.         left = right_edges;
  954.         right = left_edges;
  955.     }
  956.  
  957.     /*
  958.      * Initialize the "z_lines" array.
  959.      */
  960.     for (dx = 0; dx < width; dx++)
  961.         z_lines[dx].ready = FALSE;
  962.  
  963.     /*
  964.      * Get the texture address and its size log 2.
  965.      * Also, a mask is used to speed up overflow handling.
  966.      */
  967.     ta = texture_address (texture);
  968.     ts = texture_size_log2 (texture);
  969.     mask = texture_size (texture) - 1;
  970.  
  971.     /*
  972.      * Need to keep track of y.
  973.      */
  974.     y = float_to_fix (1 - (y_min * 2.0) /height);
  975.  
  976.     /*
  977.      * For each scanline...
  978.      */
  979.     dy = y_max - y_min;
  980.     while (dy--)
  981.     {
  982.         /*
  983.          * Get a pointer to the start of the line and
  984.          *  increment to the start of the next line.
  985.          */
  986.         t = p + *left;
  987.         p += width;
  988.         
  989.         /*
  990.          * Find the width of the span on the current line.
  991.          * This should never be less than 0. (Though stranger
  992.          *  things have happened.) It may be 0, though.
  993.          */
  994.         dx = *right - *left;
  995.         if (dx > 0)
  996.         {
  997.             /*
  998.              * Add the span to the given span buffer. The span
  999.              *  that is returned is the areas we are allowed to
  1000.              *  draw in.
  1001.              */
  1002.             cur_span = span_add (*left, *right, y_max - dy - 1);
  1003.  
  1004.             if (cur_span)
  1005.             {
  1006.                 /*
  1007.                  * Get a pointer to the start of the "z_lines"
  1008.                  *  for this scanline. Also calculate x for
  1009.                  *  the start of this scanline.
  1010.                  */
  1011.                 cols = &z_lines[*left];
  1012.                 x = float_to_fix (1 - (*left * 2.0) / width);
  1013.                 
  1014.                 /*
  1015.                  * "t" points to the beginning of the original
  1016.                  *  span for this scanline. We need to increment
  1017.                  *  it and the texture values to get to the
  1018.                  *  start of the first span we can draw into.
  1019.                  */
  1020.                 if (cur_span->next)
  1021.                     dx = 0;
  1022.                 dx = cur_span->start - *left;
  1023.                 if (dx < 0)
  1024.                     dx = 0;
  1025.  
  1026.                 while (dx--)
  1027.                 {
  1028.                     if (cols->ready)
  1029.                         cols->u += cols->du;
  1030.     
  1031.                     t++;
  1032.                     cols++;
  1033.                     x += xi;
  1034.                 }
  1035.                 
  1036.                 /*
  1037.                  * While there are more spans...
  1038.                  */
  1039.                 while (cur_span)
  1040.                 {
  1041.                     dx = cur_span->end - cur_span->start;
  1042.                     if (dx < 0)
  1043.                         dx = 0;
  1044.     
  1045.                     while (dx--)
  1046.                     {
  1047.                         /*
  1048.                          * If this column isn't ready, then we need to
  1049.                          *  do some initialization. This is basically
  1050.                          *  the same as what was done for the "horizontal"
  1051.                          *  scan conversion, except that this time "a"
  1052.                          *  is constant down a column. Actually, its even
  1053.                          *  better than that this time. "v" is also constant.
  1054.                          */
  1055.                         if (!cols->ready)
  1056.                         {
  1057.                             cols->ready = TRUE;
  1058.     
  1059.                             a = fix_mul (v1x, x) + fix_mul (v1y, y) + v1z;
  1060.                             b = (fix_mul (v2x, x) + fix_mul (v2y, y) + v2z) * s;
  1061.                             c = (fix_mul (v3x, x) + fix_mul (v3y, y) + v3z) * s;
  1062.     
  1063.                             cols->u = fix_div (b, a);
  1064.                             cols->v = fix_to_int (fix_div (c, a)) & mask;
  1065.                             cols->du = fix_div (byi, a);
  1066.     
  1067.                             intensity = fix_mul (plane_a, -x) + fix_mul (plane_b, y) - plane_c;
  1068.                             intensity = fix_div (plane_d, intensity);
  1069.     
  1070.                             intensity = fix_to_int (intensity * INTENSITY_MULT);
  1071.                             if (intensity < 0)
  1072.                                 intensity = -intensity;
  1073.                             if (intensity > 255)
  1074.                                 intensity = 255;
  1075.     
  1076.                             cols->table = intensity_table[255 - intensity];
  1077.     
  1078.                             a = fix_to_int (a * SHADE_MULT);
  1079.                             if (a < 0)
  1080.                                 a = -a;
  1081.                             if (a > 255)
  1082.                                 a = 255;
  1083.     
  1084.                             cols->table = intensity_table[cols->table[a]];
  1085.                         }
  1086.     
  1087.                         u = fix_to_int (cols->u) & mask;
  1088.                         v = cols->v;
  1089.     
  1090.                         cols->u += cols->du;
  1091.     
  1092.                         *t++ = cols->table[*(ta + (u << ts) + v)];
  1093.                         cols++;
  1094.                         x += xi;
  1095.                     }
  1096.     
  1097.                     /*
  1098.                      * There is probably (almost definately)
  1099.                      *  some distance between the end of the
  1100.                      *  current span and the start of the next.
  1101.                      *  This means we have to increment the
  1102.                      *  texture vals appropriately.
  1103.                      */
  1104.                     next_span = cur_span->next;
  1105.                     if (next_span)
  1106.                         dx = next_span->start - cur_span->end;
  1107.                     else
  1108.                         dx = *right - cur_span->end;
  1109.     
  1110.                     cur_span = next_span;
  1111.     
  1112.                     if (dx < 0)
  1113.                         dx = 0;
  1114.     
  1115.                     while (dx--)
  1116.                     {
  1117.                         if (cols->ready)
  1118.                             cols->u += cols->du;
  1119.     
  1120.                         t++;
  1121.                         cols++;
  1122.                         x += xi;
  1123.                     }
  1124.                 }
  1125.             }
  1126.         }
  1127.  
  1128.         /*
  1129.          * Increment the left and right edge pointers.
  1130.          */
  1131.         left++;
  1132.         right++;
  1133.  
  1134.         /*
  1135.          * Increment y.
  1136.          */
  1137.         y += yi;
  1138.     }
  1139. }
  1140.  
  1141. static void
  1142. scan_shade8 (y_min, y_max, intensity)
  1143.     long y_min, y_max, intensity;
  1144. {
  1145.     PIXEL8 *p, *t;
  1146.     SPAN cur_span;
  1147.     SPAN next_span;
  1148.     unsigned char *table;
  1149.     long dx, dy, dc;
  1150.     long color;
  1151.     long *left, *right;
  1152.     long *left_c, *right_c;
  1153.  
  1154.     p = get_frame_buffer_address ();
  1155.     p += y_min * width;
  1156.  
  1157.     dy = (y_max - y_min) >> 1;
  1158.     if (left_edges[dy] < right_edges[dy])
  1159.     {
  1160.         left = left_edges;
  1161.         right = right_edges;
  1162.         left_c = left_colors;
  1163.         right_c = right_colors;
  1164.     }
  1165.     else
  1166.     {
  1167.         left = right_edges;
  1168.         right = left_edges;
  1169.         left_c = right_colors;
  1170.         right_c = left_colors;
  1171.     }
  1172.  
  1173.     dy = y_max - y_min;
  1174.     while (dy--)
  1175.     {
  1176.         t = p + *left;
  1177.         p += width;
  1178.  
  1179.         dx = *right - *left;
  1180.         if (dx > 0)
  1181.         {
  1182.             cur_span = span_add (*left, *right, y_max - dy - 1);
  1183.  
  1184.             if (cur_span)
  1185.             {
  1186.                 color = *left_c;
  1187.                 dc = (*right_c - *left_c) /dx;
  1188.  
  1189.                 if (cur_span->next)
  1190.                     dx = 0;
  1191.                 dx = cur_span->start - *left;
  1192.  
  1193.                 while (dx--)
  1194.                 {
  1195.                     t++;
  1196.                     color += dc;
  1197.                 }
  1198.  
  1199.                 while (cur_span)
  1200.                 {
  1201.                     dx = cur_span->end - cur_span->start;
  1202.                     if (dx < 0)
  1203.                         dx = 0;
  1204.  
  1205.                     while (dx--)
  1206.                     {
  1207.                         *t++ = fix_to_int (fix_mul (color, intensity));
  1208.                         color += dc;
  1209.                     }
  1210.  
  1211.                     next_span = cur_span->next;
  1212.                     if (next_span)
  1213.                         dx = next_span->start - cur_span->end;
  1214.                     else
  1215.                         dx = *right - cur_span->end;
  1216.  
  1217.                     cur_span = next_span;
  1218.  
  1219.                     while (dx--)
  1220.                     {
  1221.                         t++;
  1222.                         color += dc;
  1223.                     }
  1224.                 }
  1225.             }
  1226.         }
  1227.  
  1228.         left++;
  1229.         right++;
  1230.         left_c++;
  1231.         right_c++;
  1232.     }
  1233. }
  1234.  
  1235. static void
  1236. scan_texture_horizontal24 (y_min, y_max)
  1237.     long y_min, y_max;
  1238. {
  1239.     PIXEL24 *p, *t;
  1240.     PIXEL24 *ta, pix;
  1241.     SPAN cur_span;
  1242.     SPAN next_span;
  1243.     unsigned char *table;
  1244.     long ts, mask;
  1245.     long dx, dy;
  1246.     long *left, *right;
  1247.     long a, b, c;
  1248.     long bi, ci;
  1249.     long u, v;
  1250.     long x, y;
  1251.     long intensity;
  1252.  
  1253.     p = get_frame_buffer_address ();
  1254.     p += y_min * width;
  1255.  
  1256.     dy = (y_max - y_min) >> 1;
  1257.     if (left_edges[dy] < right_edges[dy])
  1258.     {
  1259.         left = left_edges;
  1260.         right = right_edges;
  1261.     }
  1262.     else
  1263.     {
  1264.         left = right_edges;
  1265.         right = left_edges;
  1266.     }
  1267.  
  1268.     ta = texture_address (texture);
  1269.     ts = texture_size_log2 (texture);
  1270.     mask = texture_size (texture) - 1;
  1271.  
  1272.     y = float_to_fix (1 - (y_min * 2.0) /height);
  1273.  
  1274.     dy = y_max - y_min;
  1275.     while (dy--)
  1276.     {
  1277.         t = p + *left;
  1278.         p += width;
  1279.  
  1280.         dx = *right - *left;
  1281.         if (dx > 0)
  1282.         {
  1283.             cur_span = span_add (*left, *right, y_max - dy - 1);
  1284.  
  1285.             if (cur_span)
  1286.             {
  1287.                 x = float_to_fix (1 - (*left * 2.0) /width);
  1288.                 a = fix_mul (v1x, x) + fix_mul (v1y, y) + v1z;
  1289.                 b = (fix_mul (v2x, x) + fix_mul (v2y, y) + v2z) * s;
  1290.                 c = (fix_mul (v3x, x) + fix_mul (v3y, y) + v3z) * s;
  1291.  
  1292.                 b = fix_div (b, a);
  1293.                 c = fix_div (c, a);
  1294.  
  1295.                 bi = fix_div (bxi, a);
  1296.                 ci = fix_div (cxi, a);
  1297.  
  1298.                 intensity = fix_mul (plane_a, x) + fix_mul (plane_b, y) - plane_c;
  1299.                 intensity = fix_div (plane_d, intensity);
  1300.  
  1301.                 intensity = fix_to_int (intensity * INTENSITY_MULT);
  1302.                 if (intensity < 0)
  1303.                     intensity = -intensity;
  1304.                 if (intensity > 255)
  1305.                     intensity = 255;
  1306.  
  1307.                 table = intensity_table[255 - intensity];
  1308.  
  1309.                 a = fix_to_int (a * SHADE_MULT);
  1310.                 if (a < 0)
  1311.                     a = -a;
  1312.                 if (a > 255)
  1313.                     a = 255;
  1314.  
  1315.                 table = intensity_table[table[a]];
  1316.  
  1317.                 if (cur_span->next)
  1318.                     dx = 0;
  1319.                 dx = cur_span->start - *left;
  1320.  
  1321.                 while (dx--)
  1322.                 {
  1323.                     t++;
  1324.                     b += bi;
  1325.                     c += ci;
  1326.                 }
  1327.  
  1328.                 while (cur_span)
  1329.                 {
  1330.                     dx = cur_span->end - cur_span->start;
  1331.                     if (dx < 0)
  1332.                         dx = 0;
  1333.  
  1334.                     while (dx--)
  1335.                     {
  1336.                         u = fix_to_int (b) & mask;
  1337.                         v = fix_to_int (c) & mask;
  1338.  
  1339.                         pix = *(ta + (u << ts) + v);
  1340.                         *t = table[pix & 0xFF];
  1341.                         pix >>= 8;
  1342.                         *t += table[pix & 0xFF] << 8;
  1343.                         pix >>= 8;
  1344.                         *t += table[pix & 0xFF] << 16;
  1345.                         t++;
  1346.  
  1347.                         b += bi;
  1348.                         c += ci;
  1349.                     }
  1350.  
  1351.                     next_span = cur_span->next;
  1352.                     if (next_span)
  1353.                         dx = next_span->start - cur_span->end;
  1354.                     else
  1355.                         dx = *right - cur_span->end;
  1356.  
  1357.                     cur_span = next_span;
  1358.  
  1359.                     if (dx < 0)
  1360.                         dx = 0;
  1361.  
  1362.                     while (dx--)
  1363.                     {
  1364.                         t++;
  1365.                         b += bi;
  1366.                         c += ci;
  1367.                     }
  1368.                 }
  1369.             }
  1370.         }
  1371.  
  1372.         left++;
  1373.         right++;
  1374.  
  1375.         y += yi;
  1376.     }
  1377. }
  1378.  
  1379. static void
  1380. scan_texture_vertical24 (y_min, y_max)
  1381.     long y_min, y_max;
  1382. {
  1383.     PIXEL24 *p, *t;
  1384.     PIXEL24 *ta, pix;
  1385.     Z_LINE *cols;
  1386.     SPAN cur_span;
  1387.     SPAN next_span;
  1388.     long dx, dy;
  1389.     long *left, *right;
  1390.     long ts, mask;
  1391.     long a, b, c;
  1392.     long x, y;
  1393.     long u, v;
  1394.     long intensity;
  1395.  
  1396.     p = get_frame_buffer_address ();
  1397.     p += y_min * width;
  1398.  
  1399.     dy = (y_max - y_min) >> 1;
  1400.     if (left_edges[dy] < right_edges[dy])
  1401.     {
  1402.         left = left_edges;
  1403.         right = right_edges;
  1404.     }
  1405.     else
  1406.     {
  1407.         left = right_edges;
  1408.         right = left_edges;
  1409.     }
  1410.  
  1411.     for (dx = 0; dx < width; dx++)
  1412.         z_lines[dx].ready = FALSE;
  1413.  
  1414.     ta = texture_address (texture);
  1415.     ts = texture_size_log2 (texture);
  1416.     mask = texture_size (texture) - 1;
  1417.  
  1418.     y = float_to_fix (1 - (y_min * 2.0) /height);
  1419.  
  1420.     dy = y_max - y_min;
  1421.     while (dy--)
  1422.     {
  1423.         t = p + *left;
  1424.         p += width;
  1425.  
  1426.         cols = &z_lines[*left];
  1427.         x = float_to_fix (1 - (*left * 2.0) /width);
  1428.         dx = *right - *left;
  1429.  
  1430.         if (dx > 0)
  1431.         {
  1432.             cur_span = span_add (*left, *right, y_max - dy - 1);
  1433.  
  1434.             if (cur_span)
  1435.             {
  1436.                 if (cur_span->next)
  1437.                     dx = 0;
  1438.                 dx = cur_span->start - *left;
  1439.             }
  1440.  
  1441.             if (dx < 0)
  1442.                 dx = 0;
  1443.  
  1444.             while (dx--)
  1445.             {
  1446.                 if (cols->ready)
  1447.                 {
  1448.                     cols->u += cols->du;
  1449.                 }
  1450.  
  1451.                 t++;
  1452.                 cols++;
  1453.                 x += xi;
  1454.             }
  1455.  
  1456.             while (cur_span)
  1457.             {
  1458.                 dx = cur_span->end - cur_span->start;
  1459.                 if (dx < 0)
  1460.                     dx = 0;
  1461.  
  1462.                 while (dx--)
  1463.                 {
  1464.                     if (!cols->ready)
  1465.                     {
  1466.                         cols->ready = TRUE;
  1467.  
  1468.                         a = fix_mul (v1x, x) + fix_mul (v1y, y) + v1z;
  1469.                         b = (fix_mul (v2x, x) + fix_mul (v2y, y) + v2z) * s;
  1470.                         c = (fix_mul (v3x, x) + fix_mul (v3y, y) + v3z) * s;
  1471.  
  1472.                         cols->u = fix_div (b, a);
  1473.                         cols->v = fix_to_int (fix_div (c, a)) & mask;
  1474.                         cols->du = fix_div (byi, a);
  1475.  
  1476.                         intensity = fix_mul (plane_a, -x) + fix_mul (plane_b, y) - plane_c;
  1477.                         intensity = fix_div (plane_d, intensity);
  1478.  
  1479.                         intensity = fix_to_int (intensity * INTENSITY_MULT);
  1480.                         if (intensity < 0)
  1481.                             intensity = -intensity;
  1482.                         if (intensity > 255)
  1483.                             intensity = 255;
  1484.  
  1485.                         cols->table = intensity_table[255 - intensity];
  1486.  
  1487.                         a = fix_to_int (a * SHADE_MULT);
  1488.                         if (a < 0)
  1489.                             a = -a;
  1490.                         if (a > 255)
  1491.                             a = 255;
  1492.  
  1493.                         cols->table = intensity_table[cols->table[a]];
  1494.                     }
  1495.  
  1496.                     u = fix_to_int (cols->u) & mask;
  1497.                     v = cols->v;
  1498.  
  1499.                     cols->u += cols->du;
  1500.  
  1501.                     pix = *(ta + (u << ts) + v);
  1502.                     *t = cols->table[pix & 0xFF];
  1503.                     pix >>= 8;
  1504.                     *t += cols->table[pix & 0xFF] << 8;
  1505.                     pix >>= 8;
  1506.                     *t += cols->table[pix & 0xFF] << 16;
  1507.                     t++;
  1508.  
  1509.                     cols++;
  1510.                     x += xi;
  1511.                 }
  1512.  
  1513.                 next_span = cur_span->next;
  1514.                 if (next_span)
  1515.                     dx = next_span->start - cur_span->end;
  1516.                 else
  1517.                     dx = *right - cur_span->end;
  1518.  
  1519.                 cur_span = next_span;
  1520.  
  1521.                 if (dx < 0)
  1522.                     dx = 0;
  1523.  
  1524.                 while (dx--)
  1525.                 {
  1526.                     if (cols->ready)
  1527.                     {
  1528.                         cols->u += cols->du;
  1529.                     }
  1530.  
  1531.                     t++;
  1532.                     cols++;
  1533.                     x += xi;
  1534.                 }
  1535.             }
  1536.         }
  1537.  
  1538.         left++;
  1539.         right++;
  1540.  
  1541.         y += yi;
  1542.     }
  1543. }
  1544.  
  1545. static void
  1546. scan_shade24 (y_min, y_max, red, green, blue)
  1547.     long y_min, y_max;
  1548.     long red, green, blue;
  1549. {
  1550.     PIXEL24 *p, *t;
  1551.     PIXEL24 r, g, b;
  1552.     SPAN cur_span;
  1553.     SPAN next_span;
  1554.     unsigned char *table;
  1555.     long dx, dy, dc;
  1556.     long color;
  1557.     long *left, *right;
  1558.     long *left_c, *right_c;
  1559.  
  1560.     p = get_frame_buffer_address ();
  1561.     p += y_min * width;
  1562.  
  1563.     dy = (y_max - y_min) >> 1;
  1564.     if (left_edges[dy] < right_edges[dy])
  1565.     {
  1566.         left = left_edges;
  1567.         right = right_edges;
  1568.         left_c = left_colors;
  1569.         right_c = right_colors;
  1570.     }
  1571.     else
  1572.     {
  1573.         left = right_edges;
  1574.         right = left_edges;
  1575.         left_c = right_colors;
  1576.         right_c = left_colors;
  1577.     }
  1578.  
  1579.     dy = y_max - y_min;
  1580.     while (dy--)
  1581.     {
  1582.         t = p + *left;
  1583.         p += width;
  1584.  
  1585.         dx = *right - *left;
  1586.         if (dx > 0)
  1587.         {
  1588.             cur_span = span_add (*left, *right, y_max - dy - 1);
  1589.  
  1590.             if (cur_span)
  1591.             {
  1592.                 color = *left_c;
  1593.                 dc = (*right_c - *left_c) /dx;
  1594.  
  1595.                 if (cur_span->next)
  1596.                     dx = 0;
  1597.                 dx = cur_span->start - *left;
  1598.  
  1599.                 while (dx--)
  1600.                 {
  1601.                     t++;
  1602.                     color += dc;
  1603.                 }
  1604.  
  1605.                 while (cur_span)
  1606.                 {
  1607.                     dx = cur_span->end - cur_span->start;
  1608.                     if (dx < 0)
  1609.                         dx = 0;
  1610.  
  1611.                     while (dx--)
  1612.                     {
  1613.                         r = fix_to_int (fix_mul (color, red)) << 16;
  1614.                         g = fix_to_int (fix_mul (color, green)) << 8;
  1615.                         b = fix_to_int (fix_mul (color, blue));
  1616.                         *t++ = r + g + b;
  1617.  
  1618.                         color += dc;
  1619.                     }
  1620.  
  1621.                     next_span = cur_span->next;
  1622.                     if (next_span)
  1623.                         dx = next_span->start - cur_span->end;
  1624.                     else
  1625.                         dx = *right - cur_span->end;
  1626.  
  1627.                     cur_span = next_span;
  1628.  
  1629.                     while (dx--)
  1630.                     {
  1631.                         t++;
  1632.                         color += dc;
  1633.                     }
  1634.                 }
  1635.             }
  1636.         }
  1637.  
  1638.         left++;
  1639.         right++;
  1640.         left_c++;
  1641.         right_c++;
  1642.     }
  1643. }
  1644.  
  1645. static POINTS
  1646. scan_calc_y_extrema (pts, y_min, y_max)
  1647.     POINTS pts;
  1648.     long *y_min, *y_max;
  1649. {
  1650.     POINT pt;
  1651.     POINTS tmp;
  1652.  
  1653.     *y_min = height + 1;
  1654.     *y_max = -1;
  1655.  
  1656.     while (pts)
  1657.     {
  1658.         pt = points_first (pts);
  1659.  
  1660.         if (point_y (pt) < *y_min)
  1661.         {
  1662.             *y_min = point_y (pt);
  1663.             tmp = pts;
  1664.         }
  1665.         if (point_y (pt) > *y_max)
  1666.             *y_max = point_y (pt);
  1667.  
  1668.         pts = points_rest (pts);
  1669.     }
  1670.  
  1671.     return tmp;
  1672. }
  1673.  
  1674. static POINTS
  1675. scan_calc_x_extrema (pts, x_min, x_max)
  1676.     POINTS pts;
  1677.     long *x_min, *x_max;
  1678. {
  1679.     POINT pt;
  1680.     POINTS tmp;
  1681.  
  1682.     *x_min = width + 1;
  1683.     *x_max = -1;
  1684.  
  1685.     while (pts)
  1686.     {
  1687.         pt = points_first (pts);
  1688.  
  1689.         if (point_x (pt) < *x_min)
  1690.         {
  1691.             *x_min = point_x (pt);
  1692.             tmp = pts;
  1693.         }
  1694.         if (point_x (pt) > *x_max)
  1695.             *x_max = point_x (pt);
  1696.  
  1697.         pts = points_rest (pts);
  1698.     }
  1699.  
  1700.     return tmp;
  1701. }
  1702.  
  1703. static long *
  1704. scan_calc_edge (buf, xs, xe, ys, ye)
  1705.     long *buf;
  1706.     long xs, xe;
  1707.     long ys, ye;
  1708. {
  1709.     long dx, dy;
  1710.     long error, inc;
  1711.  
  1712.     dx = xe - xs;
  1713.     dy = ye - ys;
  1714.  
  1715.     if (ABS (dx) > ABS (dy))
  1716.     {
  1717.         if (dx < 0)
  1718.         {
  1719.             inc = -1;
  1720.             dx = -dx;
  1721.         }
  1722.         else
  1723.         {
  1724.             inc = 1;
  1725.         }
  1726.  
  1727.         error = -dx /2;
  1728.         while (xs != xe)
  1729.         {
  1730.             error += dy;
  1731.             if (error > 0)
  1732.             {
  1733.                 error -= dx;
  1734.                 *buf++ = xs;
  1735.             }
  1736.  
  1737.             xs += inc;
  1738.         }
  1739.     }
  1740.     else
  1741.     {
  1742.         error = -dy /2;
  1743.         if (dx < 0)
  1744.         {
  1745.             dx = -dx;
  1746.             inc = -1;
  1747.         }
  1748.         else
  1749.         {
  1750.             inc = 1;
  1751.         }
  1752.  
  1753.         while (ys++ < ye)
  1754.         {
  1755.             *buf++ = xs;
  1756.  
  1757.             error += dx;
  1758.             if (error > 0)
  1759.             {
  1760.                 error -= dy;
  1761.                 xs += inc;
  1762.             }
  1763.         }
  1764.     }
  1765.  
  1766.     return buf;
  1767. }
  1768.  
  1769. static long *
  1770. scan_calc_color (buf, is, ie, dy)
  1771.     long *buf, is, ie, dy;
  1772. {
  1773.     long di;
  1774.  
  1775.     di = (ie - is) / dy;
  1776.  
  1777.     while (dy--)
  1778.     {
  1779.         *buf++ = is;
  1780.         is += di;
  1781.     }
  1782.  
  1783.     return buf;
  1784. }
  1785.  
  1786. static void
  1787. make_span_buffer ()
  1788. {
  1789.     span_buffer = (SPAN *) ALLOC (sizeof (SPAN) * height);
  1790.     span_full = (BOOLEAN *) ALLOC (sizeof (BOOLEAN) * height);
  1791. }
  1792.  
  1793. static void
  1794. reset_span_buffer ()
  1795. {
  1796.     short i;
  1797.  
  1798.     for (i = 0; i < height; i++)
  1799.     {
  1800.         span_buffer[i] = make_span (0, width);
  1801.         span_full[i] = FALSE;
  1802.     }
  1803. }
  1804.  
  1805. static void
  1806. make_span_pool ()
  1807. {
  1808.     span_pool_size = SPAN_POOL_CHUNK;
  1809.     span_pool = (_SPAN *) ALLOC (sizeof (_SPAN) * span_pool_size);
  1810. }
  1811.  
  1812. static void
  1813. grow_span_pool ()
  1814. {
  1815. }
  1816.  
  1817. static void
  1818. reset_span_pool ()
  1819. {
  1820.     span_pool_index = 0;
  1821. }
  1822.  
  1823. static SPAN
  1824. make_span (xs, xe)
  1825.     short xs, xe;
  1826. {
  1827.     SPAN span;
  1828.  
  1829.     if (span_pool_index >= span_pool_size)
  1830.         fatal_error ("Ran out of spans");
  1831.  
  1832.     span = &span_pool[span_pool_index++];
  1833.     span->start = xs;
  1834.     span->end = xe;
  1835.     span->next = NULL;
  1836.  
  1837.     return span;
  1838. }
  1839.  
  1840. static short
  1841. span_trivial_reject (ys, ye)
  1842.     long ys, ye;
  1843. {
  1844.     short dy;
  1845.     BOOLEAN *full_spans;
  1846.  
  1847.     full_spans = &span_full[ys];
  1848.     dy = ye - ys;
  1849.  
  1850.     if (dy > 0)
  1851.         while (dy--)
  1852.             if (!(*full_spans++))
  1853.                 return FALSE;
  1854.  
  1855.     return TRUE;
  1856. }
  1857.  
  1858. static SPAN
  1859. span_add (xs, xe, y)
  1860.     long xs, xe, y;
  1861. {
  1862.     SPAN valid_span;
  1863.  
  1864.     if ((y < 0) || (y >= height) || span_full[y])
  1865.         return NULL;
  1866.  
  1867.     valid_span = span_valid (span_buffer[y], xs, xe);
  1868.     if (!valid_span)
  1869.         return NULL;
  1870.  
  1871.     span_buffer[y] = span_remove (span_buffer[y], xs, xe);
  1872.  
  1873.     if (!span_buffer[y])
  1874.         span_full[y] = TRUE;
  1875.  
  1876.     return valid_span;
  1877. }
  1878.  
  1879. static SPAN
  1880. span_valid (span, xs, xe)
  1881.     SPAN span;
  1882.     long xs, xe;
  1883. {
  1884.     SPAN valid_span;
  1885.     SPAN temp_span;
  1886.  
  1887.     valid_span = NULL;
  1888.     while (span)
  1889.     {
  1890.         if ((span->end >= xs) && (span->start <= xe))
  1891.         {
  1892.             if (valid_span)
  1893.             {
  1894.                 temp_span->next = make_span (MAX (span->start, xs), MIN (span->end, xe));
  1895.                 temp_span = temp_span->next;
  1896.             }
  1897.             else
  1898.             {
  1899.                 valid_span = make_span (MAX (span->start, xs), MIN (span->end, xe));
  1900.                 temp_span = valid_span;
  1901.             }
  1902.         }
  1903.  
  1904.         span = span->next;
  1905.     }
  1906.  
  1907.     return valid_span;
  1908. }
  1909.  
  1910. static SPAN
  1911. span_remove (span, xs, xe)
  1912.     SPAN span;
  1913.     long xs, xe;
  1914. {
  1915.     SPAN cur_span;
  1916.     SPAN prev_span;
  1917.     SPAN temp_span;
  1918.     short major_hack = 0;
  1919.  
  1920.     prev_span = NULL;
  1921.     cur_span = span;
  1922.     while (cur_span)
  1923.     {
  1924.         if ((xe >= cur_span->start) &&
  1925.             (xs <= cur_span->end))
  1926.         {
  1927.             if ((xe >= cur_span->end) &&
  1928.                 (xs <= cur_span->start))
  1929.             {
  1930.                 if (prev_span)
  1931.                 {
  1932.                     prev_span->next = cur_span->next;
  1933.                     cur_span = prev_span;
  1934.                 }
  1935.                 else
  1936.                 {
  1937.                     span = cur_span->next;
  1938.                     major_hack = 1;
  1939.                 }
  1940.             }
  1941.             else if (xe >= cur_span->end)
  1942.             {
  1943.                 cur_span->end = xs;
  1944.             }
  1945.             else if (xs <= cur_span->start)
  1946.             {
  1947.                 cur_span->start = xe;
  1948.             }
  1949.             else
  1950.             {
  1951.                 temp_span = make_span (MIN (xe, cur_span->end),
  1952.                 MAX (xe, cur_span->end));
  1953.  
  1954.                 temp_span->next = cur_span->next;
  1955.                 cur_span->end = xs;
  1956.                 cur_span->next = temp_span;
  1957.                 cur_span = cur_span->next;
  1958.             }
  1959.         }
  1960.  
  1961.         if (major_hack)
  1962.             major_hack = 0;
  1963.         else
  1964.             prev_span = cur_span;
  1965.         cur_span = cur_span->next;
  1966.     }
  1967.  
  1968.     return span;
  1969. }
  1970.