5 ms·

Line drawing on a grid

127 points by mbostock 12y ago

lovelearning 12y ago
What a stroke of luck for me! Just today I was studying line drawing techniques on a grid for a prototype related to offline mapping using polygons. It's yet another reminder how topics and links that don't seem relevant to my interests at first (games in this case) often turn out to be relevant to other areas of my interest.
jokoon 12y ago
don't forget to read his explanation of A*, it's really great, and pretty easy. explained in python so it was even better.
- dirkk0 12y ago
  You are right. Thanks for bringing this to my attention. http://www.redblobgames.com/pathfinding/a-star/introduction.html http://www.redblobgames.com/pathfinding/a-star/introduction.... Every now and then I visit Amit's pages and find something interesting that he explains in an awesome way.
- nacs 12y ago
  Another great one by the same author for those who haven't see it is the terrain generation document: http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/ http://www-cs-students.stanford.edu/~amitp/game-programming/...
forrestthewoods 12y ago
Not sure why they author immediately dismisses bresenham. It's fast, quality, and well known. I feel like if the post continued for another few logical steps of optimization that's exactly where he'd end up!
- vardump 12y ago
  Bresenham is slower on modern hardware. Well, still better on microcontrollers and less gates to implement it on silicon / FPGA resources. Ever since 486 days, it's been faster just to do a division and loop in direction of the longer delta axis. Fixed point addition and shift to truncate for shorter axis coordinate. In some old CPUs, add to eax (or even ax) and ah (higher half of 16-bit ax) for the coordinate. Requires a small (or split/tiled) frame buffer. I remember it was still worth it 20 years ago. Nowadays you don't have to perform that ax/ah/al trickery, because CPUs have been capable of register renaming, pipelining, multiple issue, etc. for at least 20 years, and extra mov, shr etc. to replace it could be sank between other instructions and memory waits. Accessing ax ah/al halves is the slower, unoptimized path in anything that resembles a modern CPU.
  - forrestthewoods 12y ago
    This benchmark from 2001 with a Pentium III has bresenham about 7.5 times faster than DDA. There's another pair of algorithms that are a little faster still. http://www.edepot.com/algorithm.html http://www.edepot.com/algorithm.html These days the limiting factor is probably going to be cache access rather than fixed vs floating point. I'm pretty sure bresenham is still the way to go but it'd be fun to see modern comparisons.
    - vardump 12y ago
      Well, DDA should use fixed point, not doubles. Old stack based x87 FPU is just slow and converting doubles into integers in a loop... Well, I guess you can understand where the time is spent in the version you linked! I meant of course IDIV and fixed point, not FDIV FADD FISTP etc. madness!
- chipsy 12y ago
  Bresenham lines are not "quality." For one, they're obviously jaggy. As well, most implementations of the algorithm will give you different results if you invert the start and end points. This matters a great deal for the common use-case in games of casting rays to determine sight lines. It is quite annoying to have a tactical combat game where a foe can shoot from behind a wall and you can't shoot back from the exact same position. Amit notes lack of symmetry in the "2.1 Orthogonal steps" implementation, which leads him to the "Supercover" implementation.
toolslive 12y ago
I remember enjoying Abrash's write up in the mid 90s. http://www.phatcode.net/res/224/files/html/ch35/35-01.html http://www.phatcode.net/res/224/files/html/ch35/35-01.html He starts with the algorithm, then a C implementation, then optimization in ASM, only to throw it all away in the subsequent chapter because of a better algorithm. He goes through this cycle several times. Splendid educational effort on multiple levels.
poseid 12y ago
great to see the examples. I am exploring a small JavaScript module approach to SVG drawing to: https://github.com/mulderp/pinboard-grid https://github.com/mulderp/pinboard-grid
- amitp 12y ago
  I used to draw the lines that way, but I've switched to drawing the squares instead. It tends to look cleaner, the code is simpler, and it also lets me color the squares individually. If I really need to draw the lines, I can set a background color. It's a cheap trick :-)
  - poseid 12y ago
    indeed good advise! I changed the implementation https://github.com/mulderp/pinboard-grid/commit/2a9d2c256ce0ba18cf90d7eae28acb8e43c7bb48 https://github.com/mulderp/pinboard-grid/commit/2a9d2c256ce0... - just saw you use transform instead of adjusting x/y
