Quadtree

[tiutiu]

 Weno estoy haciendo la parte del terreno en mi engine y por ahora cargo un heightmap en un array (unidimensional) de vertices y los renderizo por triangle strips 'a tiras', es decir, hago MAP_HEIGHT tiras de triangle strips de MAP_WIDTH triangulos xD.

Bueno, a lo q voy. Como ya os imaginais un terreno tiene bastantes miles de triangulos (el q hago yo tiene creo q 150.000, no se, un heightmap de 512x512 pixels) asi q resulta demasiado costoso d renderizarlo todo, con lo cual necesito una estructura d datos tipo arbol para organizar en nodos la geometria y q sea mas facil probar si los 'cachos' d terreno tan en el frustum.
Voy a usar quadtree, mas o menos se como hacerlo, una simple estructura de arbol q tiene 4 hijos a los q les asigno geometria con su respectiva bounding box. Pero no se hasta donde iterar. Como decidiis cuantos triangulos debe contener un nodo? habia pensado en un cacho de 32x32 quads por nodo, pero no se, dadme opiniones.

Tambien tengo pensado implementar algun tipo de LOD al terreno, algun consejo?? me va a costar mucho implementarlo si no lo hago ya desde el principio? mas q nada pq he visto alguna tecnica d LOD y se usan triangle fans para  añadirle detalle a los quads :S

Algo de orientacion en el tema? iluminadme plz q toy un poco  (nooo)  

[Zaelsius]

 Aquí­ tienes un documento muy interesante: que te ayudará a alegir el tamaño de los nodos terminales del quadtree, además de como está el tema de usar vertex-shaders para el LOD(casi indispensable para evitar el popping)

[tiutiu]

 Mas o menos eligo el numero de vertices como me peta, mas q nada pq si no se me renderiza bien la malla q mas me da el valor q ponga? xDD

Cada nodo (hoja) del quadtree guarda un puntero a los vertices d la malla del terreno y un array de indices a los vertices q contiene dicho nodo del quadtree. Para clasificarlos uso una funcion recursiva a la q le paso dicho puntero a los vertices y el array de indices d su padre (o NULL si es el root). Entonces saco la boundingbox del nodo para sacar el centro y voy repartiendo los indices del padre en 4 arrays (uno para cada hijo) segun su posicion respecto al centro (nordeste, noroeste, sudoeste, sudeste). Luego creo sus 4 hijos y llamo a la funcion recursiva para cada hijo pasandole su array de indices y el puntero a los vertices.

Al principio d la llamada miro si el numero de indices (o lo q es lo mismo, numero d vertices, q se lo paso con otro parametro mas) es menor o igual al numero maximo de vertices q contiene un nodo. Si pasa el test pues entonces le pongo el flag d q es una hoja (m_bLeaf = true), le asigno a un miembro la direccion del array de vertices (no copio vertices, solo doy la direccion, asi no chupa tantos recursos xD) y le copio el array de indices a otro miembro con los indices.

En definitiva, transformo los nodos hoja en sub-mallas de la malla inicial q le paso al root. En teoria lo hace bien pq no me salta ninguna exception ni mierdas d esas d memoria.

El problema viene al renderizarlo. Simplemente hago otra funcion recursiva q mira si el nodo q le paso es una hoja o no. Si no lo es pues llamo 4 veces a la funcion recursiva con cada uno de sus hijos (ya sabeis, NE, NW, SW y SE) y si es una hoja pues dibujo la malla mediante triangle strips con este algoritmo simple y facil q todos podemos conocer:

Código [Seleccionar] Expand


glBegin(GL_TRIANGLE_STRIP);
for(int z=0; z<pkNode->m_iNumVerts; z++)
{
   glVertex3fv(pkNode->m_pkVertices[pkNode->m_piIndices[z]]);
   glVertex3fv(pkNode->m_pkVertices[pkNode->m_piIndices[z]+MAP_SIZE]);
}
glEnd();


pkNode es el nodo q le paso a la funcion recursiva, m_pkVertices es puntero a los vertices del terreno (todos los vertices), m_piIndices pues es el array de indices de ESE nodo (el q saco al repatir la geometria probando contra el centro d la BBox del nodo q he explicao antes), m_iNumVerts es el numero d indices q tiene el nodo y MAP_SIZE es una constante cuyo valor es el ancho del mapa (seria el numero de columnas) la cual uso para saber cual es su vertice adyacente en el array de vertices, al ser este unidimensional (podria usar un array bidimensional y hacer fila+1 pero no me da la gana xDD ademas q tengo otros motivos).

Pues bien, si os fijais el codigo tiene un fallo, para la ultima fila de vertices petara pq si z marca la ultima columna y z+map_size marca la columna siguiente me dira q esta fuera del rango (normal).

Asi q mi pregunta es, como coño lo arreglo? alguna sugerencia en cuanto a reparto/almacenaje d vertices en las hojas?