/* Rendu pour le programme Win32 pour illustrer l'affichage d'un arbre BSP 2D
   illustre l'emploi des arbres BSP pour les faces visibles.
   UpdateWorld() est la fonction de haut niveau dans ce module.
   Tout le code source du rendu basé sur le BSP, et pour le compilateur
   BSP pendant, peuvent être téléchargés depuis
   ftp.idsoftware.com/mikeab, dans le fichier ddjbsp2.zip.
   Testé avec VC++ 2.0 tournant sur Windows NT 3.5. */

#define FIXEDPOINT(x)   ((FIXEDPOINT)(((long)x)*((long)0x10000)))
#define FIXTOINT(x)     ((int)(x >> 16))
#define ANGLE(x)        ((long)x)
#define STANDARD_SPEED  (FIXEDPOINT(20))
#define STANDARD_ROTATION (ANGLE(4))
#define MAX_NUM_NODES   2000
#define MAX_NUM_EXTRA_VERTICES   2000
#define WORLD_MIN_X  (FIXEDPOINT(-16000))
#define WORLD_MAX_X  (FIXEDPOINT(16000))
#define WORLD_MIN_Y  (FIXEDPOINT(-16000))
#define WORLD_MAX_Y  (FIXEDPOINT(16000))
#define WORLD_MIN_Z  (FIXEDPOINT(-16000))
#define WORLD_MAX_Z  (FIXEDPOINT(16000))
#define PROJECTION_RATIO (2.0/1.0)  // contrôle l'espace de visualisation; plus il
                              // est grand, plus l'espace de visualisation est étroit
typedef long FIXEDPOINT;
typedef struct _VERTEX {
   FIXEDPOINT x, z, viewx, viewz;
} VERTEX, *PVERTEX;
typedef struct _POINT2 { FIXEDPOINT x, z; } POINT2, *PPOINT2;
typedef struct _POINT2INT { int  x; int y; } POINT2INT, *PPOINT2INT;
typedef long ANGLE;     // les angles sont stockés en degrés
typedef struct _NODE {
   VERTEX *pstartvertex, *pendvertex;
   FIXEDPOINT  walltop, wallbottom, tstart, tend;
   FIXEDPOINT  clippedtstart, clippedtend;
   struct _NODE *fronttree, *backtree;
   int         color, isVisible;
   FIXEDPOINT  screenxstart, screenxend;
   FIXEDPOINT  screenytopstart, screenybottomstart;
   FIXEDPOINT  screenytopend, screenybottomend;
} NODE, *PNODE;
char * pDIB;            // pointeur sur la section DIB que nous afficherons 
HBITMAP hDIBSection;    // dans le handle de la section DIB 
HPALETTE hpalDIB;
int iteration = 0, WorldIsRunning = 1;
HWND hwndOutput;
int DIBWidth, DIBHeight, DIBPitch, numvertices, numnodes;
FIXEDPOINT fxHalfDIBWidth, fxHalfDIBHeight;
VERTEX *pvertexlist, *pextravertexlist;
NODE *pnodelist;
POINT2 currentlocation, currentdirection, currentorientation;
ANGLE currentangle;
FIXEDPOINT currentspeed, fxViewerY, currentYSpeed;
FIXEDPOINT FrontClipPlane = FIXEDPOINT(10);
FIXEDPOINT FixedMul(FIXEDPOINT x, FIXEDPOINT y);
FIXEDPOINT FixedDiv(FIXEDPOINT x, FIXEDPOINT y);
FIXEDPOINT FixedSin(ANGLE angle), FixedCos(ANGLE angle);
extern int FillConvexPolygon(POINT2INT * VertexPtr, int Color);

