Dostředivý Catmull – Rom spline - Centripetal Catmull–Rom spline - Wikipedia

v počítačová grafika, dostředivý Catmull – Rom spline je variantní forma Catmull-Rom spline, původně formuloval Edwin Catmull a Raphael Rom,^[1] který lze vyhodnotit pomocí rekurzivního algoritmu navrženého Barrym a Goldmanem.^[2] Jedná se o typ interpolační spline (křivka, která prochází svými kontrolními body) definovanou čtyřmi kontrolními body ${ displaystyle mathbf {P} _ {0}, mathbf {P} _ {1}, mathbf {P} _ {2}, mathbf {P} _ {3}}$ , s křivkou nakreslenou pouze z ${ displaystyle mathbf {P} _ {1}}$ na ${ displaystyle mathbf {P} _ {2}}$ .

Interpolace spline Catmull – Rom se čtyřmi body

Definice

Barry a Goldmanova pyramidová formulace

Parametrizace uzlu pro algoritmus Catmull – Rom

Nechat ${ displaystyle mathbf {P} _ {i} = [x_ {i} quad y_ {i}] ^ {T}}$ označit bod. Pro segment křivky ${ displaystyle mathbf {C}}$ definované body ${ displaystyle mathbf {P} _ {0}, mathbf {P} _ {1}, mathbf {P} _ {2}, mathbf {P} _ {3}}$ sekvence uzlů ${ displaystyle t_ {0}, t_ {1}, t_ {2}, t_ {3}}$ , dostředivý Catmull – Rom spline může být vyroben:

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

kde

{ displaystyle 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}}

{ displaystyle 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}}

{ displaystyle 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}}

{ displaystyle 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}}

{ displaystyle 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}}

a

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

ve kterém ${ displaystyle alpha}$ rozsahy od 0 do 1 pro parametrizaci uzlů a ${ displaystyle i = 0,1,2,3}$ s ${ displaystyle t_ {0} = 0}$ . U dostředivého spline Catmull – Rom je hodnota ${ displaystyle alpha}$ je ${ displaystyle 0,5}$ . Když ${ displaystyle alpha = 0}$ , výsledná křivka je standard uniformní Catmull – Rom spline; když ${ displaystyle alpha = 1}$ , produkt je a chordal Catmull – Rom spline.

Gifová animace pro jednotný, dostředivý a akordický parametrizace spline Catmull – Rom v závislosti na α hodnota

Zapojení ${ displaystyle t = t_ {1}}$ do spline rovnic ${ displaystyle mathbf {A} _ {1}, mathbf {A} _ {2}, mathbf {A} _ {3}, mathbf {B} _ {1}, mathbf {B} _ { 2},}$ a ${ displaystyle mathbf {C}}$ ukazuje, že hodnota křivky spline v ${ displaystyle t_ {1}}$ je ${ displaystyle mathbf {C} = mathbf {P} _ {1}}$ . Podobně i střídání ${ displaystyle t = t_ {2}}$ do spline rovnic to ukazuje ${ displaystyle mathbf {C} = mathbf {P} _ {2}}$ na ${ displaystyle t_ {2}}$ . To platí nezávisle na hodnotě ${ displaystyle alpha}$ protože rovnice pro ${ displaystyle t_ {i + 1}}$ není nutné k výpočtu hodnoty ${ displaystyle mathbf {C}}$ v bodech ${ displaystyle t_ {1}}$ a ${ displaystyle t_ {2}}$ .

3D dostředivý Catmull-Rom spline segment.

Rozšíření na 3D body se jednoduše dosáhne zvážením ${ displaystyle mathbf {P} _ {i} = [x_ {i} quad y_ {i} quad z_ {i}] ^ {T}}$ obecný 3D bod ${ displaystyle mathbf {P} _ {i}}$ a

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

Výhody

Centripetal Catmull – Rom spline má několik žádoucích matematických vlastností ve srovnání s původní a jinými typy Catmull-Romovy formulace.^[3] Nejprve nevytvoří smyčku ani samovolný průnik v segmentu křivky. Druhý, hrot nikdy nenastane v segmentu křivky. Za třetí, důsledněji sleduje kontrolní body.^{[vágní ]}

