¿Existe una forma eficaz y sencilla de dibujar un polígono cóncavo en Direct3d?

Question

Estoy intentando dibujar un polígono usando C# y DirectX.

Todo lo que obtengo es una lista ordenada de puntos de un archivo y necesito dibujar el polígono plano en un mundo 3D.

Puedo cargar los puntos y dibujar una forma convexa usando un ventilador triangular y dibujando primitivas de usuario.

Obviamente, esto conduce a resultados incorrectos cuando el polígono es muy cóncavo (que puede serlo).

No puedo imaginar que sea la única persona que se enfrenta a este problema (aunque soy un neófito de gfx/directx; mi experiencia es en el desarrollo de aplicaciones gui\windows).

¿Alguien puede indicarme un recurso utorial\algoritmo fácil de seguir que pueda ayudarme?

Answer 1

Direct3D sólo puede dibujar triángulos (bueno, también puede dibujar líneas y puntos, pero eso no viene al caso).Entonces, si quieres dibujar cualquier forma que sea más compleja que un triángulo, debes dibujar un montón de triángulos que se toquen y que sean iguales a esa forma.

En su caso, es un problema de triangulación de polígonos cóncavos.Dado un conjunto de vértices, puede mantenerlos como están, solo necesita calcular el "búfer de índice" (en el caso más simple, tres índices por triángulo que indican qué vértices usa el triángulo).Luego dibuje eso colocándolo en buffers de vértice/índice o usando DrawUserPrimitives.

Algunos algoritmos para triangular polígonos simples (convexos o cóncavos, pero sin autointersecciones ni agujeros) están en Sitio VTerrain.

He usado el código de Ratcliff en el pasado;muy simple y funciona bien.VTerrain tiene un vínculo inactivo;el código se puede encontrar aquí.Es C++, pero trasladarlo a C# debería ser sencillo.

Ah, y no uses abanicos triangulares.Son de uso muy limitado, ineficaces y desaparecerán pronto (p. ej.Direct3D 10 ya no los admite).Simplemente use listas triangulares.

Answer 2

La triangulación es la respuesta obvia, pero es difícil escribir un triangulador sólido.A menos que tengas dos meses para perder, ni siquiera lo intentes.

Hay un par de códigos que pueden ayudarte:

La biblioteca GPC.Muy fácil de usar, pero puede que no te guste su licencia:

http://www.cs.man.ac.uk/~toby/alan/software/gpc.html

También hay un triángulo:

http://www.cs.cmu.edu/~quake/triangle.html

Y PUÑO:

http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html

Otra opción (y mi preferida) sería utilizar el teselador GLU.Puede cargar y utilizar la biblioteca GLU desde programas DirectX sin problemas.No necesita un contexto OpenGL para usarlo y está preinstalado en todas las máquinas con Windows.Si desea una fuente, puede extraer el código de triangulación de la implementación de referencia de SGI.Lo hice una vez y me llevó sólo un par de horas.

Hasta aquí para la triangulación.También hay una forma diferente:Puedes usar trucos de plantillas.

El algoritmo general es el siguiente:

1. Desactive las escrituras de color y profundidad.Habilite las escrituras de plantilla y configure su búfer de plantilla para que invierta el valor actual de la plantilla.Un poco de plantilla es suficiente.Oh, el búfer de tu plantilla también debería borrarse.

2. Elige un punto aleatorio en la pantalla.Cualquiera servirá.Llama a este punto tu ancla.

3. Para cada borde de tu polígono, construye un triángulo a partir de los dos vértices que forman el borde y tu ancla.Dibuja ese triángulo.

4. Una vez que haya dibujado todos estos triángulos, desactive la escritura de plantilla, active la prueba de plantilla y la escritura de colores y dibuje un quad en pantalla completa en el color que elija.Esto llenará solo los píxeles dentro de su polígono convexo.

Es una buena idea colocar el ancla en el medio del polígono y simplemente dibujar un rectángulo tan grande como el cuadro límite de su polígono.Eso ahorra un poco de tasa de relleno.

Por cierto, la técnica de la plantilla también funciona para polígonos que se cruzan entre sí.

Espero que ayude, nils

Answer 3

Si puede utilizar el buffer de plantillas, no debería ser difícil hacerlo.Aquí hay un algoritmo general:

Clear the stencil buffer to 1.
Pick an arbitrary vertex v0, probably somewhere near the polygon to reduce floating-point errors.
For each vertex v[i] of the polygon in clockwise order:
    let s be the segment v[i]->v[i+1] (where i+1 will wrap to 0 when the last vertex is reached)
    if v0 is to the "right" of s:
        draw a triangle defined by s, v[i], v[i+1] that adds 1 to the stencil buffer
    else
        draw a triangle defined by s, v[i], v[i+1] that subtracts 1 from the stencil buffer
end for
fill the screen with the desired color/texture, testing for stencil buffer values >= 2.

Por "derecho de s" me refiero a la perspectiva de alguien parado en v[i] y mirando a v[i+1].Esto se puede probar usando un producto cruzado:

cruz(v0 - v[i], v[i+1] - v[i]) > 0

Answer 4

Sólo tenía que hacer esto para un proyecto.El algoritmo más simple que encontré se llama "Recorte de oreja".Un gran artículo al respecto está aquí: TriangulaciónPorEarClipping.pdf

Me tomó alrededor de 250 líneas de código C++ y 4 horas para implementar la versión de fuerza bruta.Otros algoritmos tienen mejor rendimiento, pero este fue sencillo de implementar y comprender.