El Maravilloso Mundo De Las Splines

[CoLSoN2]

 Primero un aclaramiento sobre el proyecto para disipar dudas y posibles sugerencias que estarían fuera de lugar:

@ZaelsiuS: sí, es un juego "tipo Zuma", por lo tanto 2D. Como editor usoInkScape, un editor de gráficos vectoriales de toda la vida, con lo que tengo la vida resuelta en ese aspecto. Exporto a SVG y luego con un programita simplemente "limpio" ese SVG de basura para que pese menos el fichero.

En cuanto a la solución nº 2 que comentas, ZaelsiuS, creo que te refieres al caso de que tenga un camino hecho de varios splines, y que en cada spline vaya a diferente velocidad porque son de distinta longitud, etc. Esto es cierto, pero ya lo he solucionado, basta con saber la longitud de cada spline. El problema que tengo ahora es que dentro de cada spline, tampoco va a la misma velocidad, porque parece que el coeficiente [0.0,1.0] no sólo se refiere a la longitud del spline, que sería lo ideal, sino que tiene en cuenta las tangentes, y si yo tengo un arco perfectamente simétrico, en el que el punto inicial tiene como punto de control él mismo (que es igual, vaya), y el que "crea" el arco es el punto de control del punto final, que está a tomar por culo de éste, en este caso las "cosas" que van por el spline a velocidad constante (incrementanto el coeficiente [0.0,1.0] siempre por un valor, por ejempl 0.01) irán más rápidas en la segunda mitad que en la primera. No sé si me explico con claridad.

En cuanto a la primera solución que das, no sé si podría servir.

@[Vil]:

Conseguí algo aproximativo con una funcion que lo hacia a "ojo". Iba probando valores entre 0 y 1 (no recuerdo con que precision, si 0.01 o cuanto sería) y midiendo la distancia real que me daba (en pixels) hasta llegar a la mas aproximada a la que quería.

Pues curiosamente el tío que ha hecho el Atlantis lo ha hecho así, pero como dices, preferiría una solución más elegante.

Por lo general parece que cada persona se lo cuece a su manera. Beetle Bomp lo hace dividiendo el spline en puntos, directamente. Es decir, que sólo utiliza splines a la hora de crear el nivel, pero a la hora de usarlas en el juego son todo puntos, aunque desconozco la resolución de estos, pero creo que sí están a la misma distancia uno de su antecesor. En este thread de los foros de desarrollo de PopCap, el programador del Zuma ('ace' en el thread) explica cómo lo hizo él, que es como yo pretendo, pero no me entero de nada de lo que dice XD

[Zaelsius]

 En cuanto lo tengas, tardas en mandar un COTW xD

[Ray]

 Si no he entendido mal, el problema está en que la distancia de los puntos que describen las splines es menor cuanto mas pronunciada es la curva en la que se encuentra, y en las zonas mas rectas sucede todo lo contrario, la distancia aumenta, con lo que al visualizar la animación da la sensación de cambiar de velocidad constantemente.

Entonces supongo que la solución está en recolocar dichos puntos para que queden todos a la misma distancia unos detras de otros, siguiendo siempre la trayectoria de la curva, me he decidido a intentar hacerlo y me funciona perfecto, las posiciones y las distancias entre ellos quedan exactas, por lo menos en las pruebas que he hecho con una curva Bezier, aunque estoy casi convencido de que el procedimiento es totalmente independiente del tipo de curva.

Es una función que acepta un array de puntos 2D de entrada que describen un recorrido o curva, otro que devuelve los mismos puntos pero ya separados a la misma distancia unos de otros, por ultimo se acepta como parámetro el número de puntos a calcular. No entraré en mas detalles de momento del procedimiento que he usado a menos que a Colson o a otro le interese, porque es algo largo y complicado de explicar.

Código [Seleccionar] Expand


struct PUNTO { float x, y;};

void RecolocarPuntos(PUNTO PuntosOrig[], PUNTO PuntosDest[], int NumPuntos)
{
int NumLineas=NumPuntos-1;
float *DistAbsoluta= new float[NumLineas];
float AcumDist=0;

for (int n=0;n<NumLineas;n++)
   {
   AcumDist+=sqrt( (PuntosOrig[n+1].x-PuntosOrig[n].x) * (PuntosOrig[n+1].x-PuntosOrig[n].x) +
                   (PuntosOrig[n+1].y-PuntosOrig[n].y) * (PuntosOrig[n+1].y-PuntosOrig[n].y));
   DistAbsoluta[n]=AcumDist;
   }
   
float DistMedia=AcumDist/NumLineas;

PuntosDest[0]=PuntosOrig[0];
PuntosDest[NumPuntos-1]=PuntosOrig[NumPuntos-1];

float DifDistancia;
for (int n=1;n<NumLineas;n++)
   {
   int pRef=NumPuntos-1;
   while ( (DifDistancia = DistMedia * n - DistAbsoluta[pRef-1]) < 0 && pRef>0)
       pRef--;
   float angulo = atan2( PuntosOrig[pRef+1].y - PuntosOrig[pRef].y,  
           PuntosOrig[pRef+1].x - PuntosOrig[pRef].x );
   PuntosDest[n].x=PuntosOrig[pRef].x + cos(angulo) * DifDistancia;          
   PuntosDest[n].y=PuntosOrig[pRef].y + sin(angulo) * DifDistancia;
   }

delete[] DistAbsoluta;
}


