home *** CD-ROM | disk | FTP | other *** search
/ Graphics Programming Black Book (Special Edition) / BlackBook.bin / disk1 / source / chapter67 / l67_1.c < prev   
Text File  |  1997-06-18  |  17KB  |  401 lines
  1. // Part of Win32 program to demonstrate z-sorted spans. Whitespace
  2. // removed for space reasons. Full source code, with whitespace,
  3. // available from ftp.idsoftware.com/mikeab/ddjzsort.zip.
  4. #define MAX_SPANS           10000
  5. #define MAX_SURFS           1000
  6. #define MAX_EDGES           5000
  7. typedef struct surf_s {
  8.     struct surf_s   *pnext, *pprev;
  9.     int             color, visxstart, state;
  10.     double          zinv00, zinvstepx, zinvstepy;
  11. } surf_t;
  12. typedef struct edge_s {
  13.     int             x, xstep, leading;
  14.     surf_t          *psurf;
  15.     struct edge_s   *pnext, *pprev, *pnextremove;
  16. } edge_t;
  17. // Span, edge, and surface lists
  18. span_t  spans[MAX_SPANS];
  19. edge_t  edges[MAX_EDGES];
  20. surf_t  surfs[MAX_SURFS];
  21. // Bucket list of new edges to add on each scan line
  22. edge_t  newedges[MAX_SCREEN_HEIGHT];
  23. // Bucket list of edges to remove on each scan line
  24. edge_t  *removeedges[MAX_SCREEN_HEIGHT];
  25. // Head and tail for the active edge list
  26. edge_t  edgehead, edgetail;
  27. // Edge used as sentinel of new edge lists
  28. edge_t  maxedge = {0x7FFFFFFF};
  29. // Head/tail/sentinel/background surface of active surface stack
  30. surf_t  surfstack;
  31. // pointers to next available surface and edge
  32. surf_t  *pavailsurf;
  33. edge_t  *pavailedge;
  34.  
  35. // Returns true if polygon faces the viewpoint, assuming a clockwise
  36. // winding of vertices as seen from the front.
  37. int PolyFacesViewer(polygon_t *ppoly, plane_t *pplane)
  38. {
  39.     int     i;
  40.     point_t viewvec;
  41.  
  42.     for (i=0 ; i<3 ; i++)
  43.         viewvec.v[i] = ppoly->verts[0].v[i] - currentpos.v[i];
  44.     // Use an epsilon here so we don't get polygons tilted so
  45.     // sharply that the gradients are unusable or invalid
  46.     if (DotProduct (&viewvec, &pplane->normal) < -0.01)
  47.         return 1;
  48.     return 0;
  49. }
  50.  
  51. // Add the polygon's edges to the global edge table.
  52. void AddPolygonEdges (plane_t *plane, polygon2D_t *screenpoly)
  53. {
  54.     double  distinv, deltax, deltay, slope;
  55.     int     i, nextvert, numverts, temp, topy, bottomy, height;
  56.     edge_t  *pedge;
  57.  
  58.     numverts = screenpoly->numverts;
  59.     // Clamp the polygon's vertices just in case some very near
  60.     // points have wandered out of range due to floating-point
  61.     // imprecision
  62.     for (i=0 ; i<numverts ; i++) {
  63.         if (screenpoly->verts[i].x < -0.5)
  64.             screenpoly->verts[i].x = -0.5;
  65.         if (screenpoly->verts[i].x > ((double)DIBWidth - 0.5))
  66.             screenpoly->verts[i].x = (double)DIBWidth - 0.5;
  67.         if (screenpoly->verts[i].y < -0.5)
  68.             screenpoly->verts[i].y = -0.5;
  69.         if (screenpoly->verts[i].y > ((double)DIBHeight - 0.5))
  70.             screenpoly->verts[i].y = (double)DIBHeight - 0.5;
  71.     }
  72.  
  73.     // Add each edge in turn
  74.     for (i=0 ; i<numverts ; i++) {
  75.         nextvert = i + 1;
  76.         if (nextvert >= numverts)
  77.             nextvert = 0;
  78.         topy = (int)ceil(screenpoly->verts[i].y);
  79.         bottomy = (int)ceil(screenpoly->verts[nextvert].y);
  80.         height = bottomy - topy;
  81.         if (height == 0)
  82.             continue;       // doesn't cross any scan lines
  83.         if (height < 0) {
  84.             // Leading edge
  85.             temp = topy;
  86.             topy = bottomy;
  87.             bottomy = temp;
  88.             pavailedge->leading = 1;
  89.             deltax = screenpoly->verts[i].x -
  90.                      screenpoly->verts[nextvert].x;
  91.             deltay = screenpoly->verts[i].y -
  92.                      screenpoly->verts[nextvert].y;
  93.             slope = deltax / deltay;
  94.             // Edge coordinates are in 16.16 fixed point
  95.             pavailedge->xstep = (int)(slope * (float)0x10000);
  96.             pavailedge->x = (int)((screenpoly->verts[nextvert].x +
  97.                 ((float)topy - screenpoly->verts[nextvert].y) *
  98.                 slope) * (float)0x10000);
  99.         } else {
  100.             // Trailing edge
  101.             pavailedge->leading = 0;
  102.             deltax = screenpoly->verts[nextvert].x -
  103.                      screenpoly->verts[i].x;
  104.             deltay = screenpoly->verts[nextvert].y -
  105.                      screenpoly->verts[i].y;
  106.             slope = deltax / deltay;
  107.             // Edge coordinates are in 16.16 fixed point
  108.             pavailedge->xstep = (int)(slope * (float)0x10000);
  109.             pavailedge->x = (int)((screenpoly->verts[i].x +
  110.                 ((float)topy - screenpoly->verts[i].y) * slope) *
  111.                 (float)0x10000);
  112.         }
  113.         // Put the edge on the list to be added on top scan
  114.         pedge = &newedges[topy];
  115.         while (pedge->pnext->x < pavailedge->x)
  116.             pedge = pedge->pnext;
  117.         pavailedge->pnext = pedge->pnext;
  118.         pedge->pnext = pavailedge;
  119.         // Put the edge on the list to be removed after final scan
  120.         pavailedge->pnextremove = removeedges[bottomy - 1];
  121.         removeedges[bottomy - 1] = pavailedge;
  122.         // Associate the edge with the surface we'll create for
  123.         // this polygon
  124.         pavailedge->psurf = pavailsurf;
  125.         // Make sure we don't overflow the edge array
  126.         if (pavailedge < &edges[MAX_EDGES])
  127.             pavailedge++;
  128.     }
  129.     // Create the surface, so we'll know how to sort and draw from
  130.     // the edges
  131.     pavailsurf->state = 0;
  132.     pavailsurf->color = currentcolor;
  133.     // Set up the 1/z gradients from the polygon, calculating the
  134.     // base value at screen coordinate 0,0 so we can use screen
  135.     // coordinates directly when calculating 1/z from the gradients
  136.     distinv = 1.0 / plane->distance;
  137.     pavailsurf->zinvstepx = plane->normal.v[0] * distinv *
  138.             maxscreenscaleinv * (fieldofview / 2.0);
  139.     pavailsurf->zinvstepy = -plane->normal.v[1] * distinv *
  140.             maxscreenscaleinv * (fieldofview / 2.0);
  141.     pavailsurf->zinv00 = plane->normal.v[2] * distinv -
  142.             xcenter * pavailsurf->zinvstepx -
  143.             ycenter * pavailsurf->zinvstepy;
  144.     // Make sure we don't overflow the surface array
  145.     if (pavailsurf < &surfs[MAX_SURFS])
  146.         pavailsurf++;
  147. }
  148.  
  149. // Scan all the edges in the global edge table into spans.
  150. void ScanEdges (void)
  151. {
  152.     int     x, y;
  153.     double  fx, fy, zinv, zinv2;
  154.     edge_t  *pedge, *pedge2, *ptemp;
  155.     span_t  *pspan;
  156.     surf_t  *psurf, *psurf2;
  157.  
  158.     pspan = spans;
  159.     // Set up the active edge list as initially empty, containing
  160.     // only the sentinels (which are also the background fill). Most
  161.     // of these fields could be set up just once at start-up
  162.     edgehead.pnext = &edgetail;
  163.     edgehead.pprev = NULL;
  164.     edgehead.x = -0xFFFF;           // left edge of screen
  165.     edgehead.leading = 1;
  166.     edgehead.psurf = &surfstack;
  167.     edgetail.pnext = NULL;          // mark edge of list
  168.     edgetail.pprev = &edgehead;
  169.     edgetail.x = DIBWidth << 16;    // right edge of screen
  170.     edgetail.leading = 0;
  171.     edgetail.psurf = &surfstack;
  172.     // The background surface is the entire stack initially, and
  173.     // is infinitely far away, so everything sorts in front of it.
  174.     // This could be set just once at start-up
  175.     surfstack.pnext = surfstack.pprev = &surfstack;
  176.     surfstack.color = 0;
  177.     surfstack.zinv00 = -999999.0;
  178.     surfstack.zinvstepx = surfstack.zinvstepy = 0.0;
  179.     for (y=0 ; y<DIBHeight ; y++) {
  180.         fy = (double)y;
  181.         // Sort in any edges that start on this scan
  182.         pedge = newedges[y].pnext;
  183.         pedge2 = &edgehead;
  184.         while (pedge != &maxedge) {
  185.             while (pedge->x > pedge2->pnext->x)
  186.                 pedge2 = pedge2->pnext;
  187.             ptemp = pedge->pnext;
  188.             pedge->pnext = pedge2->pnext;
  189.             pedge->pprev = pedge2;
  190.             pedge2->pnext->pprev = pedge;
  191.             pedge2->pnext = pedge;
  192.             pedge2 = pedge;
  193.             pedge = ptemp;
  194.         }
  195.         // Scan out the active edges into spans
  196.         // Start out with the left background edge already inserted,
  197.         // and the surface stack containing only the background
  198.         surfstack.state = 1;
  199.         surfstack.visxstart = 0;
  200.         for (pedge=edgehead.pnext ; pedge ; pedge=pedge->pnext) {
  201.             psurf = pedge->psurf;
  202.             if (pedge->leading) {
  203.                 // It's a leading edge. Figure out where it is
  204.                 // relative to the current surfaces and insert in
  205.                 // the surface stack; if it's on top, emit the span
  206.                 // for the current top.
  207.                 // First, make sure the edges don't cross
  208.                 if (++psurf->state == 1) {
  209.                     fx = (double)pedge->x * (1.0 / (double)0x10000);
  210.                     // Calculate the surface's 1/z value at this pixel
  211.                     zinv = psurf->zinv00 + psurf->zinvstepx * fx +
  212.                             psurf->zinvstepy * fy;
  213.                     // See if that makes it a new top surface
  214.                     psurf2 = surfstack.pnext;
  215.                     zinv2 = psurf2->zinv00 + psurf2->zinvstepx * fx +
  216.                             psurf2->zinvstepy * fy;
  217.                     if (zinv >= zinv2) {
  218.                         // It's a new top surface
  219.                         // emit the span for the current top
  220.                         x = (pedge->x + 0xFFFF) >> 16;
  221.                         pspan->count = x - psurf2->visxstart;
  222.                         if (pspan->count > 0) {
  223.                             pspan->y = y;
  224.                             pspan->x = psurf2->visxstart;
  225.                             pspan->color = psurf2->color;
  226.                             // Make sure we don't overflow
  227.                             // the span array
  228.                             if (pspan < &spans[MAX_SPANS])
  229.                                 pspan++;
  230.                         }
  231.                         psurf->visxstart = x;
  232.                         // Add the edge to the stack
  233.                         psurf->pnext = psurf2;
  234.                         psurf2->pprev = psurf;
  235.                         surfstack.pnext = psurf;
  236.                         psurf->pprev = &surfstack;
  237.                     } else {
  238.                         // Not a new top; sort into the surface stack.
  239.                         // Guaranteed to terminate due to sentinel
  240.                         // background surface
  241.                         do {
  242.                             psurf2 = psurf2->pnext;
  243.                             zinv2 = psurf2->zinv00 +
  244.                                     psurf2->zinvstepx * fx +
  245.                                     psurf2->zinvstepy * fy;
  246.                         } while (zinv < zinv2);
  247.                         // Insert the surface into the stack
  248.                         psurf->pnext = psurf2;
  249.                         psurf->pprev = psurf2->pprev;
  250.                         psurf2->pprev->pnext = psurf;
  251.                         psurf2->pprev = psurf;
  252.                     }
  253.                 }
  254.             } else {
  255.                 // It's a trailing edge; if this was the top surface,
  256.                 // emit the span and remove it.
  257.                 // First, make sure the edges didn't cross
  258.                 if (--psurf->state == 0) {
  259.                     if (surfstack.pnext == psurf) {
  260.                         // It's on top, emit the span
  261.                         x = ((pedge->x + 0xFFFF) >> 16);
  262.                         pspan->count = x - psurf->visxstart;
  263.                         if (pspan->count > 0) {
  264.                             pspan->y = y;
  265.                             pspan->x = psurf->visxstart;
  266.                             pspan->color = psurf->color;
  267.                             // Make sure we don't overflow
  268.                             // the span array
  269.                             if (pspan < &spans[MAX_SPANS])
  270.                                 pspan++;
  271.                         }
  272.                         psurf->pnext->visxstart = x;
  273.                     }
  274.                     // Remove the surface from the stack
  275.                     psurf->pnext->pprev = psurf->pprev;
  276.                     psurf->pprev->pnext = psurf->pnext;
  277.                 }
  278.             }
  279.         }
  280.         // Remove edges that are done
  281.         pedge = removeedges[y];
  282.         while (pedge) {
  283.             pedge->pprev->pnext = pedge->pnext;
  284.             pedge->pnext->pprev = pedge->pprev;
  285.             pedge = pedge->pnextremove;
  286.         }
  287.         // Step the remaining edges one scan line, and re-sort
  288.         for (pedge=edgehead.pnext ; pedge != &edgetail ; ) {
  289.             ptemp = pedge->pnext;
  290.             // Step the edge
  291.             pedge->x += pedge->xstep;
  292.             // Move the edge back to the proper sorted location,
  293.             // if necessary
  294.             while (pedge->x < pedge->pprev->x) {
  295.                 pedge2 = pedge->pprev;
  296.                 pedge2->pnext = pedge->pnext;
  297.                 pedge->pnext->pprev = pedge2;
  298.                 pedge2->pprev->pnext = pedge;
  299.                 pedge->pprev = pedge2->pprev;
  300.                 pedge->pnext = pedge2;
  301.                 pedge2->pprev = pedge;
  302.             }
  303.             pedge = ptemp;
  304.         }
  305.     }
  306.     pspan->x = -1;  // mark the end of the list
  307. }
  308.  
  309. // Draw all the spans that were scanned out.
  310. void DrawSpans (void)
  311. {
  312.     span_t  *pspan;
  313.     for (pspan=spans ; pspan->x != -1 ; pspan++)
  314.         memset (pDIB + (DIBPitch * pspan->y) + pspan->x,
  315.                 pspan->color,
  316.                 pspan->count);
  317. }
  318.  
  319. // Clear the lists of edges to add and remove on each scan line.
  320. void ClearEdgeLists(void)
  321. {
  322.     int i;
  323.     for (i=0 ; i<DIBHeight ; i++) {
  324.         newedges[i].pnext = &maxedge;
  325.         removeedges[i] = NULL;
  326.     }
  327. }
  328.  
  329. // Render the current state of the world to the screen.
  330. void UpdateWorld()
  331. {
  332.     HPALETTE        holdpal;
  333.     HDC             hdcScreen, hdcDIBSection;
  334.     HBITMAP         holdbitmap;
  335.     polygon2D_t     screenpoly;
  336.     polygon_t       *ppoly, tpoly0, tpoly1, tpoly2;
  337.     convexobject_t  *pobject;
  338.     int             i, j, k;
  339.     plane_t         plane;
  340.     point_t         tnormal;
  341.  
  342.     UpdateViewPos();
  343.     SetUpFrustum();
  344.     ClearEdgeLists();
  345.     pavailsurf = surfs;
  346.     pavailedge = edges;
  347.     // Draw all visible faces in all objects
  348.     pobject = objecthead.pnext;
  349.     while (pobject != &objecthead) {
  350.         ppoly = pobject->ppoly;
  351.         for (i=0 ; i<pobject->numpolys ; i++) {
  352.             // Move the polygon relative to the object center
  353.             tpoly0.numverts = ppoly[i].numverts;
  354.             for (j=0 ; j<tpoly0.numverts ; j++) {
  355.                 for (k=0 ; k<3 ; k++)
  356.                     tpoly0.verts[j].v[k] = ppoly[i].verts[j].v[k] +
  357.                             pobject->center.v[k];
  358.             }
  359.             if (PolyFacesViewer(&tpoly0, &ppoly[i].plane)) {
  360.                 if (ClipToFrustum(&tpoly0, &tpoly1)) {
  361.                     currentcolor = ppoly[i].color;
  362.                     TransformPolygon (&tpoly1, &tpoly2);
  363.                     ProjectPolygon (&tpoly2, &screenpoly);
  364.                     // Move the polygon's plane into viewspace
  365.                     // First move it into worldspace (object relative)
  366.                     tnormal = ppoly[i].plane.normal;
  367.                     plane.distance = ppoly[i].plane.distance +
  368.                         DotProduct (&pobject->center, &tnormal);
  369.                     // Now transform it into viewspace
  370.                     // Determine the distance from the viewpont
  371.                     plane.distance -=
  372.                           DotProduct (¤tpos, &tnormal);
  373.                     // Rotate the normal into view orientation
  374.                     plane.normal.v[0] =
  375.                             DotProduct (&tnormal, &vright);
  376.                     plane.normal.v[1] =
  377.                             DotProduct (&tnormal, &vup);
  378.                     plane.normal.v[2] =
  379.                             DotProduct (&tnormal, &vpn);
  380.                     AddPolygonEdges (&plane, &screenpoly);
  381.                 }
  382.             }
  383.         }
  384.         pobject = pobject->pnext;
  385.     }
  386.     ScanEdges ();
  387.     DrawSpans ();
  388.     // We've drawn the frame; copy it to the screen
  389.     hdcScreen = GetDC(hwndOutput);
  390.     holdpal = SelectPalette(hdcScreen, hpalDIB, FALSE);
  391.     RealizePalette(hdcScreen);
  392.     hdcDIBSection = CreateCompatibleDC(hdcScreen);
  393.     holdbitmap = SelectObject(hdcDIBSection, hDIBSection);
  394.     BitBlt(hdcScreen, 0, 0, DIBWidth, DIBHeight, hdcDIBSection,
  395.            0, 0, SRCCOPY);
  396.     SelectPalette(hdcScreen, holdpal, FALSE);
  397.     ReleaseDC(hwndOutput, hdcScreen);
  398.     SelectObject(hdcDIBSection, holdbitmap);
  399.     DeleteDC(hdcDIBSection);
  400. }
  401.