// Retourne une valeur non nulle si le mur est face à l'observateur, 0 autrement.
int WallFacingViewer(NODE * pwall)
{
   FIXEDPOINT viewxstart = pwall->pstartvertex->viewx;
   FIXEDPOINT viewzstart = pwall->pstartvertex->viewz;
   FIXEDPOINT viewxend = pwall->pendvertex->viewx;
   FIXEDPOINT viewzend = pwall->pendvertex->viewz;
   int Temp;

/*  // code C équivalent
   if (( ((pwall->pstartvertex->viewx >> 16) *
         ((pwall->pendvertex->viewz -
          pwall->pstartvertex->viewz) >> 16)) +
         ((pwall->pstartvertex->viewz >> 16) *
          ((pwall->pstartvertex->viewx -
            pwall->pendvertex->viewx) >> 16)) )
               < 0)
      return(1);
   else
      return(0);
*/
   _asm {
      mov   eax,viewzend
      sub   eax,viewzstart
      imul  viewxstart
      mov   ecx,edx
      mov   ebx,eax
      mov   eax,viewxstart
      sub   eax,viewxend
      imul  viewzstart
      add   eax,ebx
      adc   edx,ecx
      mov   eax,0
      jns   short WFVDone
      inc   eax
WFVDone:
      mov   Temp,eax
   }
   return(Temp);
}

// Met à jour le point de vue.
void UpdateViewPos()
{
   if (currentspeed != 0) {
      currentlocation.x += FixedMul(currentdirection.x,
                                    currentspeed);
      if (currentlocation.x <= WORLD_MIN_X)
         currentlocation.x = WORLD_MIN_X;
      if (currentlocation.x >= WORLD_MAX_X)
         currentlocation.x = WORLD_MAX_X - 1;
      currentlocation.z += FixedMul(currentdirection.z,
                                    currentspeed);
      if (currentlocation.z <= WORLD_MIN_Z)
         currentlocation.z = WORLD_MIN_Z;
      if (currentlocation.z >= WORLD_MAX_Z)
         currentlocation.z = WORLD_MAX_Z - 1;
   }
   if (currentYSpeed != 0) {
      fxViewerY += currentYSpeed;
      if (fxViewerY <= WORLD_MIN_Y)
         fxViewerY = WORLD_MIN_Y;
      if (fxViewerY >= WORLD_MAX_Y)
         fxViewerY = WORLD_MAX_Y - 1;
   }
}

// Transforme tous les points dans l'espace de visualisation.
void TransformVertices()
{
   VERTEX *pvertex;
   FIXEDPOINT tempx, tempz;
   int vertex;

   pvertex = pvertexlist;
   for (vertex = 0; vertex < numvertices; vertex++) {
      // Effectue une translation du point en fonction du point de vue
      tempx = pvertex->x - currentlocation.x;
      tempz = pvertex->z - currentlocation.z;
      // Rotate the vertex so viewpoint is looking down z axis
      pvertex->viewx = FixedMul(FixedMul(tempx,
                                         currentorientation.z) +
                   FixedMul(tempz, -currentorientation.x),
                   FIXEDPOINT(PROJECTION_RATIO));
      pvertex->viewz = FixedMul(tempx, currentorientation.x) +
                   FixedMul(tempz, currentorientation.z);
      pvertex++;
   }
}

