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!
Efficient line vs grid algorithm?
Author
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).
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!
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!
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).
"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).
Author
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.
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.
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.
Author
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?
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?
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
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
Author
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.
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.
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.
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'
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement