Catmull-Clarkův algoritmus

Catmull-Clark algoritmus je technika používaná v počítačové grafice k vytvoření hladkých povrchů modelováním dělení povrchu . Algoritmus vyvinuli Edwin Catmull a James Clark v roce 1978 jako zobecnění bikubických homogenních B-spline povrchů pro libovolnou topologii [1] . V roce 2005 Edwin Catmull obdržel cenu Americké akademie za technický úspěch spolu s Tonym DeRose a Jos Stam za jejich vývoj v oblasti dělení povrchu.

Rekurzivní výpočty

Catmull-Clarkovy povrchy jsou definovány rekurzivně pomocí následujícího schématu postupných zpřesňování [1] :

Začneme sítí ve tvaru libovolného mnohostěnu . Všechny vrcholy této mřížky se budou nazývat počáteční body.

Pro každý obličej přidejte bod obličeje
- Jako bod plochy zvolíme průměr všech počátečních bodů příslušné plochy .
Pro každou hranu přidejte bod hrany .
- Jako okrajový bod zvolíme průměr dvou sousedních bodů plochy a dvou počátečních koncových bodů hrany .
Pro každý bod hrany přidejte hranu pro každou hranu plochy a spojte bod hrany s bodem hrany hrany.
Pro každý původní bod P vezměte průměr F všech n (nově vytvořených) okrajových bodů pro hrany dotýkající se P a vezměte průměr R všech n okrajových bodů pro (původní) hrany dotýkající se P , kde střed každé hrany je průměr dvou koncových vrcholů (nezaměňovat s novými "hranovými body" definovanými výše). Přesuňte každý počáteční bod do bodu

{\frac {F+2R+(n-3)P}{n)).

Tento bod je barycentrem bodů P , R a F s váhami ( n − 3), 2 a 1.

Každý nový bod spojíme s novými hranovými body všech původních hran spadajících do původního vrcholu.
Definujte nové plochy ohraničené novými hranami.

Nová síť se skládá pouze ze čtyřúhelníků , které, obecně řečeno, nejsou ve stejné rovině . Nová síť bude obecně vypadat hladší než původní síť.

Opakované dělení má za následek hladší síť. Lze ukázat, že mezní plocha získaná touto metodou alespoň patří do třídy v singulárních bodech a na všech ostatních místech (zde n znamená počet spojitých derivací, když mluvíme o ). Po iteraci se počet singulárních bodů na povrchu nezmění. ${\mathcal {C}}^{1}$ ${\mathcal {C}}^{2}$ ${\mathcal {C}}^{n}$

Vzorec pro barycentrum zvolili Catmull a Clark spíše z estetických než matematických důvodů, ačkoli Catmull a Clark šli do velkých délek, aby důsledně dokázali, že metoda konverguje k bikubickým B-spline povrchům [1] .

Přesné výpočty

Výsledný dělený povrch Catmull-Clark lze získat přímo bez postupných vylepšení. To lze provést pomocí techniky Jos Stam [2] . Tato metoda reformuluje proces postupných aproximací na problém výpočtu exponentu matice , který lze vyřešit diagonalizací matice .

Software využívající dělení povrchu Catmull-Clark

3ds Max
3D kabát
AC3D
Anim8 nebo
AutoCAD
Mixér
Carrara
CATIA
CGAL
Cheetah3D
Kino 4D
Clara.io
Creo (Freestyle) [3]
DAZ Studio 2.0
gelato
Kladivo
šestiúhelník
Houdini
K-3D
LightWave 3D verze 9
Makehuman
Maya
metasekvoje
MODO
Mudbox
Pixar OpenSubdiv [4] [5] [6] [7] [8]
P.R.Man
Realsoft3D
3D
odstín
Rhinoceros 3D - Grasshopper 3D Plugin - Weaverbird Plugin
Silo
SketchUp – Je vyžadován plugin.
Softimage XSI
3D CX
Křídla 3D
Zbrush

Poznámky

↑ 1 2 3 Catmull a Clark, 1978 , str. 350.
↑ Stam, 1998 , str. 395–404.
↑ Archivovaná kopie (odkaz není dostupný) . Získáno 18. srpna 2017. Archivováno z originálu dne 23. listopadu 2016. (neurčitý)
↑ Manuel Kraemer. OpenSubdiv: Interoperating GPU Compute and Drawing // Multithreading pro vizuální efekty / Martin Watt, Erwin Coumans, George ElKoura, Ronald Henderson, Manuel Kraemer, Jeff Lait, James Reinders. - CRC Press , 2014. - S. 163-199. - ISBN 978-1-4822-4356-7 .
↑ Seznamte se s odborníky: Pixar Animation Studios, The OpenSubdiv Project – YouTube . Získáno 18. srpna 2017. Archivováno z originálu 26. ledna 2017. (neurčitý)
↑ OpenSubdiv V2 od Pixaru: detailní pohled | fxguide . Získáno 18. srpna 2017. Archivováno z originálu 30. července 2017. (neurčitý)
↑ Archivovaná kopie . Získáno 18. 8. 2017. Archivováno z originálu 12. 3. 2018. (neurčitý)
↑ Ukázka OpenSubdiv Blender – YouTube . Získáno 18. srpna 2017. Archivováno z originálu 7. ledna 2016. (neurčitý)

Literatura

Catmull E., Clark J. Rekurzivně generované B-spline povrchy na libovolných topologických sítích // Computer-Aided Design. - 1978. - T. 10 , no. 6 . - S. 350 . - doi : 10.1016/0010-4485(78)90110-0 .
Stam J. Sborník příspěvků z 25. výroční konference o počítačové grafice a interaktivních technikách - SIGGRAPH '98 . - 1998. - S. 395-404. - ISBN 0-89791-999-8 . - doi : 10.1145/280814.280945 . Archivováno 9. května 2018 na Wayback Machine

Čtení pro další čtení

Derose T., Kass M., Truong T. Subdivision surface in character animation // Sborník příspěvků z 25. výroční konference o počítačové grafice a interaktivních technikách - SIGGRAPH '98 . - 1998. - S. 85. - ISBN 0897919998 . - doi : 10.1145/280814.280826 .
Loop C., Schaefer S. Přibližování povrchů dělení Catmull-Clark pomocí bikubických záplat // ACM Transactions on Graphics. - 2008. - T. 27 . - S. 1 . - doi : 10.1145/1330511.1330519 .
Kovacs D., Mitchell J., Drone S., Zorin D. Přibližné povrchy dělení v reálném čase s posuny // Transakce IEEE na vizualizaci a počítačové grafice. - 2010. - T. 16 , no. 5 . - S. 742 . - doi : 10.1109/TVCG.2010.31 . — PMID 20616390 .
Matthias Niessner, Charles Loop, Mark Meyer, Tony DeRose. Funkce Adaptivní GPU vykreslování povrchů Catmull-Clark Subdivision // Transakce ACM na grafice. - 2012. - Leden ( roč. 31 , číslo 1 ). - doi : 10.1145/2077341.2077347 . , Videoklip
Niessner Matthias, Loop Charles, Greiner Günther. Efektivní vyhodnocení polohladkých záhybů v površích Catmull-Clark // Příloha Eurographics 2012: Short Papers (Eurographics 2012, Cagliary). - 2012. - S. str. 41-44 .
Wade Brainard. Teselace v Call of Duty: Ghosts . (neurčitý)Video se zprávou,PDFdokument
Doo D., Sabin M. Chování povrchů rekurzivního dělení v blízkosti mimořádných bodů // Computer-Aided Design. - 1978. - T. 10 , no. 6 . - doi : 10.1016/0010-4485(78)90111-2 .