El Maravilloso Mundo De Las Splines

[CoLSoN2]

 Tengo entre manos un proyecto y necesito crear caminos a base de splines para que unos objetos se muevan por ellos, pero tengo algunas dudas.

- He bajado el código de las libs de Stravaganza que Ithaqua posteó hace un tiempo y no me aclaro mucho. ¿Cuál es la diferencia entre splines Bézier, Catmull-Rom, Hermite y TCB? ¿Cuál sería la más útil para mi caso?

- También he estado mirando este código (final de la página) y parece muy sencillo, sólo haría falta encapsularlo todo en una clase, supongo.

- ¿Existe algún editor de splines? Me refiero a una herramienta para poder editarlos visualmente y obtener luego los valores de cada punto de cada segmento del camino creado (al estilo del editor de béziers de Photoshop o Flash). Lo ideal sería especificar un tamaño en pixeles para el área útil, asignarle una imagen de fondo, crear el camino y exportarlo a ASCII.

Cualquier otra idea o recomendación será bien recibida..;)

Un saludo

[Sacrifai]

 En allegro viene un ejemplo de como seguir un camino con splines. A lo mejor te sirve de algo.

[josepzinkjn]

 He visto algun ejemplo de Flash, demostrando la capacidad de creacion dinamica de Splines, que puede servirte (si es que los valores son compatibles..)

Si lo veo te digo

[gdl]

 Hace bastante tiempo que estudié eso de los splines y no puedo asegurarte corrección al 100%, pero las diferencias entre los distintos tipos de splines que conozco son:

- Bézier: Es la básica. Tiene el problema de que al mover un punto te afecta un buen tramo de la curva.
- Hermite: Cuando se quiere especificar la derivada en algunos puntos.
- C-Spline: Se hace por trozos de polinomio de tercer grado. Hay que resolverlos y puede ser una lata. Te afecta la curva localmente.
- B-Spline: Se compone de una suma de polinomios (con ciertas propiedades) llamados bases y que no hace falta resolver. Creo recordar que una C-Spline se podía reducir a una B-Spline. También afecta localmente.
- NURBS: Extensión de las B-Splines para poder trazar cónicas (círculos, elipses, etc.)

Espero que te sirva de algo.

[ProD]

 Buenas, a ver si puedo ayudar... yo en el trabajo me curré un modelo de tráfico, esto es, cochecitos que van por una trayectoria determinada y se respetan entre si, a la vez que hacen caso de las señales de tráfico. Para que los cochecitos fueran por una determinada trayectoria hacia que siguieran una spline de tipo catmull-rom, usé este tipo de curvas debido a que son bastante sencillas de calcular y a mi entender
generan unas curvas más sueaves que las bezier. Voy a pegar por aquí el código de la clase que tengo para este tipo de clases, espero que os sirva de algo.

Código [Seleccionar] Expand


/***************************************************************************
* Módulo: Spline.h                                                         *
*                                                                   *
* Fichero: () Programa                        (X) Interfaz de Clase        *
*          () Implementación de Clase         () Otros                     *
*                                                                          *
* Autor: GSC                                  *
*                                                                          *
* Fecha: 13 de Enero de 2005                                               *
*                                      *
* Ultima modificación: 18 de Enero de 2005                                 *
*                                                                          *
* Descripción:                                                             *
*               Interfaz de la clase que implementa                        *
*               Splines de tipo Catmull-rom.                               *
*                                                                          *
***************************************************************************/

#ifndef SPLINE_H
#define SPLINE_H


//--------------------------------------------------------------------------
// Declaración de clases
//--------------------------------------------------------------------------

class CSpline
{
private:

 struct SplinePoint
 {
  float x, y, z;     // Coordenadas
  float tx, ty, tz;  // Tangente
 };

 struct SplineSegment
 {
  unsigned int uiIndexPoint1;  // Índice al primer punto del segmento
  unsigned int uiIndexPoint2;  // Índice al segundo punto del segmento
  float        fLength;        // Longitud del segmento
 };

 // Longitud total de la spline
 float m_fTotalLength;  

 // Puntos que componen la curva
 vector<SplinePoint> m_vCurve;
 
 // Segmentos de la curva
 vector<SplineSegment> m_vSegments;

