Как обобщить линейный алгоритм Брезенхэма для конечных точек с плавающей точкой?

12

Я пытаюсь объединить две вещи. Я пишу игру, и мне нужно определить квадраты сетки, лежащие на линии с конечными точками с плавающей точкой.

Линия корыта сетки

Более того, мне нужно включить все квадраты сетки, к которым он прикасается (т.е. не только линию Брезенхэма, но и синюю):

Брезенхам против полной развертки

Может кто-нибудь подсказать мне, как это сделать? Очевидным решением является использование алгоритма наивной линии, но есть ли что-то более оптимизированное (быстрее)?

SmartK8
источник
В случае, если ссылка переходит в автономный режим, просто поищите в Google «более быстрый алгоритм обхода вокселей для трассировки лучей»
Gustavo Maciel

Ответы:

9

Вы ищете алгоритм обхода сетки. Эта статья дает хорошую реализацию;

Вот базовая реализация в 2D, найденная на бумаге:

loop {
    if(tMaxX < tMaxY) {
        tMaxX= tMaxX + tDeltaX;
        X= X + stepX;
    } else {
        tMaxY= tMaxY + tDeltaY;
        Y= Y + stepY;
    }
    NextVoxel(X,Y);
}

На бумаге также есть версия для 3D-лучей.

В случае, если ссылка гниет , вы можете найти много зеркал с ее именем: более быстрый алгоритм обхода вокселей для трассировки лучей .

Густаво Масиэль
источник
Ну неловко Я думаю, я переключу ответ вам и проголосую за ltjax. Потому что я решил на основании вашей ссылки на эту статью.
SmartK8
5

Идея Blue хороша, но реализация немного неуклюжа. На самом деле, вы можете легко сделать это без sqrt. Давайте пока предположим, что вы исключили вырожденные падежи ( BeginX==EndX || BeginY==EndY) и сосредоточились только на направлениях линий в первом квадранте, поэтому BeginX < EndX && BeginY < EndY. Вам придется реализовать версию как минимум для одного другого квадранта, но это очень похоже на версию для первого квадранта - вы проверяете только другие ребра. В псевдокоде C'ish:

int cx = floor(BeginX); // Begin/current cell coords
int cy = floor(BeginY);
int ex = floor(EndX); // End cell coords
int ey = floor(EndY);

// Delta or direction
double dx = EndX-BeginX;
double dy = EndY-BeginY;

while (cx < ex && cy < ey)
{
  // find intersection "time" in x dir
  float t0 = (ceil(BeginX)-BeginX)/dx;
  float t1 = (ceil(BeginY)-BeginY)/dy;

  visit_cell(cx, cy);

  if (t0 < t1) // cross x boundary first=?
  {
    ++cx;
    BeginX += t0*dx;
    BeginY += t0*dy;
  }
  else
  {
    ++cy;
    BeginX += t1*dx;
    BeginY += t1*dy;
  }
}

Теперь для других квадрантов, вы просто изменить ++cxили ++cyи условие цикла. Если вы используете это для столкновения, вам, вероятно, придется реализовать все 4 версии, в противном случае вы можете обойтись двумя, соответствующим образом поменяв местами начальную и конечную точки.

ltjax
источник
Алгоритм, предоставленный Густаво Масьелом, немного более эффективен. Он только определяет первый Ts, а затем просто добавляет 1 к вертикали или горизонтали и сдвигает Ts на размер ячейки. Но так как он не преобразовал его в ответ, я приму этот как ближайший ответ.
SmartK8
3

Ваше предположение не обязательно, чтобы найти ячейки, но линии, которые это пересекает на этой сетке.

Например, взяв ваше изображение, мы можем выделить не ячейки, а линии сетки, которые оно пересекает:

пометок

Затем это показывает, что если он пересекает линию сетки, то ячейки по обе стороны от этой линии являются заполненными.

Вы можете использовать алгоритм пересечения, чтобы определить, будет ли ваша линия с плавающей точкой пересекать их, масштабируя ваши точки в пикселях. Если у вас есть соотношение плавающих координат: пикселей 1,0: 1, то вы отсортированы, и вы можете просто перевести его напрямую. Используя алгоритм пересечения отрезков, вы можете проверить, пересекается ли ваша нижняя левая линия (1,7) (2,7) с вашей линией (1.3,6.2) (6.51,2.9). http://alienryderflex.com/intersect/

Потребуется некоторый перевод с c на C #, но вы можете понять идею из этой статьи. Я приведу код ниже в случае разрыва связи.

//  public domain function by Darel Rex Finley, 2006

//  Determines the intersection point of the line defined by points A and B with the
//  line defined by points C and D.
//
//  Returns YES if the intersection point was found, and stores that point in X,Y.
//  Returns NO if there is no determinable intersection point, in which case X,Y will
//  be unmodified.

bool lineIntersection(
double Ax, double Ay,
double Bx, double By,
double Cx, double Cy,
double Dx, double Dy,
double *X, double *Y) {

  double  distAB, theCos, theSin, newX, ABpos ;

  //  Fail if either line is undefined.
  if (Ax==Bx && Ay==By || Cx==Dx && Cy==Dy) return NO;

  //  (1) Translate the system so that point A is on the origin.
  Bx-=Ax; By-=Ay;
  Cx-=Ax; Cy-=Ay;
  Dx-=Ax; Dy-=Ay;

  //  Discover the length of segment A-B.
  distAB=sqrt(Bx*Bx+By*By);

  //  (2) Rotate the system so that point B is on the positive X axis.
  theCos=Bx/distAB;
  theSin=By/distAB;
  newX=Cx*theCos+Cy*theSin;
  Cy  =Cy*theCos-Cx*theSin; Cx=newX;
  newX=Dx*theCos+Dy*theSin;
  Dy  =Dy*theCos-Dx*theSin; Dx=newX;

  //  Fail if the lines are parallel.
  if (Cy==Dy) return NO;

  //  (3) Discover the position of the intersection point along line A-B.
  ABpos=Dx+(Cx-Dx)*Dy/(Dy-Cy);

  //  (4) Apply the discovered position to line A-B in the original coordinate system.
  *X=Ax+ABpos*theCos;
  *Y=Ay+ABpos*theSin;

  //  Success.
  return YES; }

