javascript - img - title html attribute
Optimizar el dibujo de rectángulos superpuestos (4)
Tengo una gran cantidad de rectángulos y algunos se superponen; cada rectángulo tiene un orden z absoluto y un color . (Cada ''rectángulo'' es en realidad el cuadro delimitador alineado por el eje de un efecto de partícula, malla o textura y puede ser semitransparente. Pero es más fácil pensar abstractamente sobre los rectángulos coloreados siempre que no intentes eliminar rectángulos detrás de otros , entonces lo usaré en la descripción del problema :)
El costo de cambiar el ''color'' es bastante alto; es mucho más rápido dibujar dos rectángulos azules en sucesión que dibujar dos rectángulos de diferentes colores.
El costo de dibujar rectángulos que ni siquiera están en la pantalla es bastante alto y debe evitarse.
Si dos rectángulos no se superponen, el orden en que se dibujan uno respecto del otro no es importante. Es solo si se superponen que el orden z es importante.
Por ejemplo:
1 (rojo) y 4 (rojo) pueden dibujarse juntos. 2 (azul) y 5 (azul) también se pueden unir, como 3 (verde) y 7 (verde). Pero 8 (rojo) debe dibujarse después de 6 (azul). así que o bien dibujamos los tres rojos juntos y dibujamos el azul en dos conjuntos, o dibujamos todo el azul juntos y dibujamos el rojo en dos conjuntos.
Y algunos de los rectángulos pueden moverse ocasionalmente. (No todos, algunos rectángulos son estáticos, otros se sabe que se mueven).
Dibujaré esta escena en JavaScript / webGL.
¿Cómo puedo dibujar los rectángulos en un orden razonable para minimizar los cambios de color , con una buena compensación del código de eliminación de JavaScript frente a dejar que la GPU elimine?
(Solo averiguar qué superposición de rectángulos y cuáles son visibles es costoso. Tengo un árbol cuádruple básico y esto aceleró enormemente mi escena (en comparación con solo emitir los sorteos para toda la escena); ahora la pregunta es cómo minimizar OpenGL cambios de estado y concatenar matrices de atributos tanto como sea posible)
ACTUALIZACIÓN He creado una aplicación de prueba muy simple para ilustrar el problema y servir como base para la demostración de soluciones: http://williame.github.com/opt_rects/
El código fuente está en github y se puede bifurcar fácilmente: https://github.com/williame/opt_rects
Resulta difícil hacer una pequeña aplicación de prueba con suficiente cambio de estado para recrear realmente el problema que veo en mi juego completo. En algún momento, tendrá que considerar que los cambios de estado pueden ser lo suficientemente caros. Lo que también es importante es cómo acelerar el índice espacial (quadtree en demostración) y el enfoque general.
¡Elige colores, no cajas!
En cualquier momento, una o más cajas se podrán pintar , es decir, se pueden pintar a continuación sin introducir problemas (aunque posiblemente con un costo debido a tener un color diferente al de la caja pintada más recientemente).
La pregunta en cada punto es: ¿Qué color deberíamos elegir para dibujar a continuación? No es necesario pensar en elegir cuadros individuales que se puedan pintar para dibujar, porque tan pronto como seleccione un cuadro en particular para dibujarlo a continuación, también puede dibujar todos los cuadros disponibles del mismo color que se puedan dibujar en ese momento. Eso es porque pintar una caja nunca agrega restricciones al problema, solo las elimina; y elegir no pintar una caja para pintar cuando podría hacerlo sin cambiar el color actual no puede hacer que la solución sea menos costosa de lo que sería de otra manera, ya que más adelante tendrá que pintar esta caja y puede requerir un cambio de color. Esto también significa que no importa en qué orden pintamos cajas pintables del mismo color, ya que pintaremos todas a la vez en un solo "bloque" de operaciones de pintura de cajas.
El gráfico de dependencia
Comience construyendo un gráfico de dependencia "debajo", donde cada rectángulo de color está representado por un vértice y hay un arco (flecha) de v a u si el rectángulo v se superpone con el rectángulo u y se encuentra debajo. Mi primer pensamiento fue utilizar esto para construir un gráfico de dependencia "debe dibujarse antes" al encontrar el cierre transitivo, pero en realidad no necesitamos hacer esto, ya que todos los algoritmos a continuación se preocupan por si un vértice se puede pintar o no . Los vértices pintables son los vértices que no tienen predecesores (en arcos), y tomar el cierre transitivo no altera si un vértice tiene 0 en arcos o no.
Además, cuando una caja de un color determinado tiene solo cajas del mismo color que sus antepasados, se pintará en el mismo "bloque", ya que todos esos antepasados se pueden pintar antes sin cambiar los colores.
Una aceleración
Para reducir los cálculos, observe que cada vez que todos los cuadros pintables de un color en particular no tienen descendientes de diferentes colores, pintar este color no abrirá nuevas oportunidades para que otros cuadros se puedan pintar, por lo que no es necesario que lo tengamos en cuenta. color al considerar qué color pintar a continuación - siempre podemos dejarlo hasta más tarde sin riesgo de aumentar el costo. De hecho, es mejor dejar la pintura de este color hasta más tarde, ya que en ese momento otras cajas de este color pueden haberse vuelto pintables. Llame a un color útil si hay al menos un cuadro que se puede pintar de ese color que tiene un descendiente de diferentes colores. Cuando llegamos al punto en el que no quedan colores útiles (es decir, cuando todas las cajas restantes se superponen solo con cajas del mismo color, o no hay cajas), terminamos: simplemente pinta las cajas de cada color restante, seleccionando los colores en cualquier orden.
Algoritmos
Estas observaciones sugieren dos posibles algoritmos:
- Algoritmo codicioso rápido pero posiblemente subóptimo: elija pintar a continuación el color que produce los vértices más nuevos que se pueden pintar. (Esto considerará automáticamente solo colores útiles).
Un algoritmo DP o recursivo más lento y exacto: para cada posible color útil c, considere el gráfico de dependencia producido al pintar todos los cuadros pintables de c colores siguientes:
Sea f (g) el número mínimo de cambios de color necesarios para pintar todos los cuadros en el gráfico de dependencia g. Entonces
f (g) = 1 + min (f (p (c, g)))
para todos los colores útiles c, donde p (c, g) es el gráfico de dependencia producido al pintar todos los cuadros pintables de color c. Si G es el gráfico de dependencia para el problema original, entonces f (G) será el número mínimo de cambios. Las elecciones de color en sí mismas se pueden reconstruir trazando hacia atrás a través de la matriz de costos de DP.
f (g) se puede memoised para crear un algoritmo de programación dinámica que ahorra tiempo cada vez que 2 permutaciones diferentes de opciones de color producen el mismo gráfico, lo que sucederá a menudo. Pero podría ser que incluso después de DP, este algoritmo podría tomar una cantidad de tiempo (y por lo tanto de espacio) que es exponencial en el número de cajas ... Tendré que pensar si se puede encontrar un límite más agradable.
Aquí hay una posibilidad. Tendrás que compararla para ver si realmente es una mejora.
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
No está garantizado que sea el más óptimo en términos de pedidos, pero creo que se acercará bastante, y es el peor caso cuadrático en el paso de pre-dibujo. Depende de que las lecturas del búfer gráfico sean rápidas. Un truco que podría ayudar es crear una nueva superficie de un píxel que sea una versión reducida del área de interés. Su color será la fracción del original que era blanco.
Comience por dibujar en un orden aleatorio (pero correcto), por ejemplo en orden z estricto. Al dibujar cada cuadro, cuente el número de cambios de color, o posiblemente el tiempo real que toma un cuadro completo. Cada fotograma, intente intercambiar el orden de dos rectángulos. Los rectángulos que se intercambiarán no se deben superponer, por lo tanto, se pueden dibujar en cualquier orden sin violar la corrección; Aparte de eso, se pueden elegir al azar, o hacer un pase lineal a través de la lista, o ... Si hacer el intercambio reduce el número de cambios de color, mantener el nuevo orden, si no lo revierte y probar un cambio diferente en el siguiente fotograma. Si al hacer el intercambio no se reduce ni aumenta el número de cambios de color, consérvelo con un 50% de probabilidades. Para cualquier rectángulo que no se haya superpuesto en un cuadro anterior pero que empiece a superponerse debido a un movimiento, simplemente cámbielos para que estén en orden z.
Esto tiene alguna relación con los algoritmos de clasificación que intercambian pares de elementos, excepto que no podemos comparar elementos, tenemos que revisar toda la lista y contar los cambios de color. Esto funcionará muy mal al principio, pero convergerá en un buen orden relativamente rápido y se adaptará a los cambios de escena. Creo que probablemente no valga la pena revisar y calcular un orden óptimo en cada cuadro; esto conseguirá y mantendrá un orden casi óptimo con muy poco trabajo adicional.
En referencia al dibujo, tiene: El orden inicial del sorteo elegido al azar: 1,6,2,4,5,8,3,7 (5 cambios de color). Cambiar 5,8. Nuevo orden: 1,6,2,4,8,5,3,7 (4 cambios de color) => Mantener orden nuevo.
Está asumiendo muy erróneamente que el rendimiento que recibirá en el navegador de escritorio determinará de alguna manera el rendimiento en su iPhone. Debe comprender que el hardware de iPhone implementa la representación diferida basada en mosaicos, lo que significa que el sombreador de fragmentos se utiliza muy tarde en la tubería de todos modos. Como dicen los propios Apple (" No pierdas el tiempo de la CPU clasificando objetos de adelante hacia atrás "), la ordenación en Z de tus primitivos te dará una pequeña ganancia de rendimiento.
Pero esta es mi sugerencia: si cambiar el color es caro, simplemente no cambie el color : páselo como un atributo de vértice y combine los comportamientos en un super shader para que pueda dibujar todo en uno o pocos lotes sin siquiera ordenarlos. Luego realice una evaluación comparativa y determine el tamaño de lote óptimo para su plataforma.