// Clippe tous les murs en 3D. Si une face de chaque mur reste visible,
// transforme en espace de visualisation en perspective.
void ClipWalls()
{
   NODE *pwall;
   int wall;
   FIXEDPOINT tempstartx, tempendx, tempstartz, tempendz;
   FIXEDPOINT tempstartwalltop, tempstartwallbottom;
   FIXEDPOINT tempendwalltop, tempendwallbottom;
   VERTEX *pstartvertex, *pendvertex;
   VERTEX *pextravertex = pextravertexlist;

   pwall = pnodelist;
   for (wall = 0; wall < numnodes; wall++) {
      // Suppose que le mur n'est pas visible
      pwall->isVisible = 0;
      // Génère les extrémités du mur, en comptant les valeurs et
      // le clipping
      // Calcule les coordonnées de l'espace de visualisation pour ce mur
      pstartvertex = pwall->pstartvertex;
      pendvertex = pwall->pendvertex;
      // Recherche en premier lieu le clipping en z 
      // Calcule les coordonnées z de début et de fin pour ce mur
      if (pwall->tstart == FIXEDPOINT(0))
         tempstartz = pstartvertex->viewz;
      else
         tempstartz = pstartvertex->viewz +
               FixedMul((pendvertex->viewz-pstartvertex->viewz),
               pwall->tstart);
      if (pwall->tend == FIXEDPOINT(1))
         tempendz = pendvertex->viewz;
      else
         tempendz = pstartvertex->viewz +
               FixedMul((pendvertex->viewz-pstartvertex->viewz),
               pwall->tend);
      // Clippe le plan front 
      if (tempendz < FrontClipPlane) {
         if (tempstartz < FrontClipPlane) {
            // front est entièrement clippé
            goto NextWall;
         } else {
            pwall->clippedtstart = pwall->tstart;
            // Clippe le point de fin sur le plan front de clipping 
            pwall->clippedtend =
                  FixedDiv(pstartvertex->viewz - FrontClipPlane,
                        pstartvertex->viewz-pendvertex->viewz);
            tempendz = pstartvertex->viewz +
               FixedMul((pendvertex->viewz-pstartvertex->viewz),
               pwall->clippedtend);
         }
      } else {
         pwall->clippedtend = pwall->tend;
         if (tempstartz < FrontClipPlane) {
            // Clippe le point de début sur le plan front de clipping
            pwall->clippedtstart =
                  FixedDiv(FrontClipPlane - pstartvertex->viewz,
                        pendvertex->viewz-pstartvertex->viewz);
            tempstartz = pstartvertex->viewz +
               FixedMul((pendvertex->viewz-pstartvertex->viewz),
               pwall->clippedtstart);
         } else {
            pwall->clippedtstart = pwall->tstart;
         }
      }
      // Calcule les coordonnées x 
      if (pwall->clippedtstart == FIXEDPOINT(0))
         tempstartx = pstartvertex->viewx;
      else
         tempstartx = pstartvertex->viewx +
               FixedMul((pendvertex->viewx-pstartvertex->viewx),
               pwall->clippedtstart);
      if (pwall->clippedtend == FIXEDPOINT(1))
         tempendx = pendvertex->viewx;
      else
         tempendx = pstartvertex->viewx +
               FixedMul((pendvertex->viewx-pstartvertex->viewx),
               pwall->clippedtend);
      // Clippe en x selon
      if ((tempstartx > tempstartz) || (tempstartx < -tempstartz)) {
         // Le point de départ est à l'extérieur du triangle de visualisation
         // en x;
         // effectue un test rapide pour le rejet trivial en regardant si le
         // point de fin est à l'extérieur du triangle de visualisation
         // sur le même côté que le point de départ 
         if (((tempstartx>tempstartz) && (tempendx>tempendz)) ||
            ((tempstartx<-tempstartz) && (tempendx<-tempendz)))
            // Entièrement clippé-rejet trivial
            goto NextWall;
         // Clippe le point de départ
         if (tempstartx > tempstartz) {
            // Clippe le point de départ sur le côté droit
            pwall->clippedtstart =
               FixedDiv(pstartvertex->viewx-pstartvertex->viewz,
                      pendvertex->viewz-pstartvertex->viewz -
                      pendvertex->viewx+pstartvertex->viewx);
            tempstartx = pstartvertex->viewx +
               FixedMul((pendvertex->viewx-pstartvertex->viewx),
                       pwall->clippedtstart);
            tempstartz = tempstartx;
         } else {
            // Clippe le point de départ sur le côté gauche
            pwall->clippedtstart =
               FixedDiv(-pstartvertex->viewx-pstartvertex->viewz,
                      pendvertex->viewx+pendvertex->viewz -
                      pstartvertex->viewz-pstartvertex->viewx);
            tempstartx = pstartvertex->viewx +
               FixedMul((pendvertex->viewx-pstartvertex->viewx),
                       pwall->clippedtstart);
            tempstartz = -tempstartx;
         }
      }
      // Vérifie si le point de fin doit être clippé
      if ((tempendx > tempendz) || (tempendx < -tempendz)) {
         // Clippe le point de fin
         if (tempendx > tempendz) {
            // Clippe le point de fin sur le côté droit
            pwall->clippedtend =
               FixedDiv(pstartvertex->viewx-pstartvertex->viewz,
                      pendvertex->viewz-pstartvertex->viewz -
                      pendvertex->viewx+pstartvertex->viewx);
            tempendx = pstartvertex->viewx +
               FixedMul((pendvertex->viewx-pstartvertex->viewx),
                       pwall->clippedtend);
            tempendz = tempendx;
         } else {
            // Clippe le point de fin sur le côté gauche
            pwall->clippedtend =
               FixedDiv(-pstartvertex->viewx-pstartvertex->viewz,
                      pendvertex->viewx+pendvertex->viewz -
                      pstartvertex->viewz-pstartvertex->viewx);
            tempendx = pstartvertex->viewx +
               FixedMul((pendvertex->viewx-pstartvertex->viewx),
                       pwall->clippedtend);
            tempendz = -tempendx;
         }
      }
      tempstartwalltop = FixedMul((pwall->walltop - fxViewerY),
            FIXEDPOINT(PROJECTION_RATIO));
      tempendwalltop = tempstartwalltop;
      tempstartwallbottom = FixedMul((pwall->wallbottom-fxViewerY),
            FIXEDPOINT(PROJECTION_RATIO));
      tempendwallbottom = tempstartwallbottom;
      // Clippe partiellement en y (le reste est fait ultérieurement en 2D)
      // Teste pour acceptation triviale
      if ((tempstartwalltop > tempstartz) ||
         (tempstartwallbottom < -tempstartz) ||
         (tempendwalltop > tempendz) ||
         (tempendwallbottom < -tempendz)) {
         // N'est pas non clippé trivialement; teste pour le clipping total
         if ((tempstartwallbottom > tempstartz) &&
            (tempstartwalltop < -tempstartz) &&
            (tempendwallbottom > tempendz) &&
            (tempendwalltop < -tempendz)) {
            // Outside view triangle, trivially clipped
            goto NextWall;
         }
         // Clippé partiellement en Y; nous effectuerons le clipping en Y
         // au moment de l'affichage
      }
      // Le mur est visible; le notifier et le projeter.
      // +1 car le remplissage du polygone exclut bas/droite 
      pwall->isVisible = 1;
      pwall->screenxstart =
         (FixedMulDiv(tempstartx, fxHalfDIBWidth+FIXEDPOINT(0.5),
            tempstartz) + fxHalfDIBWidth + FIXEDPOINT(0.5));
      pwall->screenytopstart =
            (FixedMulDiv(tempstartwalltop,
            fxHalfDIBHeight + FIXEDPOINT(0.5), tempstartz) +
            fxHalfDIBHeight + FIXEDPOINT(0.5));
      pwall->screenybottomstart =
            (FixedMulDiv(tempstartwallbottom,
            fxHalfDIBHeight + FIXEDPOINT(0.5), tempstartz) +
            fxHalfDIBHeight + FIXEDPOINT(0.5));
      pwall->screenxend =
            (FixedMulDiv(tempendx, fxHalfDIBWidth+FIXEDPOINT(0.5),
            tempendz) + fxHalfDIBWidth + FIXEDPOINT(0.5));
      pwall->screenytopend =
            (FixedMulDiv(tempendwalltop,
            fxHalfDIBHeight + FIXEDPOINT(0.5), tempendz) +
            fxHalfDIBHeight + FIXEDPOINT(0.5));
      pwall->screenybottomend =
            (FixedMulDiv(tempendwallbottom,
            fxHalfDIBHeight + FIXEDPOINT(0.5), tempendz) +
            fxHalfDIBHeight + FIXEDPOINT(0.5));
NextWall:
      pwall++;
   }
}

