tl;dr座標点を使用して配列内に滑らかな線を描画する非常に高速な方法は何ですか? 注: 以下の情報を読むことで、非常に必要なコンテキストが提供される可能性があります。
私は現在、コンウェイのライフ ゲームの実装に取り組んでいます。一度に 2 つのポイントに対してマウス リスナー [具体的には mouseDragged] を使用し、それらをこのメソッドに渡します。
public void findIndexSmoothed(int x, int y, int nx, int ny)
{
int size1 = size / 2 + 1; // radius
size1 *= brush;
int searchMargin = 10; // how many squares are checked within a certain
double slope;
// ((x/size) -50 >0) ? ((x/size) -50) : 0
// Optimizes performance at the expense of function
// UPDATE: a simple if/else reduced function loss to nominal levels
if (x + 2.5 < nx)
{
slope = (((double) ny - y) / (nx - x));
for (int i = 0; i < sY; i++)
{
for (int j = ((x / size) - searchMargin > 0) ? ((x / size) - searchMargin) : 0; j <
sX; j++) {
for (double c = x; c <= nx; c += 1)
{
if ((valCoord[i][j][0] >= c - size1 && valCoord[i][j][0] <= c + size1)
&& (valCoord[i][j][1] >= ((slope * (c - x)) + y) - size1 && valCoord[i][j][1] <= ((slope * (c - x)) + y)
+ size1))
{
flagVals[i][j] = true;
actualVals[i][j] = true;
cachedVals[i][j] = true;
cachedVals[i + 1][j + 1] = true;
cachedVals[i + 1][j] = true;
cachedVals[i + 1][j - 1] = true;
cachedVals[i][j + 1] = true;
cachedVals[i][j - 1] = true;
cachedVals[i - 1][j + 1] = true;
cachedVals[i - 1][j - 1] = true;
cachedVals[i - 1][j + 1] = true;
}
}
}
}
}
else if (x - 2.5 > nx)
{
slope = (((double) ny - y) / (nx - x));
int d = ((x / size) + searchMargin < sX) ? ((x / size) + searchMargin) : sX;
for (int i = 0; i < sY; i++)
{
for (int j = 0; j < d; j++)
{
for (double c = nx; c <= x; c += 1)
{
if ((valCoord[i][j][0] >= c - size1 && valCoord[i][j][0] <= c + size1)
&& (valCoord[i][j][1] >= ((slope * (c - x)) + y) - size1 && valCoord[i][j][1] <= ((slope * (c - x)) + y)
+ size1))
{
flagVals[i][j] = true;
actualVals[i][j] = true;
cachedVals[i][j] = true;
cachedVals[i + 1][j + 1] = true;
cachedVals[i + 1][j] = true;
cachedVals[i + 1][j - 1] = true;
cachedVals[i][j + 1] = true;
cachedVals[i][j - 1] = true;
cachedVals[i - 1][j + 1] = true;
cachedVals[i - 1][j - 1] = true;
cachedVals[i - 1][j + 1] = true;
}
}
}
}
}
else
{
if (ny > y)
{
for (int i = 0; i < sY; i++)
{
for (int j = ((x / size) - searchMargin > 0) ? ((x / size) - searchMargin) : 0; j < sX; j++)
{
for (double c = y; c <= ny; c++)
{
if ((valCoord[i][j][0] >= x - size1 && valCoord[i][j][0] <= x + size1)
&& (valCoord[i][j][1] >= c - size1 && valCoord[i][j][1] <= c + size1))
{
flagVals[i][j] = true;
actualVals[i][j] = true;
cachedVals[i][j] = true;
cachedVals[i + 1][j + 1] = true;
cachedVals[i + 1][j] = true;
cachedVals[i + 1][j - 1] = true;
cachedVals[i][j + 1] = true;
cachedVals[i][j - 1] = true;
cachedVals[i - 1][j + 1] = true;
cachedVals[i - 1][j - 1] = true;
cachedVals[i - 1][j + 1] = true;
}
}
}
}
}
else
{
for (int i = 0; i < sY; i++)
{
for (int j = ((x / size) - searchMargin > 0) ? ((x / size) - searchMargin) : 0; j < sX; j++)
{
for (double c = ny; c <= y; c++)
{
if ((valCoord[i][j][0] >= x - size1 && valCoord[i][j][0] <= x + size1)
&& (valCoord[i][j][1] >= c - size1 && valCoord[i][j][1] <= c + size1))
{
flagVals[i][j] = true;
actualVals[i][j] = true;
cachedVals[i][j] = true;
cachedVals[i + 1][j + 1] = true;
cachedVals[i + 1][j] = true;
cachedVals[i + 1][j - 1] = true;
cachedVals[i][j + 1] = true;
cachedVals[i][j - 1] = true;
cachedVals[i - 1][j + 1] = true;
cachedVals[i - 1][j - 1] = true;
cachedVals[i - 1][j + 1] = true;
}
}
}
}
}
}
}
わかりました、まだ目が出血していない場合は、この巨獣が正確に何をしているのか説明させてください. まず、マウスがドラッグされている方向を計算します。うまくいっているとしましょう。次に、2 つの点によって形成される直線の傾きを計算し、これら 3 つのネストされた for ループを通過します。
for (int i = 0; i < sY; i++)
{
for (int j = ((x / size) - searchMargin > 0) ? ((x / size) - searchMargin) : 0; j <
sX; j++) {
for (double c = x; c <= nx; c += 1)
{
if ((valCoord[i][j][0] >= c - size1 && valCoord[i][j][0] <= c + size1)
&& (valCoord[i][j][1] >= ((slope * (c - x)) + y) - size1 && valCoord[i][j][1] <= ((slope * (c - x)) + y)
+ size1))
{
flagVals[i][j] = true;
actualVals[i][j] = true;
cachedVals[i][j] = true;
cachedVals[i + 1][j + 1] = true;
cachedVals[i + 1][j] = true;
cachedVals[i + 1][j - 1] = true;
cachedVals[i][j + 1] = true;
cachedVals[i][j - 1] = true;
cachedVals[i - 1][j + 1] = true;
cachedVals[i - 1][j - 1] = true;
cachedVals[i - 1][j + 1] = true;
}
}
}
配列の垂直部分全体をループし、水平方向のサブセクションをループします。最後の for ループは、2 点間のすべての X 座標を通過します。if ステートメントは、その X 値を直線の方程式に代入し、対応する Y 値を見つけ、座標点の配列が一致するかどうかをチェックします。見つかった場合は、処理に使用される配列 [および対応する配列] をその場所で true に設定します。(キャッシュされた値は無視できます。これはグリッドの最適化の一部であり、質問にはあまり関係ありません)
かなり小さなグリッド (たとえば 100x100) では、これは完全に機能し、ラグはほとんどありません。ただし、700 万もの位置を含めることができる、はるかに大きなグリッド [約 3000x2500] を使用しています。このコードを最適化する [または完全に変更する] 方法についてのアイデアはありますか?
編集：だから私はこれを少し前に機能させましたが、ここに投稿するのを忘れていました。他の誰かが同様の問題を抱えている場合、ここに私の実装があります:
public void findIndexSmoothedII(int x, int y, int nx, int ny) // A custom implementation of Bresenham's Line
// Algorithm
{
// preliminary brush size and super-sampling calculations
int use = (size / 2 + 1) * brush / size;
int shift = superSampled ? 1 : 0;
// Determine distance between points in the X and Y axes, regardless of direction
int dx = Math.abs(nx - x), dy = Math.abs(ny - y);
// Determine what type of movement to take along line, based on direction
int sx = x < nx ? 1 : -1, sy = y < ny ? 1 : -1;
// threshold of offset before incrementing
int err = (dx > dy ? dx : -dy) / 2;
// The (sX,sY) values converted from the raw coordinates
int xS, yS;
while (true)
{
// if Both x and y have been incremented to the location of the second point, line is drawn and the algorithim
// can end
if (x == nx && y == ny)
break;
// Determine where cursor is in terms of (sY,sX) and handle border cases for X-Axis
if ((x / size) - use > 0 && (x / size) + use < sX)
xS = x / size;
else if ((x / size) - use > 0 && (x / size) + use >= sX)
xS = 5000;
else
xS = -5000;
// Determine where cursor is in terms of (sY,sX) and handle border cases for Y-Axis
if ((y / size) - use > 0 && (y / size) + use < sY)
yS = y / size;
else if ((y / size) - use > 0 && (y / size) + use >= sY)
yS = 5000;
else
yS = -5000;
// Below loops are responsible for array access and accounting for brush size
for (int j = yS - (use << shift); j < yS + (use << shift); j++)
{
for (int i = xS - (use << shift); i < xS + (use << shift); i++)
{
if (i < sX - 3 && i > 2 && j > 2 && j < sY - 3)
{
flagVals[j][i] = true;
actualVals[j][i] = true;
cachedVals[j][i] = true;
cachedVals[j + 1][i + 1] = true;
cachedVals[j + 1][i] = true;
cachedVals[j + 1][i - 1] = true;
cachedVals[j][i + 1] = true;
cachedVals[j][i - 1] = true;
cachedVals[j - 1][i + 1] = true;
cachedVals[j - 1][i - 1] = true;
cachedVals[j - 1][i + 1] = true;
}
}
}
// determine where to point to next
int e2 = err;
if (e2 > -dx)
{
err -= dy;
x += sx;
}
if (e2 < dy)
{
err += dx;
y += sy;
}
}
}