Supercover DDA algorithm

Question

I'm trying to figure out how to make a supercover DDA algorithm. Or in other words, a DDA algorithm that will cover ALL grid points crossed by a line. See the image below.

Hosted by imgur.com

The image was drawn by me and might not be 100% accurate but it shows the general idea. I also want to note the examples on the lower half of the image do not have integer start and end coordinates, this is necessary.

If you need to know, I intend to use this for line of sight ray casting.

I'm capable of implementing a typical DDA algorithm, but my problem is, how can I modify it to cover all points?

Thanks!

My current implementation of the DDA algorithm in Lua

function dline(x0,y0, x1,y1) -- floating point input
  local dx = x1-x0
  local dy = y1-y0

  local s = math.max(math.abs(dx),math.abs(dy))

  dx = dx/s
  dy = dy/s

  local x = x0
  local y = y0
  local i = 0
  return function() -- iterator intended for a for loop
    if i <= s then
      local rx,ry = x,y
      x = x+dx
      y = y+dy
      i = i+1
      return rx,ry
    end
  end
end

*"Questions asking for code must demonstrate a minimal understanding of the problem being solved. Include attempted solutions, why they didn't work, and the expected results."* — , Sep 18 '13 at 20:12
What is the structure of your input data? And please provide a explanantion (or link) of the algorithm you are interested in. — RBarryYoung, Sep 18 '13 at 20:14
A "simple" way to do it is to modify your step(`s`). For cheap/dirty casting I've used the same as you, but multiplied by 10 to check ten times per "unit" distance. It may skip some squares with *tiny* crossings, but it works well enough for games. If it's fast enough for your purpose, no need to complicate things. — Geobits, Sep 18 '13 at 20:20

score 4 · Accepted Answer · edited Feb 08 '17 at 14:47

Sorry, I don't ask questions too often, mainly because I'm not that good. But I'll tell you what I am good at! Solving my own problem! :D

As a note, the image in my question shows the lines crossing diagonals if the line passes through a point precisely, this algorithm does not, but after some thought, crossing diagonals is not desirable for me.

Thanks to this article I found.

Here's the new implementation

function line(x0,y0, x1,y1)
  local vx,vy = x1-x0, y1-y0           -- get the differences
  local dx = math.sqrt(1 + (vy/vx)^2)  -- length of vector <1, slope>
  local dy = math.sqrt(1 + (vx/vy)^2)  -- length of vector <1/slope, 1>

  local ix,iy = math.floor(x0), math.floor(y0) -- initialize starting positions
  local sx,ex -- sx is the increment direction
              -- ex is the distance from x0 to ix
  if vx < 0 then
    sx = -1
    ex = (x0-ix) * dx
  else
    sx = 1
    ex = (ix + 1-x0) * dx -- subtract from 1 instead of 0
                          -- to make up for flooring ix
  end

  local sy,ey
  if vy < 0 then
    sy = -1
    ey = (y0-iy) * dy
  else
    sy = 1
    ey = (iy + 1-y0) * dy
  end

  local done = false
  local len  = math.sqrt(vx^2 + vy^2)
  return function()
    if math.min(ex,ey) <= len then
      local rx,ry = ix,iy
      if ex < ey then
        ex = ex + dx
        ix = ix + sx
      else
        ey = ey + dy
        iy = iy + sy
      end
      return rx,ry
    elseif not done then -- return the final two coordinates
      done = true
      return ix,iy
    end
  end
end

score 1 · Answer 2 · answered Sep 18 '13 at 20:13

1

You can do it in the same time complexity as a normal dda algorithm by simply adding a few checks on adjacent squares.

answered Sep 18 '13 at 20:13

clwhisk

1,719
16
16

Supercover DDA algorithm

2 Answers2

Linked