// Parcourt l'arbre du fond à l'avant; supprime les faces cachées si possible,
// et affiche les murs faisant face à l'avant selon l'ordre arrière/avant.
void DrawWallsBackToFront()
{
   NODE *pFarChildren, *pNearChildren, *pwall;
   NODE *pendingnodes[MAX_NUM_NODES];
   NODE **pendingstackptr;
   POINT2INT apoint[4];

   pwall = pnodelist;
   pendingnodes[0] = (NODE *)NULL;
   pendingstackptr = pendingnodes + 1;
   for (;;) {
      for (;;) {
         // Descend le plus loin possible vers le fond,
         // mémorisant les nœuds que nous rencontrons.
         // Détermine si ce mur est face à l'avant ou
         // à l'arrière; effectué dans l'espace de visualisation car les murs 
         // non visibles ne sont pas projetés dans l'espace écran, et nous devons
         // traverser tous les murs de l'arbre BSP, qu'ils soient visibles ou non,
         // afin de trouver tous les murs visibles 
         if (WallFacingViewer(pwall)) {
            // Nous sommes du côté avant de ce mur, traite en premier lieu
            // les enfants arrière
            pFarChildren = pwall->backtree;
         } else {
            // Nous sommes du côté arrière de ce mur, traite en premier lieu
            // les enfants avant
            pFarChildren = pwall->fronttree;
         }
         if (pFarChildren == NULL)
            break;
         *pendingstackptr = pwall;
         pendingstackptr++;
         pwall = pFarChildren;
      }
      for (;;) {
         // Vérifie si le mur est visible
         if (pwall->isVisible) {
            // Vérifie si nous pouvons supprimer la face cachée de ce mur
            if (pwall->screenxstart < pwall->screenxend) {
               // Affiche ce mur
               apoint[0].x = FIXTOINT(pwall->screenxstart);
               apoint[1].x = FIXTOINT(pwall->screenxstart);
               apoint[2].x = FIXTOINT(pwall->screenxend);
               apoint[3].x = FIXTOINT(pwall->screenxend);
               apoint[0].y = FIXTOINT(pwall->screenytopstart);
               apoint[1].y = FIXTOINT(pwall->screenybottomstart);
               apoint[2].y = FIXTOINT(pwall->screenybottomend);
               apoint[3].y = FIXTOINT(pwall->screenytopend);
               FillConvexPolygon(apoint, pwall->color);
            }
         }
         // S'il y a un arbre proche de ce nœud, affichons-le;
         // sinon, revenons au dernier nœud parent empilé
         // de la feuille que nous venons de finir; nous avons terminé
         // s'il ne reste pas de nœud parent.
         // Détermine si ce mur est face avant ou arrière
         // Effectué dans l'espace de visualisation car les murs non
         // visibles ne sont pas projetés dans l'espace écran, et nous devons
            // traverser tous murs de l'arbre BSP, qu'ils soient visibles ou non,
            // afin de trouver tous les murs visibles 
         if (WallFacingViewer(pwall)) {
            // Nous sommes du côté avant de mur, traite maintenant
            // les enfants avant
            pNearChildren = pwall->fronttree;
         } else {
            // Nous sommes du côté arrière de ce mur, traite maintenant
            // les enfants arrière
            pNearChildren = pwall->backtree;
         }
         // Parcourt le sous-arbre proche de ce mur 
         if (pNearChildren != NULL)
            goto WalkNearTree;
         // Dépile le dernier mur empilé
         pendingstackptr--;
         pwall = *pendingstackptr;
         if (pwall == NULL)
            goto NodesDone;
      }
WalkNearTree:
      pwall = pNearChildren;
   }
NodesDone:
;
}

// Rendu de l'état du monde à l'écran.
void UpdateWorld()
{
   HPALETTE holdpal;
   HDC hdcScreen, hdcDIBSection;
   HBITMAP holdbitmap;

   // Affiche la trame 
   UpdateViewPos();
   memset(pDIB, 0, DIBPitch*DIBHeight);    // efface la trame
   TransformVertices();
   ClipWalls();
   DrawWallsBackToFront();

   hdcScreen = GetDC(hwndOutput);
   holdpal = SelectPalette(hdcScreen, hpalDIB, FALSE);
   RealizePalette(hdcScreen);
   hdcDIBSection = CreateCompatibleDC(hdcScreen);
   holdbitmap = SelectObject(hdcDIBSection, hDIBSection);
   BitBlt(hdcScreen, 0, 0, DIBWidth, DIBHeight, hdcDIBSection,
          0, 0, SRCCOPY);
   SelectPalette(hdcScreen, holdpal, FALSE);
   ReleaseDC(hwndOutput, hdcScreen);
   SelectObject(hdcDIBSection, holdbitmap);
   ReleaseDC(hwndOutput, hdcDIBSection);
   iteration++;
}