Existe uma maneira eficiente \ fácil de desenhar um polígono côncavo em Direct3d

Question

Eu estou tentando desenhar um polígono usando c # e DirectX

Tudo que eu vejo é uma lista ordenada de pontos de um arquivo e eu preciso para desenhar o polígono simples em um mundo 3D.

Eu posso carregar os pontos e desenhar uma forma convexa usando um trianglefan e drawuserprimitives.

Isto, obviamente, leva a resultados incorretos quando o polígono é muito côncava (que pode ser).

Eu não posso imaginar que eu sou a única pessoa a lidar com este problema (tho eu sou um gfx / DirectX neófito - Minha formação é em gui \ windows desenvolvimento de aplicações).

Alguém pode me apontar para um simples de seguir recursos \ tutorial \ algoritmo que pode me ajudar?

Answer 1

Direct3D só pode desenhar triângulos (bem, ele pode desenhar linhas e pontos também, mas isso é além do ponto). Então, se você quiser chamar qualquer forma que é mais complexo do que um triângulo, você tem que desenhar um monte de triângulos tocantes que igual a essa forma.

No seu caso, é um problema polígono triangulação côncava. Dado um monte de vértices, você pode mantê-los como é, você só precisa calcular o "tampão de índice" (no caso mais simples, três índices per triângulo que digamos que vértices os usos triângulo). Em seguida, desenhe que mediante a colocação em tampões vértice / ou índice usando DrawUserPrimitives.

Alguns algoritmos para triangulação simples (convexa ou côncava, mas sem auto-interseções ou buracos) polígonos estão em VTerrain local .

Eu tenho usado o código de Ratcliff no passado; muito simples e funciona bem. VTerrain tem um link morto a ele; o código pode ser encontrada aqui . É do C ++, mas portar que, ao longo de C # deve ser simples.

Oh, e não use ventiladores triângulo. Eles são de uso muito limitado, ineficiente e estão indo embora em breve (por exemplo Direct3D 10 não apoiá-los mais). listas apenas o uso de triângulo.

Answer 2

A triangulação é que ele resposta óbvia, mas é difícil para escrever um triangulador sólida. A menos que você tem duas vezes mês para desperdiçar nem sequer tentar.

Há um par de códigos que podem ajudá-lo:

A Biblioteca GPC. Muito fácil de usar, mas você não pode gostar dele de licença:

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

Há também triângulo:

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

E PUNHO:

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

Outra opção (e meu preferido) seria usar o tesselator GLU. Você pode carregar e usar a biblioteca GLU de programas DirectX muito bem. Ela não precisa de um contexto OpenGL para usá-lo e é pré-instalado em todas as máquinas Windows. Se você quiser fonte que você pode levantar o código triangulação da implementação de referência SGI. Eu fiz isso uma vez e ele me levou apenas um par de horas.

Até agora para triangulação. Há uma maneira diferente, bem como:. Você pode usar truques estêncil

O algoritmo geral é assim:

escreve

1. cor- Disable e profundidade. Ativar gravações estêncil e configurar o seu buffer de estêncil que ele irá inverter o valor stencil atual. Um pouco de estêncil é suficiente. Oh - o buffer estêncil devem ser apuradas bem

.

2. Escolha um ponto aleatório na tela. Qualquer fará. Chame esse ponto de sua âncora.

3. Para cada borda de seu polígono construir um triângulo a partir dos dois vértices que constroem a borda e sua âncora. Desenhar esse triângulo.

4. Uma vez que você tenha desenhado todos esses triângulos, desligue escrita estêncil, ligue teste de stencil e cor-escrever e desenhar um quad tela cheia em sua cor de escolha. Isto irá preencher apenas os pixels dentro do seu polígono convexo.

É uma boa idéia colocar a âncora para o meio do polígono e apenas desenhar um retângulo do tamanho da caixa de limite de seu polígono. Isso economiza um pouco de taxa de preenchimento.

Btw -. A técnica do estêncil trabalha para polígonos auto-interseção bem

Hope isso ajuda, Nils

Answer 3

Se você é capaz de usar o buffer estêncil, ele não deve ser difícil de fazer. Aqui está um algoritmo geral:

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 "direito de s" Quero dizer a partir da perspectiva de alguém de pé em v [i] e de frente para v [i + 1]. Isso pode ser testado usando um produto cruzado:

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

Answer 4

Eu apenas tive que fazer isso para um projeto. O mais simples algoritmo que encontrei é chamado de "Clipping Ear". Um grande papel nele está aqui: TriangulationByEarClipping.pdf

Eu me levou cerca de 250 linhas de código C ++ e 4 horas para implementar a versão força bruta do mesmo. Outros algoritmos têm melhor desempenho, mas esta era simples de implementar e entender.