ALGORITMO DE BRESENHAM
INTRODUCCIÓN
El algoritmo de Bresenham, desarrollado por Jack E. Bresenham en 1962, revolucionó los gráficos por computadora al ofrecer una solución eficiente para el trazado de líneas rectas en displays pixelados. A diferencia de métodos basados en ecuaciones de recta que requieren cálculos en punto flotante, este algoritmo utiliza solo operaciones con enteros y aritmética incremental, lo que lo hace extremadamente rápido y apto para hardware con recursos limitados, como los sistemas embebidos o las primeras computadoras gráficas.
¿Qué es?
Se basa en calcular de forma incremental el error entre la línea ideal y la aproximación pixelada, eligiendo en cada paso el píxel más cercano a la trayectoria teórica. Su principal ventaja es que utiliza únicamente aritmética de enteros, lo que lo hace rápido y adecuado para hardware de bajo nivel.
Aunque originalmente fue diseñado para líneas con pendiente entre 0 y 1, puede adaptarse fácilmente a otras pendientes intercambiando o invirtiendo coordenadas. Además, este algoritmo puede extenderse para rasterizar circunferencias y curvas. En términos simples, funciona como si se dibujara una línea sobre una hoja cuadriculada, decidiendo qué casillas pintar para lograr que la línea parezca lo más recta posible, sin usar números decimales.
CARACTERÍSTICAS
- Eficiencia computacional: Usa solo cálculos enteros (no requiere punto flotante). Minimiza operaciones costosas (solo sumas y restas).
- Precisión:Genera líneas sin aliasing (sin escalones visibles) en pendientes suaves. Selecciona el píxel más cercano al trazo teórico de la línea.
- Versatilidad:Funciona para todas las pendientes (positivas, negativas, >1 o <1). Puede adaptarse para dibujar círculos y otras curvas (versión extendida).
- Algoritmo incremental: Decide el siguiente píxel basándose en el error acumulado (variable de decisión).
- Adaptabilidad: Puede extenderse para dibujar circunferencias y otras curvas.
APLICACIONES
La principal aplicación del algoritmo de línea de Bresenham es el dibujo de líneas en una pantalla digital o lienzo . Su eficiencia lo hace ideal para la renderización en tiempo real en aplicaciones como diseño asistido por computadora (CAD), videojuegos y simulaciones por computadora.
- Dibujo de líneas en pantallas y software gráfico
Se utiliza para trazar líneas en lienzos digitales, como en herramientas de dibujo (Paint, Photoshop) y sistemas operativos (Windows, Linux) al dibujar ventanas, íconos o figuras. Su precisión y bajo consumo lo hacen ideal para estas tareas.
- Videojuegos, Pixel Art y gráficos en tiempo real
Ideal para motores gráficos 2D, especialmente en estilo pixel-art. Se usa para dibujar contornos, personajes y mapas. Gracias a su eficiencia, fue esencial en videojuegos clásicos y sigue siendo útil en dispositivos con recursos limitados.
- Diseño Asistido por Computador (CAD) e industria
Permite representar líneas rectas de manera rápida y precisa en planos técnicos y modelos industriales. Es especialmente útil en hardware con baja capacidad de procesamiento gráfico.
- Rasterización y procesamiento de imágenes
Determina qué píxeles activar en una línea, logrando visuales suaves. También se aplica en algoritmos de rasterización para contornos, regiones de interés o rutas dentro de imágenes digitales.
- Recorte de líneas (Clipping)
Permite limitar las líneas al área visible de la pantalla, evitando cálculos innecesarios y mejorando el rendimiento en gráficos en tiempo real o procesamiento de escenas complejas.
- Robótica y navegación
Usado en sistemas como SLAM para trazar líneas de visión o caminos posibles entre dos puntos. Ayuda a los robots a planear rutas y entender su entorno a través de mapas de ocupación.
FUNDAMENTO MATEMÁTICO
El algoritmo de Bresenham selecciona, empleando incrementos, el píxel que más cerca se encuentre de la posición real del punto en la recta. Para esto se debe definir el punto de inicio y el final para poder aplicar las formulas que definen el comportamiento de los pixeles. Una vez que se tienen los puntos se requieren 3 diferentes variables, las cuales son Δx, Δy y P, que determinan la dirección que toma la linea.
Δx, Δy Representación entre diferencias de coordenadas. Determina la pendiente de la recta
P = Es un parámetro que dermina la dirección de la linea.
Para determinar la dirección de la recta, sea arriba, abajo, derecha o izquierda
Una vez definida la dirección o que va tomar la recta, ahora se debe saber cual será el pixel que deberá iniciarse para poder trazar la linea. Para esto me define la variable de P y se tiene en cuenta los siguientes parámetros para cada iteración de P.
Cuando se realiza una iteración se actualiza el valor de P y se va definiendo pixel por pixel la linea. En la siguiente tabla se muestra un ejemplo de cada iteración que realiza el algoritmo desde la coordenada (3,2) hasta la coordenada (15,5).
En la tabla se realizan solo 6 iteraciones llegando hasta la coordenada (9,4), siguiendo la lógica del algoritmo se llega hasta la coordenada deseada como se muestra en la siguiente grafica que plantea una linea recta con todos los pixeles que deben encenderse para trazar esta linea.
Código Interactivo
import tkinter as tk
from tkinter import ttk
import time
class BresenhamVisualizer:
def __init__(self, root):
self.root = root
self.root.title("Algoritmo de Bresenham - Visualización")
# Configuración
self.cell_size = 15
self.grid_size = 20
self.delay = 0.5 # segundos
# Interfaz
self.setup_ui()
# Estado
self.line_points = []
self.is_running = False
def setup_ui(self):
# Canvas para dibujar
self.canvas = tk.Canvas(self.root,
width=self.grid_size*self.cell_size,
height=self.grid_size*self.cell_size,
bg="white")
self.canvas.pack(pady=10)
# Controles
control_frame = tk.Frame(self.root)
control_frame.pack(pady=10)
self.speed_slider = ttk.Scale(control_frame, from_=0.1, to=2, value=self.delay,
orient="horizontal",
command=lambda v: setattr(self, 'delay', float(v)))
self.speed_slider.pack(side="left", padx=5)
ttk.Button(control_frame, text="Dibujar línea", command=self.start_drawing).pack(side="left", padx=5)
ttk.Button(control_frame, text="Reiniciar", command=self.reset).pack(side="left", padx=5)
# Info
self.info_label = tk.Label(self.root, text="Presiona 'Dibujar línea' para comenzar", fg="blue")
self.info_label.pack(pady=5)
# Dibujar cuadrícula
self.draw_grid()
# Configurar eventos
self.canvas.bind("<Button-1>", self.set_point)
def draw_grid(self):
for x in range(0, self.grid_size*self.cell_size, self.cell_size):
self.canvas.create_line(x, 0, x, self.grid_size*self.cell_size, fill="#eee")
for y in range(0, self.grid_size*self.cell_size, self.cell_size):
self.canvas.create_line(0, y, self.grid_size*self.cell_size, y, fill="#eee")
# Etiquetas de ejes
for i in range(self.grid_size):
self.canvas.create_text(i*self.cell_size + self.cell_size//2,
self.grid_size*self.cell_size - 10,
text=str(i), fill="gray")
self.canvas.create_text(10, i*self.cell_size + self.cell_size//2,
text=str(i), fill="gray")
def set_point(self, event):
if len(self.line_points) >= 2:
self.reset()
x = event.x // self.cell_size
y = event.y // self.cell_size
# Dibujar punto
x1 = x * self.cell_size
y1 = y * self.cell_size
x2 = x1 + self.cell_size
y2 = y1 + self.cell_size
self.canvas.create_rectangle(x1, y1, x2, y2, fill="green", outline="")
self.line_points.append((x, y))
if len(self.line_points) == 1:
self.info_label.config(text=f"Punto inicial: ({x}, {y}). Selecciona el punto final.")
elif len(self.line_points) == 2:
self.info_label.config(text=f"Puntos: {self.line_points[0]} a {self.line_points[1]}. Presiona 'Dibujar línea'")
def start_drawing(self):
if len(self.line_points) == 2 and not self.is_running:
self.is_running = True
self.bresenham_line(*self.line_points[0], *self.line_points[1], self.draw_pixel)
def step_by_step(self):
if len(self.line_points) == 2 and not self.is_running:
self.is_running = True
self.bresenham_line(*self.line_points[0], *self.line_points[1], self.draw_pixel, step_by_step=True)
def reset(self):
self.is_running = False
self.line_points = []
self.canvas.delete("all")
self.draw_grid()
self.info_label.config(text="Selecciona dos puntos para dibujar una línea")
def draw_pixel(self, x, y, is_current=False):
x1 = x * self.cell_size
y1 = y * self.cell_size
x2 = x1 + self.cell_size
y2 = y1 + self.cell_size
color = "red" if is_current else "blue"
self.canvas.create_rectangle(x1, y1, x2, y2, fill=color, outline="")
self.canvas.create_text(x1 + self.cell_size//2, y1 + self.cell_size//2,
text=f"({x},{y})", fill="white")
self.root.update()
def bresenham_line(self, x1, y1, x2, y2, draw_pixel, step_by_step=False):
dx = abs(x2 - x1)
dy = abs(y2 - y1)
steep = dy > dx
if steep:
x1, y1 = y1, x1
x2, y2 = y2, x2
if x1 > x2:
x1, x2 = x2, x1
y1, y2 = y2, y1
dx = abs(x2 - x1)
dy = abs(y2 - y1)
error = dx // 2
ystep = 1 if y1 < y2 else -1
y = y1
for x in range(x1, x2 + 1):
coord = (y, x) if steep else (x, y)
draw_pixel(*coord, is_current=True)
# Mostrar información
current_error = error
self.info_label.config(
text=f"Punto actual: {coord}\n"
f"Error: {current_error}\n"
f"dx: {dx}, dy: {dy}\n"
f"Incremento Y cuando error < 0"
)
if step_by_step:
input("Presiona Enter para continuar...")
else:
time.sleep(self.delay)
# Quitar el resaltado
draw_pixel(*coord, is_current=False)
error -= dy
if error < 0:
y += ystep
error += dx
self.is_running = False
self.info_label.config(text=f"Línea completada de {self.line_points[0]} a {self.line_points[1]}")
if __name__ == "__main__":
root = tk.Tk()
app = BresenhamVisualizer(root)
root.mainloop()
VISUALIZACIÓN DEL CÓDIGO
CONCLUSIONES
El algoritmo de Bresenham marcó un hito en los gráficos por computadora al permitir el trazado eficiente de líneas en pantallas pixeladas. Su principal fortaleza radica en que no utiliza operaciones en punto flotante, sino que trabaja únicamente con enteros, lo cual era ideal para los equipos con recursos limitados de la época y aún es útil en dispositivos de bajo rendimiento.
Este algoritmo calcula cada punto de la línea de forma incremental, basándose en el anterior, lo que reduce significativamente los cálculos necesarios. En lugar de aplicar la ecuación de la línea en cada paso, usa un valor de error acumulado que le indica cuándo cambiar de fila o columna, logrando así líneas más suaves y precisas.
Su velocidad lo hace indispensable en videojuegos retro, sistemas de navegación embebidos y herramientas CAD, donde se prioriza el trazado rápido de primitivas gráficas sin dependencia de aceleración por hardware (como GPUs modernas).
El algoritmo de Bresenham sentó un precedente en la implementación de funciones básicas de rasterización en bibliotecas gráficas tempranas (como OpenGL y DirectX). Su lógica influyó en la optimización de operaciones de dibujo primitivo, incluso en APIs modernas, donde técnicas derivadas de su enfoque se usan en etapas iniciales del pipeline gráfico o en contextos de bajo nivel (ej: controladores de GPU o firmware de pantallas).
Además, ha sido adaptado para dibujar otras figuras como círculos y elipses, conservando su eficiencia y calidad visual. A pesar del paso del tiempo, el algoritmo de Bresenham sigue vigente y se emplea en diversas áreas como videojuegos y software de diseño, gracias a su equilibrio entre simplicidad, rapidez y buenos resultados visuales.
CRÉDITOS
Autores: Arlyn Jessenia Cortés García, Yerli Tatiana Urrea Naranjo, Nicolás Araújo Rodríguez
Editor: Carlos Iván Pinzón Romero
Código: UCCGG1-9
Universidad Central: Universidad Central
BIBLIOGRAFÍAS
2.3.3 Algoritmo de punto medio - Bresenham. (s. f.). http://cidecame.uaeh.edu.mx/lcc/mapa/PROYECTO/libro23/233_algoritmo_de_punto_medio__bresenham.html
Adlab. (2016, 16 febrero). Algoritmo de Bresenham. Grafica2016a. https://grafica2016a.wordpress.com/2016/02/16/algoritmo-de-bresenham/
Branch, J. W., Sánchez, G., & Atencio, P. (2012). Remuestreo estructurado de contornos de huecos en superficies 3D de objetos de forma libre utilizando Bresenham [PDF]. Universidad Nacional de Colombia. https://repositorio.unal.edu.co/bitstream/handle/unal/40612/29595-106280-1-PB.pdf?sequence=2&isAllowed=y
Bresenham’s Line Algorithm in Computer Graphics. (s. f.). https://bcalabs.org/subject/bresenhams-line-algorithm-in-computer-graphics
Bresenham Line Algorithm: A Powerful Tool for Efficient Line Drawing | Saturn Cloud Blog. (2023, 3 noviembre). https://saturncloud-io.translate.goog/blog/bresenham-line-algorithm-a-powerful-tool-for-efficient-line-drawing/?_x_tr_sl=en&_x_tr_tl=es&_x_tr_hl=es&_x_tr_pto=rq#:~:text=Applications%20of%20the%20Bresenham%20Line%20Algorithm&text=The%20primary%20application%20of%20the,video%20games%2C%20and%20computer%20simulations.
¿Cómo se puede implementar el algoritmo de líneas de Bresenham para gráficos 2D? (2024, 21 febrero). www.linkedin.com. https://es.linkedin.com/advice/3/how-can-you-implement-bresenham-line-algorithm-hfhyc?lang=es&lang=es
Edwin Duque. (2019, 2 febrero). Algoritmo para trazado de linea por computador Bresenham [Vídeo]. YouTube. https://www.youtube.com/watch?v=2_BCYD_FwII
Oguzhandelibas. (s. f.). GitHub - oguzhandelibas/LineDrawing: Drawing Lines in Unity with the Bresenham Line Algorithm. GitHub. https://github.com/oguzhandelibas/LineDrawing
Segovia, J. L. C. (2021). Algoritmo de Bresenham. Unsaac. https://www.academia.edu/50823751/Algoritmo_de_Bresenham
