Existe-t-il un moyen efficace \ facile de dessiner un polygone concave dans Direct3d

Question

J'essaie de dessiner un polygone en utilisant c # et directx

Tout ce que je reçois est une liste ordonnée de points d'un fichier et je dois dessiner le polygone plat dans un monde en 3D.

Je peux charger les points et dessiner une forme convexe à l’aide d’un trianglefan et de drawuserprimitives.

Cela conduit évidemment à des résultats incorrects lorsque le polygone est très concave (ce qui peut être le cas).

Je ne peux pas imaginer que je suis la seule personne à lutter contre ce problème (bien que je sois un néophyte gfx / directx - mon expérience est dans le développement d'applications gui \ windows).

Quelqu'un peut-il m'indiquer une ressource \ tutoriel \ algorithme simple à suivre qui pourrait m'aider?

Answer 1

Direct3D ne peut dessiner que des triangles (eh bien, il peut également dessiner des lignes et des points, mais c’est à côté du point). Donc, si vous voulez dessiner une forme plus complexe qu'un triangle, vous devez dessiner un tas de triangles touchants qui correspondent à cette forme.

Dans votre cas, il s’agit d’un problème concave de triangulation de polygone. Avec un tas de sommets, vous pouvez les conserver tels quels, il vous suffit de calculer le "tampon d'index" (Dans le cas le plus simple, trois index par triangle indiquant les sommets utilisés par le triangle). Puis dessinez-le en le mettant dans les tampons vertex / index ou en utilisant DrawUserPrimitives.

Certains algorithmes permettant de trianguler des polygones simples (convexes ou concaves, mais sans auto-intersections ni trous) se trouvent à site VTerrain .

J'ai déjà utilisé le code de Ratcliff; très simple et fonctionne bien. VTerrain a un lien mort avec elle; le code peut être trouvé ici . C'est du C ++, mais le porter sur C # devrait être simple.

Oh, et n'utilisez pas de ventilateurs triangulaires. Ils sont d’une utilisation très limitée, inefficace et disparaissent bientôt (par exemple, Direct3D 10 ne les prend plus en charge). Utilisez simplement des listes de triangles.

Answer 2

La triangulation est la réponse évidente, mais il est difficile d’écrire un triangulateur solide. N'essayez même pas, à moins que vous ayez deux mois à perdre.

Quelques codes peuvent vous aider:

La bibliothèque GPC. Très facile à utiliser, mais vous n’aimerez peut-être pas sa licence:

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

Il y a aussi un triangle:

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

Et FIST:

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

Une autre option (et celle que je préfère) serait d'utiliser le tesselator GLU. Vous pouvez charger et utiliser parfaitement la bibliothèque GLU à partir de programmes DirectX. Il n'a pas besoin d'un contexte OpenGL pour l'utiliser et il est pré-installé sur toutes les machines Windows. Si vous voulez une source, vous pouvez extraire le code de triangulation de l'implémentation de référence SGI. Je l'ai fait une fois et cela ne m'a pris que quelques heures.

Jusqu'ici pour la triangulation. Il existe également une autre méthode: vous pouvez utiliser des tours de pochoir.

L'algorithme général va comme ceci:

1. Désactivez les écritures en couleur et en profondeur. Activez les écritures de gabarit et configurez votre tampon de gabarit de manière à inverser la valeur actuelle du gabarit. Un peu de pochoir suffit. Oh, votre tampon de pochoir doit également être effacé.

2. Choisissez un point au hasard sur l'écran. Tout va faire. Appelez ce point votre ancre.

3. Pour chaque bord de votre polygone, créez un triangle à partir des deux sommets qui forment le bord et votre ancre. Dessine ce triangle.

4. Une fois que vous avez dessiné tous ces triangles, désactivez l'écriture au pochoir, activez le test du pochoir, écrivez les couleurs et dessinez un carré plein écran dans la couleur de votre choix. Cela remplira uniquement les pixels à l'intérieur de votre polygone convexe.

Il est judicieux de placer l’ancre au centre du polygone et de dessiner un rectangle aussi grand que la zone de délimitation de votre polygone. Cela économise un peu de fillrate.

Btw - la technique du pochoir fonctionne également pour les polygones à intersection automatique.

J'espère que ça aide,   Nils

Answer 3

Si vous pouvez utiliser le tampon de gabarit, cela ne devrait pas être difficile à faire. Voici un algorithme général:

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.

Par "droit de s" Je veux dire du point de vue de quelqu'un debout sur v [i] et faisant face à v [i + 1]. Ceci peut être testé en utilisant un produit croisé:

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

Answer 4

Je devais le faire pour un projet. L'algorithme le plus simple que j'ai trouvé s'appelle "Ear Clipping". Un excellent article à ce sujet se trouve ici: TriangulationByEarClipping.pdf

Je m’ai pris environ 250 lignes de code c ++ et 4 heures pour en implémenter la version brute force. D'autres algorithmes ont de meilleures performances, mais cela était simple à implémenter et à comprendre.