Algoritmo Catmull-Clark

El algoritmo Catmull-Clark es una técnica utilizada en gráficos por computadora para crear superficies suaves modelando la subdivisión de superficies . El algoritmo fue desarrollado por Edwin Catmull y James Clark en 1978 como una generalización de superficies B-spline homogéneas bicúbicas para topología arbitraria [1] . En 2005, Edwin Catmull recibió el Premio de la Academia Estadounidense por Logros Técnicos junto con Tony DeRose y Jos Stam por sus desarrollos en la subdivisión de superficies.

Cálculos recursivos

Las superficies de Catmull-Clark se definen recursivamente usando el siguiente esquema de refinamientos sucesivos [1] :

Empezamos con una malla en forma de poliedro arbitrario . Todos los vértices de esta cuadrícula se llamarán puntos iniciales.

• Para cada cara, agregue un punto de cara
  • Elegimos como punto de la cara la media de todos los puntos iniciales de la cara correspondiente .
• Para cada borde, agregue un punto de borde .
  • Elegimos como punto de la arista la media de dos puntos adyacentes de la cara y dos puntos extremos iniciales de la arista .
• Para cada punto de borde , agregue un borde para cada borde de la cara, conectando el punto de borde con el punto de borde para el borde.
• Para cada punto original P , tome el promedio F de todos los n puntos de borde (recién creados) para los bordes que tocan P , y tome el promedio R de todos los n puntos de borde para los bordes (originales) que tocan P , donde el punto medio de cada borde es el promedio de los dos vértices finales (que no debe confundirse con los nuevos "puntos de borde" definidos anteriormente). Mover cada punto de partida a un punto

• Conectamos cada nuevo punto con nuevos puntos de borde de todos los bordes originales que inciden en el vértice original.
• Defina nuevas caras encerradas por nuevas aristas.

La nueva malla consta únicamente de cuadriláteros , que, por lo general, no están en el mismo plano . La nueva malla generalmente se verá más suave que la malla original.

La subdivisión repetida da como resultado una malla más suave. Se puede demostrar que la superficie límite obtenida por este método pertenece al menos a la clase en los puntos singulares y en todos los demás lugares (aquí n significa el número de derivadas continuas cuando hablamos de ). Después de la iteración, el número de puntos singulares en la superficie no cambia.

La fórmula para el baricentro fue elegida por Catmull y Clark por razones estéticas más que matemáticas, aunque Catmull y Clark hicieron todo lo posible para demostrar rigurosamente que el método converge a superficies bicúbicas B-spline [1] .

Cálculos exactos

La superficie Catmull-Clark subdividida resultante se puede obtener directamente sin mejoras sucesivas. Esto se puede hacer usando la técnica de Jos Stam [2] . Este método reformula el proceso de aproximaciones sucesivas al problema de calcular el exponente de la matriz , el cual puede resolverse diagonalizando la matriz .

Software que utiliza subdivisión de superficie Catmull-Clark

• 3ds máximo
• abrigo 3D
• AC3D
• anim8or_
• autocad
• Licuadora
• carrara_
• CATIA
• CGAL
• Guepardo3D
• Cine 4D
• Clara.io_
• Creo (Estilo libre) [3]
• Estudio DAZ 2.0
• Helado
• Martillo
• Hexágono
• Houdini
• K-3D
• LightWave 3D versión 9
• hacerhumano
• maya
• Metasecuoya
• MODO
• Mudbox
• OpenSubdiv de Pixar [4] [5] [6] [7] [8]
• P.R.Man
• Realsoft3D
• 3D
• sombra
• Rhinoceros 3D - Complemento Grasshopper 3D - Complemento Weaverbird
• Silo
• SketchUp : se requiere un complemento.
• Imagen blanda XSI
• 3D CX
• Alas 3D
• ZBrush

Notas

