Flood Fill en ensamblador.
Moderador: Sir Cilve Sinclair
- na_th_an
- Nonamed
- Mensajes: 1889
- Registrado: Lun May 07, 2007 10:16 am
- Ubicación: Andalucía
Flood Fill en ensamblador.
¿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
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
- mcleod_ideafix
- Johnny Jones
- Mensajes: 3985
- Registrado: Vie Sep 21, 2007 1:26 am
- Ubicación: Jerez de la Frontera
- Contactar:
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í:
Dicha figura ha de dibujarse así
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
Lo mismo para las siguientes 5 lineas:
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í:
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í:
- 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
- mcleod_ideafix
- Johnny Jones
- Mensajes: 3985
- Registrado: Vie Sep 21, 2007 1:26 am
- Ubicación: Jerez de la Frontera
- Contactar:
OJO! porque por lo comentado anteriormente, este algoritmo fallaría con una figura como ésta:
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
*
* *
* *
* *
* *
* *
* *
* *
* *
* *
*
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
-
- Nonamed
- Mensajes: 1067
- Registrado: Lun May 07, 2007 10:06 pm
- na_th_an
- Nonamed
- Mensajes: 1889
- Registrado: Lun May 07, 2007 10:16 am
- Ubicación: Andalucía
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:
@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 ). 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
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:
@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 ). 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
-
- Nonamed
- Mensajes: 1067
- Registrado: Lun May 07, 2007 10:06 pm
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
Gandulf
- na_th_an
- Nonamed
- Mensajes: 1889
- Registrado: Lun May 07, 2007 10:16 am
- Ubicación: Andalucía
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
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
- na_th_an
- Nonamed
- Mensajes: 1889
- Registrado: Lun May 07, 2007 10:16 am
- Ubicación: Andalucía
-
- Nonamed
- Mensajes: 1067
- Registrado: Lun May 07, 2007 10:06 pm
-
- Nonamed
- Mensajes: 1221
- Registrado: Mar Abr 17, 2007 12:35 pm
- Ubicación: Valencia
- Contactar:
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
Me encanta
NoP / Compiler
- na_th_an
- Nonamed
- Mensajes: 1889
- Registrado: Lun May 07, 2007 10:16 am
- Ubicación: Andalucía
El algoritmo es una chorrez, no tiene nada. Todo está en splib2/graphics.h:
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
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
-
- Nonamed
- Mensajes: 1067
- Registrado: Lun May 07, 2007 10:06 pm
- na_th_an
- Nonamed
- Mensajes: 1889
- Registrado: Lun May 07, 2007 10:16 am
- Ubicación: Andalucía
-
- Nonamed
- Mensajes: 1067
- Registrado: Lun May 07, 2007 10:06 pm
¿Quién está conectado?
Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 11 invitados