Центростремительный сплайн Катмулла – Рома

В компьютерной графике центростремительный сплайн Кэтмулла-Рома представляет собой вариант формы сплайна Кэтмулла-Рома , первоначально сформулированный Эдвином Кэтмаллом и Рафаэлем Ромом . ^{[ 1 ]} который можно оценить с помощью рекурсивного алгоритма, предложенного Барри и Голдманом. ^{[ 2 ]} Это тип интерполяционного сплайна (кривая, проходящая через контрольные точки), определяемого четырьмя контрольными точками. $\mathbf {P} _{0},\mathbf {P} _{1},\mathbf {P} _{2},\mathbf {P} _{3}$ , с кривой, проведенной только из $\mathbf {P} _{1}$ к $\mathbf {P} _{2}$ .

Определение

Позволять $\mathbf {P} _{i}=[x_{i}\quad y_{i}]^{T}$ обозначить точку. Для сегмента кривой $\mathbf {C}$ определяется точками $\mathbf {P} _{0},\mathbf {P} _{1},\mathbf {P} _{2},\mathbf {P} _{3}$ и последовательность узлов $t_{0},t_{1},t_{2},t_{3}$ , центростремительный сплайн Катмулла – Рома может быть получен следующим образом:

\mathbf {C} ={\frac {t_{2}-t}{t_{2}-t_{1}}}\mathbf {B} _{1}+{\frac {t-t_{1}}{t_{2}-t_{1}}}\mathbf {B} _{2}

где

\mathbf {B} _{1}={\frac {t_{2}-t}{t_{2}-t_{0}}}\mathbf {A} _{1}+{\frac {t-t_{0}}{t_{2}-t_{0}}}\mathbf {A} _{2}

\mathbf {B} _{2}={\frac {t_{3}-t}{t_{3}-t_{1}}}\mathbf {A} _{2}+{\frac {t-t_{1}}{t_{3}-t_{1}}}\mathbf {A} _{3}

\mathbf {A} _{1}={\frac {t_{1}-t}{t_{1}-t_{0}}}\mathbf {P} _{0}+{\frac {t-t_{0}}{t_{1}-t_{0}}}\mathbf {P} _{1}

\mathbf {A} _{2}={\frac {t_{2}-t}{t_{2}-t_{1}}}\mathbf {P} _{1}+{\frac {t-t_{1}}{t_{2}-t_{1}}}\mathbf {P} _{2}

\mathbf {A} _{3}={\frac {t_{3}-t}{t_{3}-t_{2}}}\mathbf {P} _{2}+{\frac {t-t_{2}}{t_{3}-t_{2}}}\mathbf {P} _{3}

и

t_{i+1}=\left[{\sqrt {(x_{i+1}-x_{i})^{2}+(y_{i+1}-y_{i})^{2}}}\right]^{\alpha }+t_{i}

в котором $\alpha$ варьируется от 0 до 1 для параметризации узла и $i=0,1,2,3$ с $t_{0}=0$ . Для центростремительного сплайна Катмулла–Рома значение $\alpha$ является $0.5$ . Когда $\alpha =0$ , результирующая кривая представляет собой стандартный равномерный сплайн Катмулла–Рома ; когда $\alpha =1$ , результатом является хордальный сплайн Катмулла–Рома .

Затыкание $t=t_{1}$ в сплайн-уравнения $\mathbf {A} _{1},\mathbf {A} _{2},\mathbf {A} _{3},\mathbf {B} _{1},\mathbf {B} _{2},$ и $\mathbf {C}$ показывает, что значение сплайновой кривой при $t_{1}$ является $\mathbf {C} =\mathbf {P} _{1}$ . Аналогично, подставив $t=t_{2}$ в сплайн-уравнения показывает, что $\mathbf {C} =\mathbf {P} _{2}$ в $t_{2}$ . Это верно независимо от значения $\alpha$ поскольку уравнение для $t_{i+1}$ не требуется для расчета стоимости $\mathbf {C}$ в точках $t_{1}$ и $t_{2}$ .

Расширение до 3D-точек просто достигается путем рассмотрения $\mathbf {P} _{i}=[x_{i}\quad y_{i}\quad z_{i}]^{T}$ обычная 3D-точка $\mathbf {P} _{i}$ и

t_{i+1}=\left[{\sqrt {(x_{i+1}-x_{i})^{2}+(y_{i+1}-y_{i})^{2}+(z_{i+1}-z_{i})^{2}}}\right]^{\alpha }+t_{i}

Преимущества

Центростремительный сплайн Катмулла-Рома обладает несколькими желательными математическими свойствами по сравнению с исходной и другими типами формулировок Кэтмулла-Рома. ^{[ 3 ]} Во-первых, внутри сегмента кривой не будет образовываться петля или самопересечение. Во-вторых, перегиб никогда не возникает внутри сегмента кривой. В-третьих, он более плотно следует за контрольными точками. ^{[ 4 ]}^{[ нечеткий ]}

Другое использование

