Ir al contenido

Spline centrípeto de Catmull-Rom

De Wikipedia, la enciclopedia libre
Interpolación con cuatro puntos dados realizada con el spline de Catmull-Rom

En computación gráfica, el spline centrípeto de Catmull-Rom es una variante del interpolador cúbico de Hermite, formulada originalmente por Edwin Catmull y Raphael Rom,[1]​ que puede calcularse utilizando un algoritmo recursivo propuesto por Barry y Goldman.[2]​ Es un tipo de spline de interpolación definido por cuatro puntos de control (por los que pasa), pero con la curva dibujada solo de a .

Definición

[editar]
Formulación piramidal de Barry y Goldman
Parametrización de nodos para el algoritmo de Catmull-Rom

Sea un punto. Para un segmento de curva definido por los puntos y la secuencia de nodos , el spline centrípeto de Catmull-Rom se puede generar mediante:

donde

y

en el que va de 0 a 1 para la parametrización de los nodos, y con . Para el spline centrípeto de Catmull-Rom, el valor de es . Cuando , la curva resultante es el spline uniforme de Catmull-Rom estándar; y cuando , el resultado es el spline cordal de Catmull-Rom.

Animación gif para la parametrización uniforme, centrípeta y cordal del spline de Catmull-Rom, dependiendo del valor de α

Al conectar a las ecuaciones del spline y se muestra que el valor de la curva en es . De manera similar, sustituir en las ecuaciones spline muestra que en . Esto es cierto independientemente del valor de , ya que la ecuación de no es necesaria para calcular el valor de en los puntos y .

Segmento de spline de Catmull-Rom centrípeto en 3D

La extensión a puntos 3D se logra simplemente considerando respecto a un punto 3D genérico y

Ventajas

[editar]

El spline centrípeto de Catmull-Rom tiene varias propiedades matemáticas deseables en comparación con la formulación original y otros tipos de splines de Catmull-Rom.[3]​ En primer lugar, no formará un bucle ni una autointersección dentro de un segmento de curva. En segundo lugar, nunca genera cúspides dentro de un segmento de curva. En tercer lugar, sigue más estrictamente los puntos de control.[4]

En esta figura, hay una autointersección/bucle en un spline de Catmull-Rom uniforme (verde), mientras que para el spline de Catmull-Rom cordal (rojo), la curva no sigue estrictamente los puntos de control

Otros usos

[editar]

En visión artificial, se ha utilizado el spline centrípeto de Catmull-Rom para formular un modelo activo para la segmentación. El método se denomina modelo de spline activo.[5]​ El modelo está diseñado sobre la base del modelo de forma activo, pero utiliza un spline centrípeto de Catmull-Rom para unir dos puntos sucesivos (el modelo de forma activa utiliza una línea recta simple), de modo que el número total de puntos necesarios para representar una forma es menor. El uso del spline centrípeto de Catmull-Rom simplifica mucho el entrenamiento de un modelo de forma y permite una mejor manera de editar un contorno después de la segmentación.

Ejemplo de código en Python

[editar]

La siguiente es una implementación del spline de Catmull-Rom en Python, que produce el gráfico que se muestra a continuación.

import numpy
import matplotlib.pyplot as plt


QUADRUPLE_SIZE: int= 4


def num_segments(point_chain: tuple) -> int:
    # Hay 1 segmento por cada 4 puntos, por lo que se debe restar 3 al número de puntos. 
    return len(point_chain) - (QUADRUPLE_SIZE - 1)


def flatten(list_of_lists) -> list:
    # P.ej. los puntos [[ 1, 2], [3], [4, 5]] to  [1, 2, 3, 4, 5] 
    return [elem for lst in list_of_lists for elem in lst]


