Catmull-Clark algoritme

Catmull-Clark- algoritmen er en teknik, der bruges i computergrafik til at skabe glatte overflader ved at modellere overfladeunderinddeling . Algoritmen blev udviklet af Edwin Catmull og James Clark i 1978 som en generalisering af bikubiske homogene B-spline overflader til vilkårlig topologi [1] . I 2005 modtog Edwin Catmull American Academy Award for Technical Achievement sammen med Tony DeRose og Jos Stam for deres udvikling inden for overfladeinddeling.

Rekursive beregninger

Catmull-Clark-overflader defineres rekursivt ved hjælp af følgende skema med successive raffinementer [1] :

Vi starter med et net i form af et vilkårligt polyeder . Alle hjørner af dette gitter vil blive kaldt startpunkter.

Tilføj et ansigtspunkt for hvert ansigt
- Vi vælger som ansigtspunktet gennemsnittet af alle indledende punkter på det tilsvarende ansigt .
Tilføj et kantpunkt for hver kant .
- Vi vælger som kantpunkt gennemsnittet af to tilstødende punkter på ansigtet og to indledende endepunkter på kanten .
For hvert kantpunkt skal du tilføje en kant for hver kant af ansigtet, der forbinder kantpunktet med kantpunktet for kanten.
For hvert oprindelige punkt P tages gennemsnittet F af alle n (nyoprettede) kantpunkter for de kanter, der rører P , og tage det gennemsnitlige R for alle n kantpunkter for de (oprindelige) kanter, der rører P , hvor midtpunktet af hver kant er gennemsnittet af de to endepunkter (ikke at forveksle med de nye "kantpunkter" defineret ovenfor). Flyt hvert startpunkt til et punkt

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

Dette punkt er barycentret for punkterne P , R og F med vægte ( n − 3), 2 og 1.

Vi forbinder hvert nyt punkt med nye kantpunkter af alle originale kanter, der falder ind på det oprindelige toppunkt.
Definer nye ansigter omgivet af nye kanter.

Det nye net består kun af firkanter , som generelt set ikke er i samme plan . Det nye mesh vil generelt se glattere ud end det originale mesh.

Gentagen underopdeling resulterer i et glattere mesh. Det kan påvises, at grænsefladen opnået ved denne metode i det mindste tilhører klassen i entalspunkterne og alle andre steder (her betyder n antallet af kontinuerte afledte, når vi taler om ). Efter iteration ændres antallet af enkeltpunkter på overfladen ikke. ${\mathcal {C}}^{1}$ ${\mathcal {C}}^{2}$ ${\mathcal {C}}^{n}$

Formlen for barycenteret blev valgt af Catmull og Clark af æstetiske snarere end matematiske årsager, selvom Catmull og Clark gjorde meget for at bevise, at metoden konvergerer til bikubiske B-spline overflader [1] .

Præcise beregninger

Den resulterende underopdelte Catmull-Clark overflade kan opnås direkte uden successive forbedringer. Dette kan gøres ved hjælp af Jos Stam-teknikken [2] . Denne metode omformulerer processen med successive tilnærmelser til problemet med at beregne eksponenten af matrixen , som kan løses ved at diagonalisere matrixen .

Software, der bruger Catmull-Clark overfladeunderinddeling

3ds Max
3D frakke
AC3D
Anima8eller
AutoCAD
Blender
Carrara
CATIA
CGAL
Cheetah3D
Cinema 4D
Clara.io
Creo (Freestyle) [3]
DAZ Studio 2.0
Gelato
Hammer
Sekskant
Houdini
K-3D
LightWave 3D version 9
Makehuman
Maya
Metasequoia
MODO
Mudbox
Pixars OpenSubdiv [4] [5] [6] [7] [8]
P.R.Man
Realsoft3D
3D
skygge
Rhinoceros 3D - Grasshopper 3D Plugin - Weaverbird Plugin
Silo
SketchUp - Plugin påkrævet.
Softimage XSI
3D CX
Vinger 3D
Zbrush

Noter

↑ 1 2 3 Catmull og Clark, 1978 , s. 350.
↑ Stam, 1998 , s. 395-404.
↑ Arkiveret kopi (link ikke tilgængeligt) . Hentet 18. august 2017. Arkiveret fra originalen 23. november 2016. (ubestemt)
↑ 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. - S. 163-199. - ISBN 978-1-4822-4356-7 .
↑ Mød eksperterne: Pixar Animation Studios, The OpenSubdiv Project - YouTube . Hentet 18. august 2017. Arkiveret fra originalen 26. januar 2017. (ubestemt)
↑ Pixars OpenSubdiv V2: et detaljeret udseende | fxguide . Hentet 18. august 2017. Arkiveret fra originalen 30. juli 2017. (ubestemt)
↑ Arkiveret kopi . Hentet 18. august 2017. Arkiveret fra originalen 12. marts 2018. (ubestemt)
↑ OpenSubdiv Blender demo - YouTube . Hentet 18. august 2017. Arkiveret fra originalen 7. januar 2016. (ubestemt)

Litteratur

Catmull E., Clark J. Rekursivt genererede B-spline overflader på vilkårlige topologiske masker // Computer-Aided Design. - 1978. - T. 10 , no. 6 . - S. 350 . - doi : 10.1016/0010-4485(78)90110-0 .
Stam J. Proceedings af den 25. årlige konference om computergrafik og interaktive teknikker - SIGGRAPH '98 . - 1998. - S. 395-404. - ISBN 0-89791-999-8 . - doi : 10.1145/280814.280945 . Arkiveret 9. maj 2018 på Wayback Machine

Læsning for yderligere læsning

Derose T., Kass M., Truong T. Inddelingsflader i karakteranimation // 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 underinddelingsoverflader med bikubiske patches // ACM Transactions on Graphics. - 2008. - T. 27 . - S. 1 . - doi : 10.1145/1330511.1330519 .
Kovacs D., Mitchell J., Drone S., Zorin D. Real-Time Creased Approximate Subdivision Surfaces with Displacements // IEEE Transactions on Visualization and Computer Graphics. - 2010. - T. 16 , no. 5 . - S. 742 . - doi : 10.1109/TVCG.2010.31 . — PMID 20616390 .
Matthias Niessner, Charles Loop, Mark Meyer, Tony DeRose. Funktioner Adaptiv GPU-gengivelse af Catmull-Clark-underinddelingsoverflader // ACM-transaktioner på grafik. - 2012. - Januar ( bind 31 , hæfte 1 ). - doi : 10.1145/2077341.2077347 . , Videoklip
Niessner Matthias, Loop Charles, Greiner Günther. Effektiv evaluering af semi-glatte folder i Catmull-Clark underopdelingsoverflader // Eurographics 2012 Annex: Short Papers (Eurographics 2012, Cagliary). - 2012. - S. s. 41-44 .
Wade Brainard. Tessellation i Call of Duty: Ghosts . (ubestemt)Video med rapporten,PDFdokument
Doo D., Sabin M. Opførsel af rekursive divisionsflader nær ekstraordinære punkter // Computer-Aided Design. - 1978. - T. 10 , no. 6 . - doi : 10.1016/0010-4485(78)90111-2 .