12

我正在帮助某人使用用户界面代码来可视化数学图像分析。在此过程中,我们会将 2D 形状的一部分分割成三角形,并在 UI 上填充其中一些三角形。

我们正在寻找一种填充算法,它保证如果两个三角形共享一条边(特别是,如果三角形的任何两个顶点相同),那么无论绘制顺序和锯齿如何,线上都不会出现空白、未绘制的像素两者之间。(如果某些像素被绘制两次也没关系。)在任意缩放下结果应该看起来不错。一些三角形在某些地方可能是非常薄的条子,低至 1 像素宽。

理想情况下,它也应该是一个相当有效的填充算法!

抗锯齿不会用于三角形渲染,因为最终图像需要 1 位深度。

上下文是一个图像识别应用程序,因此所有顶点坐标都将精确到一个像素。

4

7 回答 7

19

鉴于要求,看起来有一个简单的解决方案。

首先,栅格化三角形边缘。您可以为此使用 Bresenham 的线条绘制算法(如下面的代码所示)或任何可行的方法。然后填写中间的区域。这适用于任意薄的三角形。

为了确保无论三角形的绘制顺序和提供给三角形绘制代码的顶点的顺序如何都没有间隙,您希望在共享边的三角形中以相同的方式光栅化共享边。相同的方式意味着每次都使用相同的像素。

为了保证每次你从相同的顶点坐标对获得相同的像素,你基本上想要建立一个固定的顺序,也就是说,建立一个规则,总是从给定的两个顶点中选择相同的一个顶点,而不管顺序如何他们被给予。

执行此顺序的一种简单方法是将您的线(三角形边)视为二维向量,如果它指向负 y 方向或平行于 x 轴并指向负 x 方向,则翻转其方向. 是时候来点 ASCII 艺术了!:)

      3   2   1
       \  |  /
        \ | /
         \|/
4 --------+--------- 0
         /|\
        / | \
       /  |  \
      5   6   7

        4 -> 0
        5 -> 1
        6 -> 2
        7 -> 3

看,这里的线段,比如说,1 和线段 5 真的是同一种东西,唯一的区别是从原点的端点到另一个端点的方向。因此,我们通过将段 4 到 7 转换为段 0 到 3 来将这些情况减少一半,并消除方向模糊。IOW,我们选择向增加 y 的方向前进,或者,如果边缘上的 y 相同,则向增加 x 的方向前进。

这是您可以在代码中执行此操作的方法:

#include <stddef.h>
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

#define SCREEN_HEIGHT 22
#define SCREEN_WIDTH  78

// Simulated frame buffer
char Screen[SCREEN_HEIGHT][SCREEN_WIDTH];

void SetPixel(long x, long y, char color)
{
  if ((x < 0) || (x >= SCREEN_WIDTH) ||
      (y < 0) || (y >= SCREEN_HEIGHT))
  {
    return;
  }

  if (Screen[y][x] == ' ')
    Screen[y][x] = color;
  else
    Screen[y][x] = '*';
}

void Visualize(void)
{
  long x, y;

  for (y = 0; y < SCREEN_HEIGHT; y++)
  {
    for (x = 0; x < SCREEN_WIDTH; x++)
    {
      printf("%c", Screen[y][x]);
    }

    printf("\n");
  }
}

typedef struct
{
  long x, y;
  unsigned char color;
} Point2D;


// min X and max X for every horizontal line within the triangle
long ContourX[SCREEN_HEIGHT][2];

#define ABS(x) ((x >= 0) ? x : -x)