 // VB que almacenará los puntos a pintar de la curva
 CDynamicVB<FVF_PosDiffuse> m_VB;

public:

 CSpline () : m_fTotalLength(0.0f) { }
 // Constructor

 void AddKey (float  x, float  y, float  z,
        float tx, float ty, float tz);
 // Añade un nuevo punto clave (punto + tangente) a la spline.

 void AddSegment (int iIndexPoint1, int iIndexPoint2, float fLength);
 // Añade un nuevo segmento a la spline

 float GetSegmentLength (unsigned int uiSegment) const { assert(uiSegment < m_vSegments.size());
                                return m_vSegments[uiSegment].fLength; }
 // Devuelve la longitud del segmento de la spline pasado por parámetro.

 unsigned int GetNumSplinePoints () const { return m_vCurve.size(); }
 // Devuelve el número de puntos clave que tiene la spline.

 unsigned int GetNumSplineSegments () const { return m_vSegments.size(); }
 // Devuelve el número de segmentos que tiene la spline.

 float GetSplineLength () const { return m_fTotalLength; }
 // Devuelve la longitud total de la spline.

 void CreateResources ();
 // Crea el VB que albergará los vértices que componen la spline.

 void ReleaseResources ();
 // Libera el VB que alberga los vértices que componen la spline.

 D3DXVECTOR3 Evaluate (float& rfDistance, unsigned int& ruiSegment);
 // Devuelve el punto en la spline dado la distancia dentro del segmento
 // y el segmento.

 void Render ();
 // Dibuja la spline.

 void Destroy ();
 // Elimina los recursos adquiridos al crear la spline.
};

#endif  // SPLINE_H


Como podeis ver, una spline se define por un conjuntos de puntos clave. Yo además conservo los segmentos
dados por dos puntos clave y una longitud. De donde saco todos estos datos? pues del 3DStudio Max. en Max el grafista creaba las trayectorias con las propias splines del Max y yo luego mediante un script de max script salvaba la información que necesitaba para luego poder recrear la curva en tiempo real. Bueno a continuación pego el .cpp

Código [Seleccionar] Expand


/***************************************************************************
* Módulo: Spline.cpp                                                       *
*                                                                   *
* Fichero: () Programa                        () Interfaz de Clase         *
*          (X) Implementación de Clase        () Otros                     *
*                                                                          *
* Autor: GSC                                  *
*                                                                          *
* Fecha: 13 de Enero de 2005                                               *
*                                      *
* Ultima modificación: 13 de Enero de 2005                                 *
*                                                                          *
* Descripción:                                                             *
*               Implementación de la clase que implementa                  *
*               Splines.                                                   *
*                                                                          *
***************************************************************************/

#include "../Precompile.h"  // Includes que usa todo el proyecto


//--------------------------------------------------------------------------
// Constantes
//--------------------------------------------------------------------------

const unsigned short BATCH = 200;
const unsigned int MAX_SPLINE_POINTS = 1000;


//--------------------------------------------------------------------------
// Implementación de los métodos públicos
//--------------------------------------------------------------------------

void CSpline::AddKey (float  x, float  y, float  z,
               float tx, float ty, float tz)
{
 SplinePoint Point;
 
 // Punto
 Point.x  =  x;
 Point.y  =  y;
 Point.z  =  z;

 // Tangente
 Point.tx = tx;
 Point.ty = ty;
 Point.tz = tz;

 // Guardamos la nueva clave
 m_vCurve.push_back(Point);
}


void CSpline::AddSegment (int iIndexPoint1, int iIndexPoint2, float fLength)
{
SplineSegment Segment;

// Longitud del segmento
Segment.fLength = fLength;

// Incrementamos la longitud total de la spline
m_fTotalLength += fLength;

// Guardamos los índices a los puntos que pertenece
// este segmento
Segment.uiIndexPoint1 = iIndexPoint1;
Segment.uiIndexPoint2 = iIndexPoint2;

// Guardamos el segmento
m_vSegments.push_back(Segment);
}


void CSpline::CreateResources ()
{
// Creamos el VB
m_VB.Create(CApplication::getDevice(), FVF_POSDIFFUSE, MAX_SPLINE_POINTS);
}


void CSpline::ReleaseResources ()
{
// Liberamos el VB
m_VB.Release();
}


