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
![{\displaystyle {\frac {F+2R+(n-3)P}{n)).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/724c5c389f8665440609b8aeac791a5325f1ba90)
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í.
![{\displaystyle {\mathcal {C}}^{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9791a5c97f2cf7a4a7ab3559dc4968fc60590fe)
![{\displaystyle {\mathcal {C}}^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/86a81a0818245a818ce645f5c119f4caa9e805aa)
![{\displaystyle {\mathcal {C}}^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5fa78532f9ecd4d2c24067453326c56c10a2507f)
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
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
Č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 .