// Scans a side of a triangle setting min X and max X in ContourX[][]
// (using the Bresenham's line drawing algorithm).
void ScanLine(long x1, long y1, long x2, long y2)
{
  long sx, sy, dx1, dy1, dx2, dy2, x, y, m, n, k, cnt;

  sx = x2 - x1;
  sy = y2 - y1;

/*
      3   2   1
       \  |  /
        \ | /
         \|/
4 --------+--------- 0
         /|\
        / | \
       /  |  \
      5   6   7

        4 -> 0
        5 -> 1
        6 -> 2
        7 -> 3
*/
  if (sy < 0 || sy == 0 && sx < 0)
  {
    k = x1; x1 = x2; x2 = k;
    k = y1; y1 = y2; y2 = k;
    sx = -sx;
    sy = -sy;
  }

  if (sx > 0) dx1 = 1;
  else if (sx < 0) dx1 = -1;
  else dx1 = 0;

  if (sy > 0) dy1 = 1;
  else if (sy < 0) dy1 = -1;
  else dy1 = 0;

  m = ABS(sx);
  n = ABS(sy);
  dx2 = dx1;
  dy2 = 0;

  if (m < n)
  {
    m = ABS(sy);
    n = ABS(sx);
    dx2 = 0;
    dy2 = dy1;
  }

  x = x1; y = y1;
  cnt = m + 1;
  k = n / 2;

  while (cnt--)
  {
    if ((y >= 0) && (y < SCREEN_HEIGHT))
    {
      if (x < ContourX[y][0]) ContourX[y][0] = x;
      if (x > ContourX[y][1]) ContourX[y][1] = x;
    }

    k += n;
    if (k < m)
    {
      x += dx2;
      y += dy2;
    }
    else
    {
      k -= m;
      x += dx1;
      y += dy1;
    }
  }
}

void DrawTriangle(Point2D p0, Point2D p1, Point2D p2)
{
  long y;

  for (y = 0; y < SCREEN_HEIGHT; y++)
  {
    ContourX[y][0] = LONG_MAX; // min X
    ContourX[y][1] = LONG_MIN; // max X
  }

  ScanLine(p0.x, p0.y, p1.x, p1.y);
  ScanLine(p1.x, p1.y, p2.x, p2.y);
  ScanLine(p2.x, p2.y, p0.x, p0.y);

  for (y = 0; y < SCREEN_HEIGHT; y++)
  {
    if (ContourX[y][1] >= ContourX[y][0])
    {
      long x = ContourX[y][0];
      long len = 1 + ContourX[y][1] - ContourX[y][0];

      // Can draw a horizontal line instead of individual pixels here
      while (len--)
      {
        SetPixel(x++, y, p0.color);
      }
    }
  }
}

int main(void)
{
  Point2D p0, p1, p2, p3;

  // clear the screen
  memset(Screen, ' ', sizeof(Screen));

  // generate random triangle coordinates

  srand((unsigned)time(NULL));

  // p0 - p1 is going to be the shared edge,
  // make sure the triangles don't intersect
  for (;;)
  {
    p0.x = rand() % SCREEN_WIDTH;
    p0.y = rand() % SCREEN_HEIGHT;

    p1.x = rand() % SCREEN_WIDTH;
    p1.y = rand() % SCREEN_HEIGHT;

    p2.x = rand() % SCREEN_WIDTH;
    p2.y = rand() % SCREEN_HEIGHT;

    p3.x = rand() % SCREEN_WIDTH;
    p3.y = rand() % SCREEN_HEIGHT;

    {
      long vsx = p0.x - p1.x;
      long vsy = p0.y - p1.y;
      long v1x = p0.x - p2.x;
      long v1y = p0.y - p2.y;
      long v2x = p0.x - p3.x;
      long v2y = p0.y - p3.y;
      long z1 = vsx * v1y - v1x * vsy;
      long z2 = vsx * v2y - v2x * vsy;
      // break if p2 and p3 are on the opposite sides of p0-p1
      if (z1 * z2 < 0) break;
    }
  }

  printf("%ld:%ld %ld:%ld %ld:%ld %ld:%ld\n\n",
         p0.x, p0.y,
         p1.x, p1.y,
         p2.x, p2.y,
         p3.x, p3.y);

  // draw the triangles

  p0.color = '-';
  DrawTriangle(p0, p3, p1);
  p1.color = '+';
  DrawTriangle(p1, p2, p0);

  Visualize();

  return 0;
}

样本输出:

30:10 5:16 16:6 59:17







                +++
               ++++++++
              ++++++++++++
             +++++++++++++++++
            +++++++++++++++****---
          +++++++++++++****-----------
         ++++++++++****-------------------
        ++++++*****----------------------------
       +++****-------------------------------------
      ****---------------------------------------------
     *-----------------------------------------------------
                                                           -

传奇:

  • “+” - 三角形 1 的像素
  • “-” - 三角形 2 的像素
  • “*” - 三角形 1 和 2 之间共享的边缘像素

