Paginacion

[neophox]

EDITO: Uppps, creo que le di al boton que no era y no lo meti en el post sobre terrenos, alguien puede moverlo please :(



Hoy habia quedado en hablar de paginacion, vamos a ver que puedo contar en el poco tiempo que tengo.

Para empezar, cuando es necesaria, pues a poco que pretendas volar sobre un terreno de grandes dimensiones (lo de grandes aqui es relativo, pongamos que grande es si no te entra en memoria con todo lo demas :D, aunque podria ser demasiado grande para que funcione en un equipo medio, digamos que es grande si al cargarlo todo va a superar el limite de memoria que quieras imponerle a tu aplicacion, esto de alguna forma tambien puede limitar la distancia a la que vas a poder ver a cierta resolucion).

Cuando no es necesaria, pues si el terreno es sintetico, es decir, lo generas sobre la marcha, evidentemente no hay nada que paginar :D. O bien si el terreno es suficientemente pequeño para entrar en memoria o es grande pero con una resolucion pobre de tal forma que los datos a cargar no ocupan demasiado. Tampoco es necesaria si haces maravillas como en el paper de Hoppe, donde comprimen la altimetria de Estados Unidos aproximadamente 100 veces y descomprimen sobre la marcha.

En que consiste la paginacion, supongo que es bastante intuitivo, pero por si acaso, se trata de ir cargando de disco los datos que seran necesarios en un futuro cercano. Es decir, mientras mostramos una parte de los datos, iremos cargando los siguientes para que cuando sean necesarios ya los tengamos disponibles y no se produzcan "tirones".

Una forma sencilla de verlo es ponerte delante un papel cuadriculado y pasarle por encima un CD/DVD. Digamos que el agujerito del CD es lo que estas pintando en pantalla, el terreno visible, cada uno de los cuadraditos del papel que caen ahi dentro serian tus trocitos de terreno. Pues bien, toda la parte del CD mas alla del agujerito seria lo que irias "paginando", tendras que elegir el "radio de paginacion", es decir, cuanto margen vamos a dejar, imaginate con un cd de 7cm o uno de 12cm, ese radio tendras que ir ajustandolo segun ciertos parametros como pueden ser: la velocidad maxima a la que permitiras moverse, la memoria disponible para cargar terreno extra, etc.

Ten en cuenta ademas que todo este proceso de paginacion no puedes hacerlo como una cosa mas en tu render loop, al menos no cargando todo lo necesario cuando lo sepas, eso produciria tirones. Aqui puedes elegir hacerlo de varias formas, lo mejor sera que experimentes por ti mismo los pros y contras de cada forma que se te ocurra. El objetivo sera ir cargando una serie de ficheros digamos que "cuando se pueda" sin que el frame rate se resienta (ideal sera que no baje de 60Hz para que el vuelo sea suave).

Bueno, para un solo post ya es bastante texto aunque muchas cosas supongo que son triviales.

Salu2.

[AK47]

Gracias por el hilo. Aparte de esto también estaría bien que explicases como lidiar con los problemas de precisión, que creo que es algo a tener en cuenta con los terrenos.

[JL10]

Neophox, por lo que comentas, ¿esta técnica hay que aplicarla para todo tipo de información del escenario: altimetría, textura, objetos de cultura, nubes, etc?.

[ethernet]

Buena introducción,  el tema de paginación de una forma u otra todos lo conocemos porque en informática/programación es el pan de cada día. La parte difícil es cómo implementar eso sin que ralentice la aplicación. Cómo lo cargas ? en un thread aparte, algunos datos en cada loop, tienes un fichero mapeado en memoria y dejas al SO que se las apañe... :). Otro tema importante es cómo indexas la información, quadtree? cuadrantes?.

[Alexpi]

como bien dice ethernet yo tambien llevo tiempo pregutandome como cargar los datos sin ralentizar la aplizacion.

La mejor opcion que veo es cargando unos pocos KB en cada loop, pero ahi se presenta el problema de que puedas necesitar unos datos que aun no se han cargado y plof.

Si pudieras comentar el mejor modo de hacerlo te lo agradeceria ^^

[neophox]