def catmull_rom_spline(
    P0: tuple,
    P1: tuple,
    P2: tuple,
    P3: tuple,
    num_points: int,
    alpha: float= 0.5,
):
    """
    Compute the points in the spline segment
    :param P0, P1, P2, and P3: The (x,y) point pairs that define the Catmull-Rom spline
    :param num_points: The number of points to include in the resulting curve segment
    :param alpha: 0.5 for the centripetal spline, 0.0 for the uniform spline, 1.0 for the chordal spline.
    :return: The points
    """

     # Calcular t0 a t4. Luego, solo calcular los puntos entre P1 y P2.
     # Reformar linspace para que se pueda multiplicar por los puntos P0 a P3
     # y obtener un punto por cada valor de t.
    def tj(ti: float, pi: tuple, pj: tuple) -> float:
        xi, yi= pi
        xj, yj= pj
        dx, dy= xj - xi, yj - yi
        l= (dx ** 2 + dy ** 2) ** 0.5
        return ti + l ** alpha

    t0: float= 0.0
    t1: float= tj(t0, P0, P1)
    t2: float= tj(t1, P1, P2)
    t3: float= tj(t2, P2, P3)
    t= numpy.linspace(t1, t2, num_points).reshape(num_points, 1)

    A1= (t1 - t) / (t1 - t0) * P0 + (t - t0) / (t1 - t0) * P1
    A2= (t2 - t) / (t2 - t1) * P1 + (t - t1) / (t2 - t1) * P2
    A3= (t3 - t) / (t3 - t2) * P2 + (t - t2) / (t3 - t2) * P3
    B1= (t2 - t) / (t2 - t0) * A1 + (t - t0) / (t2 - t0) * A2
    B2= (t3 - t) / (t3 - t1) * A2 + (t - t1) / (t3 - t1) * A3
    points= (t2 - t) / (t2 - t1) * B1 + (t - t1) / (t2 - t1) * B2
    return points


def catmull_rom_chain(points: tuple, num_points: int) -> list:
    """
    Calculate Catmull-Rom for a sequence of initial points and return the combined curve.
    :param points: Base points from which the quadruples for the algorithm are taken
    :param num_points: The number of points to include in each curve segment
    :return: The chain of all points (points of all segments)
    """
    point_quadruples= (  # Prepare function inputs
        (points[idx_segment_start + d] for d in range(QUADRUPLE_SIZE))
        for idx_segment_start in range(num_segments(points))
    )
    all_splines= (catmull_rom_spline(*pq, num_points) for pq in point_quadruples)
    return flatten(all_splines)


if __name__== "__main__":
    POINTS: tuple= ((0, 1.5), (2, 2), (3, 1), (4, 0.5), (5, 1), (6, 2), (7, 3))  # Red points
    NUM_POINTS: int= 100  # Density of blue chain points between two red points

    chain_points: list= catmull_rom_chain(POINTS, NUM_POINTS)
    assert len(chain_points)== num_segments(POINTS) * NUM_POINTS  # 400 blue points for this example

    plt.plot(*zip(*chain_points), c="blue")
    plt.plot(*zip(*POINTS), c="red", linestyle="none", marker="o")
    plt.show()
Gráfico obtenido mediante el código de ejemplo en Python proporcionado anteriormente

Código ejemplo en Unity C#

[editar]
using UnityEngine;

// a single catmull-rom curve
public struct CatmullRomCurve
{
	public Vector2 p0, p1, p2, p3;
	public float alpha;

	public CatmullRomCurve(Vector2 p0, Vector2 p1, Vector2 p2, Vector2 p3, float alpha)
   {
		(this.p0, this.p1, this.p2, this.p3)= (p0, p1, p2, p3);
		this.alpha= alpha;
	}

	// Evaluates a point at the given t-value from 0 to 1
	public Vector2 GetPoint(float t)
    {
		// calculate knots
		const float k0= 0;
		float k1= GetKnotInterval(p0, p1);
		float k2= GetKnotInterval(p1, p2) + k1;
		float k3= GetKnotInterval(p2, p3) + k2;

		// evaluate the point
		float u= Mathf.LerpUnclamped(k1, k2, t);
		Vector2 A1= Remap(k0, k1, p0, p1, u);
		Vector2 A2= Remap(k1, k2, p1, p2, u);
		Vector2 A3= Remap(k2, k3, p2, p3, u);
		Vector2 B1= Remap(k0, k2, A1, A2, u);
		Vector2 B2= Remap(k1, k3, A2, A3, u);
		return Remap(k1, k2, B1, B2, u);
	}

	static Vector2 Remap(float a, float b, Vector2 c, Vector2 d, float u)
    {
		return Vector2.LerpUnclamped(c, d, (u - a) / (b - a));
	}

