obtener normales de un terreno

[marcode]

Estoy haciendo una nueva versión de mi generador de terrenos y necesito obtener las normales de cada vértice, pero el calcular las de todos los triángulos y luego promediarlas creo que va a consumir demasiado tiempo.

Se me ocurre que lo mejor sería recorrer cada uno de los vértices y obtener su normal mediante los vértices contiguos, es decir el izquierdo, derecho, delante y atrás.

Entonces... ¿sería algo así como obtener el producto cruzado de 4 vectores?, o ¿cómo las podría obtener?. necesito que sea muy rápido porque el terreno se genera en tiempo real pseudoaletariamente  y luego necesito obtener las normales sobre millones de vértices.

[blau]

Yo no soy ningun hacha en esto, pero a bote pronto creo que de esa forma no te libra nadie de hacer los cuatro productos mas las pertinentes sumas, y la normalizacion final.

Puedes optimizarlo si calculas de antemano las normales para los triangulos, pero si vas a generar muchos y en generados de forma aleatoria en tiempo real como dices, quizas deberias plantearte acotar un poco el problema, y limitar de alguna forma esa cantidad de triangulos, o limitar la pseudo generacion de forma que limites la creacion de triangulos nuevos a un cierto numero que puedas manejar. Si lo planteas incrementalmente te podria funcionar.

BUeno espero que te sirva de algo, ...

;)

[marcode]

Pero eso sería aún más lento que lo que tenía pensado.

suponiendo que es una matriz de vértices de 10x10 tengo 100 vértices y  200 triángulos.

La idea inicial es obtener la normal de esos 200 triángulos y sumarla a cada uno de los 3 vértices que lo componen, después normalizarlas.

Lo que propones sería obtener la suma de los 6 triángulos que pertenecen a un vértice, por lo que serían 600 operaciones (más las sumas y la normalización).

Para mejorarlo habría que hacer 100 operaciones, una por vértice. O algún truco o técnica que permita acelerar la cosa, al tratarse de un terreno no hace falta tampoco que tenga mucha precisión.

[tamat]

sumas los cuatro vertices contiguos y divides entre cuatro, normalizas y ya tienes la normal en ese vertice. Es recomendable tenerlo precalculado con el propio terreno.

[marcode]

No entiendo lo de sumar los cuatro vértices contiguos tamat, ¿sumar el vector a cada uno de ellos?

[tamat]

Perdon, me confundí, quería decir que haces el producto vectorial de los cuatro vectores que van desde el punto del terreno a los puntos adyacentes y te salen cuatro vectores, esos cuatro los sumas y lo divides entre cuatro, y te sale la normal.

[senior wapo]

No podéis usar simplemente los 4 vértices vecinos porque no tenéis en cuenta que pueden formar parte de triángulos distintos, dependiendo de si por ellos pasa diagonal de triángulo o solamente los ejes horizontal y vertical.
El métido correcto es sumando las normales de los polígonos que usan el vértice.

Has dicho que no necesitas precisión, así que se me acaba de ocurrir un algoritmo rápido.
Sin cálculos costosos salvo la normalización final. Especialmente si puedes generar el mapa de alturas Z con enteros en lugar de floats.

Mira el siguiente mapa:


Para calcular la normal del vértice 0 deberias sumar las normales de los triángulos A, B, C y D.

El truco es calcular las normales de esos triángulos ¿ verdad ?
Observa lo siguiente:
La normal del triángulo A es la del plano definido por las 2 rectas que pasan por el vértice 0 y a su vez una pasa por el vértice 1 y la otra por el vértice 2.
Vale, fijate ahora que ambas rectas son paralelas a X o a Y (Z es la altura). Si calculas la pendiente de cada una de ellas (restas la altura de un vértice de la del otro) sigues definiendo con un solo número a la recta, porque sabes que es paralela a X o a Y.

Dadas dos pendientes 01 y 02 que definen las rectas del triángulo, las combinas en un solo entero y lo usas como indice de una tabla precalculada.

