// Partie du programme Win32 pour illustrer les SR triés sur z. Les espaces 
// sont supprimés pour des raisons de place. Le code source complet,
// avec les espaces, est disponible sur ftp.idsoftware.com/mikeab/ddjzsort.zip.
#define MAX_SPANS           10000
#define MAX_SURFS           1000
#define MAX_EDGES           5000
typedef struct surf_s {
    struct surf_s   *pnext, *pprev;
    int             color, visxstart, state;
    double          zinv00, zinvstepx, zinvstepy;
} surf_t;
typedef struct edge_s {
    int             x, xstep, leading;
    surf_t          *psurf;
    struct edge_s   *pnext, *pprev, *pnextremove;
} edge_t;
// Listes des SR, cotés et surfaces 
span_t  spans[MAX_SPANS];
edge_t  edges[MAX_EDGES];
surf_t  surfs[MAX_SURFS];
// Liste des zones de mémoire des nouveaux côtés à ajouter sur chaque
// ligne d'affichage
edge_t  newedges[MAX_SCREEN_HEIGHT];
// Liste des zones de mémoire des côtés à supprimer sur chaque ligne d'affchage
edge_t  *removeedges[MAX_SCREEN_HEIGHT];
// Tête et queue de la liste des côtés actifs 
edge_t  edgehead, edgetail;
// Côté utilisé comme sentinelle dans la liste des nouveaux côtés
edge_t  maxedge = {0x7FFFFFFF};
// Surface Tête/queue/sentinelle/fond de la pile de la surface active 
surf_t  surfstack;
// pointeurs sur les prochains côté et surface disponibles
surf_t  *pavailsurf;
edge_t  *pavailedge;

// Retourne true si le polygone est face au point de vue, en supposant
// que les points suivent le sens des aiguilles d'une montre vue de dessus.
int PolyFacesViewer(polygon_t *ppoly, plane_t *pplane)
{
    int     i;
    point_t viewvec;

    for (i=0 ; i<3 ; i++)
        viewvec.v[i] = ppoly->verts[0].v[i] - currentpos.v[i];
    // Utilisons un epsilon afin de ne pas récupérer des polygones si fortement 
    // inclinés que les gradients en deviennent inutilisable ou invalides
    if (DotProduct (&viewvec, &pplane->normal) < -0.01)
        return 1;
    return 0;
}