В компьютерном зрении центростремительный сплайн Катмулла-Рома использовался для формулирования активной модели сегментации. Этот метод называется активной сплайновой моделью . ^{[ 5 ]} Модель разработана на основе модели активной формы , но использует центростремительный сплайн Катмулла-Рома для соединения двух последовательных точек (модель активной формы использует простую прямую линию), так что общее количество точек, необходимых для изображения формы, меньше. Использование центростремительного сплайна Катмулла-Рома значительно упрощает обучение модели формы и позволяет лучше редактировать контур после сегментации.

Пример кода на Python

Ниже приведена реализация сплайна Catmull-Rom в Python , которая создает график, показанный ниже.

import numpy
import matplotlib.pyplot as plt


QUADRUPLE_SIZE: int = 4


def num_segments(point_chain: tuple) -> int:
    # There is 1 segment per 4 points, so we must subtract 3 from the number of points  
    return len(point_chain) - (QUADRUPLE_SIZE - 1)


def flatten(list_of_lists) -> list:
    # E.g. mapping [[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
    """

    # Calculate t0 to t4. Then only calculate points between P1 and P2.
    # Reshape linspace so that we can multiply by the points P0 to P3
    # and get a point for each value of 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()

Пример кода в Unity C#

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;
		}
	}
}

Пример кода в Unreal C++

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;
}

См. также

Кубические сплайны Эрмита

Ссылки

^ Кэтмалл, Эдвин ; Ром, Рафаэль (1974). «Класс локальных интерполирующих сплайнов». В Барнхилле, Роберт Э.; Ризенфельд, Ричард Ф. (ред.). Компьютерное геометрическое проектирование . стр. 317–326. дои : 10.1016/B978-0-12-079050-0.50020-5 . ISBN 978-0-12-079050-0 .
^ Барри, Филипп Дж.; Гольдман, Рональд Н. (август 1988 г.). Рекурсивный алгоритм вычисления для класса сплайнов Катмулла–Рома . Материалы 15-й ежегодной конференции по компьютерной графике и интерактивным технологиям, SIGGRAPH, 1988. Vol. 22. Ассоциация вычислительной техники . стр. 199–204. дои : 10.1145/378456.378511 .
^ Юксель, Цем; Шефер, Скотт; Кейзер, Джон (июль 2011 г.). «Параметризация и приложения кривых Катмулла-Рома» . Компьютерное проектирование . 43 (7): 747–755. CiteSeerX 10.1.1.359.9148 . дои : 10.1016/j.cad.2010.08.008 .
^ Юксель; Шефер; Кейзер, Джем; Скотт; Джон. «О параметризации кривых Кэтмулла-Рома» (PDF) . {{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Джен Хонг, Тан; Ачарья, У. Раджендра (2014). «Активная сплайновая модель: интерактивная сегментация на основе формы» (PDF) . Цифровая обработка сигналов . 35 : 64–74. arXiv : 1402.6387 . дои : 10.1016/j.dsp.2014.09.002 . S2CID 6953844 .

Внешние ссылки

Кривая Катмулла-Рома без точек возврата и самопересечений – реализация на Java
Кривая Катмулла-Рома без точек пересечения и самопересечений – упрощенная реализация на C++
Сплайны Catmull-Rom — интерактивная генерация с помощью Python в блокноте Jupyter
Сглаживание путей с использованием сплайнов Catmull-Rom — еще одна универсальная реализация на C++, включая центростремительные сплайны CR.

[1] Кэтмалл, Эдвин ; Ром, Рафаэль (1974). «Класс локальных интерполирующих сплайнов». В Барнхилле, Роберт Э.; Ризенфельд, Ричард Ф. (ред.). Компьютерное геометрическое проектирование . стр. 317–326. дои : 10.1016/B978-0-12-079050-0.50020-5 . ISBN 978-0-12-079050-0 .

[2] Барри, Филипп Дж.; Гольдман, Рональд Н. (август 1988 г.). Рекурсивный алгоритм вычисления для класса сплайнов Катмулла–Рома . Материалы 15-й ежегодной конференции по компьютерной графике и интерактивным технологиям, SIGGRAPH, 1988. Vol. 22. Ассоциация вычислительной техники . стр. 199–204. дои : 10.1145/378456.378511 .

[Yuksel-3] Юксель, Цем; Шефер, Скотт; Кейзер, Джон (июль 2011 г.). «Параметризация и приложения кривых Катмулла-Рома» . Компьютерное проектирование . 43 (7): 747–755. CiteSeerX 10.1.1.359.9148 . дои : 10.1016/j.cad.2010.08.008 .

[4] Юксель; Шефер; Кейзер, Джем; Скотт; Джон. «О параметризации кривых Кэтмулла-Рома» (PDF) . {{cite web}}: CS1 maint: несколько имен: список авторов ( ссылка )

[5] Джен Хонг, Тан; Ачарья, У. Раджендра (2014). «Активная сплайновая модель: интерактивная сегментация на основе формы» (PDF) . Цифровая обработка сигналов . 35 : 64–74. arXiv : 1402.6387 . дои : 10.1016/j.dsp.2014.09.002 . S2CID 6953844 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]