Hemos reducido el cálculo de la normal de un triángulo a 2 restas, un OR, un desplazamiento de bits y una consulta en tabla:

Código [Seleccionar] Expand


pendienteHorizontal= ( v1.Z - v0.Z ) ; // usar >> y & para que quede en 0-15
pendienteVertical= ( v2.Z - v0.Z ) ; // usar >> y & para que quede en 0-15

normalTriangulo = tablaNormales256Valores [ (pendienteHorizontal << 4) | pendienteVertical  ];


Donde tablaNormales256Valores es un array que contiene 256 vector3 lo cual equivale a una matriz de 16x16. Podias haber usado una matriz también.

Vértices alternos suman 4 normales, y los otros, 8. Si hubieses hecho una una malla con todas las diagonales iguales, todos los vértices sumarian 6 normales. Casos especiales los bordes del mapa.

El blucle y las estructuras internas te las buscas tu; o bien haces varias pasadas y arrays intermedios o usas un bucle con muchas variables intermedias.

[marcode]

Vale, aunque a primera lectura no lo he entendido del todo en cuanto pueda intento implementarlo. Si tengo dudas volveré.

De todas formas no se si cambia mucho, pero estoy haciendo pruebas y creo que al final por otras cuestiones técnicas la distribución de los triángulos tendrá este aspecto, aunque todavía no es seguro.



Ahora como decías tienen 6 cada uno, y quizás se podría obtener sólo a partir de 3

[marcode]

Al final lo tengo así.



Recorro todos las celdas, obtengo la normal de sus dos triángulos A y B, y se la sumo a los vértices que los componen. Después en un bucle aparte normalizo la normal de cada vértice. No sé si esto es correcto pero no me parece que quede mal.

Ahora tengo la duda para meterlo en el array que propones senior.

La pendiente vertical y horizontal me puede dar cualquier tipo de valor, desde 0 a 200 o 1000, dependiendo sobre todo del ancho de la celda. No sé cómo sacar el índice correspondiente. Debería normalizarlo ¿no?

no entiendo lo de:
// usar >> y & para que quede en 0-15

Por cierto, ¿no sería mejor que el array fuera matriz bidimensional para los valores x,y?.

VECTOR TablaNormales[256][256];

Normal = TablaNormales[PendienteVertical][PendienteHorizontal];

[marcode]

Bueno, al final no será necesario lo de precalcularlos, he sustituido la función CalcularNormal por sus correspondientes operaciones, y me he dado cuenta de que muchas de ellas eran multiplicaciones por cero y operaciones redundantes de manera que basta con esto para calcular la normal de cada triángulo.

Código [Seleccionar] Expand


PendienteX = Altura[z][x+1] - Altura[z][x];
PendienteZ = Altura[z+1][x] - Altura[z][x];

Normal.y = size * size;
Normal.x = -size * PendienteX;
Normal.z = Normal.x - (size * (PendienteZ - PendienteX));


No sé si se podrá reducir más.

Ahora el problema que tengo es que consume más tiempo el normalizar al tener que calcular la raiz cuadrada de la distancia. ¿hay alguna forma de hacerlo sin tener que usar esa operación?.

[JL10]

Hay un artículo muy interesante que creo que es lo que necesitas para calcular las normales de forma rápida. Es muy simple y muy similar al planteamiento que estais presentando. Lo he visto funcionar y es  impresionante.

Fast Heightfield Normal Calculation de Jason Shankel (Maxis). Está en Game Programming Gems 3, 2003.

Abstract: Heightfields are two-dimensional arrays of height values, commonly used to store terrain or water surface data, and are also commonly used for calculating bump maps. This article will describe how we can take advantage of the special characteristics of heightfield meshes to significantly optimize vertex normal calculation.

[Fran]

Perdon, me confundí, quería decir que haces el producto vectorial de los cuatro vectores que van desde el punto del terreno a los puntos adyacentes y te salen cuatro vectores, esos cuatro los sumas y lo divides entre cuatro, y te sale la normal.

¿? Para nada

[Fran]

