Быстрый обзор Voxel 2D

Question

Я пытаюсь пройти через все ячейки, через которые проходит линия. Я нашел Fast Voxel Traversal Algorithm, который, похоже, соответствует моим потребностям, но сейчас я нахожусь неточным. Ниже приведен график с красной линией и указывает координаты воксела, которые дает алгоритм. Как видите, это почти правильно, за исключением точки (4, 7), как и должно быть (5,6). Я не уверен, правильно ли я реализую алгоритм, поэтому включил его в Python. Итак, я думаю, мой вопрос заключается в том, что моя реализация правильная или есть лучший алгоритм для этого?

Благодаря

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 1

нет никого есть время, чтобы прочитать бумагу, размещенную и выяснить, если вы реализовали его правильно.

Возникает вопрос. Используется ли алгоритм, который вы использовали (а), чтобы определить все ячейки, через которые проходит линия, или (б) сформировать приличную воксельную аппроксимацию прямой линии между двумя точками?

Я больше знакомы с Bresenham's line algorithm, которые выполняют (b). Вот картина его в действии:

Обратите внимание, что выбор ячеек «эстетический», но не включает некоторые клетки линии проходит. В том числе это сделает линию «уродливой».

Я подозреваю, что подобное происходит с вашим алгоритмом линии воксела. Однако, глядя на ваши данные, и изображение Bresenham предлагает простое решение. Пройдите по линии обнаруженных ячеек, но, когда вам нужно сделать диагональный шаг, рассмотрите две промежуточные ячейки. Затем вы можете использовать алгоритм пересечения прямых прямоугольников (см. here), чтобы определить, какая из ячеек-кандидатов должна иметь, но не была включена.

Answer 2

Я предполагаю, что для того, чтобы быть полным, я решил использовать другой алгоритм. тот, который указан здесь dtb's answer on another question.

вот реализация

def getIntersectPts(strPt, endPt, geom=[0,1,0,0,0,1]): 
''' 
    Find intersections pts for every half cell size 
    ** cell size has only been tested with 1 

    Returns cell coordinates that the line passes through 
''' 

x0 = geom[0] 
y0 = geom[3] 

(sX, sY) = (strPt[0], strPt[1]) 
(eX, eY) = (endPt[0], endPt[1]) 
xSpace = geom[1] 
ySpace = geom[5] 

sXIndex = ((sX - x0)/xSpace) 
sYIndex = ((sY - y0)/ySpace) 
eXIndex = ((eX - sXIndex)/xSpace) + sXIndex 
eYIndex = ((eY - sYIndex)/ySpace) + sYIndex 


dx = (eXIndex - sXIndex) 
dy = (eYIndex - sYIndex) 
xHeading = 1.0 if dx > 0 else -1.0 if dx < 0 else 0.0 
yHeading = 1.0 if dy > 0 else -1.0 if dy < 0 else 0.0 

xOffset = (1 - (math.modf(sXIndex)[0])) 
yOffset = (1 - (math.modf(sYIndex)[0])) 

ptsIndexes = [] 
x = sXIndex 
y = sYIndex 
pt = (x, y) #1st pt 

if dx != 0: 
    m = (float(dy)/float(dx)) 
    b = float(sY - sX * m) 

dx = abs(int(dx)) 
dy = abs(int(dy)) 

if dx == 0: 
    for h in range(0, dy + 1): 
     pt = (x, y + (yHeading *h)) 
     ptsIndexes.append(pt) 

    return ptsIndexes 

#print("m {}, dx {}, dy {}, b {}, xdir {}, ydir {}".format(m, dx, dy, b, xHeading, yHeading)) 
#print("x {}, y {}, {} {}".format(sXIndex, sYIndex, eXIndex, eYIndex)) 

#snap to half a cell size so we can find intersections on cell boundaries 
sXIdxSp = round(2.0 * sXIndex)/2.0 
sYIdxSp = round(2.0 * sYIndex)/2.0 
eXIdxSp = round(2.0 * eXIndex)/2.0 
eYIdxSp = round(2.0 * eYIndex)/2.0 
# ptsIndexes.append(pt) 
prevPt = False 
#advance half grid size 
for w in range(0, dx * 4): 
    x = xHeading * (w/2.0) + sXIdxSp 
    y = (x * m + b) 
    if xHeading < 0: 
     if x < eXIdxSp: 
      break 
    else: 
     if x > eXIdxSp: 
      break 

    pt = (round(x), round(y)) #snapToGrid 
    # print(w, x, y) 

    if prevPt != pt: 
     ptsIndexes.append(pt) 
     prevPt = pt 
#advance half grid size 
for h in range(0, dy * 4): 
    y = yHeading * (h/2.0) + sYIdxSp 
    x = ((y - b)/m) 
    if yHeading < 0: 
     if y < eYIdxSp: 
      break 
    else: 
     if y > eYIdxSp: 
      break 
    pt = (round(x), round(y)) # snapToGrid 
    # print(h, x, y) 

    if prevPt != pt: 
     ptsIndexes.append(pt) 
     prevPt = pt 

return set(ptsIndexes) #elminate duplicates 

Answer 3

Вокселы, что вы идете старт на 0.0, то есть первый воксельная охватывает пространство от 0,0 до 1,0, А не от -0,5 до 0,5, как вы предполагаете, что. Другими словами, это те, которые отмечены пунктирной линией, а не твердой.

Если вы хотите, чтобы вокселы были вашим путем, вам придется исправить начальные вычисления maxX и maxY.