1. ↑ 1 2 3 Catmull y Clark, 1978 , p. 350.
2. ↑ Stam, 1998 , pág. 395–404.
3. ↑ Copia archivada (enlace no disponible) . Consultado el 18 de agosto de 2017. Archivado desde el original el 23 de noviembre de 2016. (indefinido) 
4. ↑ Manuel Kramer. OpenSubdiv: Cómputo y dibujo GPU interoperativos // Subprocesos múltiples para efectos visuales  / Martin Watt, Erwin Coumans, George ElKoura, Ronald Henderson, Manuel Kraemer, Jeff Lait, James Reinders. - Prensa CRC , 2014. - Pág. 163-199. - ISBN 978-1-4822-4356-7 .
5. ↑ Conozca a los expertos: Pixar Animation Studios, The OpenSubdiv Project - YouTube . Consultado el 18 de agosto de 2017. Archivado desde el original el 26 de enero de 2017. (indefinido)
6. ↑ OpenSubdiv V2 de Pixar: una mirada detallada | fxguide . Consultado el 18 de agosto de 2017. Archivado desde el original el 30 de julio de 2017. (indefinido)
7. ↑ Copia archivada . Consultado el 18 de agosto de 2017. Archivado desde el original el 12 de marzo de 2018. (indefinido)
8. ↑ Demostración de OpenSubdiv Blender - YouTube . Consultado el 18 de agosto de 2017. Archivado desde el original el 7 de enero de 2016. (indefinido)

Literatura

• Catmull E., Clark J. Superficies B-spline generadas recursivamente en mallas topológicas arbitrarias  // Diseño asistido por computadora. - 1978. - T. 10 , núm. 6 _ - S. 350 . - doi : 10.1016/0010-4485(78)90110-0 .
• Stam J. Actas de la 25 ª conferencia anual sobre gráficos por computadora y técnicas interactivas - SIGGRAPH '98 . - 1998. - S. 395-404. - ISBN 0-89791-999-8 . -doi : 10.1145/ 280814.280945 . Archivado el 9 de mayo de 2018 en Wayback Machine .

Lectura para leer más

• Derose T., Kass M., Truong T. Superficies de subdivisión en animación de personajes // Actas de la 25.ª conferencia anual sobre gráficos por computadora y técnicas interactivas: SIGGRAPH '98 . - 1998. - S. 85. - ISBN 0897919998 . -doi : 10.1145/ 280814.280826 .
• Loop C., Schaefer S. Aproximación de las superficies de subdivisión de Catmull-Clark con parches bicúbicos  // ACM Transactions on Graphics. - 2008. - T. 27 . - S. 1 . -doi : 10.1145/ 1330511.1330519 .
• Kovacs D., Mitchell J., Drone S., Zorin D. Superficies de subdivisión aproximadas arrugadas en tiempo real con desplazamientos  // Transacciones IEEE sobre visualización y gráficos por computadora. - 2010. - T. 16 , núm. 5 . - S. 742 . -doi : 10.1109/ TVCG.2010.31 . —PMID 20616390 .
• Matthias Niessner, Charles Loop, Mark Meyer, Tony DeRose. Característica Representación de GPU adaptativa de superficies de subdivisión Catmull-Clark  // Transacciones ACM en gráficos. - 2012. - enero ( vol. 31 , número 1 ). -doi : 10.1145/ 2077341.2077347 . , Videoclip
• Niessner Matthias, Loop Charles, Greiner Günther. Evaluación eficiente de pliegues semisuaves en superficies de subdivisión de Catmull-Clark  // Eurographics 2012 Anexo: Documentos breves (Eurographics 2012, Cagliary). - 2012. - S. pp 41-44 .
• Wade Brainard. Teselado en Call of Duty: Ghosts .  (indefinido)Vídeo con el informe,documentoPDF
• Doo D., Sabin M. Comportamiento de superficies de división recursivas cerca de puntos extraordinarios  // Diseño asistido por computadora. - 1978. - T. 10 , núm. 6 _ - doi : 10.1016/0010-4485(78)90111-2 .