home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / gnu / gnulib / sipp / libsipp / renderin.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-02-17  |  48.8 KB  |  1,659 lines
  1. /**
  2.  ** sipp - SImple Polygon Processor
  3.  **
  4.  **  A general 3d graphic package
  5.  **
  6.  **  Copyright Equivalent Software HB  1992
  7.  **
  8.  ** This program is free software; you can redistribute it and/or modify
  9.  ** it under the terms of the GNU General Public License as published by
  10.  ** the Free Software Foundation; either version 1, or any later version.
  11.  ** This program is distributed in the hope that it will be useful,
  12.  ** but WITHOUT ANY WARRANTY; without even the implied warranty of
  13.  ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14.  ** GNU General Public License for more details.
  15.  ** You can receive a copy of the GNU General Public License from the
  16.  ** Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17.  **/
  18.  
  19. /**
  20.  ** rendering.c - Functions that handles rendering of the scene.
  21.  **/
  22.  
  23. #include <stdio.h>
  24. #include <sys/types.h>
  25. #ifndef NOMEMCPY
  26. #include <memory.h>
  27. #endif
  28.  
  29. #include <xalloca.h>
  30. #include <smalloc.h>
  31.  
  32. #include <lightsource.h>
  33. #include <geometric.h>
  34. #include <rendering.h>
  35. #include <pixel.h>
  36. #include <objects.h>
  37. #include <sipp.h>
  38. #include <sipp_bitmap.h>
  39. #include <viewpoint.h>
  40.  
  41.  
  42. char *SIPP_VERSION = "3.0";
  43.  
  44. /*
  45.  * Static global variables.
  46.  */
  47. static bool          show_backfaces;  /* Don't do backface culling */
  48. static bool          shadows;         /* Calculate shadows */
  49. static Edge        **y_bucket;        /* Y-bucket for edge lists. */
  50. static FILE         *image_file;      /* File to store image in      */
  51.                                       /* when rendering into a file. */
  52. static void        (*pixel_set)();    /* Pointer to function for setting  */
  53.                                       /* a pixel when rendering with user */
  54.                                       /* defined function.                */
  55. static void         *im_data;         /* Data to pixel_set() */
  56.  
  57.        int           depthmap_size;   /* Size of the depthmaps */
  58.  
  59.  
  60. /*
  61.  * Stack of transformation matrices used
  62.  * when traversing an object hierarchy.
  63.  */
  64. static struct tm_stack_t {
  65.     Transf_mat         mat;
  66.     struct tm_stack_t *next;
  67. } *tm_stack;
  68.  
  69. static Transf_mat      curr_mat;     /* Current transformation matrix */
  70.  
  71.  
  72.  
  73. /*
  74.  * Calculate the normal vector for all polygons in the polygon list PSTART.
  75.  *
  76.  * Check if the polygon is backfacing with respect to the current
  77.  * viewpoint.
  78.  *
  79.  * The normalized normal is added to a normal kept at each vertex
  80.  * in the polygon. This will produce, at each vertex, an average of the
  81.  * normals of the adjectent plygons.
  82.  */
  83. static void
  84. calc_normals(pstart, eyepoint)
  85.     Polygon *pstart;    /* Head of polygon list */
  86.     Vector   eyepoint;  /* Viewpoint transformed to local coordinate system */
  87. {
  88.     Polygon    *polyref;
  89.     Vertex    **vlist;
  90.     Vector      normal;
  91.     int         i, j;
  92.     double      plane_const;
  93.  
  94.  
  95.     for (polyref = pstart; polyref != NULL; polyref = polyref->next) {
  96.  
  97.         vlist = polyref->vertex;
  98.         MakeVector(normal, 0.0, 0.0, 0.0);
  99.  
  100.         for (i = 0; i < polyref->nvertices; i++) {
  101.             j = (i + 1) % polyref->nvertices;
  102.             normal.x += ((vlist[i]->pos.y - vlist[j]->pos.y)
  103.                          * (vlist[i]->pos.z + vlist[j]->pos.z));
  104.             normal.y += ((vlist[i]->pos.z - vlist[j]->pos.z)
  105.                          * (vlist[i]->pos.x + vlist[j]->pos.x));
  106.             normal.z += ((vlist[i]->pos.x - vlist[j]->pos.x)
  107.                          * (vlist[i]->pos.y + vlist[j]->pos.y));
  108.         }
  109.         vecnorm(&normal);
  110.  
  111.         /*
  112.          * Take care of backfacing polygons.
  113.          */
  114.         plane_const = VecDot(normal, vlist[0]->pos);
  115.         if (VecDot(eyepoint, normal) - plane_const <= 0.0) {
  116.             if (show_backfaces) {
  117.                 polyref->backface = FALSE;
  118.                 VecNegate(normal);
  119.             } else {
  120.                 polyref->backface = TRUE;
  121.             }
  122.         } else {
  123.             polyref->backface = FALSE;
  124.         }
  125.             
  126.         /*
  127.          * Add the calculated normal to all vertices
  128.          * in the poygon. This will result in an avaraged normal
  129.          * at each vertex after all polygons have been processed.
  130.          */
  131.         for (i = 0; i < polyref->nvertices; i++) {
  132.             VecAdd(vlist[i]->normal, vlist[i]->normal, normal)
  133.         }
  134.     }
  135. }
  136.  
  137.  
  138.  
  139. /*
  140.  * Walk around a polygon, create the surrounding
  141.  * edges and sort them into the y-bucket.
  142.  */
  143. static void
  144. create_edges(view_vert, polygon, surface, render_mode)
  145.     View_coord *view_vert;
  146.     int         polygon;
  147.     Surface    *surface;
  148.     int         render_mode;
  149. {
  150.     Edge       *edge;
  151.     View_coord *view_ref, *last;
  152.     int         nderiv, y1, y2;
  153.     double      deltay;
  154.     double      x1, x2;
  155.     double      hden1, hden2;
  156.     Vector      world1, world2;
  157.     Vector      norm1, norm2;
  158.     Vector      text1, text2;
  159.  
  160.  
  161.     view_ref = last = view_vert;
  162.  
  163.     do {
  164.         view_ref = view_ref->next;
  165.  
  166.         /*
  167.          * If we are drawing a line image we dont need
  168.          * to build a complete edgelist. We draw the
  169.          * lines directly instead.
  170.          *
  171.          * Since many lines are drawn twice (edges shared between
  172.          * two polygons) and many line drawing algorithms are unsymmetrical
  173.          * we need to make sure lines are always drawn in the same
  174.          * direction
  175.          */
  176.         if (render_mode == LINE) {
  177.             if (view_ref->view.y < view_ref->next->view.y) {
  178.                 (*pixel_set)(im_data, 
  179.                               (int)(view_ref->view.x + 0.5), 
  180.                               (int)(view_ref->view.y + 0.5),
  181.                               (int)(view_ref->next->view.x + 0.5), 
  182.                               (int)(view_ref->next->view.y + 0.5));
  183.             } else {
  184.                 (*pixel_set)(im_data, 
  185.                               (int)(view_ref->next->view.x + 0.5), 
  186.                               (int)(view_ref->next->view.y + 0.5), 
  187.                               (int)(view_ref->view.x + 0.5), 
  188.                               (int)(view_ref->view.y + 0.5));
  189.             }
  190.             continue;
  191.         }
  192.  
  193.         /*
  194.          * Check if the slope of the edge is positive or negative
  195.          * or zero.
  196.          */
  197.         y1 = (int)(view_ref->view.y + 0.5);
  198.         y2 = (int)(view_ref->next->view.y + 0.5);
  199.         deltay = (double)(y2 - y1);
  200.  
  201.         if (deltay > 0.0)
  202.             nderiv = 1;
  203.         else if (deltay < 0.0)
  204.             nderiv = -1;
  205.         else
  206.             nderiv = 0;
  207.  
  208.         /*
  209.          * Check if the edge is horizontal. In that case we
  210.          * just skip it.
  211.          */
  212.         if (nderiv != 0) {
  213.  
  214.             edge = (Edge *)smalloc(sizeof(Edge));
  215.  
  216.             x1 = view_ref->view.x;
  217.             x2 = view_ref->next->view.x;
  218.             hden1 = view_ref->hden;
  219.             hden2 = view_ref->next->hden;
  220.             world1 = view_ref->world;
  221.             world2 = view_ref->next->world;
  222.             norm1 = view_ref->normal;
  223.             norm2 = view_ref->next->normal;
  224.             text1 = view_ref->texture;
  225.             text2 = view_ref->next->texture;
  226.  
  227.             deltay = 1.0 / fabs(deltay);
  228.  
  229.             if (nderiv > 0) {       
  230.  
  231.                 /*
  232.                  * The edge has positive slope
  233.                  */
  234.                 edge->ystart = y2;
  235.                 edge->ystop = y1;
  236.                 edge->xstart = x2;
  237.                 edge->hden = hden2;
  238.                 edge->world = world2;
  239.                 edge->normal = norm2;
  240.                 edge->texture = text2;
  241.                 edge->xstep = (x1 - x2) * deltay;
  242.                 edge->hdenstep = (hden1 - hden2) * deltay;
  243.                 if (render_mode != FLAT) {
  244.                     VecComb(edge->normalstep, deltay, norm1, -deltay, norm2);
  245.                     VecComb(edge->texturestep, deltay, text1, -deltay, text2);
  246.                     if (render_mode == PHONG) {
  247.                         VecComb(edge->worldstep, deltay, world1, 
  248.                                 -deltay, world2);
  249.                     }
  250.                 }
  251.  
  252.             } else {
  253.  
  254.                 /*
  255.                  * The edge has negative slope.
  256.                  */
  257.                 edge->ystart = y1;
  258.                 edge->ystop = y2;
  259.                 edge->xstart = x1;
  260.                 edge->hden = hden1;
  261.                 edge->world = world1;
  262.                 edge->normal = norm1;
  263.                 edge->texture = text1;
  264.                 edge->xstep = (x2 - x1) * deltay;
  265.                 edge->hdenstep = (hden2 - hden1) * deltay;
  266.                 if (render_mode != FLAT) {
  267.                     VecComb(edge->normalstep, deltay, norm2, -deltay, norm1);
  268.                     VecComb(edge->texturestep, deltay, text2, -deltay, text1);
  269.                     if (render_mode == PHONG) {
  270.                         VecComb(edge->worldstep, deltay, world2, 
  271.                                 -deltay, world1);
  272.                     }
  273.                 }
  274.             }
  275.             edge->polygon = polygon;
  276.             edge->surface = surface;
  277.             edge->next = y_bucket[edge->ystart];
  278.             y_bucket[edge->ystart] = edge;
  279.         }
  280.     } while (view_ref != last);
  281. }
  282.  
  283.  
  284.  
  285. /*
  286.  * Calculate a new vertex by interpolation between
  287.  * V1 and V2.
  288.  */
  289. static View_coord *
  290. interpolate(v1, v2, ratio)
  291.     View_coord *v1, *v2;
  292.     double      ratio;
  293. {
  294.     View_coord *tmp;
  295.  
  296.     tmp = (View_coord *)smalloc(sizeof(View_coord));
  297.  
  298.     tmp->hden = (1.0 - ratio) * v1->hden + ratio * v2->hden;
  299.     VecComb(tmp->view, 1.0 - ratio, v1->view, ratio, v2->view);
  300.     VecComb(tmp->world, 1.0 - ratio, v1->world, ratio, v2->world);
  301.     VecComb(tmp->normal, 1.0 - ratio, v1->normal, ratio, v2->normal);
  302.     VecComb(tmp->texture, 1.0 - ratio, v1->texture, ratio, v2->texture);
  303.     tmp->next = NULL;
  304.  
  305.     return tmp;
  306. }
  307.  
  308.  
  309.  
  310. /*
  311.  * Reset the averaged normals in the vertex tree P.
  312.  */
  313. static void
  314. reset_normals(vref)
  315.     Vertex *vref;
  316. {
  317.     if (vref != NULL) {
  318.         MakeVector(vref->normal, 0.0, 0.0, 0.0);
  319.         reset_normals(vref->big);
  320.         reset_normals(vref->sml);
  321.     }
  322. }
  323.  
  324.  
  325.  
  326. /*
  327.  * Clip a polygon using the Sutherland-Hodgeman algorithm for
  328.  * reentrant clipping;
  329.  */
  330. #define XMIN 0
  331. #define XMAX 1
  332. #define YMIN 2
  333. #define YMAX 3
  334. #define ZMIN 4
  335. #define ZMAX 5
  336.  
  337. static View_coord *
  338. polygon_clip(vlist, plane, first_vert)
  339.     View_coord *vlist;
  340.     int         plane;
  341.     bool        first_vert;
  342. {
  343.     static View_coord   *first;
  344.     static View_coord   *curr;
  345.     View_coord          *out1;
  346.     View_coord          *out2;
  347.     double               curr_limit;
  348.     double               first_limit;
  349.     double               vlist_limit;
  350.     double               ratio;
  351.     bool                 visible;
  352.  
  353.     out1 = out2 = NULL;
  354.  
  355.     if (vlist == NULL) {
  356.  
  357.         /*
  358.          * Did we get an empty list from the start?
  359.          */
  360.         if (first_vert) {
  361.             return NULL;
  362.         }
  363.  
  364.         /*
  365.          * Last vertex, close the polygon.
  366.          */
  367.         ratio = 0.0;
  368.         curr_limit = curr->view.z * sipp_current_camera->focal_ratio;
  369.         first_limit = first->view.z * sipp_current_camera->focal_ratio;
  370.  
  371.         switch (plane) {
  372.  
  373.           case XMIN:
  374.             if ((curr->view.x < -curr_limit 
  375.                  && first->view.x >= -first_limit)
  376.                 || (curr->view.x >= -curr_limit 
  377.                     && first->view.x < -first_limit)) {
  378.                 ratio = fabs(curr->view.x + curr_limit);
  379.                 ratio /= (ratio + fabs(first->view.x + first_limit)); 
  380.             }
  381.             break;
  382.  
  383.           case XMAX:
  384.             if ((curr->view.x <= curr_limit 
  385.                  && first->view.x > first_limit)
  386.                 || (curr->view.x > curr_limit 
  387.                     && first->view.x <= first_limit)) {
  388.                 ratio = fabs(curr->view.x - curr_limit);
  389.                 ratio /= (ratio + fabs(first->view.x - first_limit));
  390.             }
  391.             break;
  392.  
  393.           case YMIN:
  394.             if ((curr->view.y < -curr_limit 
  395.                  && first->view.y >= -first_limit)
  396.                 || (curr->view.y >= -curr_limit 
  397.                     && first->view.y < -first_limit)) {
  398.                 ratio = fabs(curr->view.y + curr_limit);
  399.                 ratio /= (ratio + fabs(first->view.y + first_limit));
  400.             }
  401.             break;
  402.  
  403.           case YMAX:
  404.             if ((curr->view.y <= curr_limit 
  405.                  && first->view.y > first_limit)
  406.                 || (curr->view.y > curr_limit 
  407.                     && first->view.y <= first_limit)) {
  408.                 ratio = fabs(curr->view.y - curr_limit);
  409.                 ratio /= (ratio + fabs(first->view.y - first_limit));
  410.             }
  411.             break;
  412.  
  413.           case ZMIN:
  414.             if ((curr->view.z < hither 
  415.                  && first->view.z >= hither)
  416.                 || (curr->view.z >= hither 
  417.                     && first->view.z < hither)) {
  418.                 ratio = fabs(curr->view.z - hither);
  419.                 ratio = ratio / (ratio + fabs(first->view.z - hither));
  420.             }
  421.             break;
  422.  
  423.           case ZMAX:
  424.             if ((curr->view.z <= yon 
  425.                  && first->view.z > yon)
  426.                 || (curr->view.z > yon 
  427.                     && first->view.z <= yon)) {
  428.                 ratio = fabs(curr->view.z - yon);
  429.                 ratio = ratio / (ratio + fabs(first->view.z - yon));
  430.             }
  431.             break;
  432.         }
  433.  
  434.         if (ratio != 0.0) {
  435.             out1 = interpolate(curr, first, ratio);
  436.             return out1;
  437.         } else {
  438.             return NULL;
  439.         }
  440.     }
  441.  
  442.     vlist_limit = vlist->view.z * sipp_current_camera->focal_ratio;
  443.     
  444.     if (first_vert) {
  445.         first = vlist;
  446.     } else {
  447.         ratio = 0.0;
  448.         curr_limit = curr->view.z * sipp_current_camera->focal_ratio;
  449.  
  450.         switch (plane) {
  451.  
  452.           case XMIN:
  453.             if ((curr->view.x < -curr_limit 
  454.                  && vlist->view.x >= -vlist_limit)
  455.                 || (curr->view.x >= -curr_limit 
  456.                     && vlist->view.x < -vlist_limit)) {
  457.                 ratio = fabs(curr->view.x + curr_limit);
  458.                 ratio /= (ratio + fabs(vlist->view.x + vlist_limit));
  459.             }
  460.             break;
  461.  
  462.           case XMAX:
  463.             if ((curr->view.x <= curr_limit 
  464.                  && vlist->view.x > vlist_limit)
  465.                 || (curr->view.x > curr_limit 
  466.                     && vlist->view.x <= vlist_limit)) {
  467.                 ratio = fabs(curr->view.x - curr_limit);
  468.                 ratio /= (ratio + fabs(vlist->view.x - vlist_limit));
  469.             }
  470.             break;
  471.  
  472.           case YMIN:
  473.             if ((curr->view.y < -curr_limit 
  474.                  && vlist->view.y >= -vlist_limit)
  475.                 || (curr->view.y >= -curr_limit 
  476.                     && vlist->view.y < -vlist_limit)) {
  477.                 ratio = fabs(curr->view.y + curr_limit);
  478.                 ratio /= (ratio + fabs(vlist->view.y + vlist_limit));
  479.             }
  480.             break;
  481.  
  482.           case YMAX:
  483.             if ((curr->view.y <= curr_limit 
  484.                  && vlist->view.y > vlist_limit)
  485.                 || (curr->view.y > curr_limit 
  486.                     && vlist->view.y <= vlist_limit)) {
  487.                 ratio = fabs(curr->view.y - curr_limit);
  488.                 ratio /= (ratio + fabs(vlist->view.y - vlist_limit));
  489.             }
  490.             break;
  491.  
  492.           case ZMIN:
  493.             if ((curr->view.z < hither 
  494.                  && vlist->view.z >= hither)
  495.                 || (curr->view.z >= hither 
  496.                     && vlist->view.z < hither)) {
  497.                 ratio = fabs(curr->view.z - hither);
  498.                 ratio = ratio / (ratio + fabs(vlist->view.z - hither));
  499.             }
  500.             break;
  501.  
  502.           case ZMAX:
  503.             if ((curr->view.z <= yon 
  504.                  && vlist->view.z > yon)
  505.                 || (curr->view.z > yon 
  506.                     && vlist->view.z <= yon)) {
  507.                 ratio = fabs(curr->view.z - yon);
  508.                 ratio = ratio / (ratio + fabs(vlist->view.z - yon));
  509.             }
  510.             break;
  511.         }
  512.  
  513.         if (ratio != 0.0) {
  514.             out1 = interpolate(curr, vlist, ratio);
  515.             out1->next = vlist;
  516.         }
  517.     }
  518.  
  519.     curr = vlist;
  520.     visible = FALSE;
  521.     switch (plane) {
  522.  
  523.       case XMIN:
  524.         visible = (curr->view.x >= -vlist_limit);
  525.         break;
  526.  
  527.       case XMAX:
  528.         visible = (curr->view.x <= vlist_limit);
  529.         break;
  530.  
  531.       case YMIN:
  532.         visible = (curr->view.y >= -vlist_limit);
  533.         break;
  534.  
  535.       case YMAX:
  536.         visible = (curr->view.y <= vlist_limit);
  537.         break;
  538.  
  539.       case ZMIN:
  540.         visible = (curr->view.z >= hither);
  541.         break;
  542.  
  543.       case ZMAX:
  544.         visible = (curr->view.z <= yon);
  545.         break;
  546.     }
  547.  
  548.     if (visible) {
  549.         out2 = curr;
  550.         out2->next = polygon_clip(curr->next, plane, FALSE);
  551.         return ((out1) ? (out1) : (out2));
  552.  
  553.     } else {
  554.         if (out1) {
  555.             out1->next = polygon_clip(curr->next, plane, FALSE);
  556.         } else {
  557.             out1 = polygon_clip(curr->next, plane, FALSE);
  558.         }
  559.         sfree(vlist);
  560.         return out1;
  561.     }
  562. }
  563.  
  564.  
  565.  
  566. /*
  567.  * Transform vertices into view coordinates. The transform is
  568.  * defined in MATRIX. Store the transformed vertices in a
  569.  * temporary list, create edges in the y_bucket.
  570.  */
  571. static void
  572. transf_vertices(vertex, nvertices, surface, view_mat, tr_mat, 
  573.                 xsiz, ysiz, render_mode)
  574.     Vertex     *vertex[];
  575.     int         nvertices;
  576.     Surface    *surface;
  577.     Transf_mat *view_mat;
  578.     Transf_mat *tr_mat;
  579.     double      xsiz, ysiz;
  580.     int         render_mode;
  581. {
  582.     static int  polygon = 0;        /* incremented for each call to provide */
  583.                                     /* unique polygon id numbers */
  584.     View_coord *nhead;
  585.     View_coord *view_ref;
  586.     View_coord *mark;
  587.     Color       color;                    
  588.     Color       opacity;
  589.     double      persp_factor;
  590.     double      minsize;
  591.     double      tmp;
  592.     int         i;
  593.  
  594.     nhead = NULL;
  595.     minsize = ((xsiz > ysiz) ? ysiz : xsiz);
  596.  
  597.     for (i = 0; i < nvertices; i++) {
  598.  
  599.         view_ref = (View_coord *)smalloc(sizeof(View_coord));
  600.  
  601.         /* Transform the normal (world coordinates) but */
  602.         /* do not include the translation part. */
  603.         view_ref->normal.x = (vertex[i]->normal.x * tr_mat->mat[0][0]
  604.                               + vertex[i]->normal.y * tr_mat->mat[1][0]
  605.                               + vertex[i]->normal.z * tr_mat->mat[2][0]);
  606.         view_ref->normal.y = (vertex[i]->normal.x * tr_mat->mat[0][1]
  607.                               + vertex[i]->normal.y * tr_mat->mat[1][1]
  608.                               + vertex[i]->normal.z * tr_mat->mat[2][1]);
  609.         view_ref->normal.z = (vertex[i]->normal.x * tr_mat->mat[0][2]
  610.                               + vertex[i]->normal.y * tr_mat->mat[1][2]
  611.                               + vertex[i]->normal.z * tr_mat->mat[2][2]);
  612.  
  613.         /* Transform the vertex to its new world coordinates. */
  614.         point_transform(&view_ref->world, &vertex[i]->pos, tr_mat);
  615.  
  616.         /* Transform the vertex into view coordinates. */
  617.         point_transform(&view_ref->view, &vertex[i]->pos, view_mat);
  618.  
  619.         /* Texture coordinates is not affected by transformations. */
  620.         VecCopy(view_ref->texture, vertex[i]->texture);
  621.  
  622.         view_ref->next = nhead;
  623.         nhead = view_ref;
  624.     }
  625.  
  626.     /* 
  627.      * Clip the resulting polygon. We need to do this
  628.      * before the perpective transformation to keep texture
  629.      * coordinates correct.
  630.      */
  631.     nhead = polygon_clip(nhead, ZMIN, TRUE);
  632.     nhead = polygon_clip(nhead, ZMAX, TRUE);
  633.     if (xsiz > ysiz) {
  634.         tmp = sipp_current_camera->focal_ratio;
  635.         sipp_current_camera->focal_ratio *= xsiz / ysiz;
  636.         nhead = polygon_clip(nhead, XMIN, TRUE);
  637.         nhead = polygon_clip(nhead, XMAX, TRUE);
  638.         sipp_current_camera->focal_ratio = tmp;
  639.         nhead = polygon_clip(nhead, YMIN, TRUE);
  640.         nhead = polygon_clip(nhead, YMAX, TRUE);
  641.     } else {
  642.         tmp = sipp_current_camera->focal_ratio;
  643.         sipp_current_camera->focal_ratio *= ysiz / xsiz;
  644.         nhead = polygon_clip(nhead, YMIN, TRUE);
  645.         nhead = polygon_clip(nhead, YMAX, TRUE);
  646.         sipp_current_camera->focal_ratio = tmp;
  647.         nhead = polygon_clip(nhead, XMIN, TRUE);
  648.         nhead = polygon_clip(nhead, XMAX, TRUE);
  649.     }
  650.  
  651.     if (nhead == NULL) {    /* Nothing left? */
  652.         return;
  653.     }
  654.  
  655.  
  656.     
  657.     /*
  658.      * If we are flat shading, we need a color for the polygon.
  659.      * We call the shader at the first vertex to get this.
  660.      * (This is not quite correct since the normal here is
  661.      * an averaged normal of the surrounding polygons)
  662.      */
  663.     if (render_mode == FLAT) {
  664.         Vector view_vec;
  665.  
  666.         VecSub(view_vec, sipp_current_camera->position, nhead->world);
  667.         vecnorm(&view_vec);
  668.         (*surface->shader)
  669.             (&nhead->world, &nhead->normal, &nhead->texture, 
  670.              &view_vec, lightsrc_stack, surface->surface, 
  671.              &color, &opacity);
  672.     }
  673.  
  674.  
  675.     /*
  676.      * Walk around the new (clipped and transformed) polygon and 
  677.      * transform it into perspective screen coordinates.
  678.      * We also do a homgenous division of texture and world coordinates
  679.      * and store a "homogenous denominator" so we can do rational
  680.      * linear interpolation.
  681.      * If we are doing gouraud shading we call the shader at each
  682.      * vertex.
  683.      * Last we tie the head and tail together forming a cirkular
  684.      * list, this simplifies edge creation.
  685.      */
  686.     for (view_ref = nhead;; view_ref = view_ref->next) {
  687.         persp_factor = view_ref->view.z * sipp_current_camera->focal_ratio; 
  688.         view_ref->view.x  = view_ref->view.x * minsize / persp_factor + xsiz;
  689.         view_ref->view.y  = view_ref->view.y * minsize / persp_factor + ysiz;
  690.         view_ref->hden = 1.0 / persp_factor;
  691.  
  692.         if (render_mode == PHONG) {
  693.             VecScalMul(view_ref->world, view_ref->hden, view_ref->world);
  694.             VecScalMul(view_ref->texture, view_ref->hden, view_ref->texture);
  695.  
  696.         } else if (render_mode == GOURAUD) {
  697.             Vector view_vec;
  698.             
  699.             VecSub(view_vec, sipp_current_camera->position, view_ref->world);
  700.             vecnorm(&view_vec);
  701.             (*surface->shader)
  702.                 (&view_ref->world, &view_ref->normal, &view_ref->texture, 
  703.                  &view_vec, lightsrc_stack, surface->surface, 
  704.                  &color, &opacity);
  705.         } 
  706.  
  707.         if (render_mode == GOURAUD || render_mode == FLAT) {
  708.             MakeVector(view_ref->normal, color.red, color.grn, color.blu);
  709.             MakeVector(view_ref->texture, 
  710.                        opacity.red, opacity.grn, opacity.blu);
  711.         } 
  712.  
  713.         if (view_ref->next == NULL) {
  714.             view_ref->next = nhead;
  715.             break;
  716.         }
  717.     }
  718.  
  719.     create_edges(nhead, polygon++, surface, render_mode);
  720.  
  721.     /*
  722.      * Free the memory used by the transformed polygon.
  723.      */
  724.     mark = nhead;
  725.     do {
  726.         view_ref = nhead;
  727.         nhead = nhead->next;
  728.         sfree(view_ref);
  729.     } while (nhead != mark);
  730. }
  731.  
  732.  
  733.  
  734.  
  735. /*
  736.  * Read edge pairs from the edge list EDGE_LIST. Walk along the scanline
  737.  * and interpolate z value, world coordinates, texture coordinates and 
  738.  * normal vector as we go. Call the shader and store in scanline pixel buffer.
  739.  */
  740. static void
  741. render_scanline(res, scanline, edge_list, render_mode)
  742.     int      res;
  743.     int     *scanline;
  744.     Edge    *edge_list;
  745.     int      render_mode;
  746. {
  747.     Edge  *startedge, *stopedge;
  748.     double hden, hdenstep;
  749.     Vector world, worldstep;
  750.     Vector norm, normstep;
  751.     Vector text, textstep;
  752.     double zfact;
  753.     double real_z;
  754.     Vector real_world;
  755.     Vector real_text;
  756.     Vector view_vec;
  757.     double ratio;
  758.     double w;
  759.     Color  color;
  760.     Color  opacity;
  761.     int    xstart, xstop;
  762.     int    i, j;
  763.     
  764.     startedge = edge_list;
  765.     stopedge = NULL;
  766.  
  767.     zfact = 1.0 / sipp_current_camera->focal_ratio;
  768.  
  769.     while (startedge != NULL) {
  770.  
  771.         stopedge = startedge->next;
  772.         xstart = (int)(startedge->xstart + 0.5);
  773.         xstop  = (int)(stopedge->xstart - 0.5);
  774.         hden = startedge->hden;
  775.         VecCopy(world, startedge->world);
  776.         VecCopy(norm, startedge->normal);
  777.         VecCopy(text, startedge->texture);
  778.  
  779.         if (xstart < xstop) {
  780.             ratio = 1.0 / (double)(xstop - xstart);
  781.             hdenstep = (stopedge->hden - hden) * ratio;
  782.             if (render_mode != FLAT) {
  783.                 VecComb(normstep, ratio, stopedge->normal, -ratio, norm);
  784.                 VecComb(textstep, ratio, stopedge->texture, -ratio, text);
  785.                 if (render_mode == PHONG) {
  786.                     VecComb(worldstep, ratio, stopedge->world, -ratio, world);
  787.                 }
  788.             }
  789.  
  790.         } else {
  791.             hdenstep = 0.0;
  792.             MakeVector(worldstep, 0.0, 0.0, 0.0);
  793.             MakeVector(normstep, 0.0, 0.0, 0.0);
  794.             MakeVector(textstep, 0.0, 0.0, 0.0);
  795.         }
  796.  
  797.         for (i = xstart; i <= xstop; i++) {
  798.             real_z = zfact / hden;
  799.             if (pixel_visible(real_z, scanline[i])) {
  800.                 if (render_mode == PHONG) {
  801.                     VecScalMul(real_text, 1.0 / hden, text);
  802.                     VecScalMul(real_world, 1.0 / hden, world);
  803.                     VecSub(view_vec, sipp_current_camera->position, 
  804.                            real_world);
  805.                     vecnorm(&view_vec);
  806.                     (*startedge->surface->shader)
  807.                         (&real_world, &norm, &real_text, 
  808.                          &view_vec, lightsrc_stack, 
  809.                          startedge->surface->surface, &color, &opacity);
  810.                     scanline[i] = pixel_insert(scanline[i], 
  811.                                                real_z, &color, &opacity);
  812.                     
  813.                 } else {
  814.                     scanline[i] = pixel_insert(scanline[i], real_z, 
  815.                                                (Color *)&norm, 
  816.                                                (Color *)&text);
  817.                 }
  818.             }
  819.             
  820.             hden += hdenstep;
  821.             if (render_mode != FLAT) {
  822.                 VecAdd(norm, norm, normstep);
  823.                 VecAdd(text, text, textstep);
  824.                 if (render_mode == PHONG) {
  825.                     VecAdd(world, world, worldstep);
  826.                 }
  827.             }
  828.         }
  829.         startedge = stopedge->next;
  830.     }
  831. }
  832.  
  833.  
  834.  
  835.  
  836. /*
  837.  * Insert an edge into an edge list. Edges belonging to the same
  838.  * polygon must be inserted sorted in x, so that edge pairs are
  839.  * created.
  840.  */
  841. static Edge *
  842. insert_edge(edge_list, edge)
  843.     Edge *edge_list, *edge;
  844. {
  845.     Edge *edge_ref1;
  846.     Edge *edge_ref2;
  847.  
  848.     /*
  849.      * If list is empty, just insert the edge.
  850.      */
  851.     if (edge_list == NULL) {
  852.     edge->next = NULL;
  853.         return edge;
  854.     }
  855.  
  856.     /*
  857.      * If the edges to our polygon is first in the list, check
  858.      * if our edge should be inserted first.
  859.      */
  860.     if (edge_list->polygon == edge->polygon) {
  861.         if (edge_list->xstart > edge->xstart) {
  862.             edge->next = edge_list;
  863.             return edge;
  864.         } else if ((((int)(edge_list->xstart + 0.5))
  865.                     == ((int)(edge->xstart + 0.5)))
  866.                    && (edge_list->xstep > edge->xstep)) {
  867.             edge->next = edge_list;
  868.             return edge;
  869.         }
  870.     }
  871.  
  872.     /*
  873.      * Check if our polygon is in the list at all.
  874.      */
  875.     edge_ref1 = edge_list;
  876.     edge_ref2 = edge_list->next;
  877.     if (edge_ref1->polygon != edge->polygon) {
  878.         while (edge_ref2 != NULL && edge_ref2->polygon != edge->polygon) {
  879.             edge_ref1 = edge_ref2;
  880.             edge_ref2 = edge_ref2->next;
  881.         }
  882.     }
  883.  
  884.     /*
  885.      * Insert the edge at the right place,  sorted in x if our 
  886.      * polygon was found, otherwize last in the list.
  887.      */
  888.     while (1) {
  889.         if (edge_ref2 == NULL) {
  890.             edge->next = edge_ref2;
  891.             edge_ref1->next = edge;
  892.             break;
  893.         } else if ((edge_ref2->polygon != edge->polygon)
  894.                    || ((edge_ref2->xstart > edge->xstart)
  895.                        || ((((int)(edge_ref2->xstart + 0.5)) 
  896.                             == ((int)(edge->xstart + 0.5)))
  897.                            && (edge_ref2->xstep > edge->xstep)))) {
  898.             edge->next = edge_ref2;
  899.             edge_ref1->next = edge;
  900.             break;
  901.         } else {
  902.             edge_ref1 = edge_ref2;
  903.             edge_ref2 = edge_ref2->next;
  904.         }
  905.     }
  906.  
  907.     return edge_list;
  908. }
  909.         
  910.  
  911.  
  912. /*
  913.  * Merge two edge lists.
  914.  */
  915. static Edge *
  916. merge_edge_lists(list1, list2)
  917.     Edge *list1, *list2;
  918. {
  919.     Edge *eref1, *eref2, *next;
  920.     
  921.     if (list2 == NULL)
  922.         return list1;
  923.  
  924.     eref1 = list1;
  925.     eref2 = list2;
  926.     do {
  927.         next = eref2->next;
  928.         eref1 = insert_edge(eref1, eref2);
  929.     eref2 = next;
  930.     } while (eref2 != NULL);
  931.  
  932.     return eref1;
  933. }
  934.  
  935.  
  936.  
  937. /*
  938.  * Store a rendered line on the place indicated by STORAGE_MODE.
  939.  */
  940. static void
  941. store_line(buf, npixels, line, storage_mode)
  942.     u_char *buf;
  943.     int            npixels;
  944.     int            line;
  945.     int            storage_mode;
  946. {
  947.     int i, j;
  948.  
  949.     switch (storage_mode) {
  950.       case PPM_FILE:
  951.         fwrite(buf, sizeof(u_char), npixels * 3, image_file);
  952.         fflush(image_file);
  953.         break;
  954.  
  955.       case FUNCTION:
  956.         for (i = 0, j = 0; j < npixels; j++, i += 3) {
  957.             (*pixel_set)(im_data, j, line, buf[i], buf[i + 1], buf[i + 2]);
  958.         }
  959.         break;
  960.  
  961.       default:
  962.         break;
  963.     }
  964. }
  965.  
  966.  
  967.  
  968. static void
  969. buffer_clear(res, scanline)
  970.     int    res;
  971.     int   *scanline;
  972. {
  973.     int         i;
  974.     
  975.     for (i = 0; i < res; i++) {
  976.         scanline[i] = -1;
  977.     }
  978. }
  979.  
  980.     
  981.  
  982. /*
  983.  * Allocate the needed buffers. Create a list of active edges and
  984.  * move down the y-bucket, inserting and deleting edges from this
  985.  * active list as we go. Call render_scanline for each scanline and
  986.  * do an average filtering before storing the scanline.
  987.  */
  988. static void
  989. scan_and_render(xres, yres, storage_mode, render_mode, oversampl, field)
  990.     int   xres, yres;
  991.     int   storage_mode;
  992.     int   render_mode;
  993.     int   oversampl;
  994.     int   field;
  995. {
  996.     Edge         *active_list;
  997.     Edge         *edgep, *edgep2;
  998.     int         **linebuf;
  999.     u_char       *line;
  1000.     int           curr_line;
  1001.     int           scanline;
  1002.     int           y, next_edge;
  1003.     Color        *pixel_color;
  1004.     Color         sum;
  1005.     int           i, j, k;
  1006.     
  1007.     line = (u_char *)smalloc(xres * 3 * sizeof(u_char));
  1008.     linebuf  = (int **)alloca(oversampl * sizeof(int *));
  1009.     for (i = 0; i < oversampl; i++) {
  1010.         linebuf[i] = (int *)scalloc(xres, sizeof(int));
  1011.     }
  1012.     pixels_setup(xres);
  1013.  
  1014.  
  1015.     if (storage_mode == PPM_FILE) {
  1016.         fprintf(image_file, "P6\n");
  1017.         /*****
  1018.         fprintf(image_file, "#Image rendered with SIPP %s\n", SIPP_VERSION);
  1019.         *****/
  1020.  
  1021.         switch (field) {
  1022.           case BOTH:
  1023.             fprintf(image_file, "%d\n%d\n255\n", xres / oversampl, 
  1024.                                                  yres / oversampl);
  1025.             break;
  1026.  
  1027.           case EVEN:
  1028.             /*****
  1029.             fprintf(image_file, "#Image field containing EVEN lines\n");
  1030.             *****/
  1031.             fprintf(image_file, "%d\n%d\n255\n", xres / oversampl, 
  1032.                     ((yres / oversampl) & 1)
  1033.                     ? ((yres / oversampl) >> 1) + 1
  1034.                     :  (yres / oversampl) >> 1);
  1035.             break;
  1036.  
  1037.           case ODD:
  1038.             /*****
  1039.             fprintf(image_file, "#Image field containing ODD lines\n");
  1040.             *****/
  1041.             fprintf(image_file, "%d\n%d\n255\n", xres / oversampl, 
  1042.                                                  (yres / oversampl) >> 1);
  1043.             break;
  1044.         }
  1045.     }
  1046.  
  1047.     y = yres - 1;
  1048.     active_list = NULL;
  1049.     curr_line = 0;
  1050.     scanline = 0;
  1051.  
  1052.     while (y >= 0) {
  1053.  
  1054.         active_list = merge_edge_lists(active_list, y_bucket[y]);
  1055.         y_bucket[y] = NULL;
  1056.         next_edge = y - 1;
  1057.  
  1058.         while (next_edge >=0 && y_bucket[next_edge] == NULL)
  1059.             next_edge--;
  1060.         while (y > next_edge) {
  1061.  
  1062.             if (field == BOTH || (scanline & 1) == field) {
  1063.                 buffer_clear(xres, linebuf[curr_line]);
  1064.                 render_scanline(xres, linebuf[curr_line], 
  1065.                                 active_list, render_mode); 
  1066.             }
  1067.  
  1068.             if (++curr_line == oversampl) {
  1069.  
  1070.                 if (field == BOTH || (scanline & 1) == field) {
  1071.                     /*
  1072.                      * Average the pixel.
  1073.                      */
  1074.                     for (i = 0; i < ((xres / oversampl)); i++) {
  1075.                         sum.red = 0.0;
  1076.                         sum.grn = 0.0;
  1077.                         sum.blu = 0.0;
  1078.                         for (j = i * oversampl;                          
  1079.                              j < (i * oversampl + oversampl); j++) {
  1080.                             for (k = 0; k < oversampl; k++) {
  1081.                                 pixel_color = pixel_collect(*(linebuf[k] + j));
  1082.                                 if (pixel_color != NULL) {
  1083.                                     sum.red += pixel_color->red;
  1084.                                     sum.grn += pixel_color->grn;
  1085.                                     sum.blu += pixel_color->blu;
  1086.                                 }
  1087.                             }
  1088.                         }
  1089.                         line[i * 3]    = (u_char)(sum.red 
  1090.                                                   / (oversampl * oversampl) 
  1091.                                                   * 255.0 + 0.5);
  1092.                         line[i * 3 + 1] = (u_char)(sum.grn
  1093.                                                    / (oversampl * oversampl) 
  1094.                                                    * 255.0 + 0.5);
  1095.                         line[i * 3 + 2] = (u_char)(sum.blu 
  1096.                                                    / (oversampl * oversampl) 
  1097.                                                    * 255.0 + 0.5);
  1098.                     }
  1099.                     store_line(line, xres / oversampl, scanline, 
  1100.                                storage_mode);
  1101.                     pixels_reinit();
  1102.                 }
  1103.  
  1104.                 curr_line = 0;
  1105.                 scanline++;
  1106.             }
  1107.             
  1108.         if (active_list != NULL) {
  1109.                 
  1110.             edgep2 = active_list;
  1111.             edgep = active_list->next;
  1112.             while (edgep != NULL) {
  1113.                 if (edgep->ystart <= (edgep->ystop + 1)) {
  1114.                         edgep2->next = edgep->next;
  1115.                 sfree(edgep);
  1116.                     edgep = edgep2->next;
  1117.             } else {
  1118.                 edgep2 = edgep;
  1119.                 edgep = edgep->next;
  1120.             }
  1121.                 }
  1122.                 
  1123.               if (active_list->ystart <= (active_list->ystop + 1)) {
  1124.                 edgep = active_list;
  1125.             active_list = active_list->next;
  1126.                 sfree(edgep);
  1127.             }
  1128.                 
  1129.             edgep = active_list;
  1130.             while (edgep != NULL) {
  1131.                 edgep->ystart--;
  1132.             edgep->xstart += edgep->xstep;
  1133.                     edgep->hden += edgep->hdenstep;
  1134.                     if (render_mode != FLAT) {
  1135.                         VecAdd(edgep->normal, edgep->normal,
  1136.                                edgep->normalstep); 
  1137.                         VecAdd(edgep->texture, edgep->texture,
  1138.                                edgep->texturestep); 
  1139.                         if (render_mode == PHONG) {
  1140.                             VecAdd(edgep->world, edgep->world, 
  1141.                                    edgep->worldstep);
  1142.                         }
  1143.                     }
  1144.             edgep = edgep->next;
  1145.             }
  1146.         }
  1147.             y--;
  1148.     }
  1149.     }
  1150.     sfree(line);
  1151.     for (i = 0; i < oversampl; i++) {
  1152.         sfree(linebuf[i]);
  1153.     }
  1154.     pixels_free();
  1155. }
  1156.  
  1157.  
  1158.  
  1159. /*
  1160.  * Push the current transformation matrix on the matrix stack.
  1161.  */
  1162. static void
  1163. matrix_push()
  1164. {
  1165.     struct tm_stack_t *new_tm;
  1166.  
  1167.     new_tm = (struct tm_stack_t *)smalloc(sizeof(struct tm_stack_t));
  1168.     MatCopy(&new_tm->mat, &curr_mat);
  1169.     new_tm->next = tm_stack;
  1170.     tm_stack     = new_tm;
  1171. }
  1172.  
  1173.  
  1174. /*
  1175.  * Pop the top of the matrix stack and make
  1176.  * it the new current transformation matrix.
  1177.  */
  1178. static void
  1179. matrix_pop()
  1180. {
  1181.     struct tm_stack_t *tmp;
  1182.  
  1183.     MatCopy(&curr_mat, &tm_stack->mat);
  1184.     tmp = tm_stack;
  1185.     tm_stack = tm_stack->next;
  1186.     sfree(tmp);
  1187. }
  1188.  
  1189.  
  1190.  
  1191. /*
  1192.  * Traverse an object hierarchy, transform each object
  1193.  * according to its transformation matrix.
  1194.  * Transform all polygons in the object to view coordinates.
  1195.  * Build the edge lists in y_bucket.
  1196.  */
  1197. static void
  1198. traverse_object_tree(object, view_mat, xres, yres, render_mode)
  1199.     Object      *object;
  1200.     Transf_mat  *view_mat;
  1201.     int          xres, yres;
  1202.     int          render_mode;
  1203. {
  1204.     Object      *objref;
  1205.     Surface     *surfref;
  1206.     Polygon     *polyref;
  1207.     Vector       eyepoint, tmp;
  1208.     Transf_mat   loc_view_mat;
  1209.     double       m[3][4], dtmp;
  1210.     int          i, j;
  1211.  
  1212.  
  1213.     if (object == NULL) {
  1214.         return;
  1215.     }
  1216.  
  1217.     for (objref = object; objref != NULL; objref = objref->next) {
  1218.  
  1219.         matrix_push();
  1220.         mat_mul(&curr_mat, &objref->transf, &curr_mat);
  1221.         mat_mul(&loc_view_mat, &curr_mat, view_mat);
  1222.  
  1223.         VecCopy(tmp, sipp_current_camera->position);
  1224.  
  1225.         /*
  1226.          * Do an inverse transformation of the viewpoint to use
  1227.          * when doing backface culling (in calc_normals()).
  1228.          */
  1229.         tmp.x -= curr_mat.mat[3][0];
  1230.         tmp.y -= curr_mat.mat[3][1];
  1231.         tmp.z -= curr_mat.mat[3][2];
  1232.         m[0][0] = curr_mat.mat[0][0] ; m[0][1] = curr_mat.mat[1][0];
  1233.         m[0][2] = curr_mat.mat[2][0] ; m[0][3] = tmp.x;
  1234.         m[1][0] = curr_mat.mat[0][1] ; m[1][1] = curr_mat.mat[1][1];
  1235.         m[1][2] = curr_mat.mat[2][1] ; m[1][3] = tmp.y;
  1236.         m[2][0] = curr_mat.mat[0][2] ; m[2][1] = curr_mat.mat[1][2];
  1237.         m[2][2] = curr_mat.mat[2][2] ; m[2][3] = tmp.z;
  1238.  
  1239.         if (m[0][0] == 0.0) {
  1240.             if (m[1][0] != 0.0)
  1241.                 j = 1;
  1242.             else
  1243.                 j = 2;
  1244.             for (i = 0; i < 4; i++) {
  1245.                 dtmp     = m[0][i];
  1246.                 m[0][i] = m[j][i];
  1247.                 m[j][i] = dtmp;
  1248.             }
  1249.         }
  1250.         
  1251.         for (j = 1; j < 3; j++) {
  1252.             m[j][0] /= (-m[0][0]);
  1253.             for (i = 1; i < 4; i++)
  1254.                 m[j][i] += m[0][i] * m[j][0];
  1255.         }
  1256.         
  1257.         if (m[1][1] == 0.0)
  1258.             for (i = 1; i < 4; i++) {
  1259.                 dtmp     = m[1][i];
  1260.                 m[1][i] = m[2][i];
  1261.                 m[2][i] = dtmp;
  1262.             }
  1263.         
  1264.         if (m[1][1] != 0.0) {
  1265.             m[2][1] /= (-m[1][1]);
  1266.             m[2][2] += m[1][2] * m[2][1];
  1267.             m[2][3] += m[1][3] * m[2][1];
  1268.         }
  1269.         
  1270.         eyepoint.z = m[2][3] / m[2][2];
  1271.         eyepoint.y = (m[1][3] - eyepoint.z * m[1][2]) / m[1][1];
  1272.         eyepoint.x = (m[0][3] - eyepoint.z * m[0][2] 
  1273.                       - eyepoint.y * m[0][1]) / m[0][0];
  1274.  
  1275.         for (surfref = objref->surfaces; surfref != NULL; 
  1276.              surfref = surfref->next) {
  1277.  
  1278.             calc_normals(surfref->polygons, eyepoint);
  1279.  
  1280.             for (polyref = surfref->polygons; polyref != NULL; 
  1281.                  polyref = polyref->next) {
  1282.  
  1283.                 if (!polyref->backface) {
  1284.                     transf_vertices(polyref->vertex, polyref->nvertices, 
  1285.                                     surfref, &loc_view_mat, &curr_mat, 
  1286.                                     (double)xres / 2.0, (double)yres / 2.0, 
  1287.                                     render_mode);
  1288.                 }
  1289.  
  1290.             }
  1291.             reset_normals(surfref->vertices);
  1292.  
  1293.         }
  1294.         traverse_object_tree(objref->sub_obj, view_mat, xres, yres, 
  1295.                              render_mode); 
  1296.         matrix_pop();
  1297.     }
  1298. }
  1299.  
  1300.  
  1301.  
  1302. /*
  1303.  * Render one scanline in a depth-map. This is just a stripped
  1304.  * version of render_scanline().
  1305.  */
  1306. static void
  1307. render_dmap_line(dmap_line, edge_list)
  1308.     float       *dmap_line;
  1309.     Edge        *edge_list;
  1310. {
  1311.     Edge  *startedge, *stopedge;
  1312.     double hden, hdenstep;
  1313.     float  zfact;
  1314.     float  real_z;
  1315.     double ratio;
  1316.     int    xstart, xstop;
  1317.     int    i;
  1318.     
  1319.     startedge = edge_list;
  1320.     stopedge = NULL;
  1321.  
  1322.     zfact = (float)(1.0 / sipp_current_camera->focal_ratio);
  1323.  
  1324.     while (startedge != NULL) {
  1325.  
  1326.         stopedge = startedge->next;
  1327.         xstart = (int)(startedge->xstart + 0.5);
  1328.         xstop  = (int)(stopedge->xstart + 0.5);
  1329.         hden = startedge->hden;
  1330.  
  1331.         if (xstart < xstop) {
  1332.             hdenstep = (stopedge->hden - hden) / (double)(xstop - xstart);
  1333.         } else {
  1334.             hdenstep = 0.0;
  1335.         }
  1336.  
  1337.         for (i = xstart; i <= xstop; i++) {
  1338.             real_z = zfact / hden;
  1339.             if (real_z < dmap_line[i]) {
  1340.                 dmap_line[i] = real_z;
  1341.             }
  1342.             hden += hdenstep;
  1343.         }
  1344.         startedge = stopedge->next;
  1345.     }
  1346. }
  1347.  
  1348.  
  1349.  
  1350. /*
  1351.  * Similar function to scan_and_render() used when rendering depthmaps.
  1352.  * Allocate the needed buffers. Create a list of active edges and
  1353.  * move down the y-bucket, inserting and deleting edges from this
  1354.  * active list as we go. Call render_dmap_line() for each scanline.
  1355.  */
  1356. static void
  1357. scan_depthmap(d_map, mat)
  1358.     float      *d_map;
  1359. {
  1360.     Edge            *active_list;
  1361.     Edge            *edgep, *edgep2;
  1362.     int              y, next_edge;
  1363.     
  1364.     y = depthmap_size - 1;
  1365.     active_list = NULL;
  1366.  
  1367.     while (y >= 0) {
  1368.  
  1369.         active_list = merge_edge_lists(active_list, y_bucket[y]);
  1370.         y_bucket[y] = NULL;
  1371.         next_edge = y - 1;
  1372.  
  1373.         while (next_edge >=0 && y_bucket[next_edge] == NULL)
  1374.             next_edge--;
  1375.  
  1376.         while (y > next_edge) {
  1377.  
  1378.             render_dmap_line(d_map + (depthmap_size - 1 - y) * depthmap_size, 
  1379.                              active_list); 
  1380.  
  1381.         if (active_list != NULL) {
  1382.                 
  1383.             edgep2 = active_list;
  1384.             edgep = active_list->next;
  1385.             while (edgep != NULL) {
  1386.                 if (edgep->ystart <= (edgep->ystop + 1)) {
  1387.                         edgep2->next = edgep->next;
  1388.                 sfree(edgep);
  1389.                     edgep = edgep2->next;
  1390.             } else {
  1391.                 edgep2 = edgep;
  1392.                 edgep = edgep->next;
  1393.             }
  1394.                 }
  1395.                 
  1396.               if (active_list->ystart <= (active_list->ystop + 1)) {
  1397.                 edgep = active_list;
  1398.             active_list = active_list->next;
  1399.                 sfree(edgep);
  1400.             }
  1401.                 
  1402.             edgep = active_list;
  1403.             while (edgep != NULL) {
  1404.                 edgep->ystart--;
  1405.             edgep->xstart += edgep->xstep;
  1406.                     edgep->hden += edgep->hdenstep;
  1407.             edgep = edgep->next;
  1408.             }
  1409.         }
  1410.             y--;
  1411.     }
  1412.     }
  1413. }
  1414.  
  1415.  
  1416.  
  1417. /*
  1418.  * Render depthmaps for the lightsources that will cast
  1419.  * shadows. Place the camera in the position of each lightsource
  1420.  * in turn and render the depthmap. Store the matrix converting
  1421.  * from world coordinates to depthmap coordinates together with 
  1422.  * the depthmap.
  1423.  */
  1424. static void
  1425. render_depthmaps()
  1426. {
  1427.     Transf_mat      view_mat;
  1428.     Vector          view_vec;
  1429.     Lightsource    *lp;
  1430.     Camera         *tmp_camera;
  1431.     Camera         *light_camera;
  1432.     bool            backface_tmp;
  1433.  
  1434.     y_bucket = (Edge **)scalloc(depthmap_size, sizeof(Edge *));
  1435.  
  1436.     tmp_camera = sipp_current_camera;
  1437.     light_camera = camera_create();
  1438.     *light_camera = *sipp_current_camera;
  1439.     backface_tmp = show_backfaces;
  1440.     show_backfaces = FALSE;
  1441.  
  1442.     for (lp = lightsrc_stack; lp != NULL; lp = lp->next) {
  1443.         if (lp->shadow.active) {
  1444.             VecCopy(light_camera->position, 
  1445.                     ((Spot_light_info *)(lp->info))->pos);
  1446.             VecCopy(light_camera->lookat, 
  1447.                     ((Spot_light_info *)(lp->info))->point);
  1448.             light_camera->focal_ratio = lp->shadow.fov_factor;
  1449.             camera_use(light_camera);
  1450.             VecSub(view_vec, light_camera->position, light_camera->lookat);
  1451.             lp->shadow.bias = VecLen(view_vec) * 0.005;
  1452.             get_view_transf(&view_mat, light_camera, PHONG);
  1453.             lp->shadow.matrix = view_mat;
  1454.  
  1455.             MatCopy(&curr_mat, &ident_matrix);
  1456.             
  1457.             traverse_object_tree(sipp_world, &view_mat, 
  1458.                                  depthmap_size - 1, depthmap_size - 1, 
  1459.                                  PHONG);
  1460.             
  1461.             scan_depthmap(lp->shadow.d_map);
  1462.         }
  1463.     }
  1464.  
  1465.     camera_use(tmp_camera);
  1466.     camera_destruct(light_camera);
  1467.     show_backfaces = backface_tmp;
  1468.     sfree(y_bucket);
  1469. }
  1470.     
  1471.  
  1472.  
  1473. /*
  1474.  * "Main" functions in rendering. Allocate y-bucket, transform vertices
  1475.  * into viewing coordinates, make edges and sort them into the y-bucket.
  1476.  * Call scan_and_render to do the real work.
  1477.  */
  1478. static void
  1479. render_main(xres, yres, storage_mode, render_mode, oversampling, field)
  1480.     int   xres, yres;
  1481.     int   storage_mode;
  1482.     int   render_mode;
  1483.     int   oversampling;
  1484.     int   field;
  1485. {
  1486.     Transf_mat      view_mat;
  1487.     int i;
  1488.  
  1489.     if (render_mode != LINE) {
  1490.         if (shadows) {
  1491.             depthmaps_create();
  1492.             render_depthmaps();
  1493.         }
  1494.         xres *= oversampling;
  1495.         yres *= oversampling;
  1496.         y_bucket = (Edge **)scalloc(yres, sizeof(Edge *));
  1497.  
  1498.     } else if (storage_mode == PBM_FILE) {
  1499.         im_data = sipp_bitmap_create(xres, yres);
  1500.         pixel_set = sipp_bitmap_line;
  1501.     }
  1502.  
  1503.     get_view_transf(&view_mat, sipp_current_camera, render_mode);
  1504.     MatCopy(&curr_mat, &ident_matrix);
  1505.     
  1506.     traverse_object_tree(sipp_world, &view_mat, xres - 1, yres - 1, 
  1507.                          render_mode);
  1508.  
  1509.     if (render_mode != LINE) {
  1510.         scan_and_render(xres, yres, storage_mode, render_mode, 
  1511.                         oversampling, field);
  1512.         sfree(y_bucket);
  1513.         if (shadows) {
  1514.             depthmaps_destruct();
  1515.         }
  1516.  
  1517.     } else if (storage_mode == PBM_FILE) {
  1518.         sipp_bitmap_write(image_file, im_data);
  1519.         sipp_bitmap_destruct(im_data);
  1520.     }
  1521. }
  1522.     
  1523.  
  1524. void
  1525. render_image_file(xres, yres, im_file, render_mode, oversampling)
  1526.     int   xres, yres;
  1527.     FILE *im_file;
  1528.     int   render_mode;
  1529.     int   oversampling;
  1530. {
  1531.     image_file = im_file;
  1532.  
  1533.     if (render_mode == LINE) {
  1534.         render_main(xres, yres, PBM_FILE, render_mode, oversampling, BOTH);
  1535.     } else {
  1536.         render_main(xres, yres, PPM_FILE, render_mode, oversampling, BOTH);
  1537.     }
  1538. }
  1539.  
  1540.  
  1541. void
  1542. render_image_func(xres, yres, pixel_func, data, render_mode, oversampling)
  1543.     int     xres, yres;
  1544.     void  (*pixel_func)();
  1545.     void   *data;
  1546.     int     render_mode;
  1547.     int     oversampling;
  1548. {
  1549.     im_data = data;
  1550.     pixel_set = pixel_func;
  1551.     render_main(xres, yres, FUNCTION, render_mode, oversampling, BOTH);
  1552. }
  1553.  
  1554.  
  1555. void
  1556. render_field_file(xres, yres, im_file, render_mode, oversampling, field)
  1557.     int   xres, yres;
  1558.     FILE *im_file;
  1559.     int   render_mode;
  1560.     int   oversampling;
  1561.     int   field;
  1562. {
  1563.     image_file = im_file;
  1564.  
  1565.     if (render_mode == LINE) {
  1566.         fprintf(stderr, "render_field_file: Can't render line fields\n");
  1567.         return;
  1568.     } else {
  1569.         render_main(xres, yres, PPM_FILE, render_mode, oversampling, field);
  1570.     }
  1571. }
  1572.  
  1573.  
  1574. void
  1575. render_field_func(xres, yres, pixel_func, data, render_mode, 
  1576.                   oversampling, field)
  1577.     int     xres, yres;
  1578.     void  (*pixel_func)();
  1579.     void   *data;
  1580.     int     render_mode;
  1581.     int     oversampling;
  1582.     int     field;
  1583. {
  1584.     if (render_mode == LINE) {
  1585.         fprintf(stderr, "render_field_func: Can't render line fields\n");
  1586.         return;
  1587.     }
  1588.  
  1589.     im_data = data;
  1590.     pixel_set = pixel_func;
  1591.     render_main(xres, yres, FUNCTION, render_mode, oversampling, field);
  1592. }
  1593.  
  1594.  
  1595.  
  1596.  
  1597. /*============= Functions that handles global initializations==============*/
  1598.  
  1599. /*
  1600.  * If called with TRUE as argument, no backface culling will 
  1601.  * be performed. If a polygon is backfacing it will be rendered
  1602.  * as facing in the opposit direction.
  1603.  */
  1604. void
  1605. sipp_show_backfaces(flag)
  1606.     bool flag;
  1607. {
  1608.     show_backfaces = flag;
  1609. }
  1610.  
  1611.  
  1612. /*
  1613.  * If called with TRUE, objects will cast shadows. The second
  1614.  * argument is then used as the size of the depthmaps.
  1615.  */
  1616. void
  1617. sipp_shadows(flag, size)
  1618.     bool flag;
  1619.     int  size;
  1620. {
  1621.     if ((shadows = flag) == TRUE) {
  1622.         if (size != 0) {
  1623.             depthmap_size = size;
  1624.         } else {
  1625.             depthmap_size = 256;
  1626.         }
  1627.     }
  1628. }
  1629.  
  1630.  
  1631.  
  1632. /*
  1633.  * Set the backgroung color of the image.
  1634.  */
  1635. void
  1636. sipp_background(red, grn, blu)
  1637.     double red, grn, blu;
  1638. {
  1639.     sipp_bgcol.red = red;
  1640.     sipp_bgcol.grn = grn;
  1641.     sipp_bgcol.blu = blu;
  1642. }
  1643.  
  1644.  
  1645.  
  1646. /*
  1647.  * Necessary initializations.
  1648.  */
  1649. void
  1650. sipp_init()
  1651. {
  1652.     objects_init();
  1653.     lightsource_init();
  1654.     camera_init();
  1655.     sipp_show_backfaces(FALSE);
  1656.     sipp_shadows(FALSE, 0);
  1657.     sipp_background(0.0, 0.0, 0.0);
  1658. }
  1659.