/* Remplit de couleur un polygone convexe. Tous les points sont sous la forme (XOffset, YOffset). "Convexe" signifie que chaque ligne horizontale affichée dans le polygone devrait, en tout point, traverser deux bords actifs exactement (ni les lignes horizontales ni les bords de longueur zéro ne comptent comme bords actifs) et que les bords droit et gauche ne se croisent jamais. (Certes, ils peuvent se toucher, tant que le bord droit ne croise jamais la gauche du bord gauche). Les polygones non convexes ne seront pas affichés correctement. Retourne 1 en cas de succès,0 si l'allocation mémoire a échoué. Compilé avec Borland C++ 4.02. Lié avec L21-3.C. Testé par Jim Mischel 11/30/94. */ #include #include #ifdef __TURBOC__ #include #else /* MSC */ #include #endif #include "polygon.h" /* Avance l'index d'un point dans la liste des points, en bouclant en fin de liste */ #define INDEX_FORWARD(Index) \ Index = (Index + 1) % VertexList->Length; /* Recule l'index d'un point dans la liste des points, en bouclant au début de la liste */ #define INDEX_BACKWARD(Index) \ Index = (Index - 1 + VertexList->Length) % VertexList->Length; /* Avance ou recule l'index d'un point dans la liste des points en bouclant à l'une des extrémités de la liste */ #define INDEX_MOVE(Index,Direction) \ if (Direction > 0) \ Index = (Index + 1) % VertexList->Length; \ else \ Index = (Index - 1 + VertexList->Length) % VertexList->Length; extern void DrawHorizontalLineList(struct HLineList *, int); static void ScanEdge(int, int, int, int, int, int, struct HLine **); int FillConvexPolygon(struct PointListHeader * VertexList, int Color, int XOffset, int YOffset) { int i, MinIndexL, MaxIndex, MinIndexR, SkipFirst, Temp; int MinPoint_Y, MaxPoint_Y, TopIsFlat, LeftEdgeDir; int NextIndex, CurrentIndex, PreviousIndex; int DeltaXN, DeltaYN, DeltaXP, DeltaYP; struct HLineList WorkingHLineList; struct HLine *EdgePointPtr; struct Point *VertexPtr; /* Pointe sur la liste des points */ VertexPtr = VertexList->PointPtr; /* Parcourt la liste pour trouver le sommet et la base du polygone */ if (VertexList->Length == 0) return(1); /* rejette les polygones nulls*/ MaxPoint_Y = MinPoint_Y = VertexPtr[MinIndexL = MaxIndex = 0].Y; for (i = 1; i < VertexList->Length; i++) { if (VertexPtr[i].Y < MinPoint_Y) MinPoint_Y = VertexPtr[MinIndexL = i].Y; /* point le plus haut */ else if (VertexPtr[i].Y > MaxPoint_Y) MaxPoint_Y = VertexPtr[MaxIndex = i].Y; /*point le plus bas */ } if (MinPoint_Y == MaxPoint_Y) return(1); /* le polygone a une hauteur=0; pour évité une boucle infinie ci-dessous */ /* Parcourt dans l'ordre croissant pour trouver le dernier point du coté haut */ MinIndexR = MinIndexL; while (VertexPtr[MinIndexR].Y == MinPoint_Y) INDEX_FORWARD(MinIndexR); INDEX_BACKWARD(MinIndexR); /* revient au dernier point du coté haut */ /* Parcourt dans l'ordre décroissant pour trouver le premier point du coté haut */ while (VertexPtr[MinIndexL].Y == MinPoint_Y) INDEX_BACKWARD(MinIndexL); INDEX_FORWARD(MinIndexL); /*revient au premier point du coté haut */ /* retrouve de la direction de la liste des points depuis le point du sommet quel est le coté gauche et quel est le droit */ LeftEdgeDir = -1; /*suppose que le coté gauche descend dans liste des points */ if ((TopIsFlat = (VertexPtr[MinIndexL].X != VertexPtr[MinIndexR].X) ? 1 : 0) == 1) { /* Si le sommet est plat, vérifie simplement quelle est l'extrémité la plus à gauche */ if (VertexPtr[MinIndexL].X > VertexPtr[MinIndexR].X) { LeftEdgeDir = 1; /* le coté gauche remonte dans la liste des points */ Temp = MinIndexL; /* permute les indexes de telle sorte que MinIndexL */ MinIndexL = MinIndexR; /* pointe sur le début du coté gauche */ MinIndexR = Temp; /* il en va de même pour MinIndexR */ } } else { /* Pointe sur l'extrémité basse de la première ligne de chacun des deux coté allant de haut en bas */ NextIndex = MinIndexR; INDEX_FORWARD(NextIndex); PreviousIndex = MinIndexL; INDEX_BACKWARD(PreviousIndex); /* Calcule les longueurs X et Y depuis le point le plus haut jusqu'à la fin de la première ligne en descendant le long de chaque coté; utiliser pour comparer les pentes et pour vérifier quelle est la ligne la plus à gauche */ DeltaXN = VertexPtr[NextIndex].X - VertexPtr[MinIndexL].X; DeltaYN = VertexPtr[NextIndex].Y - VertexPtr[MinIndexL].Y; DeltaXP = VertexPtr[PreviousIndex].X - VertexPtr[MinIndexL].X; DeltaYP = VertexPtr[PreviousIndex].Y - VertexPtr[MinIndexL].Y; if (((long)DeltaXN * DeltaYP - (long)DeltaYN * DeltaXP) < 0L) { LeftEdgeDir = 1; /* le coté gauche remonte la liste des points */ Temp = MinIndexL; /* permute les indices de telle sorte que MinIndexL */ MinIndexL = MinIndexR; /* pointe sur le début du coté gauche */ MinIndexR = Temp; /* il en va de même pour MinIndexR */ } } /* Détermine le nombre de lignes d'affichage dans le polygone, en sautant le coté de la base et le point le plus haut si le sommet n'est pas plat car dans ce cas le point le plus haut a un composant de bord droit, et paramètre la ligne d'affichage du sommet à afficher, laquelle correspond à la deuxième ligne du polygone à moins que le sommet ne soit plat */ if ((WorkingHLineList.Length = MaxPoint_Y - MinPoint_Y - 1 + TopIsFlat) <= 0) return(1); /* Rien n'est à afficher, nous avons donc fini */ WorkingHLineList.YStart = YOffset + MinPoint_Y + 1 - TopIsFlat; /* Récupère la mémoire pour stocker la liste des lignes que nous générons */ if ((WorkingHLineList.HLinePtr = (struct HLine *) (malloc(sizeof(struct HLine) * WorkingHLineList.Length))) == NULL) return(0); /* nous ne pouvons pas récupérer de mémoire pour la liste des lignes */ /* Parcourt le coté gauche et stocke les points des extrémités dans la liste */ /* Pointeur initial pour stocker les coordonnées numérisées du coté droit */ EdgePointPtr = WorkingHLineList.HLinePtr; /* Commence en haut du coté gauche */ PreviousIndex = CurrentIndex = MinIndexL; /* Saute le premier point de la première ligne à moins que le sommet ne soit plat;si le sommet n'est pas plat, le point du sommet est bien sur le coté droit et n'est pas affiché */ SkipFirst = TopIsFlat ? 0 : 1; /* Numérise chaque ligne du coté gauche de haut en bas */ do { INDEX_MOVE(CurrentIndex,LeftEdgeDir); ScanEdge(VertexPtr[PreviousIndex].X + XOffset, VertexPtr[PreviousIndex].Y, VertexPtr[CurrentIndex].X + XOffset, VertexPtr[CurrentIndex].Y, 1, SkipFirst, &EdgePointPtr); PreviousIndex = CurrentIndex; SkipFirst = 0; /* numérise le premier point */ } while (CurrentIndex != MaxIndex); /* Parcourt le coté droit et stocke les points extrêmes dans la liste */ EdgePointPtr = WorkingHLineList.HLinePtr; PreviousIndex = CurrentIndex = MinIndexR; SkipFirst = TopIsFlat ? 0 : 1; /* Numérise le coté droit, de haut en bas. Les coordonnées de X sont ajustées à 1 vers la gauche, causant effectivement la numérisation des points les plus à gauche mais pas exactement sur le coté */ do { INDEX_MOVE(CurrentIndex,-LeftEdgeDir); ScanEdge(VertexPtr[PreviousIndex].X + XOffset - 1, VertexPtr[PreviousIndex].Y, VertexPtr[CurrentIndex].X + XOffset - 1, VertexPtr[CurrentIndex].Y, 0, SkipFirst, &EdgePointPtr); PreviousIndex = CurrentIndex; SkipFirst = 0; /* numérise le premier point */ } while (CurrentIndex != MaxIndex); /* Affiche la liste des lignes représentant le polygone numérisé */ DrawHorizontalLineList(&WorkingHLineList, Color); /* Libère la mémoire de la liste des lignes, nous avons réussi */ free(WorkingHLineList.HLinePtr); return(1); } /* Numérise un coté de (X1,Y1) à (X2,Y2), ce qui ne comprend pas le point en(X2,Y2). ce qui évite le chevauchement de l'extrémité d'une ligne avec le début d'une autre, et fait que la ligne d'affichage du bas du polygone ne peut pas être affichée. Si SkipFirst != 0, le point en (X1,Y1) n'est pas affiché. Pour chaque ligne d'affichage, le pixel le plus proche de la ligne affichée sans être à la gauche de la ligne affichée est choisi */ static void ScanEdge(int X1, int Y1, int X2, int Y2, int SetXStart, int SkipFirst, struct HLine **EdgePointPtr) { int Y, DeltaX, DeltaY; double InverseSlope; struct HLine *WorkingEdgePointPtr; /* Calcule les longueurs X et Y de la ligne et la pente inverse */ DeltaX = X2 - X1; if ((DeltaY = Y2 - Y1) <= 0) return; /* évite les bords horizontaux de longueur 0 */ InverseSlope = (double)DeltaX / (double)DeltaY; /* Stocke la coordonnée X du pixel le plus proche mais pas à gauche de la ligne pour chaque coordonnée Y entre Y1 et Y2, ce qui ne comprend pas Y2 ainsi que Y1 si SkipFirst != 0 */ WorkingEdgePointPtr = *EdgePointPtr; /* évite double référence */ for (Y = Y1 + SkipFirst; Y < Y2; Y++, WorkingEdgePointPtr++) { /* Stocke la coordonnée X dans la liste du bord approprié */ if (SetXStart == 1) WorkingEdgePointPtr->XStart = X1 + (int)(ceil((Y-Y1) * InverseSlope)); else WorkingEdgePointPtr->XEnd = X1 + (int)(ceil((Y-Y1) * InverseSlope)); } *EdgePointPtr = WorkingEdgePointPtr; /* avance ptr de l'appelant */ }