D3DXVECTOR3 CSpline::Evaluate (float& rfDistance, unsigned int& ruiSegment)
{
// Si la distancia es mayor a la del segmento...
// pasamos al siguiente
if (rfDistance > m_vSegments[ruiSegment].fLength)
{
 ruiSegment = (ruiSegment + 1) % m_vSegments.size();
 rfDistance = 0.0f;
}

// Simplificamos indirección
SplineSegment* pCurrentSegment = &m_vSegments[ruiSegment];

// Distancia real en la spline
float fLength = rfDistance / pCurrentSegment->fLength;
 
 // Evaluamos el punto
float t2 = fLength * fLength;
float t3 = t2 * fLength;
   
float h1 =  2.0f * t3 - 3.0f * t2 + 1.0f;
float h2 = -2.0f * t3 + 3.0f * t2;
float h3 =  t3 - 2.0f * t2 + fLength;
float h4 =  t3 - t2;

// Conseguimos los puntos que componen el segmento donde
// estamos evaluando
SplinePoint* pPointOne = &m_vCurve[pCurrentSegment->uiIndexPoint1];
SplinePoint* pPointTwo = &m_vCurve[pCurrentSegment->uiIndexPoint2];

return D3DXVECTOR3(h1 * pPointOne->x + h2 * pPointTwo->x + h3 * pPointOne->tx + h4 * pPointTwo->tx,
          h1 * pPointOne->y + h2 * pPointTwo->y + h3 * pPointOne->ty + h4 * pPointTwo->ty,
          h1 * pPointOne->z + h2 * pPointTwo->z + h3 * pPointOne->tz + h4 * pPointTwo->tz);
}


void CSpline::Render ()
{
assert(m_vCurve.size() >= 2);

// Establecemos render states
SetTextureStageState(0, D3DTSS_COLOROP,   D3DTOP_SELECTARG1);
SetTextureStageState(0, D3DTSS_COLORARG1, D3DTA_DIFFUSE);
SetTextureStageState(0, D3DTSS_ALPHAOP,   D3DTOP_DISABLE);

// Ponemos matriz identidad...
D3DXMATRIX mIdentity;
D3DXMatrixIdentity(&mIdentity);
CApplication::getDevice()->SetTransform(D3DTS_WORLD, &mIdentity);

// Especificamos el tipo de vértice
CApplication::getDevice()->SetVertexShader(FVF_POSDIFFUSE);

// Colocamos los vértices
CApplication::getDevice()->SetStreamSource(0, m_VB.GetVertexBuffer(), sizeof(FVF_PosDiffuse));

// Bloqueamos el VB
unsigned int uiStartVertex;
unsigned int uiLock = BATCH;
FVF_PosDiffuse* pVertex = m_VB.Lock(uiLock, uiStartVertex);
assert(pVertex != NULL);

// Iteradores...
vector<SplinePoint>::iterator PointOne = m_vCurve.begin();
vector<SplinePoint>::iterator PointTwo = m_vCurve.begin() + 1;
unsigned short usPointsCount = 0;

do
{
 for (float t = 0.0f; t < 1.0f; t += 0.001f)
 {
  float t2 = t * t;
  float t3 = t2 * t;
   
  float h1 =  2.0f * t3 - 3.0f * t2 + 1.0f;
  float h2 = -2.0f * t3 + 3.0f * t2;
  float h3 =  t3 - 2.0f * t2 + t;
  float h4 =  t3 - t2;

  pVertex->vPos.x    = h1 * PointOne->x + h2 * PointTwo->x + h3 * PointOne->tx + h4 * PointTwo->tx;
  pVertex->vPos.y    = h1 * PointOne->y + h2 * PointTwo->y + h3 * PointOne->ty + h4 * PointTwo->ty;
  pVertex->vPos.z    = h1 * PointOne->z + h2 * PointTwo->z + h3 * PointOne->tz + h4 * PointTwo->tz;
  pVertex->dwDiffuse = D3DCOLOR_XRGB(255, 0, 0);
  pVertex++;

  // Un punto más
  usPointsCount++;

  // Miramos si hay que pintar...
  if (usPointsCount == BATCH)
  {
   // Desbloqueamos!
   m_VB.Unlock();

   // Pintamos
   CApplication::getDevice()->DrawPrimitive(D3DPT_POINTLIST, uiStartVertex, usPointsCount);

   // Volvemos a bloquear
   pVertex = m_VB.Lock(uiLock, uiStartVertex);
   assert(pVertex != NULL);

   // Contador a 0
   usPointsCount = 0;
  }
 }
 
 ++PointOne;
 ++PointTwo;
}
while (PointTwo != m_vCurve.end());

// Desbloqueo...
m_VB.Unlock();

// Pintamos si queda algún punto
if (usPointsCount)
{
 CApplication::getDevice()->DrawPrimitive(D3DPT_POINTLIST, uiStartVertex, usPointsCount);
}
}


