我的答案满足假设。阿德里安麦卡锡在他的回答中所说的是真的。我的算法基于类似的想法,并且是有效的。即使在我看来,不考虑像素的覆盖也是不公平的。但是,我不表示 N-1 像素的水平线,否则三角形,如果它是“碎片”,它将不会被表示。
例如:假设我们有两个相邻的三角形:
ABC [A (27.15) -B (32.15) -C (37.15)];
DEF [A (29.15) -B (32.15) -C (35.15)];
表示将重叠,但结果应该是以下类型的水平段:
++-------------------------++
所以仅仅排除最后一个像素以避免覆盖是不够的。
要表示一个实心三角形,以便可以使用创建的函数来表示实心多边形(例如:四边形),因为它们总是可以划分为三角形,所以必须能够排除边的表示,否则,可能会发生三角形的一侧被相邻三角形的一侧覆盖(显示透明多边形的问题)。我向您建议的这是C
我的算法的实现,用于表示任何类型的三角形。我建议您尝试一下,因为它速度快,虽然相当复杂且高效。这是我的Bresenham
算法变体。代表水平线段的例程的实现,我把它留给你(我已经替换了对Put
(Shadow)的调用HorizLine ()
,对于水平线段的表示,附上Line ()
说明,因为我的实现DrawHLine()
不能插入到本帖中;但是在这里我Line()
只使用指令来绘制水平线段)。
这个函数最初是为使用我自己的格式(称为 OBP)在 RAM 中的缓冲区提供的,它与 RASTER 格式的不同之处仅在于两个原因:扫描线与 16 字节对齐。在数据之前有一个 16 字节的标头(每个像素为 8 位);此标头包含前 2 个字中图像的大小(在汇编实现中,您可以选择,因此是否充分利用 CPU 寄存器,而不是 RAM 中的变量,因为 32 位寄存器可以包含两个维度并且,在中等规模的图像上,一个点的几何位置也可以包含在一个 32 位寄存器中)。这里唯一需要做的就是重写对Line()
函数,由于要指定三角形一侧的颜色,它可能与其他边不同,透明或不存在,需要修改对象的属性,而不是直接将颜色作为参数传递到line()
函数,虽然曾经可以调用SetColor()
函数,这里只是指示性的。
她是标题(triangle.h
):
#define R_OBP_Al 16 /* 16 Byte alignment; it must always be 2^N */
#define DimOBP_H 16 /* 16 Byte of OBP HEADER; it must always be >=4 */
#define True 1 /* Boolean value for true condition */
#define False 0 /* Boolean value for false condition */
typedef char TShadowTable[256]; /* Array for shadows */
typedef TShadowTable *T_Shadow_Table_Ptr; /* Pointer to an array for shadows */
typedef struct {short int X;
short int Y;} T_Coord_XY;
typedef struct {unsigned short int X;
unsigned short int Y;} T_Pos_Coord_XY;
typedef struct {unsigned short int DimX;
unsigned short int DimY;} T_Dim_XY;
typedef struct {T_Pos_Coord_XY XY; /* Coordinates of the clipping-region */
T_Dim_XY Dim_XY; /* Dimensions of the clipping-region */ } T_Clipp_Rect;
typedef T_Clipp_Rect *T_Clipp_Rect_Ptr; /* Pointer to clipping-region's type */
typedef struct {T_Coord_XY XY; /* Coordinates of the rectangle */
T_Dim_XY Dim_XY; /* Dimensions of the rectangle */ } T_Rect;
typedef T_Rect *T_Rect_Ptr; /* Pointer to a rectangle */
typedef char Boolean; /* Boolean type */
void Triangle_Wind(short int X1,
short int Y1,
short int X2,
short int Y2,
short int X3,
short int Y3,
short int FillColor,
short int BrdColAB,
short int BrdColBC,
short int BrdColCA
/* , T_Shadow_Table_Ptr ShadowTable,
void *OBPVBuff
T_Clipp_Rect_Ptr Clipp */);
以下是函数和示例 ( triangle.c
):
#include <graphics.h>
#include <conio.h>
#include <string.h>
#include <stdio.h>
#include "triangle.h"
static int *DefColors[16]=
{0FF000000H, /* Black */
0FF7F0000H, /* Blue */
0FF007F00H, /* Green */
0FF7F7F00H, /* Cyan */
0FF00007FH, /* Red */
0FF7F007FH, /* Magenta */
0FF007F7FH, /* Brown */
0FF7F7F7FH, /* LightGray */
0FF3F3F3FH, /* DarkGray */
0FFFF0000H, /* LightBlue */
0FF00FF00H, /* LightGreen */
0FFFFFF00H, /* LightCyan */
0FF0000FFH, /* LightRed */
0FFFF00FFH, /* LightMagenta */
0FF00FFFFH, /* Yellow */
0FFFFFFFFH /* White */ };
int main(void)
{
/* int gd = DETECT;
int gm;
initgraph(&gd, &gm, "C:\\TC\\BGI"); */
Triangle_Wind(80,80,320,200,160,300,
4,1,2,7);
getch();
/* closegraph(); */
return 0;
}
/* Here it is the body of the triangle routine: */
void Triangle_Wind(short int X1,
short int Y1,
short int X2,
short int Y2,
short int X3,
short int Y3,
short int FillColor,
short int BrdColAB,
short int BrdColBC,
short int BrdColCA
/* , T_Shadow_Table_Ptr ShadowTable,
void *OBPVBuff
T_Clipp_Rect_Ptr Clipp */)
{short int A=0;
short int B=1;
short int C=2; /* Identificat. vertici triangoli per ordinam. colori */
short int C1=BrdColAB;
short int C2=BrdColBC;
short int C3=BrdColCA; /* Var. temp. per i colori */
short int XT; /* X1-XT è il segmento orizzontale da disegnare */
short int OY2; /* Valore iniziale coord. Y 2° vertice del triangolo */
short int B1L;
short int B1H; /* Coord. X 1° e ultimo punto 1° bordo (segm. orizz.) */
short int B2L;
short int B2H; /* Coord. X 1° e ultimo punto 2° bordo (segm. orizz.) */
short int D0; /* Dimensione 1° bordo (segm. orizz.) */
short int D1; /* Dimensione parte centrale segm. orizz. */
short int D2; /* Dimensione 2° bordo (segm. orizz.) */
short int Tmp; /* Variabile temporanea x scambio di 2 variabili */
short int Col1; /* Colore 1° bordo segm. orizz. */
short int Col2; /* Colore 2° bordo segm. orizz. */
short int CntX1; /* Contat. per coord. X 1° punto segm. orizz. (Bresenham) */
short int IncX1; /* Increm. contat. per coord. X 1° punto segm. or. (Bresenham) */
short int CntY1; /* Contat. per coord. Y 1° punto segm. orizz. (Bresenham) */
short int Lim1; /* Limite per contat. coord. X e Y 1° punto segm. or. (Bresenham) */
short int DirX1; /* Increm. coord. X 1° punto segm. orizz. */
short int IncY1; /* Increm. contat. per coord. Y 1° punto segm. or. (Bresenham) */
short int FX1; /* Valore iniziale coord. X1 segm. orizz. X1-XT */
short int CntXT; /* Contat. per coord. X 2° punto segm. orizz. (Bresenham) */
short int IncXT; /* Increm. contat. per coord. X 2° punto segm. or. (Bresenham) */
short int CntYT; /* Contat. per coord. Y 2° punto segm. orizz. (Bresenham) */
short int LimT; /* Limite per contat. coord. X e Y 2° punto segm. or. (Bresenham) */
short int DirXT; /* Increm. coord. X 2° punto segm. orizz. */
short int IncYT; /* Increm. contat. per coord. Y 2° punto segm. or. (Bresenham) */
short int FXT; /* Valore iniziale coord. XT segm. orizz. X1-XT */
T_Rect Segm; /* Record per la rappresentazione di un segm. orizz. */
Boolean F1; /* 1° cond. iniz. (eccezione), rappresentaz. triang. */
Boolean F24; /* 2° cond. iniz. (eccezione), rappresentaz. triang. */
Boolean Overflow=False; /* FALSE: Calcola segm. orizz.; TRUE: Ha finito */
Boolean Internal; /* Variabile temp.; salva il val. iniz. di Overflow */
Boolean Finished=True; /* FALSE: 2° semi-triang.; TRUE: 1° semi-triang.} */
/* Ordina i vertici in base alla coordinata Y */
if (Y1>Y2)
{Tmp=X1;
X1=X2;
X2=Tmp;
Tmp=Y1;
Y1=Y2;
Y2=Tmp;
Tmp=A;
A=B;
B=Tmp;}
if (Y2>Y3)
{Tmp=X2;
X2=X3;
X3=Tmp;
Tmp=Y2;
Y2=Y3;
Y3=Tmp;
Tmp=B;
B=C;
C=Tmp;}
if (Y1>Y2)
{Tmp=X1;
X1=X2;
X2=Tmp;
Tmp=Y1;
Y1=Y2;
Y2=Tmp;
Tmp=A;
A=B;
B=Tmp;}
/* Calcola il colore effettivo dei lati A-B, B-C e C-A del triangolo */
switch (27*A+9*B+C)
{case 19:{BrdColAB=C3;
BrdColCA=C1;
break;}
case 29:{BrdColBC=C3;
BrdColCA=C2;
break;}
case 45:{BrdColAB=C2;
BrdColBC=C3;
BrdColCA=C1;
break;}
case 55:{BrdColAB=C3;
BrdColBC=C1;
BrdColCA=C2;
break;}
case 63:{BrdColAB=C2;
BrdColBC=C1;
break;
}}
/* Calc. incr. e limiti, inizial. i cont. lato A-C (Bresenham) */
DirXT=-1;
IncXT=X1-X3;
if (X1<X3)
{DirXT=1;
IncXT=-IncXT;}
IncXT+=1;
CntXT=IncXT>>1;
IncYT=Y3-Y1+1;
CntYT=IncYT>>1;
LimT=IncXT;
if (IncXT<IncYT)
LimT=IncYT;
/* Imposta i valori iniziali delle var. locali */
XT=X1;
OY2=Y2;
F1=(Y1>=Y2) || (Y2!=Y3);
F24=((Y1!=Y2) || (Y2>=Y3)) &&
((Y1>=Y2) || (Y2>=Y3));
/* Disegna il primo vertice del triangolo */
if ((X1=X2) && (X2=X3) &&
(Y1=Y2) && (Y2=Y3))
{/* Segm->XY->X=X1;
Segm->XY->Y=Y1;
Segm->Dim_XY->DimX=1; */
Col1=BrdColAB;
if (Col1<0)
Col1=BrdColCA;
if (Col1<0)
Col1=FillColor;
if (Col1>=0)
{setcolor(DefColors[Col1]);
line(X1,Y1,X1,Y1);}
/* if (Col1<256)
PutHorizLine(&Segm,OBPVBuff,Col1,Clipp)
else
PutShadowHorizLine(&Segm,OBPVBuff,ShadowTable,Clipp); */}
/* Disegna il triangolo */
do
{/* Calc. incr. e limiti, inizial. i cont. lato A-B (Bresenham) */
DirX1=-1;
IncX1=X1-X2;
if (X1<X2)
{DirX1=1;
IncX1=-IncX1;}
IncX1+=1;
CntX1=IncX1>>1;
IncY1=Y2-Y1+1;
CntY1=IncY1>>1;
Lim1=IncX1;
if (IncX1<IncY1)
Lim1=IncY1;
FX1=X1;
FXT=XT;
/* Rappresenta un semi-triangolo */
while ((X1!=X2) || (Y1!=Y2))
{
/* Calcola i 4 estremi del segmento orizzontale da disegnare */
do
{Internal=Overflow;
if (Overflow)
{CntY1-=Lim1;
CntYT-=LimT;
Y1+=1;}
Overflow=True;
Tmp=CntY1+IncY1;
if (Tmp<Lim1)
{CntY1=Tmp;
CntX1+=IncX1;
if (CntX1>=Lim1)
{CntX1-=Lim1;
X1+=DirX1;}
Overflow=False;}
Tmp=CntYT+IncYT;
if (Tmp<LimT)
{CntYT=Tmp;
CntXT+=IncXT;
if (CntXT>=LimT)
{CntXT-=LimT;
XT+=DirXT;}
Overflow=False;}
if (Internal)
{FX1=X1;
FXT=XT;}
} while (!Overflow);
/* Ordina (ord. ascend.) i 4 estremi del segmento orizzontale */
B1L=FX1;
B1H=X1;
if (B1L>B1H)
{Tmp=B1L;
B1L=B1H;
B1H=Tmp;}
B2L=FXT;
B2H=XT;
if (B2L>B2H)
{Tmp=B2L;
B2L=B2H;
B2H=Tmp;}
Col1=BrdColAB;
Col2=BrdColCA;
if ((B2L<B1L) || (B2H<B1H))
{Tmp=B1L;
B1L=B2L;
B2L=Tmp;
Tmp=B1H;
B1H=B2H;
B2H=Tmp;
Tmp=Col1;
Col1=Col2;
Col2=Tmp;}
/* Calcola la posizione e la dimensione dei 2 bordi del segm. orizz. */
D1=B1H-B1L+1;
D0=B2L-B1H-1;
D2=B2H-B2L+1;
/* Ove possibile, unisce bordi con parte centrale del segm. orizz. */
if (D0>0)
{if (FillColor==Col2) /* Parte0 unita a parte2, parte0 esistente */
{D0+=D2;
D2=0;}
if (Col1==FillColor) /* Parte0 unita a parte1, parte0 esistente */
{B1H=B1L-1;
D0+=D1;
D1=0;}}
else
{D0=0;
if (Col1==Col2) /* Parte1 unita a parte2, parte0 inesistente */
{D1=B2H-B1L+1;
D2=0;}}
/* Rappresenta il primo bordo del segm. orizz. */
/* Segm->XY->Y=Y1;
Segm->XY->X=B1L;
Segm->Dim_XY->DimX=D1; */
if ((Col1>=0) && (D1>0))
{setcolor(DefColors[Col1]);
line(B1L,Y1,B1L+D1-1,Y1);}
/* if (Col1<256)
PutHorizLine(&Segm,OBPVBuff,Col1,Clipp)
else
PutShadowHorizLine(&Segm,OBPVBuff,ShadowTable,Clipp); */
/* Rappresenta la parte centrale del segm. orizz. */
if (((Y1!=OY2) ||
(!Finished || F1) && (Finished || F24)) && (D0>0))
{
/* Segm->XY->X=B1H+1;
Segm->Dim_XY->DimX=D0; */
if ((FillColor>=0) && (D0!=0))
{setcolor(DefColors[FillColor]);
line(B1H+1,Y1,B1H+D0,Y1);}
/* if (FillColor<256)
PutHorizLine(&Segm,OBPVBuff,FillColor,Clipp)
else
PutShadowHorizLine(&Segm,OBPVBuff,ShadowTable,Clipp); */
}
/* Rappresenta il secondo bordo del segm. orizz. */
/* Segm->XY->X=B2L;
Segm->Dim_XY->DimX=D2; */
if ((Col2>=0) && (D2>0))
{setcolor(DefColors[Col2]);
line(B2L,Y1,B2L+D2-1,Y1);}
/* if (Col2<256)
PutHorizLine(&Segm,OBPVBuff,Col2,Clipp)
else
PutShadowHorizLine(&Segm,OBPVBuff,ShadowTable,Clipp); */
}
X2=X3;
Y2=Y3;
BrdColAB=BrdColBC;
Finished=!Finished;
} while (!Finished);
}