Algoritmul Catmull-Clark

Algoritmul Catmull-Clark este o tehnică utilizată în grafica computerizată pentru a crea suprafețe netede prin modelarea subdiviziunii suprafeței . Algoritmul a fost dezvoltat de Edwin Catmull și James Clark în 1978 ca o generalizare a suprafețelor B-spline omogene bicubice pentru topologie arbitrară [1] . În 2005, Edwin Catmull a primit premiul Academiei americane pentru performanță tehnică împreună cu Tony DeRose și Jos Stam pentru dezvoltarea lor în subdiviziunea suprafeței.

Calcule recursive

Suprafețele Catmull-Clark sunt definite recursiv folosind următoarea schemă de rafinare succesive [1] :

Începem cu o plasă sub forma unui poliedru arbitrar . Toate vârfurile acestei grile vor fi numite puncte inițiale.

• Pentru fiecare față, adăugați un punct de față
  • Alegem ca punct al feței media tuturor punctelor inițiale ale feței corespunzătoare .
• Pentru fiecare margine, adăugați un punct de margine .
  • Alegem ca punct de margine media a două puncte adiacente ale feței și a două puncte finale inițiale ale marginii .
• Pentru fiecare punct de margine , adăugați o margine pentru fiecare margine a feței, conectând punctul de margine la punctul de margine pentru margine.
• Pentru fiecare punct original P , luați media F a tuturor n puncte de margine (nou create) pentru marginile care ating P , și luați media R a tuturor n puncte de margine pentru marginile (originale) care ating P , unde punctul de mijloc al fiecărei margini este media celor două vârfuri de capăt (a nu se confunda cu noile „puncte de margine” definite mai sus). Mutați fiecare punct de plecare la un punct

• Conectăm fiecare punct nou cu puncte noi de margine ale tuturor muchiilor originale incidente la vârful original.
• Definiți fețe noi închise de muchii noi.

Noua plasă este formată doar din patrulatere , care, în general, nu sunt în același plan . Noua plasă va arăta în general mai netedă decât plasa originală.

Subdiviziunea repetată are ca rezultat o plasă mai netedă. Se poate arăta că suprafața limită obținută prin această metodă aparține cel puțin clasei la punctele singulare și în toate celelalte locuri (aici n înseamnă numărul de derivate continue când vorbim de ). După iterație, numărul de puncte singulare de pe suprafață nu se modifică.

Formula baricentrului a fost aleasă de Catmull și Clark din motive mai degrabă estetice decât matematice, deși Catmull și Clark au făcut eforturi mari pentru a demonstra riguros că metoda converge către suprafețele B-spline bicubice [1] .

Calcule exacte

Suprafața Catmull-Clark subdivizată rezultată poate fi obținută direct fără îmbunătățiri succesive. Acest lucru se poate face folosind tehnica Jos Stam [2] . Această metodă reformulează procesul de aproximări succesive în problema calculului exponentului matricei , care poate fi rezolvată prin diagonalizarea matricei .

Software care utilizează subdiviziunea suprafeței Catmull-Clark

• 3ds Max
• Haina 3D
• AC3D
• Anim8or
• AutoCAD
• Blender
• Carrara
• CATIA
• CGAL
• Ghepard3D
• Cinema 4D
• Clara.io
• Creo (Freestyle) [3]
• DAZ Studio 2.0
• gelato
• Ciocan
• hexagon
• Houdini
• K-3D
• LightWave 3D versiunea 9
• Makehuman
• Maya
• Metasequoia
• MODO
• Mudbox
• OpenSubdiv de la Pixar [4] [5] [6] [7] [8]
• P.R.Man
• Realsoft3D
• 3D
• umbra
• Rhinoceros 3D - Plugin Grasshopper 3D - Plugin Weaverbird
• Siloz
• SketchUp - Este necesar un plugin.
• Softimage XSI
• 3D CX
• Aripi 3D
• Zbrush

Note

1. ↑ 1 2 3 Catmull și Clark, 1978 , p. 350.
2. ↑ Stam, 1998 , p. 395–404.
3. ↑ Copie arhivată (link nu este disponibil) . Preluat la 18 august 2017. Arhivat din original la 23 noiembrie 2016. (nedefinit) 
4. ↑ Manuel Kraemer. OpenSubdiv: Calcul și desenarea GPU interoperabile // Multithreading pentru efecte vizuale  / 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 .
5. ↑ Meet the Experts: Pixar Animation Studios, The OpenSubdiv Project - YouTube . Preluat la 18 august 2017. Arhivat din original la 26 ianuarie 2017. (nedefinit)
6. ↑ OpenSubdiv V2 de la Pixar: o privire detaliată | fxguide . Preluat la 18 august 2017. Arhivat din original la 30 iulie 2017. (nedefinit)
7. ↑ Copie arhivată . Preluat la 18 august 2017. Arhivat din original la 12 martie 2018. (nedefinit)
8. ↑ OpenSubdiv Blender demo - YouTube . Preluat la 18 august 2017. Arhivat din original la 7 ianuarie 2016. (nedefinit)

Literatură

• Catmull E., Clark J. Suprafețe B-spline generate recursiv pe rețele topologice arbitrare  // Computer-Aided Design. - 1978. - T. 10 , nr. 6 . - S. 350 . - doi : 10.1016/0010-4485(78)90110-0 .
• Stam J. Proceedings of the 25th annual Conference on Computer graphics and interactive techniques - SIGGRAPH '98 . - 1998. - S. 395-404. - ISBN 0-89791-999-8 . - doi : 10.1145/280814.280945 . Arhivat pe 9 mai 2018 la Wayback Machine

Lectură pentru lecturi suplimentare

• Derose T., Kass M., Truong T. Subdivision surfaces in character animation // 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. Aproximarea suprafețelor de subdiviziune Catmull-Clark cu patch-uri bicubice  // 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 , nr. 5 . - S. 742 . - doi : 10.1109/TVCG.2010.31 . — PMID 20616390 .
• Matthias Niessner, Charles Loop, Mark Meyer, Tony DeRose. Caracteristică Redarea GPU adaptivă a suprafețelor de subdiviziune Catmull-Clark  // Tranzacții ACM pe grafică. - 2012. - ianuarie ( vol. 31 , numărul 1 ). - doi : 10.1145/2077341.2077347 . , Clip video
• Niessner Matthias, Loop Charles, Greiner Günther. Evaluare eficientă a cutelor semi-netede în suprafețele de subdiviziune Catmull-Clark  // Eurographics 2012 Anexă: Lucrări scurte (Eurographics 2012, Cagliary). - 2012. - S. pp 41-44 .
• Wade Brainard. Tesselare în Call of Duty: Ghosts .  (nedefinit)Video cu raportul,documentPDF
• Doo D., Sabin M. Comportamentul suprafețelor de diviziune recursive în apropierea punctelor extraordinare  // Computer-Aided Design. - 1978. - T. 10 , nr. 6 . - doi : 10.1016/0010-4485(78)90111-2 .