Optimiser le dessin des rectangles qui se chevauchent

Question

J'ai un grand nombre de rectangles, et certains en recouvrent d'autres ; chaque rectangle a un ordre z absolu et un couleur . (Chaque "rectangle" est en fait la boîte de délimitation alignée sur l'axe d'un effet de particule, d'un maillage ou d'une texture et peut être semi-transparent. Mais il est plus facile de penser abstraitement à des rectangles colorés tant que l'on n'essaie pas d'éliminer des rectangles derrière d'autres, c'est pourquoi je vais utiliser cela dans la description du problème :)

Le coût du changement de "couleur" est assez élevé ; il est beaucoup plus rapide de dessiner successivement deux rectangles bleus que de dessiner deux rectangles de couleur différente.

Le coût du dessin de rectangles qui ne sont même pas sur l'écran est également assez élevé et doit être évité.

Si deux rectangles ne se chevauchent pas, l'ordre dans lequel ils sont dessinés l'un par rapport à l'autre n'est pas important. Ce n'est que s'ils se chevauchent que l'ordre z est important.

Par exemple :

1 (rouge) et 4 (rouge) peuvent être tirés ensemble. Le 2 (bleu) et le 5 (bleu) peuvent également être dessinés ensemble, tout comme le 3 (vert) et le 7 (vert). Mais le 8 (rouge) doit être dessiné après le 6 (bleu). Donc, soit on dessine les trois rouges ensemble et on dessine les bleus en deux séries, soit on dessine tous les bleus ensemble et on dessine les rouges en deux séries.

Et certains des rectangles peuvent bouger occasionnellement. (Pas tous ; certains rectangles sont connus pour être statiques ; d'autres sont connus pour bouger).

Je vais dessiner cette scène en JavaScript/webGL.

Comment puis-je dessiner les rectangles dans un ordre raisonnable pour minimiser les changements de couleur avec un bon compromis entre l'élimination du code en JavaScript et l'élimination par le GPU ?

(Le simple fait de déterminer quels rectangles se chevauchent et lesquels sont visibles est coûteux. J'ai un quadtree de base et cela a accéléré énormément le dessin de ma scène (par rapport à l'émission des draw-ops pour toute la scène) ; maintenant la question est de savoir comment minimiser les changements d'état OpenGL et concaténer les tableaux d'attributs autant que possible)

UPDATE J'ai créé une application de test très simple pour illustrer le problème et servir de base à la démonstration des solutions : http://williame.github.com/opt_rects/

Le code source est sur github et peut facilement être forké : https://github.com/williame/opt_rects

Il s'avère qu'il est difficile de créer une petite application de test avec suffisamment de changements d'état pour recréer le problème que je vois dans mon jeu complet. À un moment donné, vous devrez considérer comme acquis que les changements d'état peuvent être suffisamment coûteux. Ce qui est également important est de savoir comment accélérer l'index spatial (quadtree dans la démo) et l'approche globale.

Answer 1

Vous faites l'hypothèse erronée que les performances que vous obtiendrez sur le navigateur de bureau détermineront en quelque sorte les performances de votre iPhone. Vous devez comprendre que le matériel de l'iPhone met en œuvre Rendu différé basé sur les tuiles ce qui signifie que le fragment shader est utilisé très tard dans le pipeline de toute façon. Comme Apple le disent eux-mêmes (" Ne perdez pas de temps à trier les objets de l'avant vers l'arrière. "), trier vos primitives en Z ne vous apportera qu'un faible gain de performance.

Mais voici ma suggestion : si changer la couleur est coûteux, mais ne changez pas la couleur Il s'agit de le passer comme un attribut de vertex et de fusionner les comportements dans un super shader afin de pouvoir tout dessiner en un ou plusieurs lots sans même faire de tri. Ensuite, évaluez et déterminez la taille optimale des lots pour votre plateforme.

Answer 2

Choisissez des couleurs, pas des boîtes !

A tout moment, une ou plusieurs boîtes seront à peindre En d'autres termes, elles peuvent être peintes à la suite sans que cela ne pose de problème (bien que cela puisse entraîner un coût en raison de la couleur différente de celle de la dernière boîte peinte).

La question qui se pose à chaque instant est la suivante : Qu'est-ce que couleur devrait-on choisir le prochain tirage au sort ? Il n'est pas nécessaire de penser à choisir des boîtes à peindre individuelles, car dès que vous choisissez une boîte particulière à dessiner, vous pouvez aussi bien dessiner toutes les boîtes disponibles de la même couleur qui peuvent être dessinées à ce moment-là. C'est parce que peindre une boîte n'est jamais ajoute De plus, choisir de ne pas peindre une boîte à peindre alors que vous pouvez le faire sans changer la couleur actuelle ne peut pas rendre la solution moins coûteuse qu'elle ne le serait autrement, puisque vous devrez peindre cette boîte plus tard et que cela peut nécessiter un changement de couleur. Cela signifie également que l'ordre dans lequel nous peignons les boîtes à peindre de la même couleur n'a pas d'importance, puisque nous les peindrons toutes en même temps dans un seul "bloc" d'opérations de peinture de boîtes.

Le graphe des dépendances

Commencez par construire un graphe de dépendance "lies underneath", où chaque rectangle coloré est représenté par un sommet et où il existe un arc (flèche) de v à u si le rectangle v chevauche le rectangle u et se trouve en dessous. Ma première idée était de l'utiliser pour construire un graphe de dépendance "doit être dessiné avant" en trouvant la fermeture transitive, mais en fait nous n'avons pas besoin de le faire, puisque tout ce dont les algorithmes ci-dessous se soucient est de savoir si un sommet peut être peint ou non. Les sommets pouvant être peints sont les sommets qui n'ont pas de prédécesseurs (in-arcs), et prendre la fermeture transitive ne change rien au fait qu'un sommet ait 0 in-arcs ou non.

En outre, chaque fois qu'une case d'une couleur donnée n'a que des cases de la même couleur que ses ancêtres, elle sera peinte dans le même "bloc" -- puisque tous ces ancêtres peuvent être peints avant elle sans changer de couleur.

Une accélération

Pour réduire les calculs, notez que lorsque toutes les boîtes pouvant être peintes d'une certaine couleur n'ont pas de descendants de couleur différente, peindre cette couleur n'ouvrira pas de nouvelles opportunités pour d'autres boîtes de devenir peignables, donc nous n'avons pas besoin de prendre en compte cette couleur lorsque nous réfléchissons à la couleur à peindre ensuite -- nous pouvons toujours la laisser à plus tard sans risque d'augmenter le coût. En fait, c'est meilleur de ne peindre cette couleur que plus tard, car d'ici là, d'autres boîtes de cette couleur peuvent être peintes. Appelez une couleur utile s'il existe au moins une boîte à peindre de cette couleur qui a un descendant de couleur différente. Lorsque nous arrivons au point où il n'y a plus de couleurs utiles (c'est-à-dire lorsque toutes les cases restantes ne recouvrent que des cases de la même couleur, ou aucune case), nous avons terminé : il suffit de peindre les cases de chaque couleur restante, en choisissant les couleurs dans n'importe quel ordre.