Na tomto obrázku je křivka / smyčka na jednotném Catmull-Rom spline (zelená), zatímco u chordal Catmull-Rom spline (červená) křivka těsně nesleduje kontrolní body.

Jiná použití

v počítačové vidění, k formulaci aktivního modelu pro segmentaci byl použit dostředivý spline Catmull-Rom. Tato metoda se nazývá aktivní spline model.^[4] Model je navržen na základě aktivní tvarový model, ale používá dostředivé spline Catmull-Rom ke spojení dvou po sobě jdoucích bodů (aktivní model tvaru používá jednoduchou přímku), takže celkový počet bodů nutných k zobrazení tvaru je menší. Díky použití dostředivého spline Catmull-Rom je trénink tvarového modelu mnohem jednodušší a umožňuje lepší způsob úpravy kontury po segmentaci.

Příklad kódu v Pythonu

Následuje implementace spline Catmull – Rom v Krajta který vytváří níže zobrazený graf.

import numpyimport matplotlib.pyplot tak jako pltdef CatmullRomSpline(P0, P1, P2, P3, nBody=100):    """    P0, P1, P2 a P3 by měly být (x, y) dvojice bodů, které definují spline Catmull-Rom.    nPoints je počet bodů, které mají být zahrnuty do tohoto segmentu křivky.    """    # Převeďte body na numpy, abychom mohli dělat násobení pole    P0, P1, P2, P3 = mapa(numpy.pole, [P0, P1, P2, P3])    # Parametrická konstanta: 0,5 pro dostředivý spline, 0,0 pro rovnoměrný spline, 1,0 pro chordální spline.    alfa = 0.5    # Předemplikovaná výkonová konstanta pro následující funkci tj ().    alfa = alfa/2    def tj(ti, Pi, Pj):        xi, yi = Pi        xj, yj = Pj        vrátit se ((xj-xi)**2 + (yj-yi)**2)**alfa + ti    # Vypočítejte t0 až t4    t0 = 0    t1 = tj(t0, P0, P1)    t2 = tj(t1, P1, P2)    t3 = tj(t2, P2, P3)    # Vypočítávejte pouze body mezi P1 a P2    t = numpy.linspace(t1, t2, nBody)    # Přetvarujte, abychom mohli vynásobit body P0 až P3    # a získejte bod za každou hodnotu t.    t = t.přetvarovat(len(t), 1)    tisk(t)    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    tisk(A1)    tisk(A2)    tisk(A3)    B1 = (t2-t)/(t2-t0)*A1 + (t-t0)/(t2-t0)*A2    B2 = (t3-t)/(t3-t1)*A2 + (t-t1)/(t3-t1)*A3    C = (t2-t)/(t2-t1)*B1 + (t-t1)/(t2-t1)*B2    vrátit se Cdef CatmullRomŘetěz(P):    """    Vypočítejte Catmull – Rom pro řetězec bodů a vraťte kombinovanou křivku.    """    sz = len(P)    # Křivka C bude obsahovat pole (x, y) bodů.    C = []    pro i v rozsah(sz-3):        C = CatmullRomSpline(P[i], P[i+1], P[i+2], P[i+3])        C.rozšířit(C)    vrátit se C# Definujte sadu bodů, kterými má křivka projítBody = [[0, 1.5], [2, 2], [3, 1], [4, 0.5], [5, 1], [6, 2], [7, 3]]# Vypočítejte spline Catmull-Rom skrz bodyC = CatmullRomŘetěz(Body)# Převeďte body křivky Catmull-Rom na pole xay a vykreslete jeX, y = zip(*C)plt.spiknutí(X, y)# Vyneste kontrolní bodypx, py = zip(*Body)plt.spiknutí(px, py, 'nebo')plt.ukázat()

Plot získaný výše uvedeným ukázkovým kódem Pythonu