// Ajoute les côtés du polygone dans la table GET.
void AddPolygonEdges (plane_t *plane, polygon2D_t *screenpoly)
{
    double  distinv, deltax, deltay, slope;
    int     i, nextvert, numverts, temp, topy, bottomy, height;
    edge_t  *pedge;

    numverts = screenpoly->numverts;
    // Verrouille les points du polygone au cas où des points trop rapprochés
    // déborderaient de l'intervalle à cause de l'imprécision de la virgule flottante
    for (i=0 ; i<numverts ; i++) {
        if (screenpoly->verts[i].x < -0.5)
            screenpoly->verts[i].x = -0.5;
        if (screenpoly->verts[i].x > ((double)DIBWidth - 0.5))
            screenpoly->verts[i].x = (double)DIBWidth - 0.5;
        if (screenpoly->verts[i].y < -0.5)
            screenpoly->verts[i].y = -0.5;
        if (screenpoly->verts[i].y > ((double)DIBHeight - 0.5))
            screenpoly->verts[i].y = (double)DIBHeight - 0.5;
    }

    // Ajoute l'un après l'autre chaque côté
    for (i=0 ; i<numverts ; i++) {
        nextvert = i + 1;
        if (nextvert >= numverts)
            nextvert = 0;
        topy = (int)ceil(screenpoly->verts[i].y);
        bottomy = (int)ceil(screenpoly->verts[nextvert].y);
        height = bottomy - topy;
        if (height == 0)
            continue;       // ne coupe aucune ligne d'affichage
        if (height < 0) {
            // Premier côté
            temp = topy;
            topy = bottomy;
            bottomy = temp;
            pavailedge->leading = 1;
            deltax = screenpoly->verts[i].x -
                     screenpoly->verts[nextvert].x;
            deltay = screenpoly->verts[i].y -
                     screenpoly->verts[nextvert].y;
            slope = deltax / deltay;
            // Les coordonnées du côté sont en virgule fixe 16.16 
            pavailedge->xstep = (int)(slope * (float)0x10000);
            pavailedge->x = (int)((screenpoly->verts[nextvert].x +
                ((float)topy - screenpoly->verts[nextvert].y) *
                slope) * (float)0x10000);
        } else {
            // Dernier coté
            pavailedge->leading = 0;
            deltax = screenpoly->verts[nextvert].x -
                     screenpoly->verts[i].x;
            deltay = screenpoly->verts[nextvert].y -
                     screenpoly->verts[i].y;
            slope = deltax / deltay;
            // Les coordonnées du côté sont en virgule fixe 16.16 
            pavailedge->xstep = (int)(slope * (float)0x10000);
            pavailedge->x = (int)((screenpoly->verts[i].x +
                ((float)topy - screenpoly->verts[i].y) * slope) *
                (float)0x10000);
        }
        // Place le côté à ajouter dans la liste sur le haut du parcours
        pedge = &newedges[topy];
        while (pedge->pnext->x < pavailedge->x)
            pedge = pedge->pnext;
        pavailedge->pnext = pedge->pnext;
        pedge->pnext = pavailedge;
        // Place le côté à supprimer dans la liste juste après le dernier parcours
        pavailedge->pnextremove = removeedges[bottomy - 1];
        removeedges[bottomy - 1] = pavailedge;
        // Associe le côté à la surface que nous allons créer
        // pour ce polygone
        pavailedge->psurf = pavailsurf;
        // S'assure de ne pas dépasser le tableau des côtés
        if (pavailedge < &edges[MAX_EDGES])
            pavailedge++;
    }
    // Crée la surface, si bien que nous saurons comment trier et afficher 
    // à partir des côtés
    pavailsurf->state = 0;
    pavailsurf->color = currentcolor;
    // Configure les gradients 1/z depuis le polygone, en calculant la valeur 
    // de base à la coordonnée d'écran 0,0 nous pouvons ainsi utiliser directement
    // les coordonnées lors de calculs 1/z depuis les gradients
    distinv = 1.0 / plane->distance;
    pavailsurf->zinvstepx = plane->normal.v[0] * distinv *
            maxscreenscaleinv * (fieldofview / 2.0);
    pavailsurf->zinvstepy = -plane->normal.v[1] * distinv *
            maxscreenscaleinv * (fieldofview / 2.0);
    pavailsurf->zinv00 = plane->normal.v[2] * distinv -
            xcenter * pavailsurf->zinvstepx -
            ycenter * pavailsurf->zinvstepy;
    // S'assure ne pas sortir du tableau de surface 
    if (pavailsurf < &surfs[MAX_SURFS])
        pavailsurf++;
}

