Flood Fill en ensamblador.

Todo sobre la creación, diseño y programación de nuevo software para
nuestro Spectrum

Moderador: Sir Cilve Sinclair

Avatar de Usuario
na_th_an
Nonamed
Mensajes: 1889
Registrado: Lun May 07, 2007 10:16 am
Ubicación: Andalucía

Flood Fill en ensamblador.

Mensaje por na_th_an » Mié Oct 17, 2007 4:23 pm

¿Alguien conoce una buena rutina de relleno en ensamblador, que no pille mucha pila? He mirado en el WOS y he encontrado dos, pero una no rellena las figuras completas si los polígonos son convexos y la otra pinta lineas raras donde le da la gana.

Busco algo sencillo que pueda colocar al final de la memoria y llamar desde BASIC.

Es que estoy restaurando un viejo proyecto mío. Uno de los bloques de la cinta era precísamente un programa en MC que hacía flood fill y no he podido recuperarlo. Y tampoco recuerdo de dónde leches lo saqué en tiempos :lol:

Avatar de Usuario
mcleod_ideafix
Johnny Jones
Mensajes: 3985
Registrado: Vie Sep 21, 2007 1:26 am
Ubicación: Jerez de la Frontera
Contactar:

Mensaje por mcleod_ideafix » Mié Oct 17, 2007 10:39 pm

El blitter del Commodore Amiga usa un algoritmo muy sencillo para hacer fill por hardware, que funciona con polígonos concavos y convexos. Su base topológica es la de que si tenemos una figura cerrada, todo lo compleja que queramos, pero que no se corte a sí misma, y pintamos dos puntos y trazamos el segmento de recta entre esos dos puntos se cumple siempre que:
- La recta corta a la figura un número par de veces (0,2,4...): entonces los dos puntos o bien están ambos dentro de la figura, o bien fuera.
- La recta corta a la figura en un número impar de puntos (1,3,5...): entonces los dos puntos están, uno fuera y el otro dentro de la figura.

La cosa va más o menos así:
- Encierra la figura a la que le vas a hacer el flood fill en un rectángulo imaginario (es decir, busca un rectángulo que circunscriba a tu figura). Dicho rectángulo no debe tocar los bordes de la figura.
- Escanea cada linea horizontal de ese rectángulo y mantén una variable booleana que determine si el pixel que se está escaneando debe rellenarse o no. Esa variable al principio de cada línea estará a 0 (no rellenar). Cada vez que te encuentres con un punto iluminado (que pertenezca al borde de la figura a rellenar) basculas el valor de esa variable (si valía 0, ahora vale 1, y si valía 1, ahora vale 0).

Para que la cosa funcione, en cada raster (linea horizontal) sólo puede haber un pixel que pertenezca al borde de tu figura.
Ejemplo: si quieres rellenar una figura tal que así:

Código: Seleccionar todo

                ******************
            ****                  *
         ***                      *
       **                      ***
      *                      **
     *                      *
     *                 **  *
      *              **  * *
       **           *     *
         *******   *
                ***


Dicha figura ha de dibujarse así

Código: Seleccionar todo

                *                *
            *                     *
         *                        *
       *                         *
      *                       *
     *                      *
     *                 **  *
      *               *  * *
       *            *     **
         *         *
                * *


Para la primera linea (raster), el algoritmo comienza con la variable a 0, así que no rellena ningún pixel hasta que se encuentra el primero. En ese momento, la variable cambia a 1 y sigue el escaneo de píxeles: todos los que se encuentre apagados, los enciende, hasta que vuelve a encontrarse a otro que ya estaba encendido. En ese momento, la variable vuelve a ser 0 y el algoritmo deja de pintar. Así hasta que termina la linea

Código: Seleccionar todo

                ******************
            *                     *
         *                        *


Lo mismo para las siguientes 5 lineas:

Código: Seleccionar todo

                ******************
            ***********************
         **************************
       ***************************
      *************************
     ************************
     *                 **  *
      *               *  * *
       *            *     **
         *         *
                * *


La sexta linea es donde la figura tiene parte cóncava. Aún así, el algoritmo funciona:
- Como las otras veces, al llegar al primer punto, pasa de no pintar a pintar.
- Llega al segundo punto, así que para de pintar.
- Llega al tecer punto (que está pegado al segundo), así que vuelve otra vez a pintar
- Llega al cuarto punto, y para de pintar.
Si te fijas, en cada linea horizontal de la figura "preparada" (la segunda) siempre hay un número par de puntos

La línea quedaría así:

Código: Seleccionar todo

                ******************
            ***********************
         **************************
       ***************************
      *************************
     ************************
     ***********************
      *               *  * *
       *            *     **
         *         *
                * *


La siguiente quedaría igual, así como la siguiente. Fíjate que en esta última se ha añadido un pixel extra que no estaba en la original (la primera). Esto es para que se siga cumpliendo lo del número par de puntos en cada línea (ráster).

Al final, queda así:

Código: Seleccionar todo

                ******************
            ***********************
         **************************
       ***************************
      *************************
     ************************
     ***********************
      *****************  ***
       **************     **
         ***********
                ***
