Julio / Revolution Ellipses Rápidas. Artículo aparecido en la Rom 3. escrito por Touchstone de Essence. y traducido por Julio'Revolution. Sino entendeis algo puede que sea por la tradución, si os interesa podeis solicitar el original. Todos habéis visto la demo de la party 4 de Andromeda. Uno de los efectos era una bola luminosa como las de las discotecas. Todo el efecto estaba construido a base de ellipses. Otro ejemplo del poder de las ellipses se puede encontrar en el juego Estatics de PC. Todas las figuras están hechas con ellipses, y todo parece muy real. Como puees ver, las ellipses son muy útiles y por eso he decidido hacer mi propia rutina de ellipses normales y ellipses giratorias, ahora os mostrare como funciona basicamente. Circulos: El algoritmo de Bresenham. Jack E. Bresenham (ver[1]) desde 1977, describió un algoritmo muy bueno para generar circulos, basado en la selección de una malla de puntos. Este algoritmo está basado en una fórmula simple: X2 +Y2=R2 Dónde X es la coordinada X, Y es la coordenada Y y R es el radio del círculo. Hay algunas publicaciones que explican el funcionamiento de esta fórmula, pero si la simplificas un poco y la construyes con un error constante llamado Delta, acabarás con algo similar a lo siguiente: 010 xo=320: yo=128: ra=100 020 xp=0: yp=ra: co=ra-1: 030 While xp=>yp 040 if co<0 then 050 yp=yp-1 060 co=co+yp+yp 070 End If 080 Pset (xo-xp*2,yo-yp) 090 Pset (xo+xp*2,yo-yp) 100 Pset (xo+xp*2,yo+yp) 110 Pset (xo-xp*2,yo+yp) 120 Pset (xo-yp*2,yo-xp) 130 Pset (xo+yp*2,yo-xp) 140 Pset (xo+yp*2,yo+xp) 150 Pset (xo-yp*2,yo+xp) 160 co = co-xp-xp-1 170 xp=xp+1 180 wend Como puedes ver, todo el código trabaja con enteros, lo que hace la traducción al ensamblador muy fácil. El algoritmo de Bresenham sólo necesita 8 cálculos en este programa de basic, por lo que es muy rápido. Sólo usa sumas y restas. La velocidad del algoritmo viene de que sólo calcula 1/8 del círculo, y dibuja los otros puntos mediante el truco del espejo. Algunos codes conocen este algoritomo, y lo utilizan a menudo. Ellipses: La nueva generación. Las primeras rutinas de ellipses se basaban en estrechar o anchar los datos calculados. Esto es muy lento y necesitas una rutina real de ellipses que sea muy rápida. Algunas rutina de algunos libros [2] nos ayudaron un montón a los coders y nacieron los efectos de ellipses. Algunos todavia pueden recordar los efectos del 92-93. El concepto básico es muy simple, porque ahora se calcula un cuarto de la ellipse (lo que retrasa el algoritmo pero ahora es matemáticamente correcto). Las sumandos (codigo basic de antes: co, xp y yp) se estrechaban sólo una vez y el codigo completo se volvía a organizar. La siguiente rutina de ellipses está basada en el algoritmo de Van Aken [3]. 010 xo=320: yo=128: a=200: b=50 020 x=a: y=0: asquare=a*a 025 bsquare=b*b 030 a22=asquare+asquare 035 b22=bsquare+bsquare 040 xslope=b22*a: yslope=0 050 fmid=-bsquare*a+asquare 060 While xslope>yslope 070 pset (xo+x,yo+y) 080 pset (xo-x,yo+y) 090 pset (xo+x,yo-y) 100 pset (xo-x,yo-y)T12 110 y=y+1 120 yslope=yslope+a22 130 if fmid=>0 then 140 x=x-1 150 xslope=xslope-b22 160 fmid=fmid-xslope 170 end if 180 fmid=fmid+yslope+asquare 190 WendT12 200 fmid=fmid-(yslope+xslope)/ 2+b22-a22 210 while x=>0 220 Pset (xo+x,yo+y) 230 Pset (xo-x,yo+y) 240 Pset (xo+x,yo-y) 250 Pset (xo-x,yo-y) 260 x=x-1 270 xslope=xslope-b22 280 if fmid<=0 then 290 y=y+1 300 yslope=yslope+a22 310 fmid=fmid+yslope 320 End if 330 fmid=fmid-xslope+bsquare 340 WendT12 *** La linea 200 original era: 200 fmid = fmid - (yslope + xslope)/2+b2-a2. Yo creo que esta mal, y en el código anterior ya esta corregida, pero por si acaso, pongo también la orginal. Como puedes ver es un poco más complicado que el generador de círculos de Bresenham, la razón es que lo primero se calcula la mitad de la ellipse, esto divide el programa en dos partes. Este método no es exactamente el mismo que en [2] porque había calculos con valores que no eran enteros. Esta versión trabaja sólo con valores enteros!!!. De nuevo no voy a explicar los detalles del funcionamiento de este algoritmo, porque creo que los libros [2] o [3] lo harán mucho mejor (*** Si hubiera por aqui....). Ellipses rotatorias - El máximo. Aparte de Nexus 7, se pueden encontrar en una vieja demo de Thomas Lansburg, y en el reciente juego Estatics. Hay dos métodos diferentes de hacerlo: El primer método es hacer un nuevo código del algoritmo. Hay algunas desventajas, la primera es la velocidad, porque este lo dividirá de nuevo en dos, porque el truco del espejo sólo es posible de un eje. La segunda es la complejidad de la rutina, por que el algoritmo se dividirá de nuevo. Pero la gran ventaja es la precisión. Si quieres más detalles sobre este método, contacta conmigo, y te enviaré mi rutina. Desafortunadamente, es demasiado largo escribirlo en este artículo. Creo que uno de los principales fastores de las demos es la velocidad, para lo que el segundo método es más adecuado. Es muy simple y sólo unos ciclos más lento que un algoritmo ordinario de ellipses. Pero hay una gran desventaja, la imprecisión. La rutina tiene un factor de precisión muy bajo!. El problema no aparecer cuando la ellipse sólo rote por un denominador pequeño y en todos y cada uno de los frames, porque la baja precisión es dificil de ver en una animación!. El sistema es simple porque el algoritmo normal de linea de Bresenham, se une al algoritmo de la ellipse. En la image (1), se puede ver porque no se puede generar por una rutina normal de ellipses y una de lineas, por el mencionado error de precisión. El radio 1 (Altura) y el 2 (Anchura) no son el mismo!, La ellipse rotatoria es mucho más alta, pero más pequeña que la primera ellipse normal. Por lo que hay que calcular una nueva anchura y altura, @jul080 influenciadas por el ángulo alfa. La imgen (2) muestra la relación entre estos valores. Se necesitan tres fórmulas, para la nueva anchura, la nueva altura y el punto de comienzo para x, pero creo que cualquier coder será capaz de saber como hacerlo. Con estos valores, se puede calcular una rutina de ellipses muy, muy rápida. Tu generador de ellipses se podría construir para hacer algo como esos 6 circulos que estamos hasta los cojones de ver en el A500. El truco es dibujar sólo los círculos en el bitplane pointer y no en el bitplane proper, y cambiar sólo los registros del soft scroll. Si lo haces así, el algoritmo es mucho más sencillo, porque sólo debes corregir los bitplanes pointer y los registros del soft scroll, mediante unh generador de lineas, el problema es que sólo puedes genrar dos círculos, porque sólo hay dos registros de soft por linea, por supuesto hay otra manera de superar este límite... El algoritmo de las ellipses rotatorias no se publica aqui en su integridad, porque debe ser trabajo del coder convertirlo de Basic a esnamblador. La información aqui dada es más que suficiente para hacer un generador de ellipses. Referencias: [1]: J. E. Bresenham "A linear Algorithm for Incremental Digital display of Circular Arcs:. Communications of the ACM. [2]: M. R. Kappel, " An ellipse drawing algorithm for raster display" [3]: J. R. Van Aken, "An eficient ellipse drawing algorithm", Computer graph.