Algoritmo de Bresenham para el dibujo lineal en 3D

Dadas dos coordenadas tridimensionales, necesitamos encontrar los puntos en la línea que las une. Todos los puntos tienen coordenadas enteras.

Ejemplos:

Input  : (-1, 1, 1), (5, 3, -1)
Output : (-1, 1, 1), (0, 1, 1), (1, 2, 0),
          (2, 2, 0), (3, 2, 0), (4, 3, -1), 
          (5, 3, -1)





Input  : (-7, 0, -3), (2, -5, -1)
Output : (-7, 0, -3), (-6, -1, -3), (-5, -1, -3),
         (-4, -2, -2), (-3, -2, -2), (-2, -3, -2),
         (-1, -3, -2), (0, -4, -1), (1, -4, -1),
          (2, -5, -1)

El algoritmo de Bresenham es eficiente ya que evita las operaciones aritméticas de coma flotante. Como en el caso del dibujo lineal en 2D , usamos una variable para almacenar el error de pendiente, es decir, el error en la pendiente de la línea que se está trazando a partir de la línea geométrica real. Tan pronto como este error de pendiente exceda el valor permisible, modificamos el digital para negar el error.

El eje conductor de la línea a trazar es aquel a lo largo del cual la línea se desplaza más, es decir, la diferencia en las coordenadas de los ejes es mayor. Por lo tanto, los valores de las coordenadas aumentan linealmente en 1 a lo largo del eje impulsor y la variable de error de pendiente se usa para determinar el cambio en los valores de las coordenadas del otro eje.

En el caso de una línea 2D, usamos una variable de error de pendiente, pero en el caso de una línea 3D, necesitamos dos ( $py, pz$ ) de ellas para cada uno de los ejes no motores. Si el punto actual es $P_{k}$ (x, y, z) y el eje impulsor es el eje X positivo, entonces el siguiente punto $P_{k+1}$ podría ser

(x+1, y, z)
(x+1, y+1, z)
(x+1, y, z+1)
(x+1, y+1, z+1)

Candidate points for next point on a 3D Line

El valor de las variables de error de pendiente se determina de acuerdo con las siguientes ecuaciones:
$py_{k+1} = py_{k} + 2dy - 2dx(y_{k+1} - y_{k})\\ pz_{k+1} = pz_{k} + 2dz - 2dx(z_{k+1} - z_{k})$

El valor inicial de las variables de error de pendiente viene dado por las siguientes ecuaciones:
$py_{0} = 2dy - dx\\ pz_{0} = 2dz - dx$
Aquí se $dx, dy, dz$ indica la diferencia en las coordenadas de los dos puntos finales a lo largo de los ejes X, Y, Z.

Algoritmo:-

Ingrese los dos puntos finales y almacene el punto inicial como $(x_{0}, y_{0}, z_{0})$
Gráfico $(x_{0}, y_{0}, z_{0})$
Calcule constantes $dx, dy, dz$ y determine el eje impulsor comparando
los valores absolutos de $dx, dy, dz$
Si abs( $dx$ ) es máximo, entonces el eje X es el eje impulsor
Si abs( $dy$ ) es máximo, entonces el eje Y es el eje impulsor
Si abs( $dz$ ) es máximo, entonces el eje Z es el eje impulsor
Supongamos que el eje X es el eje impulsor, entonces
$py_{0} = 2dy - dx\\ pz_{0} = 2dz - dx$
En cada uno a lo largo de la línea, comenzando en k = 0, verifique las siguientes condiciones
y determine el siguiente punto:
- Si $py_{k} < 0$ Y $pz_{k} < 0$ , entonces
  trazar $(x_{k}+1, y_{k}, z_{k})$ y
  establecer $py_{k+1}=py_{k}+2dy, pz_{k+1}=pz_{k}+2dz$
- De lo contrario, si $py_{k} > 0$ AND $pz_{k} < 0$ ,
  trazar $(x_{k}+1, y_{k}+1, z_{k})$ y
  establecer $py_{k+1}=py_{k}+2dy-2dx, pz_{k+1}=pz_{k}+2dz$
- Else If $py_{k} 0$ , luego
  graficar $(x_{k}+1, y_{k}, z_{k}+1)$ y
  establecer $py_{k+1}=py_{k}+2dy, pz_{k+1}=pz_{k}+2dz-2dx$
- De lo contrario,
  trazar $(x_{k}+1, y_{k}+1, z_{k}+1)$ y
  establecer $py_{k+1}=py_{k}+2dy-2dx, pz_{k+1}=pz_{k}+2dz-2dx$ >
Repita el paso 5 $dx-1$ veces

Python3

# Python3 code for generating points on a 3-D line 
# using Bresenham's Algorithm
  
def Bresenham3D(x1, y1, z1, x2, y2, z2):
    ListOfPoints = []
    ListOfPoints.append((x1, y1, z1))
    dx = abs(x2 - x1)
    dy = abs(y2 - y1)
    dz = abs(z2 - z1)
    if (x2 > x1):
        xs = 1
    else:
        xs = -1
    if (y2 > y1):
        ys = 1
    else:
        ys = -1
    if (z2 > z1):
        zs = 1
    else:
        zs = -1
  
    # Driving axis is X-axis"
    if (dx >= dy and dx >= dz):        
        p1 = 2 * dy - dx
        p2 = 2 * dz - dx
        while (x1 != x2):
            x1 += xs
            if (p1 >= 0):
                y1 += ys
                p1 -= 2 * dx
            if (p2 >= 0):
                z1 += zs
                p2 -= 2 * dx
            p1 += 2 * dy
            p2 += 2 * dz
            ListOfPoints.append((x1, y1, z1))
  
    # Driving axis is Y-axis"
    elif (dy >= dx and dy >= dz):       
        p1 = 2 * dx - dy
        p2 = 2 * dz - dy
        while (y1 != y2):
            y1 += ys
            if (p1 >= 0):
                x1 += xs
                p1 -= 2 * dy
            if (p2 >= 0):
                z1 += zs
                p2 -= 2 * dy
            p1 += 2 * dx
            p2 += 2 * dz
            ListOfPoints.append((x1, y1, z1))
  
    # Driving axis is Z-axis"
    else:        
        p1 = 2 * dy - dz
        p2 = 2 * dx - dz
        while (z1 != z2):
            z1 += zs
            if (p1 >= 0):
                y1 += ys
                p1 -= 2 * dz
            if (p2 >= 0):
                x1 += xs
                p2 -= 2 * dz
            p1 += 2 * dy
            p2 += 2 * dx
            ListOfPoints.append((x1, y1, z1))
    return ListOfPoints
  
  
def main():
    (x1, y1, z1) = (-1, 1, 1)
    (x2, y2, z2) = (5, 3, -1)
    ListOfPoints = Bresenham3D(x1, y1, z1, x2, y2, z2)
    print(ListOfPoints)
  
main()

Producción:

[(-1, 1, 1), (0, 1, 1), (1, 2, 0), (2, 2, 0), (3, 2, 0), (4, 3, -1), (5, 3, -1)]

Publicación traducida automáticamente

Artículo escrito por nabaneet247 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Python3

Deja una respuesta Cancelar la respuesta