https://stackoverflow.com/questions/19618285
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianImplement Bresenham's line algorithm (http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm). Its very simple and you can use the array indices directly as coordinates.
Drawing smooth lines to a grid [2D array] in Conway's Game of Life
-
01-07-2022 - |
Question
tl;dr What is a very fast way to use coordinate points to draw smooth lines in an array? Note: reading the below information will probably provide some much-needed context.
I am currently working on an implementation of Conway's Game of Life. I use a Mouse Listener [mouseDragged, specifically] to two points at a time, and pass them into this method:
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;
}
}
}
}
}
}
}
Okay, if your eyes aren't bleeding yet, allow me to explain what exactly this behemoth does. First, it calculates which way the mouse is being dragged. Let's say it's going right. Then it calculates the slope of the line formed by the two points, and goes through these three nested for loops.
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;
}
}
}
It loops entirely through the vertical portion of the array, and through a subsection of it horizontally. The last for loop goes through every X-coordinate between the two points. The if-statement plugs that X value into the equation of the line, finds a corresponding Y value, and checks an array of coordinate points for a match. If it finds one, it then sets the array used for processing [and it's counterpart] equal to true at that location. (You can ignore the cachedVals, that's part of an optimization for the grid, and not really relevant to the question)
On a fairly small grid, say 100x100, this works perfectly, with almost 0 lag. However, I am using much larger grids [approx 3000x2500], that can contain as many as 7 million positions. Any ideas on how to optimize [or completely change] this code?
EDIT: So I got this working a while ago, but I forgot to post it here. Should anybody else have a similar problem, here's my implementation:
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;
}
}
}
Solution
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