	float GetKnotInterval(Vector2 a, Vector2 b)
    {
		return Mathf.Pow(Vector2.SqrMagnitude(a - b), 0.5f * alpha);
	}
}


using UnityEngine;

// Draws a catmull-rom spline in the scene view,
// along the child objects of the transform of this component
public class CatmullRomSpline : MonoBehaviour
{
	[Range(0, 1)]
    public float alpha= 0.5f;
	int PointCount=> transform.childCount;
	int SegmentCount=> PointCount - 3;
	Vector2 GetPoint(int i)=> transform.GetChild(i).position;

	CatmullRomCurve GetCurve(int i)
    {
		return new CatmullRomCurve(GetPoint(i), GetPoint(i+1), GetPoint(i+2), GetPoint(i+3), alpha);
	}

	void OnDrawGizmos()
    {
		for (int i= 0; i < SegmentCount; i++)
			DrawCurveSegment(GetCurve(i));
	}

	void DrawCurveSegment(CatmullRomCurve curve)
    {
		const int detail= 32;
		Vector2 prev= curve.p1;

		for (int i= 1; i < detail; i++)
        {
			float t= i / (detail - 1f);
			Vector2 pt= curve.GetPoint(t);
			Gizmos.DrawLine(prev, pt);
			prev= pt;
		}
	}
}

Código ejemplo en Unreal C++

[editar]
float GetT( float t, float alpha, const FVector& p0, const FVector& p1 )
{
    auto d= p1 - p0;
    float a= d|d; // Dot product
    float b= FMath::Pow( a, alpha*.5f );
    return (b + t);
}

FVector CatmullRom( const FVector& p0, const FVector& p1, const FVector& p2, const FVector& p3, float t /* between 0 and 1 */, float alpha=.5f /* between 0 and 1 */ )
{
    float t0= 0.0f;
    float t1= GetT( t0, alpha, p0, p1 );
    float t2= GetT( t1, alpha, p1, p2 );
    float t3= GetT( t2, alpha, p2, p3 );
    t= FMath::Lerp( t1, t2, t );
    FVector A1= ( t1-t )/( t1-t0 )*p0 + ( t-t0 )/( t1-t0 )*p1;
    FVector A2= ( t2-t )/( t2-t1 )*p1 + ( t-t1 )/( t2-t1 )*p2;
    FVector A3= ( t3-t )/( t3-t2 )*p2 + ( t-t2 )/( t3-t2 )*p3;
    FVector B1= ( t2-t )/( t2-t0 )*A1 + ( t-t0 )/( t2-t0 )*A2;
    FVector B2= ( t3-t )/( t3-t1 )*A2 + ( t-t1 )/( t3-t1 )*A3;
    FVector C= ( t2-t )/( t2-t1 )*B1 + ( t-t1 )/( t2-t1 )*B2;
    return C;
}

Véase también

[editar]

Referencias

[editar]
  1. Catmull, Edwin; Rom, Raphael (1974). «A class of local interpolating splines». En Barnhill, Robert E.; Riesenfeld, Richard F., eds. Computer Aided Geometric Design. pp. 317–326. ISBN 978-0-12-079050-0. doi:10.1016/B978-0-12-079050-0.50020-5. 
  2. Barry, Phillip J.; Goldman, Ronald N. (August 1988). A recursive evaluation algorithm for a class of Catmull–Rom splines. Proceedings of the 15st Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1988 22 (4). Association for Computing Machinery. pp. 199-204. doi:10.1145/378456.378511. 
  3. Yuksel, Cem; Schaefer, Scott; Keyser, John (July 2011). «Parameterization and applications of Catmull-Rom curves». Computer-Aided Design 43 (7): 747-755. doi:10.1016/j.cad.2010.08.008. «citeseerx: 10.1.1.359.9148». 
  4. Yuksel; Schaefer; Keyser, Cem; Scott; John. «On the Parameterization of Catmull-Rom Curves». 
  5. Jen Hong, Tan; Acharya, U. Rajendra (2014). «Active spline model: A shape based model-interactive segmentation». Digital Signal Processing 35: 64-74. S2CID 6953844. arXiv:1402.6387. doi:10.1016/j.dsp.2014.09.002. 

Enlaces externos

[editar]