Descomponiendo una malla cóncava en un conjunto de mallas convexas

Me gustaría poder descomponer una malla cóncava en un conjunto de mallas convexas por 2 razones:

1. Renderizado transparente
2. Formas físicas

¿Existe algún algoritmo que tome un conjunto de triángulos (cóncavos) como entrada y genere varios conjuntos de triángulos (convexos)? Me gustaría que no rellene los agujeros entre las partes de la malla original.

Ya me he encontrado con una pequeña idea: encontrar todos los bordes cóncavos y dividir las mallas a lo largo de los bucles de los bordes. ¿Estoy en el camino correcto? ¿Cómo podría implementar esto?

Diría que está en el camino correcto, pero encontrar un algoritmo óptimo y / o eficiente es otra cuestión: es un problema difícil. Sin embargo, a menos que su interés sea académico, una solución lo suficientemente buena puede ser suficiente.

Primero, si no está interesado en encontrar su propia solución, CGAL ya contiene un algoritmo para la descomposición de poliedros convexos: http://doc.cgal.org/latest/Convex_decomposition_3/index.html

Ahora para el método; Al igual que muchos problemas en 3D, a menudo es útil considerar el problema 2D que es más fácil de entender. Para 2D, la tarea es identificar los vértices reflejos y dividir el polígono en dos creando un nuevo borde (y posiblemente nuevos vértices) a partir de ese vértice reflejo, y continuar hasta que quede sin vértices reflejos (y, por lo tanto, polígonos totalmente convexos). )

La descomposición poligonal de J. Mark Keil contiene el siguiente algoritmo (en forma no optimizada):

diags = decomp(poly)
    min, tmp : EdgeList
    ndiags : Integer
    for each reflex vertex i
        for every other vertex j
            if i can see j
                left = the polygon given by vertices i to j
                right = the polygon given by vertices j to i
                tmp = decomp(left) + decomp(right)
                if(tmp.size < ndiags)
                    min = tmp
                    ndiags = tmp.size
                    min += the diagonal i to j
    return min

Básicamente, compara exhaustivamente todas las particiones posibles y devuelve la que tiene menos diagonales producidas. En este sentido, es algo brutal y óptimo.

Si desea descomposiciones "más bonitas", es decir, las que producen formas más compactas en lugar de alargadas, también podría considerar esta producida por Mark Bayazit , que es codiciosa (por lo tanto, mucho más rápida) y se ve mejor, pero tiene algunas deficiencias. Básicamente funciona tratando de conectar los vértices reflejos al mejor opuesto, típicamente a otro vértice reflejo:

Una de las deficiencias es que ignora las "mejores" descomposiciones al crear puntos Steiner (puntos que no existen en un borde existente):

El problema en 3D puede ser similar; en lugar de vértices reflejos, identifica "bordes de muesca". Una implementación ingenua sería identificar bordes de muesca y realizar cortes planos en el poliedro repetidamente hasta que todos los poliedros sean convexos. Echa un vistazo a "convexo particiones de poliedros: un límite inferior y peor de los casos óptima Algoritmo" por Bernard Chazelle para más detalles.

Tenga en cuenta que este enfoque podría producir en el peor de los casos un número exponencial de subpoliedros. Esto se debe a que podría tener casos degenerados como este:

Pero si tiene una malla no trivial (piense en una superficie con baches), obtendrá malos resultados de todos modos. Es muy probable que desee hacer muchas simplificaciones de antemano, si alguna vez necesita usar esto para mallas complejas.

Calcular una descomposición convexa exacta de una superficie S es un problema NP-difícil y generalmente produce una gran cantidad de grupos. Para superar estas limitaciones, la restricción de convexidad exacta se puede relajar y en su lugar se calcula una descomposición convexa aproximada de S. Aquí, el objetivo es determinar una partición de los triángulos de malla con un número mínimo de grupos, al tiempo que se garantiza que cada grupo tenga una concavidad inferior al umbral definido por el usuario.

Consulte las siguientes bibliotecas aproximadas de descomposición convexa: https://code.google.com/p/v-hacd/ http://sourceforge.net/projects/hacd/

Aquí hay un código que podría ayudarlo. Está en Java, por lo que deberá convertirlo a c ++.

Aquí también hay otro artículo que puede ayudarte