Algoritmos

Algoritmos geométricos

El Algoritmo de Bresenham es un método preciso para la generación de líneas de rastreo que utiliza solo cálculos incrementales con enteros. Se puede adaptar para rasterizar también circunferencias y curvas. Los ejes verticales muestran las posiciones de rastreo y los ejes horizontales identifican columnas de pixel.

Ejemplo de aplicación del algoritmo de Bresenham.

Algoritmo

El algoritmo sería el siguiente:

Si 0<|m|<1 almacena="" capturan="" de="" e="" el="" en="" extremo="" extremos="" izquierdo="" l="" la="" los="" nea="" se="" style="line-height: 1em;" sub="" x="" y="">0

,y₀). *Se carga (x₀,y₀) en el bufer de estructura (se traza el primer punto) *Se calculan las constantes Δx,Δy, 2Δy y 2Δy-Δx y se obtiene el valor inicial para el parámetro de decisión p₀=2Δy-Δx. Para j=0 mientras j<Δx *En cada x_k a lo largo de la línea, que inicia en k=0 se efectúa la prueba siguiente: Si p_k<0 razamos="" style="line-height: 1em;" sub="" x="">k+1,y_k). *Asignamos p_k+1= p_k+2Δy. Si no *Trazamos (x_k+1,y_k+1). *Asignamos p_k+1= p_k+2Δy-2Δx. Fin Para Si |m|>1 *Recorremos la dirección en pasos unitarios y calculamos los valores sucesivos de x que se aproximen más a la trayectoria de la línea.

Implementación en Java

Esta es la implementación del algoritmo:

public void Bresenham(Graphics g,int x0, int y0, int x1, int y1) { 
  int x, y, dx, dy, p, incE, incNE, stepx, stepy;
  dx = (x1 - x0);
  dy = (y1 - y0);

 /* determinar que punto usar para empezar, cual para terminar */
  if (dy < 0) { 
    dy = -dy; 
    stepy = -1; 
  } 
  else {
    stepy = 1;
  }

  if (dx < 0) {  
    dx = -dx;  
    stepx = -1; 
  } 
  else {
    stepx = 1;
  }

  x = x0;
  y = y0;
  g.drawLine( x0, y0, x0, y0);
 /* se cicla hasta llegar al extremo de la línea */
  if(dx>dy){
    p = 2*dy - dx;
    incE = 2*dy;
    incNE = 2*(dy-dx);
    while (x != x1){
      x = x + stepx;
      if (p < 0){
        p = p + incE;
      }
      else {
        y = y + stepy;
        p = p + incNE;
      }
      g.drawLine( x, y, x, y);
    }
  }
  else{
    p = 2*dx - dy;
    incE = 2*dx;
    incNE = 2*(dx-dy);
    while (y != y1){
      y = y + stepy;
      if (p < 0){
        p = p + incE;
      }
      else {
        x = x + stepx;
        p = p + incNE;
      }
      g.drawLine( x, y, x, y);
    }
  }
 }

Implementación en Gambas

Esta es la implementación del algoritmo:

Public Sub hacerlinea(x0 As Integer, y0 As Integer, x1 As Integer, y1 As Integer)

  Dim x, y, dx, dy, p, incE, incNE, stepx, stepy As Integer

  dx = x1 - x0
  dy = y1 - y0

 ' determinar que punto usar para empezar, cual para terminar
  If dy < 0 Then
    dy = - dy
    stepy = -1
  Else 
    stepy = 1
  Endif
  
  If dx < 0 Then
    dx = - dx
    stepx = -1
  Else
    stepx = 1
  Endif

  x = x0
  y = y0
  
  Draw.Begin(DrawingArea1)
  Draw.Point(x0, y0)
' se cicla hasta llegar al extremo de la l ínea
  If dx > dy Then
    p = 2 * dy - dx
    incE = 2 * dy
    incNE = 2 * (dy - dx)
    While x <> x1
      x = x + stepx
      If p < 0 Then
        p = p + incE
      Else 
        y = y + stepy
        p = p + incNE
      Endif
      Draw.Point(x, y)
    Wend 
  Else 
    p = 2 * dx - dy
    incE = 2 * dx
    incNE = 2 * (dx - dy)
    While y <> y1
      y = y + stepy
      If p < 0 Then
        p = p + incE      
      Else 
        x = x + stepx
        p = p + incNE
      Endif
       Draw.Point(x, y)
     Wend
  Endif