请注意,即使没有未填充的间隙(像素),其像素(在共享边缘上)被覆盖的三角形(因为在其上绘制的另一个三角形)如果太薄,可能会显示为不相交或形状不规则. 例子:

2:20 12:8 59:15 4:17









            *++++++
           *+++++++++++++
          *+++++++++++++++++++++
         -*++++++++++++++++++++++++++++
        -*++++++++++++++++++++++++++++++++++++
        *+++++++++++++++++++++++++++++++++++++++++++
       *+++++++++++++++++++++++++++++++++++++++++++++++++++
      *+++++++++++++++++++++++++++++++++++++++++++++++++++++
     *+++++++++++++++++++++++++++++++++++++++++++
    -*+++++++++++++++++++++++++++++++
   -*+++++++++++++++++++++
   *++++++++++
  *
于 2012-06-21T19:50:07.663 回答
3

您对相邻三角形的关注是有效的。如果两个三角形共享一条边,您要确保沿该边的每个像素都“属于”一个三角形或另一个。如果其中一个像素不属于任何一个三角形,则您有一个间隙。如果它属于两个三角形,则您有过度绘制(效率低下),并且颜色可能取决于三角形的渲染顺序(这可能不是确定性的)。

由于您没有使用抗锯齿,这实际上并不太难。与其说是您需要的智能算法,不如说是仔细实施。

栅格化三角形的典型方法是计算从上到下作为三角形一部分的水平线段。您可以通过跟踪当前的左右边缘来做到这一点,并且基本上对每个扫描线的每个边缘进行 x 截距计算。它也可以通过两个 Bresenhem 风格的线条绘制算法一起运行来完成。y实际上,光栅化相当于对一个函数的多次调用,该函数在某个扫描线上从某个左坐标x0到某个右坐标绘制水平线段x1

void DrawHLine(int y, int x0, int x1);

通常所做的是确保光栅化器以一致的方式舍入 x 截距,以便一致地计算 x 坐标,无论它们是一个三角形的右边缘的一部分还是相邻三角形的左边缘的一部分. 这保证了共享边上的每个像素都属于两个三角形。

我们通过调整解决双重所有权问题DrawHLine,使其填充像素从x0inclusive 到x1 Exclusive。所以共享边上的所有双重拥有的像素都被定义为属于共享边右侧的三角形。

于 2012-06-21T16:57:51.920 回答
3

我意识到不鼓励仅链接的答案,但我已经在我的博客上写过这个确切的问题。Fabian Giesen还在他的优秀系列“优化软件遮挡剔除”中对其进行了讨论。

The gist of it is that you should select a fill rule, which determines how to break the tie for pixels shared between two faces. One such fill rule is specified and well-documented for Microsoft's Direct3D API. It can be implemented using an algorithm similar to Bresenham's line algorithm, but a bit of extra care must be given to the rounding and edge cases.

Even the accepted answer here does not handle negative-x slopes in a consistent way, although since your output is just 1-bit and you don't need to interpolate any attributes, it will probably not matter much.

于 2020-11-16T14:04:03.143 回答
0

这不是最有效的,但您可以遍历包含三角形的正方形并测试每个像素是否在三角形内。

伪代码:

for(x : minX -> maxX)
    for(y : minY -> maxY)
        if(triangle.contains(x,y))
            drawPixel(x,y);

其中 minX 是三个顶点之间的最小 X 坐标,maxX、minY 和 maxY 也是如此。

对于更快的算法,您可以先进行一些快速而肮脏的填充(例如 slashmais Flood 填充),然后对边缘周围的像素执行此操作。

此处描述了三角点测试。

于 2012-06-21T16:10:51.193 回答
0

这是一个经过充分研究的问题。了解 bresenham 画线算法。

http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

于 2012-06-21T17:02:57.620 回答
0

我的答案满足假设。阿德里安麦卡锡在他的回答中所说的是真的。我的算法基于类似的想法,并且是有效的。即使在我看来,不考虑像素的覆盖也是不公平的。但是,我不表示 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);

}
于 2020-03-05T14:37:04.513 回答
-1

您正在寻找的是一种floodfill算法。

这是一个

另一个链接

您可以谷歌“洪水填充算法”了解更多信息。

[编辑]

也许这个网站[Shader-Based Wireframe Drawing] 可以提供更多的想法。

于 2012-06-21T14:06:57.447 回答