An answer to this question on Stack Overflow.

Question

I'm trying traverse all the cells that a line goes through. I've found the Fast Voxel Traversal Algorithm that seems to fit my needs, but I'm currently finding to be inaccurate. Below is a graph with a red line and points as voxel coordinates that the algorithm gives. As you can see it is almost correct except for the (4, 7) point, as it should be (5,6). I'm not sure if i'm implementing the algorithm correctly either so I've included it in Python. So i guess my question is my implementation correct or is there a better algo to this?

Thanks

def getVoxelTraversalPts(strPt, endPt, geom):
  Max_Delta = 1000000.0
  #origin
  x0 = geom[0]
  y0 = geom[3]
  (sX, sY) = (strPt[0], strPt[1])
  (eX, eY) = (endPt[0], endPt[1])
  dx = geom[1]
  dy = geom[5]
  sXIndex = ((sX - x0) / dx)
  sYIndex = ((sY - y0) / dy)
  eXIndex = ((eX - sXIndex) / dx) + sXIndex
  eYIndex = ((eY - sYIndex) / dy) + sYIndex
  deltaX = float(eXIndex - sXIndex)
  deltaXSign = 1 if deltaX > 0 else -1 if deltaX < 0 else 0
  stepX = deltaXSign
  tDeltaX = min((deltaXSign / deltaX), Max_Delta) if deltaXSign != 0 else Max_Delta
  maxX = tDeltaX * (1 - sXIndex + int(sXIndex)) if deltaXSign > 0 else tDeltaX * (sXIndex - int(sXIndex))
  deltaY = float(eYIndex - sYIndex)
  deltaYSign = 1 if deltaY > 0 else -1 if deltaY < 0 else 0
  stepY = deltaYSign
  tDeltaY = min(deltaYSign / deltaY, Max_Delta) if deltaYSign != 0 else Max_Delta
  maxY = tDeltaY * (1 - sYIndex + int(sYIndex)) if deltaYSign > 0 else tDeltaY * (sYIndex - int(sYIndex))
  x = sXIndex
  y = sYIndex
  ptsIndexes = []
  pt = [round(x), round(y)]
  ptsIndexes.append(pt)
  prevPt = pt
  while True:
    if maxX < maxY:
        maxX += tDeltaX
        x += deltaXSign
    else:
        maxY += tDeltaY
        y += deltaYSign
    pt = [round(x), round(y)]
    if pt != prevPt:
        #print pt
        ptsIndexes.append(pt)
        prevPt = pt
    if maxX > 1 and maxY > 1:
        break
  return (ptsIndexes)

Answer

Ain't nobody got time to read the paper you posted and figure out if you've implemented it correctly.

Here's a question, though. Is the algorithm you've used (a) actually meant to determine all the cells that a line passes through or (b) form a decent voxel approximation of a straight line between two points?

I'm more familiar with Bresenham's line algorithm which performs (b). Here's a picture of it in action:

Note that the choice of cells is "aesthetic", but omits certain cells the line passes through. Including these would make the line "uglier".

I suspect a similar thing is going on with your voxel line algorithm. However, looking at your data and the Bresenham image suggests a simple solution. Walk along the line of discovered cells, but, whenever you have to make a diagonal step, consider the two intermediate cells. You can then use a line-rectangle intersection algorithm (see here) to determine which of the candidate cells should have, but wasn't, included.