Draw.End
End

Binary space partitioning o Partición Binaria del Espacio (BSP) es un método para subdividir recursivamente un espacio en elementos convexos empleando hiperplanos. Esta subdivisión da lugar a una representación de la escena por medio de una estructura de datos del árbol conocida como árbol de BSP.

Descripción

En diseño por ordenador es deseable que el dibujo de una escena sea correcta y rápida. Una manera sencilla de dibujar una escena correctamente es el algoritmo del pintor: dibujar primero lo más lejano y después lo más cercano. Sin embargo, este sistema es muy limitado ya que se pierde tiempo pintando objetos que más tarde serán tapados por otros.

La técnica del Z-Buffer puede asegurar que las escenas se dibujarán correctamente y que se eliminará la necesidad de seguir un orden como en el algoritmo del pintor, pero es poco eficiente en términos de memoria. Los árboles BSP dividen los objetos de forma que el algoritmo del pintor los dibujará correctamente sin necesidad de emplear un Z-buffer ni de ordenar los objetos como un simple árbol transversal que los mantenga en el orden adecuado. También sirve como base para otros algoritmos, como las listas de visibilidad, que buscan evitar dibujar sin necesidad.

El problema es que necesita un pre-procesamiento de la escena, lo que hace difícil e ineficiente insertar los objetos móviles directamente en el árbol BSP. Esto se suele solucionar empleando conjuntamente un Z-Buffer, usándolo para unir correctamente los objetos móviles como puertas y enemigos con el resto de la escena.

Los árboles BSP se emplean normalmente en los videojuegos, especialmente en los de acción en primera persona y en los que tienen entornos de interior. Probablemente el primer juego que empleó esta técnica fue Doom (ver motor de Doom para más información sobre la implementación). Otros usos incluye el Ray tracing y la detección de colisiones.

Definición recursiva del árbol binario

T(S):

Si ${\displaystyle card(S)=1}$:

T(S) es una hoja, v;
En la hoja se almacena el objeto (si existe), S(v).


Si ${\displaystyle card(S)>1}$:

La raíz v de T(S) almacena:

una recta (plano) hv,
conjunto S(v) de objetos contenidos en hv.


Hijo izquierdo de v: raíz de un árbol T(S-), con ${\displaystyle S-=}$ {hv- instp S : s ? S}.
Hijo derecho de v: raíz de un árbol T(S+), con ${\displaystyle S+=}$ {hv+ instp S : s ? S}.




instp: interceptado

Generación

La partición binaria del espacio es un proceso genérico que divide una escena recursivamente en dos hasta que satisface uno o más requisitos. El método específico empleado varía dependiendo del objetivo final. Por ejemplo, en un árbol BSP empleado para la detección de colisiones el objeto original sería dividido hasta que cada parte sea lo suficientemente sencilla como para ser individualmente comprobada, y en el renderizaje interesa que cada parte sea convexa, de forma que el algoritmo del pintor pueda ser usado.

El número final de objetos crecerá inevitablemente ya que las líneas y caras que se crucen con el plano de partición serán divididas en dos, y también es deseable que el árbol final esté razonablemente balanceado. De hecho, el algoritmo para crear un árbol BSP correcta y eficientemente es la parte más difícil de implementar. En un espacio de tres dimensiones, se emplean planos para dividir las caras de un objeto; en un espacio de dos se emplean líneas.

La siguiente imagen ilustra el proceso de partición de un polígono irregular en una serie de polígonos convexos. Destacar cómo cada paso produce polígonos con menos segmentos hasta que se llega a F y G, que son convexos y no necesitan mayor partición. En este caso en particular, la línea de partición se ha tomado empleando vértices existentes del polígono y no se intersecciona con ninguno de sus segmentos. Si la línea de partición se intersecciona con un segmento, o una cara en un modelo tridimensional, el/los segmento/s o cara/s tienen que ser divididas en dos dado que cada partición debe ser un objeto completo e independiente.




