Superficie de subdivisión Catmull – Clark - Catmull–Clark subdivision surface

Subdivisión de nivel 3 de Catmull – Clark de un cubo con la superficie de subdivisión límite que se muestra a continuación. (Tenga en cuenta que, aunque parece que la interpolación bicúbica se acerca a una esfera , una esfera real es cuadrática ).

Diferencia visual entre la esfera (verde) y la superficie de subdivisión Catmull-Clark (magenta) de un cubo

El algoritmo Catmull-Clark es una técnica utilizada en gráficos por computadora en 3D para crear superficies curvas mediante el modelado de superficies de subdivisión . Fue ideado por Edwin Catmull y Jim Clark en 1978 como una generalización de bi-cúbico uniforme B-spline superficies a arbitraria topología .

En 2005, Edwin Catmull, junto con Tony DeRose y Jos Stam , recibieron un Premio de la Academia por Logros Técnicos por su invención y aplicación de superficies de subdivisión. DeRose escribió sobre "interpolación justa y eficiente" y animación de personajes. Stam describió una técnica para una evaluación directa de la superficie límite sin recursividad.

Evaluación recursiva

Las superficies de Catmull-Clark se definen de forma recursiva , utilizando el siguiente esquema de refinamiento.

Comience con una malla de un poliedro arbitrario . Todos los vértices de esta malla se denominarán puntos originales .

• Para cada cara, agregue un punto de cara
  • Establezca cada punto de la cara para que sea el promedio de todos los puntos originales para la cara respectiva
    

    Puntos faciales (esferas azules)
• Para cada borde, agregue un punto de borde .
  • Establezca cada punto de borde para que sea el promedio de los dos puntos frontales vecinos y sus dos extremos originales
    

    Puntos de borde (cubos magenta)
• Para cada punto original ( P) , tome el promedio ( F) de todos los n puntos de cara (creados recientemente) para las caras que tocan P , y tome el promedio (R) de todos los n puntos medios de los bordes para los bordes originales que tocan P , donde cada punto medio de los bordes es el promedio de sus dos vértices de punto final (que no debe confundirse con los nuevos puntos de borde anteriores). (Tenga en cuenta que desde la perspectiva de un vértice P , el número de aristas vecinas a P es también el número de caras adyacentes, por lo tanto, n )
  • Mueva cada punto original al nuevo punto de vértice (Este es el baricentro de P , R y F con pesos respectivos ( n - 3), 2 y 1)${\ Displaystyle {\ frac {F + 2R + (n-3) P} {n}}}$
    

    Nuevos puntos de vértice (conos verdes)
• Formar bordes y caras en la nueva malla
  • Conecte cada nuevo punto de cara a los nuevos puntos de borde de todos los bordes originales que definen la cara original
    

    Nuevos bordes, 4 por punto de cara
  • Conecte cada nuevo punto de vértice a los nuevos puntos de borde de todos los bordes originales incidentes en el vértice original
    

    3 aristas nuevas por punto de vértice de los vértices originales desplazados
  • Definir caras nuevas encerradas por aristas
    

    Caras finales a la malla

Propiedades

La nueva malla estará formada únicamente por cuadriláteros , que en general no serán planos . La nueva malla generalmente se verá "más suave" (es decir, menos "dentada" o "puntiaguda") que la antigua. La subdivisión repetida da como resultado mallas cada vez más redondeadas.

La fórmula del baricentro de aspecto arbitrario fue elegida por Catmull y Clark basándose en la apariencia estética de las superficies resultantes más que en una derivación matemática , aunque hacen todo lo posible para mostrar rigurosamente que el método converge a superficies bicúbicas B-spline.

Se puede demostrar que la superficie límite obtenida por este proceso de refinamiento es al menos en vértices extraordinarios y en cualquier otro lugar (cuando n indica cuántas derivadas son continuas , hablamos de continuidad ). Después de una iteración, el número de puntos extraordinarios en la superficie permanece constante. ${\ Displaystyle {\ mathcal {C}} ^ {1}}$${\ Displaystyle {\ mathcal {C}} ^ {2}}$${\ Displaystyle {\ mathcal {C}} ^ {n}}$

Evaluación exacta

La superficie límite de las superficies de subdivisión de Catmull-Clark también se puede evaluar directamente, sin ningún refinamiento recurrente. Esto se puede lograr mediante la técnica de Jos Stam (1998). Este método reformula el proceso de refinamiento recursivo en un problema matricial exponencial , que puede resolverse directamente mediante la diagonalización matricial .

Software que utiliza el algoritmo

Ver también

• Notación de poliedro de Conway : un conjunto de poliedros topológicos relacionados y operadores de malla poligonal.
• Superficie de subdivisión Doo-Sabin
• Superficie de subdivisión de bucle

Referencias

Otras lecturas

• Derose, T .; Kass, M .; Truong, T. (1998). "Superficies de subdivisión en animación de personajes" (PDF) . Actas de la 25ª conferencia anual sobre gráficos por ordenador y técnicas interactivas - SIGGRAPH '98 . pp.  85 . CiteSeerX  10.1.1.679.1198 . doi : 10.1145 / 280814.280826 . ISBN 978-0897919999. S2CID  1221330 .
• Bucle, C .; Schaefer, S. (2008). "Aproximación de superficies de subdivisión de Catmull-Clark con parches bicúbicos" (PDF) . Transacciones ACM en gráficos . 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). "Superficies de subdivisión aproximadas arrugadas en tiempo real con desplazamientos" (PDF) . Transacciones IEEE sobre visualización y gráficos por computadora . 16 (5): 742–51. doi : 10.1109 / TVCG.2010.31 . PMID  20616390 . S2CID  17138394 . preimpresión
• Matthias Nießner, Charles Loop, Mark Meyer, Tony DeRose, " Representación de GPU adaptable a funciones de superficies de subdivisión Catmull-Clark ", ACM Transactions on Graphics Volume 31 Issue 1, enero de 2012, doi : 10.1145 / 2077341.2077347 , demostración
• Nießner, Matthias; Loop, Charles; Greiner, Günther: Evaluación eficiente de pliegues semi-lisos en superficies de subdivisión Catmull-Clark : Eurographics 2012 Anexo: Documentos breves (Eurographics 2012, Cagliary). 2012, págs. 41–44.
• Wade Brainerd, Tessellation en Call of Duty: Ghosts también se presentó como un tutorial de SIGGRAPH2014 [1]
• D. Doo y M. Sabin: Comportamiento de superficies de división recursiva cerca de puntos extraordinarios , Diseño asistido por computadora, 10 (6) 356–360 (1978), ( doi , pdf )