Occlusion Culling

[tiutiu]

 Bueno, he implementado una jerarquia de nodos en mi engine y le he añadido el frustum culling. Los bounding volumes los guardo en una clase cuyos miembros son: radio, vector centro, y 6 floats con las esquinas de la bounding box (axis-alligned) top, bottom, left, right, front y back. Para probar contra el frustum d la camara uso la esfera ya q es mas rapido, aunq puedo ponerle un flag a las meshes con las q vaya mejor un test de boundingbox pero weno, eso es una optimizacion q no viene al caso.

Ahora ha llegado el momento de implementar el occlusion culling, el cual es una maravilla. Para los q no lo sepan simplemente es un frustum (o conjunto de planos) que ocluyen el espacio que encierran, al contrario que el frustum d la camara (o viewing frustum) que muestra el espacio q encierra.

Pues bien, este conjunto de planos tengo pensado sacarlo con la bounding box del objeto, ya que como mucho son 6 planos (se ven 3 caras de la caja como mucho, las cuales forman un contorno de 6 lados) lo cual es mucho mas optimizado q usar un convex hull y sacar su contorno q puede ser d muchos planos. Estos planos los añado a la camara para usarlos en su funcion de culling (prueba una esfera con los planos del frustum completo, usea viewing+occlusion)

Por supuesto el computo del occlusion frustum solo lo haran los objetos q yo marque como posibles occluders, que en mi caso actual me interesa que sean los nodos del quadtree, ya q pueden tener varios miles d vertices tal como tengo ahora el quadtree y el terreno (sin LOD). Aqui pongo un screenshot del terreno con los boundingboxes de cada hoja del quadtree (todos los nodos tienen bbox, no solo las hojas)


El triangulo rosa es la camara, las lineas verdes vienen a ser el viewing frustum. Sin el occlusion culling se verian 12 nodos (ya los he contado yo). Ahora vienen mis teorias para que las corrijais/comenteis.
El rectangulo rojo seria la parte de la bounding box del nodo mas cercano a la camara con cuyas aristas hariamos los planos de oclusion (seguid leyendo para entender esta parte si no la veis).

Si implemento el OC supongo q deberia ordenar a los posibles occluders por distancia con la camara y usar este algoritmo:

Código [Seleccionar] Expand


for each x WorldObject in OccluderList
 if(!isCulled(x))
   Plane *planes = CalcularPlanosDeBoundingBox(x.Bound, Camara.Location)
   Camara.PushPlanes(planes)
   Renderer.Draw(x)


Tenemos que comprobar si el objeto esta fuera del frustum, ya que el q venia antes ha podido añadir una serie de planos al frustum que ocluyen a otros ocluders; por ejemplo un camion ha tapado a la caseta d la once q tapaba a esa tia tan wena q mirabamos, la caseta d la once y el camion son occluders los dos, pero la caseta ha sido tapada por el camion, asi q ya no la computamos.

El algoritmo para sacar los planos no lo tengo muy claro. Tengo que mirar que caras apuntan a la camara (cada cara son 4 lados ya q es un cubo, no hace falta bajar hasta triangulos) y con las aristas q forman el contorno (las cuales no se como sacar) hacer un plano mediante 2 puntos de la arista y location d la camara.

Si alguien tiene algun comentario q lo diga

[BeRSeRKeR]

 Si no recuerdo mal, hace un tiempo leí un artículo (muy corto) en el que hablaba de construir el occluder volume de la misma forma que lo harías con un shadow volume. La cosa estaría en extruir aquellos vértices del bbox del nodo cuyas normales apunten a la cámara. Pero en este caso, la referencia en vez de ser una luz sería la propia cámara.

Con esto ya tendrías el frustum del occcluder y por lo tanto ya podrías hacer el test contra el resto de nodos...

Esto a grandes rasgos porque habría que tener en cuenta algunas cosillas más...pero bueno, sólo es una idea :)

Saludos

[BeRSeRKeR]

 

El algoritmo para sacar los planos no lo tengo muy claro. Tengo que mirar que caras apuntan a la camara (cada cara son 4 lados ya q es un cubo, no hace falta bajar hasta triangulos) y con las aristas q forman el contorno (las cuales no se como sacar) hacer un plano mediante 2 puntos de la arista y location d la camara.

Debería leer mejor...en fin, lo que tú has dicho es prácticamente lo mismo que yo he dicho pero con otras palabras :D

PD: Con respecto a calcular el contorno, supongo que habría que eliminar los vértices que comparten arista. Creo que es algo parecido a como lo harías al calcular el shadow volume...

[Gunder]

 Buenas,

se trata de un offtopic, pero creo que ya que estas implementando algo así, podrias contemplar la posibilidad de precalcular impostors para cada nodo del arbol, serian 4 impostor por nodo en el peor de los casos y 0 en el mejor. Me explico, para cuando un nodo está literalmente a tomar por culo, en unidades de camara y tu sensacion de tridimensionalidad se ve reducida por tu perspectiva podrias remplazar el render de ese nodo por un impostor que, o bien precalculas o bien recalculas cuando lo necesites y lo calzas en un plano. El impostor seria el render que resulta al proyectar el lado del plano contra todos los nodos que se vean afectados desde un punto de camara. Nose, para nodos alejados deberia de quedar bien, quizas el precalculo generaria impostor muy forzado, pero reclaculando si el angulo es maypr que alpha quedaria bien y te ahorra repintar todo el fondo en cada frame.