1. A es la raíz del árbol y de todo el polígono.
2. Se divide A en B y C
3. Se divide B en D y E.
4. Se divide D en F y G, que son convexos y se convierten en hojas del árbol.




Dado que la utilidad de un árbol BSP depende de cómo se generó, un buen algoritmo es esencial. La mayoría de los algoritmos prueban muchas posibilidades para cada partición hasta que se encuentra un resultado lo suficientemente bueno, y también mantienen la información necesaria en memoria para poder retroceder en caso de que una rama del árbol no sea satisfactoria y probar otras opciones. Por eso generar un árbol necesita mucho tiempo de computación.

Usos del Árbol BSP

Inicialmente, esta idea se propuso para los gráficos 3D por ordenador para incrementar la eficiencia de renderizado. Otros usos son el procesamiento geométrico con formas, Constructive Solid Geometry en herramientas CAD, detección de colisiones en robótica y videojuegos 3D, y otras aplicaciones informáticas que incluyen el manejo de estructuras espaciales complejas. la eliminación de caras ocultas ya que gracias a los planos divisorios del árbol conoceríamos qué polígonos están detrás o delante, teniendo solamente que considerar determinadas ramas del árbol a través de la posición desde la que nos estemos posicionando en él.

El uso más común de los árboles de BSP es probablemente retiro superficial ocultado en tres dimensiones. Los árboles de BSP proporcionan un método elegante, eficiente para clasificar polígonos vía una primera caminata del árbol de la profundidad: algoritmo “del pintor delantero” o Algoritmo del pintor.

Objetivos de los árboles BSP

Permiten determinar el orden en que deben ser dibujados los polígonos para lograr el retiro superficial ocultado.
Permiten determinar si un punto determinado está en una parte sólida del modelo o no.
Permiten detectar las colisiones con el modelo.


Construcción de un árbol BSP

El algoritmo para construir un árbol de BSP es muy simple:

Seleccionar un plano de la partición.
Repartir el sistema de polígonos en el plano.
Recubrir con cada uno de los dos nuevos sistemas.


Uso del BSPT

El uso más común de los árboles de BSP es probablemente retiro superficial ocultado en tres dimensiones. Los árboles de BSP proporcionan un método elegante, eficiente para clasificar polígonos vía una primera caminata del árbol de la profundidad: algoritmo “del pintor delantero” o algoritmo del pintor.

Algoritmo del pintor

El Algoritmo “del pintor conocido” refiere a un pintor simple-importado que pinte las partes distantes de una escena al principio y después las cubra por esas piezas que sean más cercanas. El algoritmo del pintor clasifica todos los polígonos en una escena por su profundidad y después los pinta en esta orden.


Detección de Colisiones

La escena queda representada en un árbol binario BSP. Las hojas de dicho árbol representan a un objeto, mientras que los nodos no-hojas representan planos-ejes separadores. Un eje/semiplano divide la subdivisión representada por el padre en dos partes, una a la izquierda y otra a la derecha (considerando el semieje con base en el semieje padre, por ejemplo)

Otras estructuras de partición

Los árboles BSP dividen una región del espacio en dos subregiones en cada nodo. Estos están relacionados con los árboles cuaternarios y los árboles octales, que dividen cada región en cuatro u ocho subregiones respectivamente.
Tabla de relaciones

Nombre
p
s
Partición binaria
1
2
Partición cuaternaria
2
4
Partición octal
3
8


donde p es el número de planos empleados para dividir, y s el número de regiones obtenidas.
Tabla de comparaciones

Nombre
Voxel
Octree
BSP
CSG
Exactitud
No
No
Poca
Poca
Concisa
No
No
No
Si
Invariante afin
No
No
Si
Si
Fácil adquisición
Poca
Poca
No
Poca
Validación garantizada
Si
Si
Si
No
Operaciones booleanas eficientes
Si
Si
Si
No
Visualización eficiente
No
No
Si
No


Los árboles BSP pueden ser usados en espacios con cualquier número de dimensiones, pero los cuaternarios y los octales son más útiles en la división de espacios de 2 y 3 dimensiones respectivamente. Otro tipo de árbol que es como un árbol cuaternario u octal, pero que es útil en cualquier número de dimensiones, es el árbol kd.