guelo 12y ago
Too bad there was nothing about using color for anti aliasing.
cafebeen 12y ago
Anyone seen a similar run-down for 3D grids?
- amitp 12y ago
  One nice thing about linear interpolation is that the same algorithm works for 2D grids, 3D grids, and hex grids. For 3D, the diagonal_distance, point_lerp, and point_round functions can look at at z in addition to x and y. For hex grids, you need hex grid distances and hex grid rounding (http://www.redblobgames.com/grids/hexagons/#line-drawing http://www.redblobgames.com/grids/hexagons/#line-drawing).
andrewchoi 12y ago
Great demo. I really appreciate the interactivity. Is there something similar for antialiasing?

127 points by mbostock 12y ago

What a stroke of luck for me! Just today I was studying line drawing techniques on a grid for a prototype related to offline mapping using polygons. It's yet another reminder how topics and links that don't seem relevant to my interests at first (games in this case) often turn out to be relevant to other areas of my interest.

jokoon 12y ago

don't forget to read his explanation of A*, it's really great, and pretty easy. explained in python so it was even better.

dirkk0 12y ago
You are right. Thanks for bringing this to my attention. http://www.redblobgames.com/pathfinding/a-star/introduction.html http://www.redblobgames.com/pathfinding/a-star/introduction.... Every now and then I visit Amit's pages and find something interesting that he explains in an awesome way.
nacs 12y ago
Another great one by the same author for those who haven't see it is the terrain generation document: http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/ http://www-cs-students.stanford.edu/~amitp/game-programming/...

forrestthewoods 12y ago

Not sure why they author immediately dismisses bresenham. It's fast, quality, and well known. I feel like if the post continued for another few logical steps of optimization that's exactly where he'd end up!

vardump 12y ago
Bresenham is slower on modern hardware. Well, still better on microcontrollers and less gates to implement it on silicon / FPGA resources. Ever since 486 days, it's been faster just to do a division and loop in direction of the longer delta axis. Fixed point addition and shift to truncate for shorter axis coordinate. In some old CPUs, add to eax (or even ax) and ah (higher half of 16-bit ax) for the coordinate. Requires a small (or split/tiled) frame buffer. I remember it was still worth it 20 years ago. Nowadays you don't have to perform that ax/ah/al trickery, because CPUs have been capable of register renaming, pipelining, multiple issue, etc. for at least 20 years, and extra mov, shr etc. to replace it could be sank between other instructions and memory waits. Accessing ax ah/al halves is the slower, unoptimized path in anything that resembles a modern CPU.
- forrestthewoods 12y ago
  This benchmark from 2001 with a Pentium III has bresenham about 7.5 times faster than DDA. There's another pair of algorithms that are a little faster still. http://www.edepot.com/algorithm.html http://www.edepot.com/algorithm.html These days the limiting factor is probably going to be cache access rather than fixed vs floating point. I'm pretty sure bresenham is still the way to go but it'd be fun to see modern comparisons.
  - vardump 12y ago
    Well, DDA should use fixed point, not doubles. Old stack based x87 FPU is just slow and converting doubles into integers in a loop... Well, I guess you can understand where the time is spent in the version you linked! I meant of course IDIV and fixed point, not FDIV FADD FISTP etc. madness!
chipsy 12y ago
Bresenham lines are not "quality." For one, they're obviously jaggy. As well, most implementations of the algorithm will give you different results if you invert the start and end points. This matters a great deal for the common use-case in games of casting rays to determine sight lines. It is quite annoying to have a tactical combat game where a foe can shoot from behind a wall and you can't shoot back from the exact same position. Amit notes lack of symmetry in the "2.1 Orthogonal steps" implementation, which leads him to the "Supercover" implementation.

toolslive 12y ago

I remember enjoying Abrash's write up in the mid 90s. http://www.phatcode.net/res/224/files/html/ch35/35-01.html http://www.phatcode.net/res/224/files/html/ch35/35-01.html He starts with the algorithm, then a C implementation, then optimization in ASM, only to throw it all away in the subsequent chapter because of a better algorithm. He goes through this cycle several times. Splendid educational effort on multiple levels.

poseid 12y ago

great to see the examples. I am exploring a small JavaScript module approach to SVG drawing to: https://github.com/mulderp/pinboard-grid https://github.com/mulderp/pinboard-grid

amitp 12y ago
I used to draw the lines that way, but I've switched to drawing the squares instead. It tends to look cleaner, the code is simpler, and it also lets me color the squares individually. If I really need to draw the lines, I can set a background color. It's a cheap trick :-)
- poseid 12y ago
  indeed good advise! I changed the implementation https://github.com/mulderp/pinboard-grid/commit/2a9d2c256ce0ba18cf90d7eae28acb8e43c7bb48 https://github.com/mulderp/pinboard-grid/commit/2a9d2c256ce0... - just saw you use transform instead of adjusting x/y

guelo 12y ago

Too bad there was nothing about using color for anti aliasing.

cafebeen 12y ago

Anyone seen a similar run-down for 3D grids?

amitp 12y ago
One nice thing about linear interpolation is that the same algorithm works for 2D grids, 3D grids, and hex grids. For 3D, the diagonal_distance, point_lerp, and point_round functions can look at at z in addition to x and y. For hex grids, you need hex grid distances and hex grid rounding (http://www.redblobgames.com/grids/hexagons/#line-drawing http://www.redblobgames.com/grids/hexagons/#line-drawing).

andrewchoi 12y ago

Great demo. I really appreciate the interactivity. Is there something similar for antialiasing?