void CSpline::Destroy ()
{
// Eliminamos recursos...
m_fTotalLength = 0.0f;
m_vCurve.clear();
m_vSegments.clear();
m_VB.Release();
}


A destacar el método Evaluate que es quien te devuelve el nuevo punto de la curva.
Los métodos relevantes al render... podeis obviarlos la spline se pinta punto por punto y
es una forma muy lenta de pintarla, simplemente era para unas pruebecillas... Bueno espero que
a alguien le sirva el code, saludos.

[Pogacha]

 Muy bueno e instructivo.

Saludos.

[ethernet]

 Me da la impresión de que Colson lo que quiere saber son los entresijos matemáticos, porque código hay a patadas en internet.

No sé demasiado de curvas, pero da la impresión que la diferencia entre unas y otras tiene que ver con la coincidencia de las derivadas (primeras, segundas...) en los puntos indicados, como bien han apuntado anteriormente.

[Ithaqua]

Las principales diferencias son las características que comenta Ethernet y por otro lado los parámetros que las definen (lo que da mayor o menor flexibilidad).

Resumiendo un poco en cuanto a lo segundo:

Bezier/Hermite: cada segmento se compone de dos puntos (inicio y fin) y dos tangentes (entrada y salida) que definen la dirección de la curva entre los puntos. Hay una correspondencia entre Hermite y Bezier y es que una usa tangentes (vectores) y otra usa puntos (los dos del segmento y otros dos que definen adicionalmente la dirección), pero a partir de los cuales se pueden sacar las tangentes.
Estas curvas vienen bien cuando quieres interpolar entre puntos y aparte tener algo de control sobre como es la forma de la curva a través de ellos.

Catmull-rom: Sirven para interpolar un camino a través de una serie de puntos sin más, tiene pinta de que es más o menos lo que buscas. En un segmento de dos puntos la interpolación es recta, pero a medida que vas añadiendo puntos la interpolación hace que se vaya creando un camino curvo entre ellos.
En mis librerías, lo comento porque dices que las has mirado, las he "simulado" con bezier o hermite, no recuerdo. Más que nada por facilidad a la hora de crear un interfaz común.
El "truco" que más o menos he utilizado es que el "usuario" define los puntos a través de los cuales quiere interpolar y yo calculo internamente las tangentes. La tangente del punto p se calcula usando el vector que va de p-1 a p+1, con lo cual la tangente en p es paralela al segmento que une p-1 a p+1. La implementación "real" usa también más o menos esta propiedad.

TCB: Son curvas que introducen 3 parámetros adicionales (tension, control y bias) que básicamente sirven para aumentar el control que se tiene sobre la interpolación. Se usan mucho en paquetes como 3dsMAX.


Tienes que tener cuidado ya que las curvas generalmente se definen en base a conjuntos de segmentos. Cuando evalúas una curva (por ejemplo, CVector3 CCurve::Evaluate(float time)) lo normal suele ser primero pillar el segmento en el cual cae ese tiempo y luego aplicar el algoritmo de interpolación propio de cada curva en ese segmento. Esto tiene el problema de que se pasa igual de rápido por segmentos cortos que largos.
Yo cuando uso catmull-rom tengo 2 opciones:
a) Forma cutre. Crear las keys más o menos equiparadas en espaciamiento :)
b) Mejor. Preprocesar la curva y asignarle a cada key un valor de tiempo. Si tienes una curva con dos segmentos, y el primero es el doble de largo que el segundo tendrías 3 keys con (0, 0.66 y 1.0). Para hallar estos valores una forma es interpolar cada segmento n veces (a mayor n más precisión) lo que da una serie de puntos cuyas distancias sumas. Así obtienes de forma aproximada la longtitud de cada arco y sabes que valor tienes que asignar.