Vaya, cuanta respuesta :D
No estoy en casa este fin de semana (ahora mismo estoy a casi 500km :D) asi que tendreis que perdonarme hasta el domingo o el lunes que pueda contestar las dudas. De todas formas estoy seguro que hay mucha gente en este foro que sabe daros respuesta, salid de vuestro escondite !! ;)

Buen finde!

[gdl]

Creo que para evitar el problema de la ralentización, lo mejor es dividir en páginas chiquititas. De esa manera se van cargando de forma distribuida a lo largo del tiempo y, como se traspasa poca información cada vez, el retardo es casi irrelevante.

Para los datos que aún no se han cargado, pues aumentas la zona de precarga de páginas y le das mucha más prioridad a las que estén mas cerca de tu entorno de visualización. Si no hay mucho desplazamiento del centro de visualización, no debería haber problemas.

[neophox]

AK47:
 Efectivamente, pueden existir problemas de precision si las coordenadas son muy grandes. Para ello habra que relativizarlas.


JL10:
 Si, es posible aplicar la paginacion al resto de informacion, aunque no siempre necesario. Puede haber cosas que entren en memoria sin problemas y no merezca la pena paginar. La paginacion es una herramienta mas, el hecho de descubrir el martillo no ha de llevarnos a utilizarlo para todo.


ethernet, Alexpi, gdl:

 Efectivamente, el como implementar la paginacion evitando parones en la aplicacion tiene su miga. Una opcion es la que comentais de ir cargando en un thread independiente poco a poco, aqui tendreis que controlar el tiempo disponible para la carga y con eso os tendreis que arreglar. Lo mismo se puede hacer sin thread independiente, ya que le vais a dar un tiempo y dedicaros solo a cargar en ese tiempo.
 En Windows, desconozco si en sistemas unix tb, existen los completion ports donde podeis decirle que leer y cuando termine os avisa.

 Respecto al tamaño de los archivos que pagineis, no siempre es mejor el tamaño mas pequeño, aqui os aconsejo hacer pruebas, tal vez descubrais que es mas costoso abrir muchos ficheros pequeños que menos ficheros de mayor tamaño. Incluso os animaria a hacer pruebas juntando varios ficheros en uno solo con una pequeña FAT al principio. Tambien podeis abrirlo con file mapping, teoricamente dicen que es la forma mas rapida de hacerlo en windows (las pruebas que he hecho no me han confirmado eso aunque no han sido demasiado extensas).

 En cuanto al problema que comenta Alexpi de quedarse sin datos, eso es algo que puede ocurrir, pero debemos configurar nuestro paginador para evitarlo (ampliar el radio de paginacion por ejemplo).

[tiutiu]

¿Y no se podria usar el tiempo que esta la GPU trabajando para cargar los datos?
Todavia no se bien como funciona este aspecto del renderizado, es decir, que no se si mientras la GPU trabaja, el proceso que le da las ordenes se queda bloqueado o esperando o que.
A ver si alguien arroja algo de luz sobre mis dudas :D

[marcode]

Creo que si se trata de que no pierda velocidad de frames supongo que la gpu andará demasiado ocupada con las vertex, los pixels y la madre que los parió, como para andar cargando datos que por otro lado supongo que deberán ser descomprimidos, clasificados, etc, y guardados en la memoria del sistema. Aunque igual un manitas que conozca a fondo la mecánica interna pudiera sacar provecho, pero si ya de por sí la programación de videojuegos es un problema permanente... como para meterse en ese follón sin tener suficiente experiencia.

Mi opinión es que deberá haber un thread dedicado a cargar los datos comprimidos del disco (preferiblemente de archivos grandes) a la memoria, y que hará también el proceso de descompresión y las operaciones que sean necesarias con los datos obtenidos para dejarlos preparados para ser usados rápidamente cuando sea requerido, este proceso debería ser sin mucha prioridad para que no baje mucho el rendimiento de la cpu, pero continuado.

Toda la información cargada y preparada por este thread podrá ser usada cuando sea necesario por el proceso principal para crear los vertex buffers y las texturas, pero surge el problema de que esto requiere un tiempo de creación que probablemente no pueda ser subsanado ni con otro thread.

Si creas buffers y texturas muy pequeñas, seguramente al desplazarse habrá que esperar un rato hasta que se hagan visibles, si los creas muy grandes habrá que soportar los parones, o las bajadas de fps (que viene a ser casi lo mismo).

