Catmull–Clark indelningsyta

Catmull–Clark nivå-3 indelning av en kub med gränsindelningsytan som visas nedan. (Observera att även om det ser ut som att den bikubiska interpolationen närmar sig en sfär , är en faktisk sfär kvadrisk .)

Visuell skillnad mellan sfär (grön) och Catmull-Clark underavdelningsyta (magenta) från en kub

Catmull –Clark- algoritmen är en teknik som används i 3D-datorgrafik för att skapa krökta ytor genom att använda underavdelnings- ytmodellering . Den utarbetades av Edwin Catmull och Jim Clark 1978 som en generalisering av bikubiska enhetliga B-splineytor till godtycklig topologi .

2005 fick Edwin Catmull, tillsammans med Tony DeRose och Jos Stam , en Oscar för teknisk prestation för deras uppfinning och applicering av indelningsytor. DeRose skrev om "effektiv, rättvis interpolation" och karaktärsanimering. Stam beskrev en teknik för en direkt utvärdering av gränsytan utan rekursion.

Rekursiv utvärdering

Catmull–Clark-ytor definieras rekursivt med hjälp av följande förfiningsschema.

Börja med ett nät av en godtycklig polyeder . Alla hörn i detta nät ska kallas originalpunkter .

• ansiktspunkt för varje ansikte
  • Ange att varje ansiktspunkt ska vara medelvärdet av alla ursprungliga poäng för respektive ansikte
    

    Ansiktspunkter (blå sfärer)
• kantpunkt för varje kant .
  • Ställ in varje kantpunkt som medelvärdet av de två angränsande ytpunkterna (AF) och mittpunkten på kanten (ME) ${\frac {AF+ME}{2}}$
    

    Kantpunkter (magenta kuber)
• För varje originalpunkt ( P) tar du medelvärdet ( F) av alla n (nyligen skapade) ansiktspunkter för ansikten som rör vid P , och tar medelvärdet (R) av alla n kantmittpunkter för originalkanter som rör P , där varje kantmittpunkt är medelvärdet av dess två ändpunkter (inte att förväxla med nya kantpunkter ovan). (Observera att ur perspektivet av en vertex P är antalet kanter som gränsar till P också antalet intilliggande ytor, därav n )
  • Flytta varje ursprunglig punkt till den nya vertexpunkten ${\displaystyle {\frac {F+2R+(n-3)P}{n}}} ($ Detta är barycentrum för P , R och F med respektive vikt ( n − 3), 2 och 1)
    

    Nya vertexpunkter (gröna koner)
• Forma kanter och ytor i det nya nätet
  • Anslut varje ny ytpunkt till de nya kantpunkterna på alla originalkanter som definierar originalytan
    

    Nya kanter, 4 per framsida
  • Anslut varje ny vertexpunkt till de nya kantpunkterna för alla ursprungliga kanter som faller på den ursprungliga vertexen
    

    3 nya kanter per spetspunkt för förskjutna ursprungliga spetsar
  • Definiera nya ansikten som omslutna av kanter
    

    Sista ansikten till nätet

Egenskaper

Det nya nätet kommer endast att bestå av fyrhörningar , som i allmänhet inte kommer att vara plana . Det nya nätet kommer i allmänhet att se "jämnare" ut (dvs mindre "skakigt" eller "spetsigt") än det gamla nätet. Upprepad indelning resulterar i maskor som blir mer och mer rundade.

Den godtyckligt utseende barycenterformeln valdes av Catmull och Clark baserat på det estetiska utseendet hos de resulterande ytorna snarare än på en matematisk härledning , även om de går långt för att noggrant visa att metoden konvergerar till bikubiska B-splineytor.

Det kan visas att gränsytan som erhålls genom denna förfiningsprocess är minst ${\mathcal {C}}^{1}$ vid extraordinära hörn och ${\mathcal {C}}^ {2}$ överallt annars (när n indikerar hur många derivator som är kontinuerliga talar vi om ${\mathcal {C}}^{n}$ kontinuitet ). Efter en iteration förblir antalet extraordinära punkter på ytan konstant.

Exakt utvärdering

Gränsytan för Catmull–Clarks indelningsytor kan också utvärderas direkt, utan någon rekursiv förfining. Detta kan åstadkommas med hjälp av Jos Stams (1998) teknik . Denna metod omformulerar den rekursiva förfiningsprocessen till ett matrisexponentiellt problem, som kan lösas direkt med hjälp av matrisdiagonalisering .

Programvara som använder algoritmen

• 3ds Max
• 3D-Coat
• AC3D
• Anim8eller
• AutoCAD
• Blandare
• Carrara
• CATIA (Imagine and Shape)
• CGAL
• Cheetah3D
• Cinema4D
• Clara.io
• Creo (Freestyle)
• Daz Studio, 2.0
• DeleD Community Edition
• DeleD Designer
• Gelato
• Hammare
• Sexhörning
• Houdini
• LightWave 3D, version 9
• Makehuman
• Maya
• Metasequoia
• MODO
• Mudbox
• Power Surfacing-tillägg för SolidWorks
• Pixars OpenSubdiv
• PRMan
• Realsoft3D
• Remo 3D
• Skugga
• Rhinoceros 3D - Grasshopper 3D Plugin - Weaverbird Plugin
• Silo
• SketchUp - Kräver en plugin.
• Softimage XSI
• Strata 3D CX
• Vingar 3D
• Zbrush

Se även

• Conway polyhedron notation - En uppsättning relaterade topologiska polyhedron och polygonal mesh operatorer.
• Doo-Sabin indelningsyta
• Slinga indelningsyta

Vidare läsning

•     Derose, T.; Kass, M.; Truong, T. (1998). "Underdelning ytor i karaktärsanimering" (PDF) . Uppdrag från den 25:e årliga konferensen om datorgrafik och interaktiva tekniker - SIGGRAPH '98 . s. 85 . CiteSeerX 10.1.1.679.1198 . doi : 10.1145/280814.280826 . ISBN 978-0897919999 . S2CID 1221330 .
•    Loop, C.; Schäfer, S. (2008). "Uppskattning av Catmull-Clarks indelningsytor med bikubiska fläckar" (PDF) . ACM-transaktioner på grafik . 27 : 1–11. CiteSeerX 10.1.1.153.2047 . doi : 10.1145/1330511.1330519 . S2CID 6068564 .
•    Kovacs, D.; Mitchell, J.; Drone, S.; Zorin, D. (2010). "Realtidsveckade ungefärliga indelningsytor med förskjutningar" ( PDF) . IEEE-transaktioner på visualisering och datorgrafik . 16 (5): 742–51. doi : 10.1109/TVCG.2010.31 . PMID 20616390 . S2CID 17138394 . förtryck
• Matthias Nießner, Charles Loop, Mark Meyer, Tony DeRose, " Feature Adaptive GPU Rendering of Catmull-Clark Subdivision Surfaces ", ACM Transactions on Graphics Volume 31 Issue 1, January 2012, doi : 10.1145 / 2077341.2077347
• Nießner, Matthias ; Slinga, 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 41–44.
• Wade Brainerd, Tessellation i Call of Duty: Ghosts presenterades också som en SIGGRAPH2014 handledning [ 1]
• D. Doo och M. Sabin: Behaviour of rekursiva divisionsytor nära extraordinära punkter , Computer-Aided Design, 10 (6) 356–360 (1978), ( doi , pdf )