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
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.
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
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
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 .