Web: ZX Projects | Twitter: @zxprojects

Avatar de Usuario
mcleod_ideafix
Johnny Jones
Mensajes: 3985
Registrado: Vie Sep 21, 2007 1:26 am
Ubicación: Jerez de la Frontera
Contactar:

Mensaje por mcleod_ideafix » Mié Oct 17, 2007 11:08 pm

OJO! porque por lo comentado anteriormente, este algoritmo fallaría con una figura como ésta:

Código: Seleccionar todo

      *
     * *
    *   *
   *     *
  *       *
 *         *
  *       *
   *     *
    *   *
     * *
      *


En este caso, habría que "rematar" los bordes de alguna forma para que se siguiera cumpliendo la regla de un número par de píxeles en cada ráster.

Código: Seleccionar todo

      **
     *  *
    *    *
   *      *
  *        *
 *          *
  *        *
   *      *
    *    *
     *  *
      **
Web: ZX Projects | Twitter: @zxprojects

Gandulf
Nonamed
Mensajes: 1067
Registrado: Lun May 07, 2007 10:06 pm

Mensaje por Gandulf » Jue Oct 18, 2007 9:24 am

Hombre, si no se encuentra ninguna hecha podemos hacer una, pero yo creo que las tiene que haber hechas. Ayer miré en la MH pero estaba caído el sitio microhobby.org, a ver si puede volver a echar un ojo hoy.
Un saludo,

Gandulf

Avatar de Usuario
na_th_an
Nonamed
Mensajes: 1889
Registrado: Lun May 07, 2007 10:16 am
Ubicación: Andalucía

Mensaje por na_th_an » Jue Oct 18, 2007 11:21 am

No os preocupéis. He seguido el consejo que me ha dado Alvin Albrecht y me he creado un pequeño módulo en C que hace flood-fill ocupando sólo 900 bytes y usando patrones UDG. Ya de paso he codificado todo un intérprete de gráficos vectoriales. En total ocupa 1.8Kb que puede parecer mucho pero que a mí me sirve perfectamente.

La cosa es que había conseguido medio-recuperar un viejo juego mío que usaba un paquete de rutinas que saqué de dios sabe donde para pintar gráficos hechos con lineas y rellenos en pantalla. La cosa es que la zona de la cinta donde estaba este bloque en CM está arrugada y se ha perdido casi todo el sonido, por lo que no dispongo de este bloque. Necesitaba un sustituto rápido, y ayer lo hice en 10 minutos en C con el pfill de la splib2 y las rutinas de trazado de lineas de z88dk y me viene al pelo. Ya lo veréis publicado en mi blog dentro de poco :)

Un adelanto:

Imagen

@mcleod_ideafix: Ése algoritmo lo conocía, de hecho tuvimos que implementarlo en una asignatura de la carrera (Técnicas de Representación Gráfica por Computador :lol:). Mi problema es que mi nivel de ensamblador es ABC y si me pongo a hacerlo yo estoy seguro de que ocupa 10K y tarda 10 minutos por relleno :lol:

Gandulf
Nonamed
Mensajes: 1067
Registrado: Lun May 07, 2007 10:06 pm

Mensaje por Gandulf » Jue Oct 18, 2007 11:32 am

Casi 1 K para una sóla rutina de relleno es muchísimo, pero si te vale, mejor que mejor. Siempre es mejor usar tu propio código que el de terceros, al menos es lo que pienso yo. Lo digo porque 1K son muchísimas líneas de código ASM. Si me mandas o pones la rutina en C te hago la versión ASM de lo mismo y seguramente ocupará bastante menos e irá más rápido (si es sin prisa, que ando un poco liado).
Un saludo,

Gandulf

Avatar de Usuario
na_th_an
Nonamed
Mensajes: 1889
Registrado: Lun May 07, 2007 10:16 am
Ubicación: Andalucía

Mensaje por na_th_an » Jue Oct 18, 2007 12:09 pm

La rutina en C es lo de menos, ya que usa el fill y los trazadores de lineas de splib2 y z88dk, respectivamente. Ahí está el grueso del código, ya que se incluyen rutinas demasiado genéricas que ocupan mucho. Lo que es el código C son apenas 10 lineas que se encargan de ir leyendo la memoria, interpretando los comandos y llamando al trazador y al rellenador.

El rellenador funciona de muerte ya que ocupa muy poca pila (esto es, además, configurable: cuanta más memoria le des menos tarda) y puedes usar UDG para dar tramas. Los trazadores de lineas son muy rápidos. Como esto es para dar soporte a un programa BASIC que hice hace quince años, tampoco me importa que ocupe 1.8Kb porque hay sitio de sobra.