Если вам нужно выяснить только, когда (и где) пересекаются отрезки, вы можете изменить функцию следующим образом:

//  public domain function by Darel Rex Finley, 2006  

//  Determines the intersection point of the line segment defined by points A and B
//  with the line segment defined by points C and D.
//
//  Returns YES if the intersection point was found, and stores that point in X,Y.
//  Returns NO if there is no determinable intersection point, in which case X,Y will
//  be unmodified.

bool lineSegmentIntersection(
double Ax, double Ay,
double Bx, double By,
double Cx, double Cy,
double Dx, double Dy,
double *X, double *Y) {

  double  distAB, theCos, theSin, newX, ABpos ;

  //  Fail if either line segment is zero-length.
  if (Ax==Bx && Ay==By || Cx==Dx && Cy==Dy) return NO;

  //  Fail if the segments share an end-point.
  if (Ax==Cx && Ay==Cy || Bx==Cx && By==Cy
  ||  Ax==Dx && Ay==Dy || Bx==Dx && By==Dy) {
    return NO; }

  //  (1) Translate the system so that point A is on the origin.
  Bx-=Ax; By-=Ay;
  Cx-=Ax; Cy-=Ay;
  Dx-=Ax; Dy-=Ay;

  //  Discover the length of segment A-B.
  distAB=sqrt(Bx*Bx+By*By);

  //  (2) Rotate the system so that point B is on the positive X axis.
  theCos=Bx/distAB;
  theSin=By/distAB;
  newX=Cx*theCos+Cy*theSin;
  Cy  =Cy*theCos-Cx*theSin; Cx=newX;
  newX=Dx*theCos+Dy*theSin;
  Dy  =Dy*theCos-Dx*theSin; Dx=newX;

  //  Fail if segment C-D doesn't cross line A-B.
  if (Cy<0. && Dy<0. || Cy>=0. && Dy>=0.) return NO;

  //  (3) Discover the position of the intersection point along line A-B.
  ABpos=Dx+(Cx-Dx)*Dy/(Dy-Cy);

  //  Fail if segment C-D crosses line A-B outside of segment A-B.
  if (ABpos<0. || ABpos>distAB) return NO;

  //  (4) Apply the discovered position to line A-B in the original coordinate system.
  *X=Ax+ABpos*theCos;
  *Y=Ay+ABpos*theSin;

  //  Success.
  return YES; }
Том Блю Пиддок
источник
Привет, обход сетки точно с целью оптимизации тысяч пересечений линий по всей сетке. Это не может быть решено тысячами пересечений линий. У меня есть карта в игре с наземными линиями, которые игрок не может пересечь. Там может быть тысячи таких. Мне нужно определить, для чего рассчитывать дорогой перекресток. Чтобы определить их, я хочу рассчитать только пересечения линий движения игрока (или света от источника света). В вашем случае мне нужно было бы определить пересечения с ~ 256x256x2 отрезками линии каждый раунд. Это не будет оптимизировано вообще.
SmartK8
Но все равно спасибо за ответ. Технически это работает и правильно. Но просто не осуществимо для меня.
SmartK8
3
float difX = end.x - start.x;
float difY = end.y - start.y;
float dist = abs(difX) + abs(difY);

float dx = difX / dist;
float dy = difY / dist;

for (int i = 0, int x, int y; i <= ceil(dist); i++) {
    x = floor(start.x + dx * i);
    y = floor(start.y + dy * i);
    draw(x,y);
}
return true;

JS Demo:

Imgur

A-312
источник
1
Для меня это не удалось из-за числовых ошибок с плавающей запятой (цикл выполнит дополнительную итерацию для самой малой дроби следующего целого числа, которая будет выдвигать конечную точку строки за пределы местоположения 'end'). Простое исправление заключается в том, чтобы сначала вычислить dist как ceil, чтобы dx, dy были разделены на целое число итераций цикла (это означает, что вы можете потерять ceil (dist) в цикле for).
PeteB
0

Я столкнулся с той же проблемой сегодня и сделал довольно большую гору спагетти из холма моль, но в итоге получил кое-что, что работает: https://github.com/SnpM/Pan-Line-Algorithm .

Из ReadMe:

Основная концепция этого алгоритма аналогична концепции Брезенхема в том, что он увеличивает на 1 единицу по одной оси и проверяет увеличение по другой оси. Фракции, однако, значительно увеличивают приращение, и приходится добавлять много пицц. Например, увеличение от X = .21 до X = 1.21 с наклоном 5 создает сложную проблему (координатные комбинации между этими неприятными числами). трудно предсказать), но увеличение от 1 до 2 с наклоном 5 облегчает задачу. Шаблон координат между целыми числами очень легко решить (просто линия, перпендикулярная к возрастающей оси). Чтобы решить простую задачу, приращение смещается к целому числу, причем все вычисления выполняются отдельно для дробной части. Таким образом, вместо того, чтобы начать увеличение на .21,

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

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

JPtheK9
источник