Catmull-Clark algoritm
Catmull-Clark- algoritmen är en teknik som används i datorgrafik för att skapa jämna ytor genom att modellera ytunderdelning . Algoritmen utvecklades av Edwin Catmull och James Clark 1978 som en generalisering av bikubiska homogena B-splineytor för godtycklig topologi [1] . År 2005 mottog Edwin Catmull American Academy Award for Technical Achievement tillsammans med Tony DeRose och Jos Stam för deras utveckling inom ytindelning.
Rekursiva beräkningar
Catmull-Clark-ytor definieras rekursivt med hjälp av följande schema av successiva förbättringar [1] :
Vi börjar med ett nät i form av en godtycklig polyeder . Alla hörn i detta rutnät kommer att kallas initialpunkter.
- Lägg till en ansiktspunkt för varje ansikte
- Vi väljer som ansiktspunkt medelvärdet av alla initiala punkter på motsvarande ansikte .
- Lägg till en kantpunkt för varje kant .
- Vi väljer som kantpunkt genomsnittet av två angränsande punkter på ansiktet och två initiala slutpunkter på kanten .
- För varje kantpunkt , lägg till en kant för varje kant av ansiktet, anslut kantpunkten till kantpunkten för kanten.
- För varje ursprunglig punkt P , ta medelvärdet F för alla n (nyskapade) kantpunkter för kanterna som rör P , och ta medelvärdet R för alla n kantpunkter för de (ursprungliga) kanterna som rör P , där mittpunkten av varje kant är medelvärdet av de två ändpunkten (inte att förväxla med de nya "kantpunkterna" definierade ovan). Flytta varje startpunkt till en punkt
- Vi kopplar varje ny punkt med nya kantpunkter på alla ursprungliga kanter som faller in på den ursprungliga vertexen.
- Definiera nya ansikten omslutna av nya kanter.
Det nya nätet består endast av fyrhörningar , som generellt sett inte är i samma plan . Det nya nätet kommer i allmänhet att se jämnare ut än det ursprungliga nätet.
Upprepad uppdelning resulterar i ett jämnare nät. Det kan visas att den gränsyta som erhålls med denna metod åtminstone tillhör klassen vid singularpunkterna och på alla andra ställen (här betyder n antalet kontinuerliga derivator när vi talar om ). Efter iteration ändras inte antalet singulära punkter på ytan.
Formeln för barycentret valdes av Catmull och Clark av estetiska snarare än matematiska skäl, även om Catmull och Clark gick långt för att rigoröst bevisa att metoden konvergerar till bikubiska B-splineytor [1] .
Exakta beräkningar
Den resulterande uppdelade Catmull-Clark-ytan kan erhållas direkt utan successiva förbättringar. Detta kan göras med hjälp av Jos Stam-tekniken [2] . Denna metod omformulerar processen med successiva approximationer till problemet med att beräkna matrisens exponent , vilket kan lösas genom att diagonalisera matrisen .
Programvara som använder Catmull-Clark yta subdivision
- 3ds Max
- 3D kappa
- AC3D
- Anim8or
- AutoCAD
- Blandare
- Carrara
- CATIA
- CGAL
- Cheetah3D
- Cinema 4D
- Clara.io
- Creo (Freestyle) [3]
- DAZ Studio 2.0
- Gelato
- Hammare
- Hexagon
- Houdini
- K-3D
- LightWave 3D version 9
- Makehuman
- Maya
- Metasequoia
- MODO
- Mudbox
- Pixars OpenSubdiv [4] [5] [6] [7] [8]
- P.R.Man
- Realsoft3D
- 3D
- skugga
- Rhinoceros 3D - Grasshopper 3D Plugin - Weaverbird Plugin
- Silo
- SketchUp - Plugin krävs.
- Softimage XSI
- 3D CX
- Vingar 3D
- Zbrush
Anteckningar
- ↑ 1 2 3 Catmull och Clark, 1978 , sid. 350.
- ↑ Stam, 1998 , sid. 395–404.
- ↑ Arkiverad kopia (länk ej tillgänglig) . Hämtad 18 augusti 2017. Arkiverad från originalet 23 november 2016.
- ↑ Manuel Kraemer. OpenSubdiv: Interoperating GPU Compute and Drawing // Multithreading for Visual Effects / Martin Watt, Erwin Coumans, George ElKoura, Ronald Henderson, Manuel Kraemer, Jeff Lait, James Reinders. - CRC Press , 2014. - P. 163-199. - ISBN 978-1-4822-4356-7 .
- ↑ Möt experterna: Pixar Animation Studios, The OpenSubdiv Project - YouTube . Hämtad 18 augusti 2017. Arkiverad från originalet 26 januari 2017.
- ↑ Pixars OpenSubdiv V2: en detaljerad titt | fxguide . Hämtad 18 augusti 2017. Arkiverad från originalet 30 juli 2017.
- ↑ Arkiverad kopia . Hämtad 18 augusti 2017. Arkiverad från originalet 12 mars 2018.
- ↑ OpenSubdiv Blender-demo - YouTube . Hämtad 18 augusti 2017. Arkiverad från originalet 7 januari 2016.
Litteratur
- Catmull E., Clark J. Rekursivt genererade B-spline-ytor på godtyckliga topologiska maskor // Computer-Aided Design. - 1978. - T. 10 , nr. 6 . - S. 350 . - doi : 10.1016/0010-4485(78)90110-0 .
- Stam J. Proceedings från den 25:e årliga konferensen om datorgrafik och interaktiva tekniker - SIGGRAPH '98 . - 1998. - S. 395-404. - ISBN 0-89791-999-8 . - doi : 10.1145/280814.280945 . Arkiverad 9 maj 2018 på Wayback Machine
Läsning för vidare läsning
- Derose T., Kass M., Truong T. Subdivision ytor i karaktärsanimering // Proceedings of the 25th annual conference on Computer graphics and interactive techniques - SIGGRAPH '98 . - 1998. - S. 85. - ISBN 0897919998 . - doi : 10.1145/280814.280826 .
- Loop C., Schaefer S. Approximating Catmull-Clark subdivision ytor med bikubiska fläckar // ACM Transactions on Graphics. - 2008. - T. 27 . - S. 1 . - doi : 10.1145/1330511.1330519 .
- Kovacs D., Mitchell J., Drone S., Zorin D. Realtidsveckade ungefärliga indelningsytor med förskjutningar // IEEE-transaktioner på visualisering och datorgrafik. - 2010. - T. 16 , nr. 5 . - S. 742 . - doi : 10.1109/TVCG.2010.31 . — PMID 20616390 .
- Matthias Niessner, Charles Loop, Mark Meyer, Tony DeRose. Funktioner Adaptiv GPU-rendering av Catmull-Clark Subdivision Ytor // ACM Transactions on Graphics. - 2012. - Januari ( vol. 31 , nummer 1 ). - doi : 10.1145/2077341.2077347 . , Videoklipp
- Niessner Matthias, Loop Charles, Greiner Günther. Effektiv utvärdering av halvsläta veck i Catmull-Clark Subdivision Ytor // Eurographics 2012 Annex: Short Papers (Eurographics 2012, Cagliary). - 2012. - S. s 41-44 .
- Wade Brainard. Tessellation i Call of Duty: Ghosts . Video med rapporten,PDFdokument
- Doo D., Sabin M. Beteende hos rekursiva delningsytor nära extraordinära punkter // Computer-Aided Design. - 1978. - T. 10 , nr. 6 . - doi : 10.1016/0010-4485(78)90111-2 .