Příklad kódu v Unity C #

použitím UnityEngine;použitím System.Collections;použitím System.Collections.Generic;veřejnost třída Catmul : Mono chování {	// Použijte transformace GameObjects ve 3D prostoru jako své body nebo definujte pole s požadovanými body	veřejnost Přeměnit[] bodů;		// Ukládejte body na křivce Catmull, abychom je mohli vizualizovat	Seznam<Vector2> newPoints = Nový Seznam<Vector2>();		// Kolik bodů chcete na křivce	uint numberOfPoints = 10;		// Parametrická konstanta: 0,0 pro rovnoměrný spline, 0,5 pro dostředivý spline, 1,0 pro akordový spline	veřejnost plovák alfa = 0,5f;		/////////////////////////////		prázdnota Aktualizace()	{	    CatmulRom();	}		prázdnota CatmulRom()	{		newPoints.Průhledná();		Vector2 p0 = bodů[0].pozice; // Vector3 má implicitní převod na Vector2		Vector2 p1 = bodů[1].pozice;		Vector2 p2 = bodů[2].pozice;		Vector2 p3 = bodů[3].pozice;		plovák t0 = 0,0f;		plovák t1 = GetT(t0, p0, p1);		plovák t2 = GetT(t1, p1, p2);		plovák t3 = GetT(t2, p2, p3);		pro (plovák t=t1; t<t2; t+=((t2-t1)/(plovák)numberOfPoints))		{		    Vector2 A1 = (t1-t)/(t1-t0)*p0 + (t-t0)/(t1-t0)*p1;		    Vector2 A2 = (t2-t)/(t2-t1)*p1 + (t-t1)/(t2-t1)*p2;		    Vector2 A3 = (t3-t)/(t3-t2)*p2 + (t-t2)/(t3-t2)*p3;		    		    Vector2 B1 = (t2-t)/(t2-t0)*A1 + (t-t0)/(t2-t0)*A2;		    Vector2 B2 = (t3-t)/(t3-t1)*A2 + (t-t1)/(t3-t1)*A3;		    		    Vector2 C = (t2-t)/(t2-t1)*B1 + (t-t1)/(t2-t1)*B2;		    		    newPoints.Přidat(C);		}	}	plovák GetT(plovák t, Vector2 p0, Vector2 p1)	{	    plovák A = Mathf.Pow((p1.X-p0.X), 2,0f) + Mathf.Pow((p1.y-p0.y), 2,0f);	    plovák b = Mathf.Pow(A, alfa * 0,5f);	   	    vrátit se (b + t);	}		// Vizualizujte body	prázdnota OnDrawGizmos()	{	    Gizmos.barva = Barva.Červené;	    pro každého (Vector2 tepl v newPoints)	    {	        Vector3 poz = Nový Vector3(tepl.X, tepl.y, 0);	        Gizmos.DrawSphere(poz, 0,3 f);	    }	}}

U implementace v 3D prostoru by se po převodu bodů Vector2 na Vector3 měl první řádek funkce GetT změnit na toto: Mathf.Pow ((p1.x-p0.x), 2.0f) + Mathf.Pow ((p1.y-p0.y), 2.0f) + Mathf.Pow ((p1.z-p0.z), 2,0f);

Příklad kódu v Unreal C ++

plovák GetT( plovák t, plovák alfa, konst FVektor& p0, konst FVektor& p1 ){    auto d  = p1 - p0;    plovák A = d | d; // Tečkovaný produkt    plovák b = FMath::Pow( A, alfa*.5f );    vrátit se (b + t);}FVektor CatMullRom( konst FVektor& p0, konst FVektor& p1, konst FVektor& p2, konst FVektor& p3, plovák t / * mezi 0 a 1 * /, plovák alfa=.5f / * mezi 0 a 1 * / ){    plovák t0 = 0,0f;    plovák t1 = GetT( t0, alfa, p0, p1 );    plovák t2 = GetT( t1, alfa, p1, p2 );    plovák t3 = GetT( t2, alfa, p2, p3 );    t = FMath::Lerp( t1, t2, t );    FVektor A1 = ( t1-t )/( t1-t0 )*p0 + ( t-t0 )/( t1-t0 )*p1;    FVektor A2 = ( t2-t )/( t2-t1 )*p1 + ( t-t1 )/( t2-t1 )*p2;    FVektor A3 = ( t3-t )/( t3-t2 )*p2 + ( t-t2 )/( t3-t2 )*p3;    FVektor B1 = ( t2-t )/( t2-t0 )*A1 + ( t-t0 )/( t2-t0 )*A2;    FVektor B2 = ( t3-t )/( t3-t1 )*A2 + ( t-t1 )/( t3-t1 )*A3;    FVektor C  = ( t2-t )/( t2-t1 )*B1 + ( t-t1 )/( t2-t1 )*B2;    vrátit se C;}

Viz také

Cubic Hermite splajny

Reference

^ Catmull, Edwin; Rom, Raphaeli (1974). "Třída lokálních interpolačních splajnů". V Barnhill, Robert E .; Riesenfeld, Richard F. (eds.). Počítačem podporovaný geometrický design. 317–326. doi:10.1016 / B978-0-12-079050-0.50020-5. ISBN 978-0-12-079050-0.
^ Barry, Phillip J .; Goldman, Ronald N. (srpen 1988). Algoritmus rekurzivního vyhodnocení pro třídu Spline Catmull – Rom. Sborník z 15. výroční konference o počítačové grafice a interaktivních technikách, SIGGRAPH 1988. 22. Sdružení pro výpočetní techniku. 199–204. doi:10.1145/378456.378511.
^ Yuksel, Cem; Schaefer, Scott; Keyser, John (červenec 2011). "Parametrizace a aplikace křivek Catmull-Rom". Počítačem podporovaný design. 43 (7): 747–755. CiteSeerX 10.1.1.359.9148. doi:10.1016 / j.cad.2010.08.008.
^ Jen Hong, Tan; Acharya, U. Rajendra (2014). "Aktivní spline model: modelová interaktivní segmentace založená na tvaru" (PDF). Zpracování digitálních signálů. 35: 64–74. arXiv:1402.6387. doi:10.1016 / j.dsp.2014.09.002. S2CID 6953844.

externí odkazy

Křivka Catmull-Rom bez hrbolů a bez křižovatek - implementace v Javě
Křivka Catmull-Rom bez hrbolů a bez křižovatek - zjednodušená implementace v C ++
Catmull-Rom splajny - interaktivní generování přes Python, v notebooku Jupyter

[1] Catmull, Edwin; Rom, Raphaeli (1974). "Třída lokálních interpolačních splajnů". V Barnhill, Robert E .; Riesenfeld, Richard F. (eds.). Počítačem podporovaný geometrický design. 317–326. doi:10.1016 / B978-0-12-079050-0.50020-5. ISBN 978-0-12-079050-0.

[2] Barry, Phillip J .; Goldman, Ronald N. (srpen 1988). Algoritmus rekurzivního vyhodnocení pro třídu Spline Catmull – Rom. Sborník z 15. výroční konference o počítačové grafice a interaktivních technikách, SIGGRAPH 1988. 22. Sdružení pro výpočetní techniku. 199–204. doi:10.1145/378456.378511.

[Yuksel-3] Yuksel, Cem; Schaefer, Scott; Keyser, John (červenec 2011). "Parametrizace a aplikace křivek Catmull-Rom". Počítačem podporovaný design. 43 (7): 747–755. CiteSeerX 10.1.1.359.9148. doi:10.1016 / j.cad.2010.08.008.

[4] Jen Hong, Tan; Acharya, U. Rajendra (2014). "Aktivní spline model: modelová interaktivní segmentace založená na tvaru" (PDF). Zpracování digitálních signálů. 35: 64–74. arXiv:1402.6387. doi:10.1016 / j.dsp.2014.09.002. S2CID 6953844.

[1]

[2]

[3]

[4]