La solución pasaría por cargar con un LOD muy bajo tanto los vertex buffers como las texturas e irlo elevando para aquellas zonas que se encuentre más próximas a la cámara.

El thread encargado de cargar los datos también deberá guardarlos al nivel de detalle adecuado según la distancia a la cámara para no consumir  toda la memoria y estaría aislado del API 3D para molestar lo menos posible, el proceso principal estaría aislado del disco duro, y solo crearía las texturas y los vertex buffers de la memoria cuyos datos ya deberán estar descomprimidos, clasificados y empaquetados según su LOD cuando sean requeridos, con lo que se podrían generar las texturas y los vertex buffers en la memoria de vídeo muy rápidamente.

¿Qué os parece el planteamiento?. Es que estoy también liado desde hace algún tiempo con un terreno gigantesco (toda españa, con visibilidad en el horizonte de hasta 80Km)  y tengo que solucionar también el tema de los parones. A ver si surgen las ideas y los expertos, y podemos progresar más.

En cuanto a la precisión, lo que hago es que cuando avanzo un cierto recorrido (10Km creo) todo se va para atrás (incluido yo) con lo que nunca estoy en una coordenada mayor de 10000 ni menor de -10000 y de igual modo ninguna parte del escenario está más lejos del tamaño visible.

Imagino que es a lo que se refiere Neophox con lo de relativizarlas, por ejemplo aunque cuenca ciudad esté en las coordenadas UTM 430000, 4570000 y yo me encuentre en la 400000, 4500000, al relativizar yo estaría en la 0,0 y cuenca se dibujará en la coordenada relativa 30000, 70000. Si avanzo 10Km al norte yo pasaré a estar de la 0,10000 a la 0,0 y cuenca quedará en la 30000,60000, es decir, todo retrocede 10000 metros.

Por cierto, otro problema que tengo al no usar coordenadas geodésicas si no transversales, es para dar el "salto" de un Huso a otro, pero eso ya es otra historia.

Están interesantes estos últimas discusiones sobre terrenos. :wink:

[neophox]

Mi opinión es que deberá haber un thread dedicado a cargar los datos comprimidos del disco (preferiblemente de archivos grandes) a la memoria, y que hará también el proceso de descompresión y las operaciones que sean necesarias con los datos obtenidos para dejarlos preparados para ser usados rápidamente cuando sea requerido, este proceso debería ser sin mucha prioridad para que no baje mucho el rendimiento de la cpu, pero continuado.

Yo prefiero tener el control sobre cuando se leen los datos, decirle cuando debe leer y durante cuanto tiempo como maximo. En condiciones normales estaras cargando datos que se encuentran muy lejos del observador y que tardaran en entrar en escena, luego no habra problemas de quedarte pillado sin datos.
Una buena aproximacion es la de los geometry clipmaps (pesadito que estoy con este metodo :D), tiene en cuenta varios niveles de LOD de tal forma que si en un momento por lo que sea no puedes cargar datos de un cierto LOD (normalmente el mas detallado que sera el que cambie mas a menudo) se apaña con los de un LOD menos detallado que, de todas formas, si vas a mucha velocidad (buen motivo para no tener tiempo a cargar todo) no vas a notar la diferencia apenas.

Imagino que es a lo que se refiere Neophox con lo de relativizarlas, por ejemplo aunque cuenca ciudad esté en las coordenadas UTM 430000, 4570000 y yo me encuentre en la 400000, 4500000, al relativizar yo estaría en la 0,0 y cuenca se dibujará en la coordenada relativa 30000, 70000. Si avanzo 10Km al norte yo pasaré a estar de la 0,10000 a la 0,0 y cuenca quedará en la 30000,60000, es decir, todo retrocede 10000 metros.

Asi es, se trata de no permitir que las coordenadas tomen valores demasiado altos.

[marcode]

Yo prefiero tener el control sobre cuando se leen los datos, decirle cuando debe leer y durante cuanto tiempo como maximo. En condiciones normales estaras cargando datos que se encuentran muy lejos del observador y que tardaran en entrar en escena, luego no habra problemas de quedarte pillado sin datos.

Bueno, era sólo una opinión, la verdad es que no sé como deberé hacerlo todavía hasta que no haga pruebas y me aclaré.