🔒 Locked

Efficient line vs grid algorithm?

Started by CodeImp Apr 4, 2006 at 3:52 PM 10 replies 8.2k views

Original Post

Apr 4, 2006 at 3:52 PM

Ok I have been pondering on this for 2 days now and cannot find a satisfying solution while I'm sure there must be one (for which im probably going to slap myself in the face for not seeing it). Line-grid image picturing the problem

The blue line is a limited line from coordinates A to B. These are floating point coordinates, hence the resolution is virtually infinite. The grid are integer cells (rows and columns), they are square and of fixed size. I want to know what cells are touched by the line. (as I indicated here by coloring the cells red) I can come up with several inefficient algorithms like, for example, running through all cells and see if they touch the line, but that is not acceptable. Does anyone know of a way to do this properly? Any tutorial describing it maybe? Any help would be much appreciated!

Sharlin

Apr 4, 2006 at 4:03 PM

Unfortunately, Bresenham doesn't work without modification because it only considers integer coordinates.

"Grid traversal" is a good search term for what you want. A nice and simple algorithm is presented here, for example (scroll down a couple of pages).

CodeImp

Apr 4, 2006 at 4:04 PM

Anonymous Poster: No, I looked at that (actually worked with the algorithm before in a previous project) and its not what I'm looking for. This is NOT the same situation here. Please see me picture and description of the problem.

Antheus

Apr 4, 2006 at 4:13 PM

How about Xiaolin Wu's line algorithm. It's linked under references under the previously posted bresenham's algortihm page.

http://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm

The only modification you'd need is instead of rendering alpha adjusted values to simply tag those fields.

It has been a long time since I did manual line anti-aliasing, but from a quick look, this should work. Given that it considers two pixels (instead of one as per Bresenham case), it should cover all the cases. Looking at the problem naively, I'd say that the difference between Bresenham's and your algorithm will be at most two pixels per scanline (one at each edge), so Wu's should work.

CodeImp

Apr 4, 2006 at 4:26 PM

Antheus: I looked at that also (I am familliar with google and wikis :P) but also that is not exactly what I need. I do not want nearby cells (which is what anti-aliasing colors), only the cells actually touched.

Sharlin: That looks like the solution im looking for! However the article is somewhat vague on some parts, like "we determine how far we must move along the ray to cross one cell. Again, we do this for x, y and z; the result is stored in tDeltaX, tDeltaY and tDeltaZ."... How do they do that?

haphazardlynamed

Apr 4, 2006 at 5:03 PM

Why not just walk the line?
find starting cell at one end of line (easily done with a few divisions)
find which side of current cell the line exits, left or right or top or bottom (just some line intersection test)
repeat for the cell in that direction
continue till reach cell that contains endpoint of line

CodeImp

Apr 4, 2006 at 5:15 PM

All the intersection tests that would have to be done along the line would be less efficient than the method Sharlin proposed.

I would like an answer to the vague description in that method Sharlin proposed though, as I wrote in my previous post. This could be the most efficient solution I've encountered so far.

Zakwayda

Apr 4, 2006 at 5:18 PM

This may have already been mentioned in one of the above links, but you're probably looking for DDA or 3D-DDA. These are algorithms that are related to some of the line-drawing algorithms mentioned above, but are geared toward the problem you mention, that is, finding all cells touched by a given ray.

haphazardlynamed

Apr 4, 2006 at 6:13 PM

Quote:
Original post by CodeImp
All the intersection tests that would have to be done along the line would be less efficient than the method Sharlin proposed.

*Looks through Sharlin's link*

DDA
Yeah, thats basically what I was suggesting. He gets 'tMaxX' and 'tMaxY' by doing the gridline interesection I mentioned, but omitted the details in the description. It's also optimized to take advantage of line directionality so only 2 of 4 cell walls need to be checked. Either that or its psuedocode...

I didn't know that algorithm had a name...
Good to know

whats DDA an acronym for? I just call it 'line walking'

Zakwayda

Apr 4, 2006 at 6:31 PM

Quote:
Original post by haphazardlynamed
whats DDA an acronym for? I just call it 'line walking'

DDA = 'digital differential analyzer'.

Sharlin

Apr 5, 2006 at 1:26 PM

Ah, here's the original paper by the discoverers of the algorithm. Even they don't elaborate on how to calculate the deltas; however, that is quite straightforward, as we see:

Given a ray r described in parametric form:

v = orig + t * dir

Or, component-wise:

x_v = x_orig + t * x_dir
y_v = y_orig + t * y_dir

Then tDeltaX and tDeltaY are simply deltas you have to add to t to move along the ray from one grid line to another horizontally or vertically, respectively. The cases are analogous, so only the x case is detailed here:

If one grid block has width dx, then we have to find dt such that:

x_v = x_orig + t * x_dir x_v+dx = x_orig + (t+dt) * x_dir

Solving that, we get

      dxdt = ---- .      x<sub><small>dir</small></sub>

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.