数学的画像分析を視覚化するためのユーザー インターフェイス コードで誰かを支援しています。このプロセスでは、2D 形状の一部を三角形に分割し、UI でこれらの三角形の一部を塗りつぶします。
2 つの三角形がエッジを共有している場合 (具体的には、三角形の 2 つの頂点が同一である場合)、描画順序とエイリアシングに関係なく、線上に空白の未描画ピクセルが存在しないことを保証する塗りつぶしアルゴリズムを探しています。ふたつの間に。(一部のピクセルが 2 回描画されても問題ありません。) 結果は、任意のスケーリングで問題なく表示されるはずです。一部の三角形は、幅が 1 ピクセルまでの非常に薄いスライバーである場合があります。
理想的には、適度に効率的な塗りつぶしアルゴリズムであるべきです!
最終イメージは 1 ビット深度である必要があるため、三角形のレンダリングではアンチエイリアシングは使用されません。
コンテキストは画像認識アプリケーションであるため、すべての頂点座標は 1 ピクセルの精度になります。
要件を考えると、簡単な解決策があるようです。
まず、三角形のエッジをラスタライズします。Bresenham の線画アルゴリズム (以下のコードのように) または機能するものなら何でも使用できます。次に、その間の領域を埋めます。これは、任意の薄い三角形で機能します。
三角形が描画される順序に関係なく、また三角形描画コードに提供される頂点の順序に関係なくギャップがないことを確認するには、エッジを共有する三角形で同じ方法で共有エッジをラスタライズします。同じ方法は、毎回同じピクセルを意味します。
同じ頂点座標のペアから同じピクセルを取得するたびに、基本的に固定された順序を確立することを保証するために、つまり、順序に関係なく、指定された 2 つの頂点から常に同じ頂点を選択するルールを確立します。それらが与えられます。
この順序を強制する簡単な方法の 1 つは、線 (三角形の辺) を 2 次元ベクトルとして扱い、それが負の 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 が同じ場合、x が増加する方向で、y が増加する方向に進むことを選択します。
コードでそれを行う方法は次のとおりです。
#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
+++
++++++++
++++++++++++
+++++++++++++++++
+++++++++++++++****---
+++++++++++++****-----------
++++++++++****-------------------
++++++*****----------------------------
+++****-------------------------------------
****---------------------------------------------
*-----------------------------------------------------
-
伝説：
塗りつぶされていないギャップ (ピクセル) がなくても、(共有エッジ上の) ピクセルが上書きされる (その上に別の三角形が描画されるため) 三角形は、細すぎるとバラバラまたはぎこちない形で表示される可能性があることに注意してください。 . 例：
2:20 12:8 59:15 4:17
*++++++
*+++++++++++++
*+++++++++++++++++++++
-*++++++++++++++++++++++++++++
-*++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++
-*+++++++++++++++++++++++++++++++
-*+++++++++++++++++++++
*++++++++++
*
隣接する三角形に関するあなたの懸念は有効なものです。2 つの三角形が 1 つのエッジを共有している場合、そのエッジに沿ったすべてのピクセルがいずれかの三角形に排他的に「属している」ことを確認する必要があります。これらのピクセルの 1 つがどちらの三角形にも属さない場合、ギャップがあります。両方の三角形に属している場合は、オーバードロー (非効率的) であり、色は三角形がレンダリングされる順序に依存する可能性があります (決定論的ではない可能性があります)。
アンチエイリアスを使用していないため、実際にはそれほど難しくありません。慎重に実装する必要があるほど、スマートなアルゴリズムではありません。
三角形をラスタライズする一般的な方法は、三角形の一部である水平セグメントを上から下に計算することです。これを行うには、現在の左端と右端を追跡し、基本的に各走査線で各端の x 切片を計算します。また、2 つの Bresenhem スタイルの線描画アルゴリズムを同時に実行して実行することもできます。y事実上、ラスター化は、左座標x0から右座標まで、あるスキャンラインで水平線分を描画する関数を数回呼び出すことになりますx1。
void DrawHLine(int y, int x0, int x1);
通常、ラスタライザーが一貫した方法で x 切片を丸めるようにすることで、x 座標が 1 つの三角形の右端の一部であるか隣接する三角形の左端の一部であるかに関係なく、一貫して x 座標が計算されます。 . これにより、共有エッジに沿ったすべてのピクセルが両方の三角形に属することが保証されます。
二重所有権は、包括的から排他DrawHLine的までのピクセルを埋めるように微調整することで解決します。したがって、共有エッジ上の二重所有ピクセルはすべて、共有エッジの右側の三角形に属するように定義されます。x0x1
これは最も効率的ではありませんが、三角形を含む正方形をループして、各ピクセルが三角形内にあるかどうかをテストできます。
擬似コード：
for(x : minX -> maxX)
for(y : minY -> maxY)
if(triangle.contains(x,y))
drawPixel(x,y);
ここで、minXは3つの頂点間の最小X座標であり、maxX、minY、およびmaxYについても同様です。
より高速なアルゴリズムの場合、最初にいくつかの迅速で汚れた塗りつぶし（たとえば、slashmaisフラッド塗りつぶし）を実行してから、エッジの周りのピクセルに対してこれを実行できます。
ポイントイントライアングルテストについては、ここで説明します。
これはよく研究されている問題です。Bresenham 線描画アルゴリズムについて学習します。