c# - vectoriales - Línea rasterización: ¿Cubre todos los píxeles, independientemente del gradiente de línea?

tipos de imagenes vectoriales

Question

Básicamente, quiero usar una línea algo para determinar qué celdas verificar las colisiones para mi raycaster.

Bresenham no es muy bueno para esto, ya que utiliza un enfoque de grosor unificado, lo que significa que ignora las celdas que no cubren la línea por lo menos a la mitad. No del todo bien, porque significa que algunos segmentos de mi línea no están siendo revisados ​​en busca de intersecciones con las celdas, lo que lleva a errores.

Parece que no puedo encontrar ningún algoritmo de "línea gruesa", ¿puede alguien ayudarme a encontrar uno?

Verde: Lo que me gustaría.
Rojo: Lo que actualmente tengo y no quiero.

Answer 1

¿Qué pasa con Bresenham con una restricción adicional de que no se permiten movimientos diagonales? Genere los puntos con el algoritmo tradicional, luego, como paso posterior al procesamiento, inserte los pasos adicionales necesarios para realizar solo movimientos ortogonales.

Answer 2

Este hilo está viejo, pero pensé que valdría la pena ponerlo en Internet:

// This prints the pixels from (x, y), increasing by dx and dy.
// Based on the DDA algorithm (uses floating point calculations).
void pixelsAfter(int x, int y, int dx, int dy)
{
    // Do not count pixels |dx|==|dy| diagonals twice:
    int steps = Math.abs(dx) == Math.abs(dy)
            ? Math.abs(dx) : Math.abs(dx) + Math.abs(dy);
    double xPos = x;
    double yPos = y;
    double incX = (dx + 0.0d) / steps;
    double incY = (dy + 0.0d) / steps;
    System.out.println(String.format("The pixels after (%d,%d) are:", x, y));
    for(int k = 0; k < steps; k++)
    {
        xPos += incX;
        yPos += incY;
        System.out.println(String.format("A pixel (%d) after is (%d, %d)",
            k + 1, (int)Math.floor(xPos), (int)Math.floor(yPos)));
    }
}

Answer 3

Hay un artículo interesante disponible en GPU Gems, tal vez pueda ayudarte: Capítulo 22. Líneas prefiltradas rápidas

Answer 4

Podría encontrar todas las intersecciones que tiene su rayo con las líneas horizontales de la cuadrícula, y luego marcar todas las celdas de una fila que tengan un punto de intersección en un lado o estar entre las dos celdas con las intersecciones de la fila.

Las intersecciones se pueden hacer comenzando desde el origen, avanzando el punto a la primera intersección (y marcando las celdas en el proceso), descubriendo el vector que te lleva de una intersección a la siguiente (ambas operaciones son triángulos básicos similares) (o trig)) y luego avanzar columna por columna hasta que hayas llegado lo suficientemente lejos. El avance columna por columna implica una adición de vector por columna y un pequeño bucle para completar las celdas entre las que tienen intersecciones. Reemplace "marca" con "proceso" si está procesando las celdas sobre la marcha; se garantiza que este algoritmo marcará cada celda solo una vez.

Lo mismo podría hacerse con las líneas verticales, pero las cuadrículas generalmente se almacenan en cortes horizontales, así que elegí eso. Si está utilizando trigonometría, deberá manejar líneas horizontales rectas con un estuche especial.

Por cierto, que yo sepa, esta es la forma en que se realizaron los viejos juegos "3D" de Raycaster basados ​​en cuadrícula (como Wolfenstein 3D). La primera vez que leí sobre este algoritmo de este libro , hace eones.

Answer 5

Sin pérdida de generalidad, supongamos que x2> = x1, entonces

int x = floor(x1);
int y = floor(y1);
double slope = (x2 - x1) / (y2 - y1);
if (y2 >= y1) {
  while (y < y2) {
    int r = floor(slope * (y - y1) + x1);
    do {
      usepixel(x, y);
      ++x;
    } while (x < r);
    usepixel(x, y);
    ++y;
  }
}
else {
  while (y > y2) {
    int r = floor(slope * (y - y1) + x1);
    do {
      usepixel(x, y);
      ++x;
    } while (x < r);
    usepixel(x, y);
    --y;
  }
}

Las llamadas de planta probablemente se pueden escribir solo como una conversión a entero.

Answer 6

Tuve exactamente el mismo problema que tú y encontré una solución muy simple. Generalmente, Bresenham tiene dos if consecutivos para determinar si debe aumentar la coordenada para las dos dimensiones:

public void drawLine(int x0, int y0, int x1, int y1, char ch) {
    int dx =  Math.abs(x1 - x0), sx = x0 < x1 ? 1 : -1;
    int dy = -Math.abs(y1 - y0), sy = y0 < y1 ? 1 : -1;
    int err = dx + dy, e2; // error value e_xy

    for (;;) {
        put(x0, y0, ch);

        if (x0 == x1 && y0 == y1) break;

        e2 = 2 * err;

        // horizontal step?
        if (e2 > dy) {
            err += dy;
            x0 += sx;
        }

        // vertical step?
        if (e2 < dx) {
            err += dx;
            y0 += sy;
        }
    }
}

Ahora todo lo que tiene que hacer es insertar una else anterior a la segunda if :

public void drawLineNoDiagonalSteps(int x0, int y0, int x1, int y1, char ch) {
    int dx =  Math.abs(x1 - x0), sx = x0 < x1 ? 1 : -1;
    int dy = -Math.abs(y1 - y0), sy = y0 < y1 ? 1 : -1;
    int err = dx + dy, e2;

    for (;;) {
        put(x0, y0, ch);

        if (x0 == x1 && y0 == y1) break;

        e2 = 2 * err;

        // EITHER horizontal OR vertical step (but not both!)
        if (e2 > dy) { 
            err += dy;
            x0 += sx;
        } else if (e2 < dx) { // <--- this "else" makes the difference
            err += dx;
            y0 += sy;
        }
    }
}

Ahora el algoritmo ya no cambia ambas coordenadas a la vez. No he probado esto a fondo, pero parece funcionar bastante bien.