// Parcourt tous les côtés dans la table GET table en SR.
void ScanEdges (void)
{
    int     x, y;
    double  fx, fy, zinv, zinv2;
    edge_t  *pedge, *pedge2, *ptemp;
    span_t  *pspan;
    surf_t  *psurf, *psurf2;

    pspan = spans;
    // Configure la liste des côtés actifs comme initialement vide, contenant 
    // uniquement les sentinelles (qui sont également le remplissage du fond) 
    // La plupart de ces champs pourrait être configurés en une seule fois
    //au départ
    edgehead.pnext = &edgetail;
    edgehead.pprev = NULL;
    edgehead.x = -0xFFFF;           // côté gauche de l'écran 
    edgehead.leading = 1;
    edgehead.psurf = &surfstack;
    edgetail.pnext = NULL;          // notifie le coté de la liste 
    edgetail.pprev = &edgehead;
    edgetail.x = DIBWidth << 16;    // côté droit de l'écran 
    edgetail.leading = 0;
    edgetail.psurf = &surfstack;
    // La surface du fond est à l'origine la pile entière, et
    // est éloignée à l'infini, aussi tout ce qui est trié est devant elle.
    // ce qui pourrait être paramétré en une seule fois dès le début
    surfstack.pnext = surfstack.pprev = &surfstack;
    surfstack.color = 0;
    surfstack.zinv00 = -999999.0;
    surfstack.zinvstepx = surfstack.zinvstepy = 0.0;
    for (y=0 ; y<DIBHeight ; y++) {
        fy = (double)y;
        // Trie tous les côtés qui commencent sur ce parcours
        pedge = newedges[y].pnext;
        pedge2 = &edgehead;
        while (pedge != &maxedge) {
            while (pedge->x > pedge2->pnext->x)
                pedge2 = pedge2->pnext;
            ptemp = pedge->pnext;
            pedge->pnext = pedge2->pnext;
            pedge->pprev = pedge2;
            pedge2->pnext->pprev = pedge;
            pedge2->pnext = pedge;
            pedge2 = pedge;
            pedge = ptemp;
        }
        // convertit tous les côtés actifs en SR
        // Commence par le côté gauche du fond déjà inséré,
        // et la pile de la surface contenant seulement le fond
        surfstack.state = 1;
        surfstack.visxstart = 0;
        for (pedge=edgehead.pnext ; pedge ; pedge=pedge->pnext) {
            psurf = pedge->psurf;
            if (pedge->leading) {
                // Premier côté. Détermine s'il est bien sur les
                // surfaces courantes et s'il est bien inséré dans la
                // pile de la surface; s'il est en haut, crée le SR
                // pour le haut courant.
                // S'assure avant out que les côtés ne se coupent pas
                if (++psurf->state == 1) {
                    fx = (double)pedge->x * (1.0 / (double)0x10000);
                    // Calcule la valeur 1/z de la surface à ce pixel
                    zinv = psurf->zinv00 + psurf->zinvstepx * fx +
                            psurf->zinvstepy * fy;
                    psurf2 = surfstack.pnext;
                    zinv2 = psurf2->zinv00 + psurf2->zinvstepx * fx +
                            psurf2->zinvstepy * fy;
                    if (zinv >= zinv2) {
                        // C'est une nouvelle surface de haut
                        // crée le SR pour le haut courant
                        x = (pedge->x + 0xFFFF) >> 16;
                        pspan->count = x - psurf2->visxstart;
                        if (pspan->count > 0) {
                            pspan->y = y;
                            pspan->x = psurf2->visxstart;
                            pspan->color = psurf2->color;
                            // S'assure de ne pas déborder
                            // du tableau SR
                            if (pspan < &spans[MAX_SPANS])
                                pspan++;
                        }
                        psurf->visxstart = x;
                        // Ajoute le coté dans la pile
                        psurf->pnext = psurf2;
                        psurf2->pprev = psurf;
                        surfstack.pnext = psurf;
                        psurf->pprev = &surfstack;
                    } else {
                        // Ce n'est pas un nouveau haut; trie dans la pile de la 
                        // surface.
                        // Garantie de terminer en raison de la surface sentinelle
                        // de fond
                        do {
                            psurf2 = psurf2->pnext;
                            zinv2 = psurf2->zinv00 +
                                    psurf2->zinvstepx * fx +
                                    psurf2->zinvstepy * fy;
                        } while (zinv < zinv2);
                        // Insère la surface dans la pile
                        psurf->pnext = psurf2;
                        psurf->pprev = psurf2->pprev;
                        psurf2->pprev->pnext = psurf;
                        psurf2->pprev = psurf;
                    }
                }
            } else {
                // Dernier côté; s'il s'agit de la surface de haut,
                // crée le SR et le supprime.
                // S'assure avant tout que les côtés ne se coupent pas
                if (--psurf->state == 0) {
                    if (surfstack.pnext == psurf) {
                        // C'est le haut, crée le SR
                        x = ((pedge->x + 0xFFFF) >> 16);
                        pspan->count = x - psurf->visxstart;
                        if (pspan->count > 0) {
                            pspan->y = y;
                            pspan->x = psurf->visxstart;
                            pspan->color = psurf->color;
                            // S'assure de ne pas déborder
                            // du tableau SR
                            if (pspan < &spans[MAX_SPANS])
                                pspan++;
                        }
                        psurf->pnext->visxstart = x;
                    }
                    // Supprime la surface dans la pile
                    psurf->pnext->pprev = psurf->pprev;
                    psurf->pprev->pnext = psurf->pnext;
                }
            }
        }
        // Supprime les côtés terminés
        pedge = removeedges[y];
        while (pedge) {
            pedge->pprev->pnext = pedge->pnext;
            pedge->pnext->pprev = pedge->pprev;
            pedge = pedge->pnextremove;
        }
        // Avance les côtés restant d'une ligne d'affichage, et re-trie
        for (pedge=edgehead.pnext ; pedge != &edgetail ; ) {
            ptemp = pedge->pnext;
            // Avance le côté
            pedge->x += pedge->xstep;
            // Replace le côté à son emplacement correct,
            // si nécessaire 
            while (pedge->x < pedge->pprev->x) {
                pedge2 = pedge->pprev;
                pedge2->pnext = pedge->pnext;
                pedge->pnext->pprev = pedge2;
                pedge2->pprev->pnext = pedge;
                pedge->pprev = pedge2->pprev;
                pedge->pnext = pedge2;
                pedge2->pprev = pedge;
            }
            pedge = ptemp;
        }
    }
    pspan->x = -1;  // notifie la fin de la liste
}