Es una idea.

Respecto al Occlusion Culling, yo empezaria con la bounding box minima que esta por debajo del terreno o la boundig box minima que es inscribe en un objeto, no es mucho, pero si tienes un buen pedazo de montaña delante te quitara casi todo el terreno o si ese camion esta cerca de la camara, es un calculo muy rapido y que puede quitar mucha morraya.

Otra opcion seria calcular PVS para cada nodo, lo haces en tiempo de carga de mapas y te ahorras muchos calculos.

Bueno, que para un pregunta que esta animada... a ver si sacamos algo en claro entre todos.

Aprovecho para meter el tema de texturado de terrenos, ideas please.

Ale

[BeRSeRKeR]

 Veo que hay gente interesada en el tema así que, aunque a tiutiu ya se lo recomendé un día en el IRC, lo haré aquí también.

Existe un documento que trata las técnicas que utiliza un motor llamado dPVS. A lo mejor ya lo conocíais pero por si acaso, podéis descargar dicho documento desde aquí.

Podéis encontrar información sobre distintos métodos de determinación de visibilidad. Concretamente, en el apartado 10.4 (Conservative Visibility Determination) trata el tema algoritmos en Image-Space. Entre ellos se puede encontrar en el punto 10.4.4 el algoritmo Hierarchical Occlusion Maps. En el punto 11.2 también hay bastante información sobre cómo escoger los occluders, fusionar distintos occluders para optimizar el descarte de geometría, etc.

También he podido ver en un apartado que trata el tema de Image-Based Rendering. Entre las técnicas de este tipo de render está la que mencionaba Gunder de los impostors...pero bueno, como digo el paper este está bastante completo y contiene mucha información que os podría ser útil. ¡Al menos podría daros ideas!

Saludos

[tiutiu]

 Primero de todo gracias por las respuestas ;)

Ya me baje el paper ese, aunq mas q paper es un libro (450pags o asi xD). Estoy mirandolo ahora pues se me fue la cabeza y no lo mire tras bajarlo al ver tantas paginas. Parece dar wenas ideas sobre la oclusion.

Bueno, voy a hablar un poco sobre culling a modo de mini-tutorial para q el q no sepa mucho sobre el tema pueda sacar algo en claro y opinar. El culling se basa en ver quien se muestra y quien no. Para ello se crea un frustum a partir de la camara y sus propiedades. La camara proyecta una piramide de vision cortada por el near plane y el far plane (definidos al usar glFrustum o gluPerspective). Es un conjunto de 6 planos con las normales hacia dentro.
Para el culling lo mas comun es usar esferas como bounding volume y mirar si esta en la mitad a la q apunta la normal del plano, lo cual es un producto vectorial entre la normal y el centro d la esfera (3 multiplicaciones y 3 sumas) y una comparacion con la constante del plano. Con lo cual mirar si una esfera esta dentro del frustum (solo el formado por la camara) son 6 comprobaciones por plano como mucho para descartarlo.

Pues bien, cuando calculamos los planos q forma un occluder sacamos de 4 a 6 planos (segun como miremos la bounding box; es el volumen con menos caras q genere frustum d oclusion) q añadimos a la camara, lo cual nos añade de 4 a 6 comprobaciones plano-esfera mas.

Luego esto se puede optimizar reduciendo el numero d lados del contorno de la boundingbox con algun algoritmo q ahora mismo no se :rolleyes: , fundiendo occluders (creo haber visto q el paper q ha nombrado BeRSeRKeR sale algo sobre eso) y lo mas importante d todo, seleccionando occluders (puede ser una malla o todo un nodo, p.ej, un nodo d la escena q englobe un bosque puede ser un occluder, ya q lo q no tapa un arbol lo tapa otro, y mas visto desde cierta distancia.

Mi principal problema es q creo q deberia ordenar los occluders por distancia con la camara(cualquier nodo hoja del quadtree es un occluder por ejemplo) y luego ir probando si estan ocluidos por el frustum, añadir los planos d su contorno al frustum y seguir con el resto d occluders, y luego con el resto de la escena y al final del render resetear el frustum a los 6 planos de la camara, claro.

A ver si la gente se anima a postear lo q se le ocurra sobre el tema, q de todo se pueden sacar ideas por mucho q no se sea un crack del tema (yo no sabia nada hasta hace pocos dias xD)

[tiutiu]

 Hmmm no se puede editar un mensaje? Forum Master puedes activarlo? seria d gran ayuda ;)

Una cosa q me dejaba es la siguiente. Los occluders creo q idealmente deberian ser objetos estaticos, con lo cual se puede calcular una OBB (oriented bounding box) de volumen minimo y usarla para la oclusion. Evitaria bastantes problemas de oclusion cuando en verdad no la hay ;) O quizas mejor aun usar un convex hull (por ejemplo si miras desde el techo d una casa abajo, la bounding box de la casa te tapa una parte q la pendiente del tejado en realidad no tapa). Sugerencias?