Aquí un ejemplo de utilización con una típica curva Bezier.

Código [Seleccionar] Expand



...
PUNTO PuntosOrig[11]={-50,0, -47.2,6.3,  -39.7,8.5, -28.3,7.6, -14.8,4.4, 0,0,
              14.8,-4.4,  28.3,-7.6,  39.7,-8.5,  47.2,-6.3, 50,0};

PUNTO PuntosDest[11];

RecolocarPuntos(PuntosOrig, PuntosDest, 11);
...



[CoLSoN2]

 No entiendo bien lo que estás haciendo. Los datos de entrada de tu algoritmo serían también los puntos de control o sólo los que pasan por la curva (el origen y fin de cada curva). Como dices, la deformación de la "velocidad" la producen las tangentes, los puntos de control, y no la distancia entre el origen y el fin, por lo que no creo que solucione nada.

De todos modos, a falta de una solución elegante (si lo que dices acaba siendo útil seguramente la utilice) he obtado por hacer como en Beetle Bomp y directamente dividir el spline en N segmentos rectos, que me facilita mucho todo, y realmente no necesito una suavidad extrema. Teniendo en cuenta que la pantalla será de 800x600 y que un camino que recorra la pantalla puede estar compuesto de 3 o 4 splines, me da unos 350 de media de segmentos por spline. Si a los 800px de ancho le añadimos unas curvas, subidas y bajadas, redondeando a 1500px nos da unos 4px por segmento, tampoco está mal, teniendo en cuenta que no habrá curvas muy pronunciadas. En todo caso siempre puedo incrementar la resolución de la subdivisión.

[Ray]

 Los puntos a trasformar en mi algoritmo son una secuencia de puntos que describen una curva, o un conjunto indeterminado de curvas y rectas (un camino).

Cuando dibujas curvas lo que te queda al final son los puntos que la describen, a mayor número de estos mayor precisión. En mi opinión quizas sea mejor quedarse solo con esos puntos (Segun cuentas asi lo hace Beetle Bomp) en lugar de los parámetros de las curvas o los puntos de control que pueden liar o complicar mucho el desarrollo del programa.

Mi algoritmo simplemente soluciona el problema de la distancia entre puntos que produce el defecto en la animación, En el ejemplo que he puesto se convierte una curva Bézier descrita por 11 puntos (logicamente en la zona más recta de la curva estan mas alejados unos de otros) en otra similar pero con los puntos equidistantes unos detras de otros.

De todas formas no he probado la función lo suficiente como para garantizar que no este exenta de errores, ni está optimizada, y no se si habrá otro codigo mejor por ahí. Estaría bién que la peña lo probase a ver que le sale.  Solo hay que pasarle a la función los puntos de un camino, y recuperar los puntos convertidos, después dibujarlos trazando rectas de cada array de puntos con diferente color para comprobar la diferencia.

Un saludo.

[CoLSoN2]

 Pero si eso es lo que hace tu algoritmo, no sirve para curvas bezier (que están compuestas por dos puntos que marcan su origen y fin, y sí pertenecen a la curva; y otros dos de control que determinan la forma de ésta), porque si mueves el origen y el fin, que según tú es lo único que forma el camino, los puntos de control quedan en el mismo sitio y la curva cambia de forma. Quizá lo que propones serviría para las Catmull-rom, que cómo dice Ithaqua:
"Catmull-rom: Sirven para interpolar un camino a través de una serie de puntos sin más"

Ya he implementado la subdivisión del conjunto de beziers en un conjunto de segmentos rectos sin más y la verdad es que va de lujo, así que me quedaré con este método.  

[Ray]

 La verdad es que es lioso el tema, te digo como lo he hecho.

He creado una curva Bezier con OpenGL, a la cual le he pasado los puntos de control, y me ha devuelto 11 puntos para dibujarla (son 11 como podría haber solicitado 100.000), estos puntos vistos en la pantalla por las zonas mas curvas tienden a agruparse para definir bien la curva, y a alejarse unos de otros en las zonas mas rectas porque son necesarios menos puntos para describir esa zona.

He creado el algoritmo para que se redistribuyan esos puntos a lo largo de la trayectoria de toda la curva y que produzca una animación suave.

El algoritmo acepta cualquier numero de puntos que sigan la ruta de un camino. bien sea una curva bezier o un montón de curvas y rectas hechas de cualquier manera enlazadas unas con otras. De manera que se distribuyen todos los puntos unos detrás de otros a una distancia igual a la suma de todas las distancias dividido entre el numero total de puntos menos 1.

Yo lo que hago es obtener todos los puntos que me de la gana de las curvas Bezier o de otro tipo de curvas, y luego me despreocupo de sus puntos de control que tal vez sea muy lioso trabajar con ellos (sobre todo para los que no controlamos de mates). Pero si ya consigues hacerlo de otra manera pues perfecto.

Suerte con el proyecto y hasta otra.