No podéis usar simplemente los 4 vértices vecinos porque no tenéis en cuenta que pueden formar parte de triángulos distintos, dependiendo de si por ellos pasa diagonal de triángulo o solamente los ejes horizontal y vertical.
El métido correcto es sumando las normales de los polígonos que usan el vértice.

Has dicho que no necesitas precisión, así que se me acaba de ocurrir un algoritmo rápido.
Sin cálculos costosos salvo la normalización final. Especialmente si puedes generar el mapa de alturas Z con enteros en lugar de floats.

Mira el siguiente mapa:


Para calcular la normal del vértice 0 deberias sumar las normales de los triángulos A, B, C y D.

El truco es calcular las normales de esos triángulos ¿ verdad ?
Observa lo siguiente:
La normal del triángulo A es la del plano definido por las 2 rectas que pasan por el vértice 0 y a su vez una pasa por el vértice 1 y la otra por el vértice 2.
Vale, fijate ahora que ambas rectas son paralelas a X o a Y (Z es la altura). Si calculas la pendiente de cada una de ellas (restas la altura de un vértice de la del otro) sigues definiendo con un solo número a la recta, porque sabes que es paralela a X o a Y.

Dadas dos pendientes 01 y 02 que definen las rectas del triángulo, las combinas en un solo entero y lo usas como indice de una tabla precalculada.

Hemos reducido el cálculo de la normal de un triángulo a 2 restas, un OR, un desplazamiento de bits y una consulta en tabla:

Código [Seleccionar] Expand


pendienteHorizontal= ( v1.Z - v0.Z ) ; // usar >> y & para que quede en 0-15
pendienteVertical= ( v2.Z - v0.Z ) ; // usar >> y & para que quede en 0-15

normalTriangulo = tablaNormales256Valores [ (pendienteHorizontal << 4) | pendienteVertical  ];


Donde tablaNormales256Valores es un array que contiene 256 vector3 lo cual equivale a una matriz de 16x16. Podias haber usado una matriz también.

Vértices alternos suman 4 normales, y los otros, 8. Si hubieses hecho una una malla con todas las diagonales iguales, todos los vértices sumarian 6 normales. Casos especiales los bordes del mapa.

El blucle y las estructuras internas te las buscas tu; o bien haces varias pasadas y arrays intermedios o usas un bucle con muchas variables intermedias.

ingenioso. se va a notar un huevo si se ven tanques desplazándose p.e. pero está bien

[habier]

hola,

yo para calcular las normales de los vertices (por si te vale de algo) he usado lo del smoothing group del fichero 3ds, pero en tu caso que creo que no tienes smoothing group vi por ahi que lo q se hacia es lo que se llama average normals, que no se si es lo mismo que comentabais atras.. pero es bastante sencillo.. seria esto nada mas:

for each vertex {
  vertex normal = zero
}
for each face {
  calculate face normal
  add face normal to all 3 vertex normals of face
}
for each vertex {
  noramlize vertex normal
}

osea, tienes un array de normales con N normales, y N es el numero de vertices, y cada vez q pasas por un triangulo sumas a la vertex normal de los 3 vertices del triangulo la face normal de ese triangulo. Y al final normalizas.

[marcode]

Sí, así es como lo hice. Pero el problema que tenía después es que el normalizar todos los vértices me consumía casi todo el proceso. Hasta tal punto que desistí de introducir en una tabla las normales precalculadas como se me recomendó, ya que no me iba a solucionar prácticamente nada.

Y es que el problema es que el normalizar requiere del cálculo de la raiz cuadrada, esta es la función que uso y que está dentro de la clase VECTOR:

Código [Seleccionar] Expand


inline void Normalize()
{
float size = sqrt( x*x + y*y + z*z );
if (size==0) return;
x/=size, y/=size, z/=size;
}


Ya pregunté antes si se podía conseguir sin usar sqrt pero al no obtener respuesta deduje que no la hay. De todos modos ahora lo tengo un poco aparcado, y estoy más liado con otro proyecto por lo que no me he preocupado excesivamente en buscar una solución.