Sign in to follow this  
CodeImp

Efficient line vs grid algorithm?

Recommended Posts

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!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
check this out:
http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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'

Share this post


Link to post
Share on other sites
Quote:
Original post by haphazardlynamed
whats DDA an acronym for? I just call it 'line walking'
DDA = 'digital differential analyzer'.

Share this post


Link to post
Share on other sites
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:

xv = xorig + t * xdir
yv = yorig + t * ydir

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:

xv = xorig + t * xdir
xv+dx = xorig + (t+dt) * xdir


Solving that, we get

dx
dt = ---- .
xdir





Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this