Una página que resume muy bien todo la tienes en http://www.cubic.org/docs/hermite.htm. Va muy al grano sin entrar en complicaciones matemáticas ;)

[Edit] He desactivado los emoticones porque me creaba alguno sin querer en símbolos.

[CoLSoN2]

 Muchas gracias a todos, en especial a Ithaqua que ha explicado exactamente lo que quería :)

[ethernet]

 Ahora me da la gana y pego mi código de interpolación:

Código [Seleccionar] Expand


//10.12.2k4- el cabrón del vc7.1 da error con los templates de
// clases con miembros estáticos
//
#pragma once


#include "Serialize.h"


// Library code
//template <template <class Created> class CreationPolicy>
template <class key,template <class ,class> class Lerp >
class KeyFrameSequence
{
 public:

       struct KeyFrame
       {
           KeyFrame(const key &_k,float t)
               :k(_k),time(t)
           {
           }
           key k;
           float time;
       };

//classes
 typedef key KeyType;
       std::vector<KeyFrame> keys;
 float _timeoffset;
 typedef unsigned char mem_t;
     

       KeyFrameSequence(mem_t* mem)
       {
           serialize(mem);
       }
       void serialize(mem_t* mem)
       {
           int numkeys = SERIALIZE(int,mem);
           for (int i=0;i< numkeys; i++)
           {
                  key k;
                  float t = SERIALIZE(float,mem);
                  k.serialize(mem);
                  keys.push_back(KeyFrame(k,t));
           
           }

       }
       KeyFrameSequence(const std::vector<KeyFrame> &k,float timeoffset = 0):
         _timeoffset(timeoffset),
   keys(k) {}

       ~KeyFrameSequence()
       {
           keys.clear();
       }

 const KeyFrame& operator[](int i)
 {
 
  if(i < 0) i = 0;
  else if(i > keys.size()-1) i = keys.size()-1;
  return keys[i];
 }
       key  GetFrame(float curr)
       {
  //assert (dentro de rango)
           int i = 1;
           float t;
           for(;i<keys.size() && keys[i].time < curr;++i);
           i--;
           if(curr > keys.back().time )
           {
               t = 1;
               i = keys.size() - 1;
           }
           else
             t=(curr - keys[i].time)/((*this)[i+1].time - (*this)[i].time);

  return Lerp::Interpolation(*this,i, t  );            
       }
 

 


       
};


template <typename KeyFrameType,typename KeyType>
class KeyFrameLinear
{
public:
 
     static KeyType Interpolation(KeyFrameType &keys,unsigned idx,float t)
  {
   
   return Linear(keys[idx].k,keys[idx+1].k,t);
  }
  enum{ NumKeys = 2 };
};

template <typename KeyFrameType,typename KeyType>
class KeyFrameBezier
{
public:
//   template <typename KeyFrameType>
  static KeyType Interpolation(KeyFrameType &k,unsigned idx,float t)
  {
   idx = (NumKeys-1)*idx;
   return sampleBezier(k[idx],k[idx+1],k[idx+2],k[idx+3],t);
  }
  enum{ NumKeys = 4 };
};

template <typename KeyFrameType,typename KeyType>
class KeyFrameCatmull
{
public:
 // template <typename KeyFrameType>
  static KeyType Interpolation(KeyFrameType &k,unsigned idx,float t)
  {
   idx = (NumKeys-1)*idx;
   return Catmull(k[idx],k[idx+1],k[idx+2],k[idx+3],t);
  }
  enum{ NumKeys = 2 };
};



[CoLSoN2]

 Bien, al final me apañé bien con curvas bezier de toda la vida y la verdad es que me van de lujo, sólo tengo un problemilla.

Me he dado cuenta de que incrementando la posición dentro del spline (el valor que va de 0.0 a 1.0, vaya) por un valor constante cada frame, obtengo velocidades (en pixeles) distintas dependiendo de las tangentes. Normal, pero no había pensado en eso XD

