Comment obtenir des résultats précis avec l'algorithme de Painter?

14

Il y a quelque temps, j'ai demandé comment déterminer quand un visage en chevauchait un autre. Le conseil était d'utiliser un Z-buffer.

Cependant, je ne peux pas utiliser de Z-buffer dans mon projet actuel et j'aimerais donc utiliser l'algorithme du peintre. Cependant, je n'ai aucune idée de quand une surface est derrière ou devant une autre. J'ai essayé de nombreuses méthodes, mais elles échouent toutes dans des cas marginaux, ou elles échouent même dans des cas généraux.

Voici une liste des méthodes de tri que j'ai essayées jusqu'à présent:

  • Distance au milieu de chaque face
  • Distance moyenne à chaque sommet de chaque face
  • Valeur z moyenne de chaque sommet
  • Valeur z la plus élevée des sommets de chaque face et dessinez-les en premier
  • Valeur z la plus basse des sommets de chaque face et dessinez ces derniers

Le problème est qu'un visage peut avoir une distance plus proche mais est encore plus éloigné. Toutes ces méthodes semblent peu fiables.

Modifier: Par exemple, dans l'image suivante, la surface avec le point bleu comme milieu est peinte sur la surface avec le point rouge comme milieu, car le point bleu est plus proche. Cependant, cela est dû au fait que la surface du point rouge est plus grande et que le point médian est plus éloigné. La surface avec le point rouge doit être peinte sur la bleue, car elle est plus proche , tandis que la distance médiane indique le contraire.

entrez la description de l'image ici

À quoi sert exactement l'algorithme du peintre pour déterminer l'ordre dans lequel les objets doivent être dessinés?

pimvdb
la source
1
L' algorithme des peintres dessine simplement de l'arrière vers l'avant.
Jonathan Connell
1
@ 3nixios: Oui, bien sûr, mais de quelle manière puis-je déterminer l'ordre de "l'arrière vers l'avant"?
pimvdb
1
Tous vos objets, triangles ou sommets seront à une certaine distance de la caméra lorsque vous commencerez à dessiner. La mise en œuvre de l'algorithme de base (avez-vous réussi?) Reviendrait à déterminer cette distance de la caméra pour chaque triangle et à les tracer dans l'ordre le plus éloigné au plus proche. Une fois cela fait, vous devez commencer à chercher des intersections et à découper vos triangles, ce qui est un tout autre jeu de balle . Pourquoi ne pouvez-vous pas déjà utiliser Z-Buffer? : P
Jonathan Connell
@ 3nixios: Vous avez tout à fait raison, mais le problème auquel je suis confronté est le calcul de la distance. Comme je l'ai dit, j'ai essayé plusieurs méthodes de distance mais elles ne sont pas toutes parfaites. Cet ordre résulte du tri de la distance à mi-chemin: i.imgur.com/AcfCm.png .
pimvdb
1
Est-ce que tous vos polygones sur une grille régulière sont comme ça? Si c'est le cas, vous pouvez faire des choses spécifiques au réseau pour améliorer cela.
CiscoIPPhone

Réponses:

14

Habituellement, la distance entre le milieu d'un polygone et la caméra est utilisée pour le tri en z. L'algorithme du peintre ne peut pas être précis à 100% par sa nature. Il y aura toujours des cas où le tri échouera, quel que soit le point de référence que vous utilisez.

Si vous voulez un z-sort correct avec l'algorithme du peintre, vous devrez découper les polygones qui se chevauchent en parties plus petites (par exemple en utilisant un arbre quadruple) et trier ces parties individuellement. Cela peut devenir assez lourd sur le CPU.

J'ai trouvé ce fichier Powerpoint qui illustre bien le problème ( version PDF ).

bummzack
la source
Merci pour ce Powerpoint, cela m'a aidé à résoudre le problème.
pimvdb
Le lien est rompu. Quelqu'un peut-il en trouver une copie?
Keavon
1
@Keavon Edited. J'ai trouvé un lien de travail pour le fichier.
bummzack
1

Dans de tels cas, pour moi, cela fonctionnait toujours en utilisant des arbres bsp. Divisez la scène jusqu'à ce que vous ayez un ensemble convexe de polygones dans le nœud de bsp-tree, puis vous pouvez facilement trier les polygones dans les nœuds. Notez qu'en triant les polygones du nœud bsp-tree, cela semble être le même problème que celui décrit ci-dessus, mais il y a une condition pas si évidente - après avoir construit l'arbre bsp, tous les cas problématiques sont déjà résolus - dans le nœud, vous devez terminer avec un ensemble de polygones à partir desquels le test de convexité doit passer - si vous choisissez un avion d'un polygone de cet ensemble, les autres polygones sont tous soit devant l'avion, soit derrière l'avion. L'utilisation de ces informations facilite le tri - le foncteur de tri prend 2 polygones - vérifiez dans quel demi-espace se trouve le 1er polygone par rapport au 2e polygone et vérifiez également le placement de la caméra par rapport au deuxième polygone.

Notez également que les tests pour déterminer le côté du placement de la caméra par rapport aux polygones et la traversée de bsp-tree sont légèrement différents lorsqu'il s'agit de projection orthographique et en perspective.

Si vous ne pouvez pas vous permettre de fractionner les polygones d'entrée, je pense que vous n'avez pas de chance.

évêque
la source