CODEWITHSUNDEEP
c++algorithmmathgeometry
user173342
user173342

Reputation: 1840

Getting all intersection points between a line segment and a 2^n grid, in integers

I have a line going from (x0, y0) to (x1, y1) through a grid made of square tiles 2^n wide. I not only need to find the tiles the line intersects, but also the corresponding entry and exit points. All the SO questions on this I can find deal with "1x1" tiles without caring where the intersections occur within the tile.

enter image description here

The points won't always be precisely on an integer, and in some cases I'll use the natural floor and others I'll want to round up. But letting it naturally floor in all cases for this is fine for now.

I found an example that eventually gets to a very simple case of raytracing with integers, but it doesn't keep track of the intersection points and also isn't adapted for anything but lines going through the center (assumed 0.5, 0.5 offset) of 1x1 tiles.

void raytrace(int x0, int y0, int x1, int y1)
{
    int dx = abs(x1 - x0);
    int dy = abs(y1 - y0);
    int x = x0;
    int y = y0;
    int n = 1 + dx + dy;
    int x_inc = (x1 > x0) ? 1 : -1;
    int y_inc = (y1 > y0) ? 1 : -1;
    int error = dx - dy;
    dx *= 2;
    dy *= 2;

    for (; n > 0; --n)
    {
        visit(x, y);

        if (error > 0)
        {
            x += x_inc;
            error -= dy;
        }
        else
        {
            y += y_inc;
            error += dx;
        }
    }
}

How can it be adapted to find the intersected 2^n x 2^n grid tiles while also grabbing the 2 relevant intersection points? It seems the ability to start "anywhere" in a tile really mucks up this algorithm, and my solutions end up using division and probably setting things up to accumulate error over each iteration. And that's no good...

Also I think for the first and last tile, the endpoint can be assumed to be the "other" intersection point.

Upvotes: 2

Views: 3941

Answers (3)

prasoonblueluck
prasoonblueluck

Reputation: 85

You can reduce your 2^n X 2^n tile size to 1 X 1 by dividing the entire coordinate system by 2^n.

Precisely, in our case that would mean that you divide the coordinates of the start point and end point of the line by 2^n. From now on, you can treat the problem as a 1X1 sized tile problem. At the end of the problem, we'll multiply 2^n back into our solution so get the answer for 2^n X 2^n solution.

Now the part of finding the entry and exit points in each tile. Suppose the line starts at (2.4, 4.6 ) and ends at (7.9, 6.3)

  • Since the x-coordinates of the start and end point of the line are 2.4 and 7.9, hence, all integer values between them will be intersected by our line, i.e. tiles with x-coordinates of 3,4,5,6,7 will be intersected. We can calculate the corresponding y-coordinates of these x-coordinates using the equation of the input line.
  • Similarly, all integers between the y-coordinates of the start and end point of the line, will lead to another set of intersection points between the line and the tiles.
  • Sort all these points on the basis of their x - coordinates. Now pick them in pairs, the first will be the entry point, the second will be the exit.
  • Multiply these points back with 2^n to get solution for the original problem.

Algorithm Complexity : O(nlog n ) where n is the range of integers between the start and end coordinates of the line. Through minor modifications, this can further be reduced to O(n).

Upvotes: 2

mbeckish
mbeckish

Reputation: 10579

Plug in each integer value of x in the range x0..x1, and solve for each y. That will give you the locations of the intersections on the sides of the tiles.

Plug in each integer value of y in the range y0..y1, and solve for x. That will give you the locations of the intersections on the top/bottom of the tiles.

EDIT

The code gets a little uglier when dealing with different tile sizes and starting inside of a tile, but the idea is the same. Here is a solution in C# (runs as-is in LINQPad):

List<Tuple<double,double>> intersections = new List<Tuple<double,double>>();

int tile_width = 4;

int x0 = 3;
int x1 = 15;
int y0 = 1;
int y1 = 17;

int round_up_x0_to_nearest_tile = tile_width*((x0 + tile_width -1)/tile_width);
int round_down_x1_to_nearest_tile = tile_width*x1/tile_width;

int round_up_y0_to_nearest_tile = tile_width*((y0 + tile_width -1)/tile_width);
int round_down_y1_to_nearest_tile = tile_width*y1/tile_width;

double slope = (y1-y0)*1.0/(x1-x0);
double inverse_slope = 1/slope;

for (int x = round_up_x0_to_nearest_tile; x <= round_down_x1_to_nearest_tile; x += tile_width)
{
    intersections.Add(new Tuple<double,double>(x, slope*(x-x0)+y0));
}

for (int y = round_up_y0_to_nearest_tile; y <= round_down_y1_to_nearest_tile; y += tile_width)
{
    intersections.Add(new Tuple<double,double>(inverse_slope*(y-y0)+x0, y));
}

intersections.Sort();

Console.WriteLine(intersections);

The downside to this method is that, when the line intersects a tile exactly on a corner (i.e. the x and y coordinates of the intersection are both integers), then the same intersection point will be added to the list from each of the 2 for loops. In that case, you would want to remove the duplicate intersection points from your list.

Upvotes: 1

MBo
MBo

Reputation: 80327

There is useful article "Fast Voxel Traversal Algorithm..." by Woo, Amanatides. Look at the practical implementation (grid traversal section) too. I've used this method with good results.

Upvotes: 2

Related Questions