home *** CD-ROM | disk | FTP | other *** search
/ Graphics Programming Black Book (Special Edition) / BlackBook.bin / disk1 / source / chapter62 / l62_1.c
Text File  |  1997-06-18  |  18KB  |  451 lines
  1. /* Core renderer for Win32 program to demonstrate drawing from a 2D
  2.    BSP tree; illustrate the use of BSP trees for surface visibility.
  3.    UpdateWorld() is the top-level function in this module.
  4.    Full source code for the BSP-based renderer, and for the
  5.    accompanying BSP compiler, may be downloaded from
  6.    ftp.idsoftware.com/mikeab, in the file ddjbsp2.zip.
  7.    Tested with VC++ 2.0 running on Windows NT 3.5. */
  8. #define FIXEDPOINT(x)   ((FIXEDPOINT)(((long)x)*((long)0x10000)))
  9. #define FIXTOINT(x)     ((int)(x >> 16))
  10. #define ANGLE(x)        ((long)x)
  11. #define STANDARD_SPEED  (FIXEDPOINT(20))
  12. #define STANDARD_ROTATION (ANGLE(4))
  13. #define MAX_NUM_NODES   2000
  14. #define MAX_NUM_EXTRA_VERTICES   2000
  15. #define WORLD_MIN_X  (FIXEDPOINT(-16000))
  16. #define WORLD_MAX_X  (FIXEDPOINT(16000))
  17. #define WORLD_MIN_Y  (FIXEDPOINT(-16000))
  18. #define WORLD_MAX_Y  (FIXEDPOINT(16000))
  19. #define WORLD_MIN_Z  (FIXEDPOINT(-16000))
  20. #define WORLD_MAX_Z  (FIXEDPOINT(16000))
  21. #define PROJECTION_RATIO (2.0/1.0)  // controls field of view; the
  22.                     // bigger this is, the narrower the field of view
  23. typedef long FIXEDPOINT;
  24. typedef struct _VERTEX {
  25.    FIXEDPOINT x, z, viewx, viewz;
  26. } VERTEX, *PVERTEX;
  27. typedef struct _POINT2 { FIXEDPOINT x, z; } POINT2, *PPOINT2;
  28. typedef struct _POINT2INT { int  x; int y; } POINT2INT, *PPOINT2INT;
  29. typedef long ANGLE;     // angles are stored in degrees
  30. typedef struct _NODE {
  31.    VERTEX *pstartvertex, *pendvertex;
  32.    FIXEDPOINT  walltop, wallbottom, tstart, tend;
  33.    FIXEDPOINT  clippedtstart, clippedtend;
  34.    struct _NODE *fronttree, *backtree;
  35.    int         color, isVisible;
  36.    FIXEDPOINT  screenxstart, screenxend;
  37.    FIXEDPOINT  screenytopstart, screenybottomstart;
  38.    FIXEDPOINT  screenytopend, screenybottomend;
  39. } NODE, *PNODE;
  40. char * pDIB;            // pointer to DIB section we'll draw into
  41. HBITMAP hDIBSection;    // handle of DIB section
  42. HPALETTE hpalDIB;
  43. int iteration = 0, WorldIsRunning = 1;
  44. HWND hwndOutput;
  45. int DIBWidth, DIBHeight, DIBPitch, numvertices, numnodes;
  46. FIXEDPOINT fxHalfDIBWidth, fxHalfDIBHeight;
  47. VERTEX *pvertexlist, *pextravertexlist;
  48. NODE *pnodelist;
  49. POINT2 currentlocation, currentdirection, currentorientation;
  50. ANGLE currentangle;
  51. FIXEDPOINT currentspeed, fxViewerY, currentYSpeed;
  52. FIXEDPOINT FrontClipPlane = FIXEDPOINT(10);
  53. FIXEDPOINT FixedMul(FIXEDPOINT x, FIXEDPOINT y);
  54. FIXEDPOINT FixedDiv(FIXEDPOINT x, FIXEDPOINT y);
  55. FIXEDPOINT FixedSin(ANGLE angle), FixedCos(ANGLE angle);
  56. extern int FillConvexPolygon(POINT2INT * VertexPtr, int Color);
  57.  
  58. // Returns nonzero if a wall is facing the viewer, 0 else.
  59. int WallFacingViewer(NODE * pwall)
  60. {
  61.    FIXEDPOINT viewxstart = pwall->pstartvertex->viewx;
  62.    FIXEDPOINT viewzstart = pwall->pstartvertex->viewz;
  63.    FIXEDPOINT viewxend = pwall->pendvertex->viewx;
  64.    FIXEDPOINT viewzend = pwall->pendvertex->viewz;
  65.    int Temp;
  66.  
  67. /*  // equivalent C code
  68.    if (( ((pwall->pstartvertex->viewx >> 16) *
  69.          ((pwall->pendvertex->viewz -
  70.           pwall->pstartvertex->viewz) >> 16)) +
  71.          ((pwall->pstartvertex->viewz >> 16) *
  72.           ((pwall->pstartvertex->viewx -
  73.             pwall->pendvertex->viewx) >> 16)) )
  74.                < 0)
  75.       return(1);
  76.    else
  77.       return(0);
  78. */
  79.    _asm {
  80.       mov   eax,viewzend
  81.       sub   eax,viewzstart
  82.       imul  viewxstart
  83.       mov   ecx,edx
  84.       mov   ebx,eax
  85.       mov   eax,viewxstart
  86.       sub   eax,viewxend
  87.       imul  viewzstart
  88.       add   eax,ebx
  89.       adc   edx,ecx
  90.       mov   eax,0
  91.       jns   short WFVDone
  92.       inc   eax
  93. WFVDone:
  94.       mov   Temp,eax
  95.    }
  96.    return(Temp);
  97. }
  98.  
  99. // Update the viewpoint position as needed.
  100. void UpdateViewPos()
  101. {
  102.    if (currentspeed != 0) {
  103.       currentlocation.x += FixedMul(currentdirection.x,
  104.                                     currentspeed);
  105.       if (currentlocation.x <= WORLD_MIN_X)
  106.          currentlocation.x = WORLD_MIN_X;
  107.       if (currentlocation.x >= WORLD_MAX_X)
  108.          currentlocation.x = WORLD_MAX_X - 1;
  109.       currentlocation.z += FixedMul(currentdirection.z,
  110.                                     currentspeed);
  111.       if (currentlocation.z <= WORLD_MIN_Z)
  112.          currentlocation.z = WORLD_MIN_Z;
  113.       if (currentlocation.z >= WORLD_MAX_Z)
  114.          currentlocation.z = WORLD_MAX_Z - 1;
  115.    }
  116.    if (currentYSpeed != 0) {
  117.       fxViewerY += currentYSpeed;
  118.       if (fxViewerY <= WORLD_MIN_Y)
  119.          fxViewerY = WORLD_MIN_Y;
  120.       if (fxViewerY >= WORLD_MAX_Y)
  121.          fxViewerY = WORLD_MAX_Y - 1;
  122.    }
  123. }
  124.  
  125. // Transform all vertices into viewspace.
  126. void TransformVertices()
  127. {
  128.    VERTEX *pvertex;
  129.    FIXEDPOINT tempx, tempz;
  130.    int vertex;
  131.  
  132.    pvertex = pvertexlist;
  133.    for (vertex = 0; vertex < numvertices; vertex++) {
  134.       // Translate the vertex according to the viewpoint
  135.       tempx = pvertex->x - currentlocation.x;
  136.       tempz = pvertex->z - currentlocation.z;
  137.       // Rotate the vertex so viewpoint is looking down z axis
  138.       pvertex->viewx = FixedMul(FixedMul(tempx,
  139.                                          currentorientation.z) +
  140.                    FixedMul(tempz, -currentorientation.x),
  141.                    FIXEDPOINT(PROJECTION_RATIO));
  142.       pvertex->viewz = FixedMul(tempx, currentorientation.x) +
  143.                    FixedMul(tempz, currentorientation.z);
  144.       pvertex++;
  145.    }
  146. }
  147.  
  148. // 3D clip all walls. If any part of each wall is still visible,
  149. // transform to perspective viewspace.
  150. void ClipWalls()
  151. {
  152.    NODE *pwall;
  153.    int wall;
  154.    FIXEDPOINT tempstartx, tempendx, tempstartz, tempendz;
  155.    FIXEDPOINT tempstartwalltop, tempstartwallbottom;
  156.    FIXEDPOINT tempendwalltop, tempendwallbottom;
  157.    VERTEX *pstartvertex, *pendvertex;
  158.    VERTEX *pextravertex = pextravertexlist;
  159.  
  160.    pwall = pnodelist;
  161.    for (wall = 0; wall < numnodes; wall++) {
  162.       // Assume the wall won't be visible
  163.       pwall->isVisible = 0;
  164.       // Generate the wall endpoints, accounting for t values and
  165.       // clipping
  166.       // Calculate the viewspace coordinates for this wall
  167.       pstartvertex = pwall->pstartvertex;
  168.       pendvertex = pwall->pendvertex;
  169.       // Look for z clipping first
  170.       // Calculate start and end z coordinates for this wall
  171.       if (pwall->tstart == FIXEDPOINT(0))
  172.          tempstartz = pstartvertex->viewz;
  173.       else
  174.          tempstartz = pstartvertex->viewz +
  175.                FixedMul((pendvertex->viewz-pstartvertex->viewz),
  176.                pwall->tstart);
  177.       if (pwall->tend == FIXEDPOINT(1))
  178.          tempendz = pendvertex->viewz;
  179.       else
  180.          tempendz = pstartvertex->viewz +
  181.                FixedMul((pendvertex->viewz-pstartvertex->viewz),
  182.                pwall->tend);
  183.       // Clip to the front plane
  184.       if (tempendz < FrontClipPlane) {
  185.          if (tempstartz < FrontClipPlane) {
  186.             // Fully front-clipped
  187.             goto NextWall;
  188.          } else {
  189.             pwall->clippedtstart = pwall->tstart;
  190.             // Clip the end point to the front clip plane
  191.             pwall->clippedtend =
  192.                   FixedDiv(pstartvertex->viewz - FrontClipPlane,
  193.                         pstartvertex->viewz-pendvertex->viewz);
  194.             tempendz = pstartvertex->viewz +
  195.                FixedMul((pendvertex->viewz-pstartvertex->viewz),
  196.                pwall->clippedtend);
  197.          }
  198.       } else {
  199.          pwall->clippedtend = pwall->tend;
  200.          if (tempstartz < FrontClipPlane) {
  201.             // Clip the start point to the front clip plane
  202.             pwall->clippedtstart =
  203.                   FixedDiv(FrontClipPlane - pstartvertex->viewz,
  204.                         pendvertex->viewz-pstartvertex->viewz);
  205.             tempstartz = pstartvertex->viewz +
  206.                FixedMul((pendvertex->viewz-pstartvertex->viewz),
  207.                pwall->clippedtstart);
  208.          } else {
  209.             pwall->clippedtstart = pwall->tstart;
  210.          }
  211.       }
  212.       // Calculate x coordinates
  213.       if (pwall->clippedtstart == FIXEDPOINT(0))
  214.          tempstartx = pstartvertex->viewx;
  215.       else
  216.          tempstartx = pstartvertex->viewx +
  217.                FixedMul((pendvertex->viewx-pstartvertex->viewx),
  218.                pwall->clippedtstart);
  219.       if (pwall->clippedtend == FIXEDPOINT(1))
  220.          tempendx = pendvertex->viewx;
  221.       else
  222.          tempendx = pstartvertex->viewx +
  223.                FixedMul((pendvertex->viewx-pstartvertex->viewx),
  224.                pwall->clippedtend);
  225.       // Clip in x as needed
  226.       if ((tempstartx > tempstartz) || (tempstartx < -tempstartz)) {
  227.          // The start point is outside the view triangle in x;
  228.          // perform a quick test for trivial rejection by seeing if
  229.          // the end point is outside the view triangle on the same
  230.          // side as the start point
  231.          if (((tempstartx>tempstartz) && (tempendx>tempendz)) ||
  232.             ((tempstartx<-tempstartz) && (tempendx<-tempendz)))
  233.             // Fully clipped--trivially reject
  234.             goto NextWall;
  235.          // Clip the start point
  236.          if (tempstartx > tempstartz) {
  237.             // Clip the start point on the right side
  238.             pwall->clippedtstart =
  239.                FixedDiv(pstartvertex->viewx-pstartvertex->viewz,
  240.                       pendvertex->viewz-pstartvertex->viewz -
  241.                       pendvertex->viewx+pstartvertex->viewx);
  242.             tempstartx = pstartvertex->viewx +
  243.                FixedMul((pendvertex->viewx-pstartvertex->viewx),
  244.                        pwall->clippedtstart);
  245.             tempstartz = tempstartx;
  246.          } else {
  247.             // Clip the start point on the left side
  248.             pwall->clippedtstart =
  249.                FixedDiv(-pstartvertex->viewx-pstartvertex->viewz,
  250.                       pendvertex->viewx+pendvertex->viewz -
  251.                       pstartvertex->viewz-pstartvertex->viewx);
  252.             tempstartx = pstartvertex->viewx +
  253.                FixedMul((pendvertex->viewx-pstartvertex->viewx),
  254.                        pwall->clippedtstart);
  255.             tempstartz = -tempstartx;
  256.          }
  257.       }
  258.       // See if the end point needs clipping
  259.       if ((tempendx > tempendz) || (tempendx < -tempendz)) {
  260.          // Clip the end point
  261.          if (tempendx > tempendz) {
  262.             // Clip the end point on the right side
  263.             pwall->clippedtend =
  264.                FixedDiv(pstartvertex->viewx-pstartvertex->viewz,
  265.                       pendvertex->viewz-pstartvertex->viewz -
  266.                       pendvertex->viewx+pstartvertex->viewx);
  267.             tempendx = pstartvertex->viewx +
  268.                FixedMul((pendvertex->viewx-pstartvertex->viewx),
  269.                        pwall->clippedtend);
  270.             tempendz = tempendx;
  271.          } else {
  272.             // Clip the end point on the left side
  273.             pwall->clippedtend =
  274.                FixedDiv(-pstartvertex->viewx-pstartvertex->viewz,
  275.                       pendvertex->viewx+pendvertex->viewz -
  276.                       pstartvertex->viewz-pstartvertex->viewx);
  277.             tempendx = pstartvertex->viewx +
  278.                FixedMul((pendvertex->viewx-pstartvertex->viewx),
  279.                        pwall->clippedtend);
  280.             tempendz = -tempendx;
  281.          }
  282.       }
  283.       tempstartwalltop = FixedMul((pwall->walltop - fxViewerY),
  284.             FIXEDPOINT(PROJECTION_RATIO));
  285.       tempendwalltop = tempstartwalltop;
  286.       tempstartwallbottom = FixedMul((pwall->wallbottom-fxViewerY),
  287.             FIXEDPOINT(PROJECTION_RATIO));
  288.       tempendwallbottom = tempstartwallbottom;
  289.       // Partially clip in y (the rest is done later in 2D)
  290.       // Check for trivial accept
  291.       if ((tempstartwalltop > tempstartz) ||
  292.          (tempstartwallbottom < -tempstartz) ||
  293.          (tempendwalltop > tempendz) ||
  294.          (tempendwallbottom < -tempendz)) {
  295.          // Not trivially unclipped; check for fully clipped
  296.          if ((tempstartwallbottom > tempstartz) &&
  297.             (tempstartwalltop < -tempstartz) &&
  298.             (tempendwallbottom > tempendz) &&
  299.             (tempendwalltop < -tempendz)) {
  300.             // Outside view triangle, trivially clipped
  301.             goto NextWall;
  302.          }
  303.          // Partially clipped in Y; we'll do Y clipping at
  304.          // drawing time
  305.       }
  306.       // The wall is visible; mark it as such and project it.
  307.       // +1 on scaling because of bottom/right exclusive polygon
  308.       // filling
  309.       pwall->isVisible = 1;
  310.       pwall->screenxstart =
  311.          (FixedMulDiv(tempstartx, fxHalfDIBWidth+FIXEDPOINT(0.5),
  312.             tempstartz) + fxHalfDIBWidth + FIXEDPOINT(0.5));
  313.       pwall->screenytopstart =
  314.             (FixedMulDiv(tempstartwalltop,
  315.             fxHalfDIBHeight + FIXEDPOINT(0.5), tempstartz) +
  316.             fxHalfDIBHeight + FIXEDPOINT(0.5));
  317.       pwall->screenybottomstart =
  318.             (FixedMulDiv(tempstartwallbottom,
  319.             fxHalfDIBHeight + FIXEDPOINT(0.5), tempstartz) +
  320.             fxHalfDIBHeight + FIXEDPOINT(0.5));
  321.       pwall->screenxend =
  322.             (FixedMulDiv(tempendx, fxHalfDIBWidth+FIXEDPOINT(0.5),
  323.             tempendz) + fxHalfDIBWidth + FIXEDPOINT(0.5));
  324.       pwall->screenytopend =
  325.             (FixedMulDiv(tempendwalltop,
  326.             fxHalfDIBHeight + FIXEDPOINT(0.5), tempendz) +
  327.             fxHalfDIBHeight + FIXEDPOINT(0.5));
  328.       pwall->screenybottomend =
  329.             (FixedMulDiv(tempendwallbottom,
  330.             fxHalfDIBHeight + FIXEDPOINT(0.5), tempendz) +
  331.             fxHalfDIBHeight + FIXEDPOINT(0.5));
  332. NextWall:
  333.       pwall++;
  334.    }
  335. }
  336.  
  337. // Walk the tree back to front; backface cull whenever possible,
  338. // and draw front-facing walls in back-to-front order.
  339. void DrawWallsBackToFront()
  340. {
  341.    NODE *pFarChildren, *pNearChildren, *pwall;
  342.    NODE *pendingnodes[MAX_NUM_NODES];
  343.    NODE **pendingstackptr;
  344.    POINT2INT apoint[4];
  345.  
  346.    pwall = pnodelist;
  347.    pendingnodes[0] = (NODE *)NULL;
  348.    pendingstackptr = pendingnodes + 1;
  349.    for (;;) {
  350.       for (;;) {
  351.          // Descend as far as possible toward the back,
  352.          // remembering the nodes we pass through on the way.
  353.          // Figure whether this wall is facing frontward or
  354.          // backward; do in viewspace because non-visible walls
  355.          // aren't projected into screenspace, and we need to
  356.          // traverse all walls in the BSP tree, visible or not,
  357.          // in order to find all the visible walls
  358.          if (WallFacingViewer(pwall)) {
  359.             // We're on the forward side of this wall, do the back
  360.             // children first
  361.             pFarChildren = pwall->backtree;
  362.          } else {
  363.             // We're on the back side of this wall, do the front
  364.             // children first
  365.             pFarChildren = pwall->fronttree;
  366.          }
  367.          if (pFarChildren == NULL)
  368.             break;
  369.          *pendingstackptr = pwall;
  370.          pendingstackptr++;
  371.          pwall = pFarChildren;
  372.       }
  373.       for (;;) {
  374.          // See if the wall is even visible
  375.          if (pwall->isVisible) {
  376.             // See if we can backface cull this wall
  377.             if (pwall->screenxstart < pwall->screenxend) {
  378.                // Draw the wall
  379.                apoint[0].x = FIXTOINT(pwall->screenxstart);
  380.                apoint[1].x = FIXTOINT(pwall->screenxstart);
  381.                apoint[2].x = FIXTOINT(pwall->screenxend);
  382.                apoint[3].x = FIXTOINT(pwall->screenxend);
  383.                apoint[0].y = FIXTOINT(pwall->screenytopstart);
  384.                apoint[1].y = FIXTOINT(pwall->screenybottomstart);
  385.                apoint[2].y = FIXTOINT(pwall->screenybottomend);
  386.                apoint[3].y = FIXTOINT(pwall->screenytopend);
  387.                FillConvexPolygon(apoint, pwall->color);
  388.             }
  389.          }
  390.          // If there's a near tree from this node, draw it;
  391.          // otherwise, work back up to the last-pushed parent
  392.          // node of the branch we just finished; we're done if
  393.          // there are no pending parent nodes.
  394.          // Figure whether this wall is facing frontward or
  395.          // backward; do in viewspace because non-visible walls
  396.          // aren't projected into screenspace, and we need to
  397.             // traverse all walls in the BSP tree, visible or not,
  398.             // in order to find all the visible walls
  399.          if (WallFacingViewer(pwall)) {
  400.             // We're on the forward side of this wall, do the
  401.             // front children now
  402.             pNearChildren = pwall->fronttree;
  403.          } else {
  404.             // We're on the back side of this wall, do the back
  405.             // children now
  406.             pNearChildren = pwall->backtree;
  407.          }
  408.          // Walk the near subtree of this wall
  409.          if (pNearChildren != NULL)
  410.             goto WalkNearTree;
  411.          // Pop the last-pushed wall
  412.          pendingstackptr--;
  413.          pwall = *pendingstackptr;
  414.          if (pwall == NULL)
  415.             goto NodesDone;
  416.       }
  417. WalkNearTree:
  418.       pwall = pNearChildren;
  419.    }
  420. NodesDone:
  421. ;
  422. }
  423.  
  424. // Render the current state of the world to the screen.
  425. void UpdateWorld()
  426. {
  427.    HPALETTE holdpal;
  428.    HDC hdcScreen, hdcDIBSection;
  429.    HBITMAP holdbitmap;
  430.  
  431.    // Draw the frame
  432.    UpdateViewPos();
  433.    memset(pDIB, 0, DIBPitch*DIBHeight);    // clear frame
  434.    TransformVertices();
  435.    ClipWalls();
  436.    DrawWallsBackToFront();
  437.    // We've drawn the frame; copy it to the screen
  438.    hdcScreen = GetDC(hwndOutput);
  439.    holdpal = SelectPalette(hdcScreen, hpalDIB, FALSE);
  440.    RealizePalette(hdcScreen);
  441.    hdcDIBSection = CreateCompatibleDC(hdcScreen);
  442.    holdbitmap = SelectObject(hdcDIBSection, hDIBSection);
  443.    BitBlt(hdcScreen, 0, 0, DIBWidth, DIBHeight, hdcDIBSection,
  444.           0, 0, SRCCOPY);
  445.    SelectPalette(hdcScreen, holdpal, FALSE);
  446.    ReleaseDC(hwndOutput, hdcScreen);
  447.    SelectObject(hdcDIBSection, holdbitmap);
  448.    ReleaseDC(hwndOutput, hdcDIBSection);
  449.    iteration++;
  450. }
  451.