#define MAX_NUM_LINESEGS 1000 #define MAX_INT 0x7FFFFFFF #define MATCH_TOLERANCE 0.00001 // Un point typedef struct _VERTEX { double x; double y; } VERTEX; // Partie éventuellement séparée d'un segment de droite, traitée à partir la // droite de base dans la liste initiale typedef struct _LINESEG { _LINESEG *pnextlineseg; int startvertex; int endvertex; double walltop; double wallbottom; double tstart; double tend; int color; _LINESEG *pfronttree; _LINESEG *pbacktree; } LINESEG, *PLINESEG; static VERTEX *pvertexlist; static int NumCompiledLinesegs = 0; static LINESEG *pCompiledLinesegs; // Construit un arbre BSP à partir de la liste de droites spécifiée. La liste // doit avoir une entrée au minimum. Si pCurrentTree est NULL, il s'agit bien du // nœud d'origine, autrement pCurrentTree est l'arbre en construction. // Retourne NULL en cas d'erreurs. LINESEG * SelectBSPTree(LINESEG * plineseghead, LINESEG * pCurrentTree, LINESEG ** pParentsChildPointer) { LINESEG *pminsplit; int minsplits; int tempsplitcount; LINESEG *prootline; LINESEG *pcurrentline; double nx, ny, numer, denom, t; // Sélectionne une droite comme origine, et la supprime dans la liste des // droites à classer. Cette droite sélectionnée est celle qui sépare // le moins de droites dans la liste des droites minsplits = MAX_INT; prootline = plineseghead; while (prootline != NULL) { pcurrentline = plineseghead; tempsplitcount = 0; while (pcurrentline != NULL) { // Vérifie le nombre de droites que la droite courante sépare nx = pvertexlist[prootline->startvertex].y - pvertexlist[prootline->endvertex].y; ny = -(pvertexlist[prootline->startvertex].x - pvertexlist[prootline->endvertex].x); // Calcule le produit scalaire pour déterminer l'intersection // et les relations entre les lignes dans l'espace numer = (nx * (pvertexlist[pcurrentline->startvertex].x - pvertexlist[prootline->startvertex].x)) + (ny * (pvertexlist[pcurrentline->startvertex].y - pvertexlist[prootline->startvertex].y)); denom = ((-nx) * (pvertexlist[pcurrentline->endvertex].x - pvertexlist[pcurrentline->startvertex].x)) + ((-ny) * (pvertexlist[pcurrentline->endvertex].y - pvertexlist[pcurrentline->startvertex].y)); // Détermine si les droites de la droite courante // et l'origine se coupent; si tel est le cas, détermine si le // segment de la droite courante est réellement séparé, le sépare, // et ajoute les murs de dessus et de dessous if (denom == 0.0) { // Il n'y a pas d'intersection, car les droites sont parallèles; // Il n'y pas de séparation, donc ne rien faire } else { // Les droites se coupent; détermine si le segment de la droite // courante coupe l'origine // et si tel est le cas sépare t = numer / denom; if ((t > pcurrentline->tstart) && (t < pcurrentline->tend)) { // L'origine divise la droite courante tempsplitcount++; } else { // Intersection à l'extérieur des droites du segment, il // n'y a pas de séparation, ne rien faire } } pcurrentline = pcurrentline->pnextlineseg; } if (tempsplitcount < minsplits) { pminsplit = prootline; minsplits = tempsplitcount; } prootline = prootline->pnextlineseg; } // En fait un nœud pour le moment afin que nous puissions // traverser l'arbre comme s'il était à cette étape. // BuildBSPTree() ajoutera correctement les enfants pminsplit->pfronttree = NULL; pminsplit->pbacktree = NULL; // Le pointeur de l'enfant de parent pointe sur ce nœud, afin que nous // puissions suivre la construction de l'arbre *pParentsChildPointer = pminsplit; return BuildBSPTree(plineseghead, pminsplit, pCurrentTree); } // Construit un arbre BSP en fonction de l'origine spécifiée, en créant les // listes des murs de dessus et de dessous des droites restantes, et en les // appelant elles-mêmes de manière récursive LINESEG * BuildBSPTree(LINESEG * plineseghead, LINESEG * prootline, LINESEG * pCurrentTree) { LINESEG *pfrontlines; LINESEG *pbacklines; LINESEG *pcurrentline; LINESEG *pnextlineseg; LINESEG *psplitline; double nx, ny, numer, denom, t; int Done; // Classe toutes les droites qui ne sont pas l'origine soit au-dessus soit // au-dessous de l'origine, ou sépare par l'origine //, dans ce cas nous la séparons en deux droites pfrontlines = NULL; pbacklines = NULL; pcurrentline = plineseghead; while (pcurrentline != NULL) { // Saute l'origine quand nous la rencontrons if (pcurrentline == prootline) { pcurrentline = pcurrentline->pnextlineseg; } else { nx = pvertexlist[prootline->startvertex].y - pvertexlist[prootline->endvertex].y; ny = -(pvertexlist[prootline->startvertex].x - pvertexlist[prootline->endvertex].x); // Calcule le produit scalaire pour déterminer l'intersection // et les relations entre les droites dans l'espace numer = (nx * (pvertexlist[pcurrentline->startvertex].x - pvertexlist[prootline->startvertex].x)) + (ny * (pvertexlist[pcurrentline->startvertex].y - pvertexlist[prootline->startvertex].y)); denom = ((-nx) * (pvertexlist[pcurrentline->endvertex].x - pvertexlist[pcurrentline->startvertex].x)) + (-(ny) * (pvertexlist[pcurrentline->endvertex].y - pvertexlist[pcurrentline->startvertex].y)); // Détermine si les droites de la droite courante et // l'origine se coupent; si tel est le cas, détermine si le // segment de la droite courante est réellement séparé, alors le sépare // et ajoute correctement les murs de dessus et de dessous if (denom == 0.0) { // Il n'y a pas d'intersection, car les droites sont parallèles; // ajoute dans la liste appropriée pnextlineseg = pcurrentline->pnextlineseg; if (numer < 0.0) { // La droite courante est au-dessus de l'origine; effectue // un lien vers la liste des murs de dessus pcurrentline->pnextlineseg = pfrontlines; pfrontlines = pcurrentline; } else { // La droite courante est au-dessous de l'origine; // effectue un lien vers la liste des murs de dessous pcurrentline->pnextlineseg = pbacklines; pbacklines = pcurrentline; } pcurrentline = pnextlineseg; } else { // Les droites se coupent; détermine si le segment de droite // courant coupe l'origine, si tel est le cas // sépare t = numer / denom; if ((t > pcurrentline->tstart) && (t < pcurrentline->tend)) { // Le segment de droite doit être séparé; ajoute un segment // séparé dans chaque liste if (NumCompiledLinesegs > (MAX_NUM_LINESEGS - 1)) { DisplayMessageBox("Out of space for line segs; " "increase MAX_NUM_LINESEGS"); return NULL; } // Fait une nouvelle entrée de droite dans la partie séparée //de la droite psplitline = &pCompiledLinesegs[NumCompiledLinesegs]; NumCompiledLinesegs++; *psplitline = *pcurrentline; psplitline->tstart = t; pcurrentline->tend = t; pnextlineseg = pcurrentline->pnextlineseg; if (numer < 0.0) { // La partie pré-séparée est au-dessus de l'origine; // effectue un lien vers la liste des murs de dessus et // place cette partie dans la liste des murs de dessous pcurrentline->pnextlineseg = pfrontlines; pfrontlines = pcurrentline; psplitline->pnextlineseg = pbacklines; pbacklines = psplitline; } else { // La partie pré-séparée est au-dessous del'origine; // effectue un lien vers la liste des murs de dessous et // place cette partie dans la liste des murs de dessus psplitline->pnextlineseg = pfrontlines; pfrontlines = psplitline; pcurrentline->pnextlineseg = pbacklines; pbacklines = pcurrentline; } pcurrentline = pnextlineseg; } else { // l'intersection est à l'extérieur des limites du segment, // nous n'avons pas à séparer; ajoute simplement dans la liste // appropriée pnextlineseg = pcurrentline->pnextlineseg; Done = 0; while (!Done) { if (numer < -MATCH_TOLERANCE) { // La droite courante est au-dessus de l'origine; // effectue un lien vers la liste des murs de dessus pcurrentline->pnextlineseg = pfrontlines; pfrontlines = pcurrentline; Done = 1; } else if (numer > MATCH_TOLERANCE) { // La droite courante est en-dessous l'origine; effectue // un lien vers la liste des murs de dessous pcurrentline->pnextlineseg = pbacklines; pbacklines = pcurrentline; Done = 1; } else { // Le point sélectionné sur la droite courante pour // faire l'évaluation dessus/dessous s'avère être // colinéaire avec l'origine, utilise par conséquent // l'autre extrémité de la droite et ressaie numer = (nx * (pvertexlist[pcurrentline->endvertex].x - pvertexlist[prootline->startvertex].x))+ (ny * (pvertexlist[pcurrentline->endvertex].y - pvertexlist[prootline->startvertex].y)); } } pcurrentline = pnextlineseg; } } } } // Crée un nœud en dehors de l'origine, avec les arbres de dessus et dessous // liés if (pfrontlines == NULL) { prootline->pfronttree = NULL; } else { if (!SelectBSPTree(pfrontlines, pCurrentTree, &prootline->pfronttree)) { return NULL; } } if (pbacklines == NULL) { prootline->pbacktree = NULL; } else { if (!SelectBSPTree(pbacklines, pCurrentTree, &prootline->pbacktree)) { return NULL; } } return(prootline); }