Por lo que me han dicho, tengo que normalizar el spline (que supongo será redistribuir los puntos de control para que, manteniendo la forma de la curva, se consiga esa normalización de "velocidad"), que se conoce como "arc length parametrization" o algo así, pero no he encontrado más que papers muy teóricos.

¿Alguien tiene idea de cómo hacerlo?

[[Vil]]

 Yo tuve un problema similar al tuyo CoLSoN2 (creo) y no conseguí ninguna forma elegante de hacerlo... y al final lo mande todo a tomar por saco.

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.

No se si me explico, las una gran cutrada, pero funcionaba bastante bien. Al final mande a la mierda los splines y simplifique mis trayectorias. Es lo que tiene ser un perro y no seguir investigando

Ciao!

[Zaelsius]

 Yo caí en ese mismo problema cuando me estaba planteando hacer un clon del F-Zero hace unos meses.. estuve leyendo bastante, y no hay soluciones triviales.

Por lo que he visto, hay dos familias de soluciones:

1 ) Subdividir la curva entera en m segmentos con de igual longitud. Así te aseguras una velocidad linear en cualquiera de los segmentos. A más segmentos m, más precisión en la continuidad.

2 ) Calcular una tabla con coeficientes en base a la longitud del segmento actual, mediante el cual se ajusta el parámetro (0..1).(ejemplo borrado, ver el de Ithaqua)

edit Ithaqua ha puesto el mismo ejemplo al final de su post, aunque de manera más simple : ). Efectivamente cada coeficiente corresponde a un punto de control, y no a un segmento.



Cada una de estas soluciones se divide a su vez en varios subproblemas que tampoco son triviales, como el cálculo de la longitud de los arcos, etc..

En las páginas 18 y 19 tienes un esbozo de los algoritmos(na, 4 líneas de PPT de mierda):
http://www.cs.uiowa.edu/~kearney/22c196Spr...eterization.ppt

Sabiendo eso ya puedes centrar más las búsquedas en Google y buscar alguna implementación, o bien desempolvar el libro de cálculo y echarle huevos xDD.

PD: El proyecto lo dejo para más adelante, seguramente como PFC.. con su editor de pistas y tal  :rolleyes:

PD2: Por cierto Colson, ¿estás planeando algo tipo Zuma xD?

[Ray]

 Como un apunte más me gustaría plantearte la posibilidad de que tal vez te interese programar un editor visual de propósito general para las pantallas o niveles tu proyecto, tal vez te ahorre muchísimo trabajo después, aunque te lleve algunas semanas hacerlo.

Si sabes OpenGL te facilitará muchísimo las cosas para hacer todo tipo de curvas sin perderte en las matemáticas ya que todo se basa en parámetros de curvas y coordenadas de puntos que deberías poder crear y modificar fácilmente con el ratón desde el propio editor, si ya sabes tu como dibujar esas lineas pues perfecto.

Si al editor le añades una opción de dividir las curvas o lineas en varias partes iguales obtienes un numero determinado de puntos de control que servirán de referencia para que se dirijan o situen progresivamente los personajes. No se si es ese exactamente tu problema pero si yo tuviera que hacerlo esa es la forma que se me ocurre.

Después puedes ampliar ese editor para otras cosas además de los caminos, como por ejemplo situar objetos, personajes, tipos de terreno, o cualquier otra cosa que pertenezca a un determinado nivel. Si es un proyecto a largo plazo yo creo que vale la pena hacer también su propio editor visual, incluso te puede ayudar gente que no sepa programar diseñando los niveles con él.

Un saludo.

[Zaelsius]

 En relación al comentario de Ray, si el editor es 2D, con WindowsForms te puedes hacer uno en dos tardes usando Graphics.DrawBezier:

http://winfx.msdn.microsoft.com/library/de...1310cebea9f.asp

Código [Seleccionar] Expand


Point p1 = new Point(10, 100);   // Start point
Point c1 = new Point(100, 10);   // First control point
Point c2 = new Point(150, 150);  // Second control point
Point p2 = new Point(200, 100);  // End point

Pen pen = new Pen(Color.FromArgb(255, 0, 0, 255));
e.Graphics.DrawBezier(pen, p1, c1, c2, p2);


Yo hice una pequeña aplicación para mover los puntos de control y añadir segmentos, y me resultó fácil.