Получить все пиксели, через которые проходит луч

У меня есть двумерное пространство и луч в этом пространстве.

сетка с лучом

Мне нужно получить координаты красных прямоугольников в порядке номеров.

Моя попытка: у меня есть начало луча, которое является двойным.
У меня есть значение yaw, которое является направлением в радианах.
Я сделал это, чтобы получить координату следующего красного квадрата.

double tanyaw = Math.tan(yaw);
if ((int) (x + 1/tanyaw) == (int) x) {
    x += 1/tanyaw;
    z += Math.signum(tanyaw);
} else {
    x += Math.signum(tanyaw);
    z += tanyaw;
}

Однако:
grid

Это было с yaw = 3*pi/8 обратите внимание, что линия была сделана в программе для рисования и верна лишь приблизительно.


algorithm graphics 2d rasterize
person Alice Ryhl    schedule 24.08.2014    source источник
comment
Может быть, вместо деления с плавающей запятой используется целочисленное деление? кстати, это обычная сетка для оптимизации столкновений?   -  person huseyin tugrul buyukisik    schedule 24.08.2014
comment
@huseyintugrulbuyukisik Луч похож на выстрел, и я ищу сущность, которая будет поражена им первой, я делаю это, потому что я могу быстро получить сущности в этих квадратах, поэтому мне не нужно проверять все сущности в мире.   -  person Alice Ryhl    schedule 24.08.2014
comment
И вы продвигаете положение луча / волновой фронт небольшими временными шагами? Может как широкофазный?   -  person huseyin tugrul buyukisik    schedule 24.08.2014
comment
@huseyintugrulbuyukisik Я делаю это, чтобы получить фрагменты мира, для каждого фрагмента я проверяю, не поражен ли какой-либо объект в фрагментах.   -  person Alice Ryhl    schedule 24.08.2014
comment
Это похоже на алгоритм рисования линии на пикселях, но вместо этого на прямоугольниках. en.wikipedia.org/wiki/Line_drawing_algorithm   -  person huseyin tugrul buyukisik    schedule 24.08.2014
comment
en.wikipedia.org/wiki/Bresenham's_line_algorithm   -  person Bartlomiej Lewandowski    schedule 24.08.2014
comment
Посмотрите на мой ответ здесь: stackoverflow.com/ вопросы/25016603/   -  person MBo    schedule 24.08.2014

Ответы (1)


arrow_upward
0
arrow_downward

Уравнение линии:

x = x0 + t*xd
y = y0 + t*yd

Для простоты определите, что начало выстрела уходит в t=0, а последняя позиция для проверки – в t=1. Затем вы можете просто определить размеры шага с помощью (при условии, что вы можете просто вычислить конечную позицию x1, y1):

xstep = 1/(x1 - x0)
ystep = 1/(y1 - y0)
xpos = x0
ypos = y0

А затем простой цикл, пока вы не достигнете пересечения или не закончите, используя:

while(!hitsomething()) {
    if (xpos + xstep - x0 < ypos + ystep - y0) {
           xpos += xstep;
           visit(xpos, ypos);
    } else {
           ypos += ystep;
           visit(xpos, ypos);
    }
}
person Pauli Nieminen    schedule 24.08.2014