La cosa es que ahora estoy básicamente sin tiempo, y de emplearlo en desarrollo prefiero emplearlo en los proyectos de CEZGS que tengo abiertos. No quiería emplear más que un rato con esto, que a fin de cuentas es un proyecto propio para resucitar un viejo juego al que probablemente nadie jugará más de una vez. Quizá de estar más libre me hubiera puesto a hacerlo yo en condiciones, sólo por frikismo, pero no es el caso :(

Gandulf
Nonamed
Mensajes: 1067
Registrado: Lun May 07, 2007 10:06 pm

Mensaje por Gandulf » Jue Oct 18, 2007 12:12 pm

ok. ¿Es una conversacional?
Un saludo,

Gandulf

Avatar de Usuario
na_th_an
Nonamed
Mensajes: 1889
Registrado: Lun May 07, 2007 10:16 am
Ubicación: Andalucía

Mensaje por na_th_an » Jue Oct 18, 2007 12:13 pm

Más o menos. Sí, es una conversacional, pero no "una conversacional de verdad" :lol: Sé que lees mi blog así que creo que sabes a qué me refiero :D

Gandulf
Nonamed
Mensajes: 1067
Registrado: Lun May 07, 2007 10:06 pm

Mensaje por Gandulf » Jue Oct 18, 2007 12:19 pm

Pues la verdad es que lo leía más antes que ahora, ahora sólo echo un vistazo rápido a los juegos que pones, si veo noticias nuevas. No es que haya dejado de interesarne el blog, pero prefiero leerlo en modo "alta impedancia"
Un saludo,

Gandulf

sromero
Nonamed
Mensajes: 1221
Registrado: Mar Abr 17, 2007 12:35 pm
Ubicación: Valencia
Contactar:

Mensaje por sromero » Jue Oct 18, 2007 12:21 pm

na_th_an escribió:No os preocupéis. He seguido el consejo que me ha dado Alvin Albrecht y me he creado un pequeño módulo en C que hace flood-fill ocupando sólo 900 bytes y usando patrones UDG. Ya de paso he codificado todo un intérprete de gráficos vectoriales. En total ocupa 1.8Kb que puede parecer mucho pero que a mí me sirve perfectamente.


Si lo cuelgas en algún sitio, me gustaría verlo. Y también el algoritmo que hayas seguido, me gustaría programarlo en ASM sin usar SPLIB, por guarrear un rato.

O sea, yo me pongo a hacer todo, menos acabar los juegos que tengo abiertos X-D

Imagen


Me encanta :-)
NoP / Compiler

Avatar de Usuario
na_th_an
Nonamed
Mensajes: 1889
Registrado: Lun May 07, 2007 10:16 am
Ubicación: Andalucía

Mensaje por na_th_an » Jue Oct 18, 2007 12:30 pm

El algoritmo es una chorrez, no tiene nada. Todo está en splib2/graphics.h:

Código: Seleccionar todo

   while (!terminado) {
      
      cmd = (*address_ptr);
      address_ptr++;
      x = (*address_ptr);
      address_ptr++;
      y = (*address_ptr);
      address_ptr++;
      ex = (*address_ptr);
      address_ptr++;
      
      switch (cmd) {
         case 0:
            d_x = x;
            d_y = y;
            plot (x, y);
            break;
         case 1:
            draw (d_x, d_y, x, y);
            d_x = x;
            d_y = y;
            break;
         case 2:
            sp_PFill(x, y, patterns + (ex << 3), 300);   
            break;
         case 3:
            terminado = 1;   
            break;
      }
   }


Faltan las definiciones de los UDG para los rellenos. De todos modos en cuanto tenga esto listo lo colgaré todo de mi blog, hasta el módulo este por separado con un pequeño editor cutre por si la gente lo quiere usar para hacerse sus aventurillas :)

Gandulf
Nonamed
Mensajes: 1067
Registrado: Lun May 07, 2007 10:06 pm

Mensaje por Gandulf » Jue Oct 18, 2007 12:36 pm

[OffTopic mayúsculo]
Cuidado no te vaya a venir un "ingeniero de software" o "consultor" a decir que los Breaks son instrucción indeseada :lol: :lol: :lol: , a mi particularmente me encanta y hago bastante uso de ella
[/OffTopic mayúsculo]
Un saludo,

Gandulf

Avatar de Usuario
na_th_an
Nonamed
Mensajes: 1889
Registrado: Lun May 07, 2007 10:16 am
Ubicación: Andalucía

Mensaje por na_th_an » Jue Oct 18, 2007 12:42 pm

Goto y Break han de ser usados hasta la saciedad por quien sepa usarlas. Pero efectivamente son un peligro para los novatillos espagueteros.

Me encantaba un artículo que se llamaba "GOTO considered harmful... considered harmful" en respuesta al original de Dijkstra :lol:

Gandulf
Nonamed
Mensajes: 1067
Registrado: Lun May 07, 2007 10:06 pm

Mensaje por Gandulf » Jue Oct 18, 2007 12:47 pm

Yo el GOTO la verdad es que no lo he vuelto a usar porque para cosas no "serias" uso ASM, y ahí tengo mis estupendos saltos, que no hay otra cosa. Posiblemente si hiciera en C otro tipo de cosas donde necesitara velocidad a saco sí los empleara. Pero los Breaks los uso cada 2x3.
Un saludo,

Gandulf

Responder

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 11 invitados