¿Cómo generalizo el algoritmo de línea de Bresenham a puntos finales de punto flotante?

12

Estoy tratando de combinar dos cosas. Estoy escribiendo un juego y necesito determinar los cuadrados de la cuadrícula que se encuentran en una línea con los puntos finales de punto flotante.

Línea de rejilla

Además, necesito que incluya todos los cuadrados de cuadrícula que toca (es decir, no solo la línea de Bresenham sino la azul):

Bresenham vs barrido completo

¿Alguien puede ofrecerme alguna idea sobre cómo hacerlo? La solución obvia es usar un algoritmo de línea ingenuo, pero ¿hay algo más optimizado (más rápido)?

SmartK8
fuente
En caso de que el enlace se desconecte, solo busque en Google un "Algoritmo de recorrido de voxel más rápido para el trazado de rayos"
Gustavo Maciel

Respuestas:

9

Está buscando un algoritmo transversal de cuadrícula. Este documento ofrece una buena implementación;

Aquí está la implementación básica en 2D que se encuentra en el documento:

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

También hay una versión de proyección de rayos 3D en el papel.

En caso de que el enlace se pudra , puede encontrar muchos espejos con su nombre: un algoritmo de recorrido de voxel más rápido para el trazado de rayos .

Gustavo Maciel
fuente
Bueno, incomodo. Supongo que te cambiaré la respuesta y votaré a favor de ltjax. Porque lo resolví en función de su enlace a ese documento.
SmartK8
5

La idea de Blue es buena, pero la implementación es un poco torpe. De hecho, puede hacerlo fácilmente sin sqrt. Supongamos por el momento que excluye casos degenerados ( BeginX==EndX || BeginY==EndY) y nos enfocamos solo en las direcciones de línea en el primer cuadrante, entonces BeginX < EndX && BeginY < EndY. También tendrá que implementar una versión para al menos otro cuadrante, pero es muy similar a la versión para el primer cuadrante: solo verifica otros bordes. En el pseudocódigo 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;
  }
}

Ahora, para otros cuadrantes, que acaba de cambiar la ++cxo ++cyy la condición del bucle. Si usa esto para colisión, es probable que tenga que implementar las 4 versiones, de lo contrario, puede salirse con dos intercambiando adecuadamente los puntos de inicio y finalización.

ltjax
fuente
El algoritmo proporcionado por Gustavo Maciel es un poco más eficiente. Solo determina primero Ts y luego agrega 1 a vertical u horizontal y desplaza Ts por un tamaño de celda. Pero como no lo convirtió en una respuesta, aceptaré esta como la respuesta más cercana.
SmartK8
3

Su suposición no es necesariamente encontrar las celdas sino las líneas que cruza en esta cuadrícula.

Por ejemplo, al tomar su imagen, podemos resaltar no las celdas, sino las líneas de la cuadrícula que cruza:

Líneas rojas

Esto muestra que si cruza una línea de cuadrícula, las celdas a cada lado de esta línea son las que están rellenas.

Puede usar un algoritmo de intersección para encontrar si su línea de coma flotante los cruzará escalando sus puntos a píxeles. Si tiene una relación de 1.0: 1 de coordenadas flotantes: píxeles, entonces está ordenado y puede traducirlo directamente. Usando el algoritmo de intersección de segmento de línea puede verificar si su línea inferior izquierda (1,7) (2,7) se cruza con su línea (1.3,6.2) (6.51,2.9). http://alienryderflex.com/intersect/

Se necesitará alguna traducción de c a C #, pero puede obtener la idea de ese documento. Pondré el código a continuación en caso de que el enlace se rompa.

//  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; }

Si necesita averiguar solo cuándo (y dónde) se intersecan los segmentos de línea, puede modificar la función de la siguiente manera:

//  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; }
Tom 'Blue' Piddock
fuente
Hola, el recorrido de la cuadrícula es exactamente para optimizar miles de intersecciones de líneas en toda la cuadrícula. Esto no se puede resolver con miles de intersecciones de línea. Tengo un mapa en un juego con líneas de tierra que el jugador no puede cruzar. Puede haber miles de estos. Necesito determinar para cuál calcular la intersección costosa. Para determinar esto solo quiero calcular las intersecciones de aquellos en la línea de movimiento del jugador (o luz de la fuente de luz). En su caso, necesitaría determinar las intersecciones con ~ 256x256x2 segmentos de línea en cada ronda. Eso no se optimizaría en absoluto.
SmartK8
Pero aún así gracias por tu respuesta. Técnicamente funciona y es correcto. Pero simplemente no es factible para mí.
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;

Demo de JS:

Imgur

A-312
fuente
1
Esto falló para mí debido a errores numéricos de coma flotante (el bucle hará una iteración adicional para la fracción más pequeña sobre el siguiente entero que empujará el punto final de la línea más allá de la ubicación 'final'). La solución simple es calcular dist como ceil en primer lugar para que dx, dy se dividan por el número entero de iteraciones del bucle (esto significa que puede perder el ceil (dist) en el bucle for).
PeteB
0

Me encontré con el mismo problema hoy e hice una gran montaña de espagueti con una colina de mole, pero terminé con algo que funciona: https://github.com/SnpM/Pan-Line-Algorithm .

Desde el archivo Léame:

El concepto central de este algoritmo es similar al de Bresenham en que se incrementa en 1 unidad en un eje y prueba el aumento en el otro eje. Sin embargo, las fracciones hacen que el incremento sea considerablemente más difícil, y se tuvieron que agregar muchas pizzas. Por ejemplo, el incremento de X = .21 a X = 1.21 con una pendiente de 5 crea un problema complejo (patrones de coordenadas entre esos números desagradables son difíciles de predecir), pero aumentar de 1 a 2 con una pendiente de 5 hace que sea un problema fácil. El patrón de coordenadas entre enteros es muy fácil de resolver (solo una línea perpendicular al eje de incremento). Para obtener el problema fácil, el incremento se compensa con un número entero con todos los cálculos realizados por separado para la pieza fraccional. Entonces, en lugar de comenzar el incremento en .21,

ReadMe explica la solución mucho mejor que el código. Estoy planeando revisarlo para que sea menos dolor de cabeza.

Sé que llegué un año tarde a esta pregunta, pero espero que esto llegue a otros que buscan una solución a este problema.

JPtheK9
fuente