2 ms·

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

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.
- CamperBob2 12y ago
  Bresenham-rendered lines are symmetrical if you start with a half-step, aren't they?
- abcd_f 12y ago
  Pray tell which tactical combat game determines the line of sight using a discrete grid.
  - mattdesl 12y ago
    An awful lot of top down 2D tile based games.
- TheLoneWolfling 12y ago
  "Just" use a hex grid. (And then have fun with your raycasting)

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.

CamperBob2 12y ago
Bresenham-rendered lines are symmetrical if you start with a half-step, aren't they?
abcd_f 12y ago
Pray tell which tactical combat game determines the line of sight using a discrete grid.
- mattdesl 12y ago
  An awful lot of top down 2D tile based games.
TheLoneWolfling 12y ago
"Just" use a hex grid. (And then have fun with your raycasting)