//Affiche tous les côtés que nous avons parcourus.
void DrawSpans (void)
{
    span_t  *pspan;
    for (pspan=spans ; pspan->x != -1 ; pspan++)
        memset (pDIB + (DIBPitch * pspan->y) + pspan->x,
                pspan->color,
                pspan->count);
}

// Vide les listes des côtés à ajouter ou à supprimer sur chaque ligne d'affichage.
void ClearEdgeLists(void)
{
    int i;
    for (i=0 ; i<DIBHeight ; i++) {
        newedges[i].pnext = &maxedge;
        removeedges[i] = NULL;
    }
}

// Rendu de l'état du monde à l'écran.
void UpdateWorld()
{
    HPALETTE        holdpal;
    HDC             hdcScreen, hdcDIBSection;
    HBITMAP         holdbitmap;
    polygon2D_t     screenpoly;
    polygon_t       *ppoly, tpoly0, tpoly1, tpoly2;
    convexobject_t  *pobject;
    int             i, j, k;
    plane_t         plane;
    point_t         tnormal;

    UpdateViewPos();
    SetUpFrustum();
    ClearEdgeLists();
    pavailsurf = surfs;
    pavailedge = edges;
    // Affiche toutes les faces visible dans tous les objets
    pobject = objecthead.pnext;
    while (pobject != &objecthead) {
        ppoly = pobject->ppoly;
        for (i=0 ; i<pobject->numpolys ; i++) {
            // Déplace le polygone au centre de l'objet
            tpoly0.numverts = ppoly[i].numverts;
            for (j=0 ; j<tpoly0.numverts ; j++) {
                for (k=0 ; k<3 ; k++)
                    tpoly0.verts[j].v[k] = ppoly[i].verts[j].v[k] +
                            pobject->center.v[k];
            }
            if (PolyFacesViewer(&tpoly0, &ppoly[i].plane)) {
                if (ClipToFrustum(&tpoly0, &tpoly1)) {
                    currentcolor = ppoly[i].color;
                    TransformPolygon (&tpoly1, &tpoly2);
                    ProjectPolygon (&tpoly2, &screenpoly);
                    // Déplace le plan du polygone dans l'espace de visualisation
                    // Le déplace avant tout dans l'espace monde
                    // (par rapport à l'objet)
                    tnormal = ppoly[i].plane.normal;
                    plane.distance = ppoly[i].plane.distance +
                        DotProduct (&pobject->center, &tnormal);
                    // Le transforme maintenant dans l'espace de visualisation
                    // Détermine la distance à partir du point de vue
                    plane.distance -=
                          DotProduct (&currentpos, &tnormal);
                    // Effectue la rotation de la normale 
                            plane.normal.v[0] =
                            DotProduct (&tnormal, &vright);
                    plane.normal.v[1] =
                            DotProduct (&tnormal, &vup);
                    plane.normal.v[2] =
                            DotProduct (&tnormal, &vpn);
                    AddPolygonEdges (&plane, &screenpoly);
                }
            }
        }
        pobject = pobject->pnext;
    }
    ScanEdges ();
    DrawSpans ();
    
    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);
    DeleteDC(hdcDIBSection);
}