Algorithmes

Ces observations suggèrent deux algorithmes possibles :

1. Un algorithme rapide mais éventuellement sous-optimal : Choisissez de peindre ensuite la couleur qui produit le plus de nouveaux sommets à peindre. (Cela ne prendra automatiquement en compte que les couleurs utiles).

2. Un algorithme plus lent, exact DP ou récursif : Pour chaque couleur utile c possible, on considère le graphe de dépendance produit par la peinture de toutes les boîtes de couleur c peignables suivantes :

   Soit f(g) le nombre minimal de changements de couleur requis pour peindre toutes les cases du graphe de dépendance g. Alors

   f(g) = 1 + min(f(p(c, g)))

   pour toutes les couleurs utiles c, où p(c, g) est le graphe de dépendance produit en peignant toutes les boîtes à peindre de couleur c. Si G est le graphe de dépendance pour le problème original, alors f(G) sera le nombre minimum de changements. Les choix de couleurs eux-mêmes peuvent être reconstruits en remontant dans la matrice des coûts du DP.

   f(g) peut être mémorisé créer un algorithme de programmation dynamique qui permet de gagner du temps lorsque deux permutations différentes de choix de couleurs produisent le même graphique, ce qui arrivera souvent. Mais il se pourrait que même après la programmation dynamique, cet algorithme prenne une quantité de temps (et donc d'espace) qui est exponentielle dans le nombre de boîtes... Je vais réfléchir pour voir si une limite plus agréable peut être trouvée.

Answer 3

Voici une possibilité. Vous devrez l'évaluer pour voir si c'est vraiment une amélioration.

For all rectangles, back to front:
  If this rectangle has been marked as drawn, skip to the next one
  Set a screen-sized unseen surface to all black
  Call this rectangle's color "the color"
  For rectangles starting with this one and proceeding toward the front
    If (this rectangle's color is the color and
        all the pixels of this rectangle on the unseen are black) then
      Add this rectangle to the to-draw list
    Draw a white rectangle with this rectangle's shape on the unseen surface
    If the unseen surface is more than half white, break
  For all rectangles on the to-draw list:
    Draw the rectangle
    Mark it as drawn

Il n'est pas garanti qu'elle soit la plus optimale en termes d'ordonnancement, mais je pense qu'elle s'en rapprochera, et dans le pire des cas, elle est quadratique dans l'étape de pré-dessin. Cela dépend de la rapidité des lectures du tampon graphique. Une astuce qui pourrait aider est de créer une nouvelle surface d'un pixel qui est une version réduite de la zone d'intérêt. Sa couleur sera la fraction de l'original qui était blanche.

Answer 4

Commencez par dessiner dans un ordre aléatoire (mais correct), par exemple dans un ordre z strict. Lorsque vous dessinez chaque image, comptez soit le nombre de changements de couleur, soit le temps réel que prend une image complète. À chaque image, essayez de permuter l'ordre de deux rectangles. Les rectangles à échanger ne doivent pas se chevaucher, donc ils peuvent être dessinés dans n'importe quel ordre sans violer la correction ; à part cela, ils peuvent être choisis au hasard, ou faire un passage linéaire dans la liste, ou... Si la permutation réduit le nombre de changements de couleur, gardez le nouvel ordre, sinon revenez en arrière et essayez une permutation différente dans la prochaine image. Si l'échange ne réduit ni n'augmente le nombre de changements de couleur, gardez-le avec une chance sur deux. Pour tous les rectangles qui ne se chevauchaient pas dans une image précédente mais qui commencent à se chevaucher à cause d'un déplacement, il suffit de les échanger pour qu'ils soient dans l'ordre z.

Cela a un certain rapport avec les algorithmes de tri qui échangent des paires d'éléments, sauf que nous ne pouvons pas comparer les éléments, nous devons parcourir toute la liste et compter les changements de couleur. Cette méthode donnera de très mauvais résultats au début, mais convergera vers un bon ordre relativement rapidement, et s'adaptera aux changements de scène. Je pense qu'il n'est probablement pas utile de calculer un ordre optimal à chaque image ; cette méthode permettra d'atteindre et de maintenir un ordre quasi-optimal avec très peu de travail supplémentaire.

En se référant au dessin que vous avez : Ordre de tirage initial tiré au sort : 1,6,2,4,5,8,3,7 (5 changements de couleur). Echanger 5,8. Nouvel ordre : 1,6,2,4,8,5,3,7 (4 changements de couleur) => Garder le nouvel ordre.