Funciones trigonométricas optimizadas?

[melon]

Muy buenas gente.
Pues el caso es que en mi programa tengo que realizar un montón de operaciones trigonométricas cada vez que se renderiza la pantalla (es una aplicación en 3D).
De las operaciones con matrices de transformación ya se encarga OpenGL, pero el caso es que necesito calcular constantemente unas cuantas arcotangentes y raíces cuadradas y me preguntaba si no serán las funciones de la unidad math un poco lentas para lo que quiero... Conocéis alguna implementación optimizada de estas funciones? Me suena que por ejemplo Quake utilizaba algoritmos propios optimizados que eran como cien veces más rápidos, pero tampoco es plan, además no estoy seguro del todo...
Un saludo.

[OSKR]

Ignoro bastante sobre este caso (el de la optimización) pero si fuera mi caso yo probaría creando registros de las operaciones q ya haya ejecutado previamente (algo asi como loq hace el TLB (Translation Lookaside buffer) de la cahe de datos y direcciones) pero al fin y al cabo son mas operaciones..........bueno..........no es la mejor ......... .rayos !!......mmmmmmmmm pero si probaria la diferencia de tiempo entre una función propia y la función de librería, por ejemplo podría usar el Polinomio Interpolante de Lagrange u otro semejante para no ir a extremos donde usaría varias pares ordenados q son puntos reales de la función q se ha de probar para q él devuelva el resultado estimado mediante la interpolación ante una X no ingresada...los resultados son muy buenospero sería cuestión de probar su rapidez

[melon]

Lo que comentas de la interpolación, había pensado en una interpolación a tramos (rectas) en base a puntos conocidos, supongo que será será lo de lagrange que comentas, hace ya años que estudié cálculo y mi memoria es bastante limitada...
Para los senos y cosenos me acuerdo hace muuuucho tiempo con el turbopascal que para agilizar mi 'motor-chapuza 3d' almacenaba los valores en tablas, entonces era peligroso porque siempre iba apurado de memoria pero hoy en dia... En el caso del arcotangente (más concreto el arctan2 que devuelve el cuadrante) necesita dos parámetros, así que habrá que buscar otra solución. Me he encontrado por ahí algoritmos iterativos pero tienen muy poca precisión.
En cuanto a la raíz cuadrada me he encontrado con la función que utilizan Quake3 y Doom3, pero es que de C ni idea oiga, a ver si alguien la puede traducir me haría un gran favor:

float InvSqrt (float x)
{
    float xhalf = 0.5f*x;
    int i = *(int*)&x;
    i = 0x5f3759df - (i >> 1);
    x = *(float*)&i;
    x = x*(1.5f - xhalf*x*x);
    return x;
}

La he sacado de aquí:
http://http://www.gamedev.net/commun...opic_id=139956
Según comentan es unas 10 veces más rápida que la de math.h, es el algoritmo de Newton-Rhapson y es la inversa(1/sqrt), que por alguna extraña razón es la que usa la gente en historias de 3D.
Seguiremos investigando...

[OSKR]

Jmmmm...yo podría reducir aún más esas lineas..pero bueno.lo q puedes hacer para la raiz cuadrada es un metodo iterativo en donde P es el número original y X es el resulatdo anterior pero inicia desde 1
float Xa,Xb=1;
float P=9;
float epsilon=0.00001; //Margen de error
do
{ Xa=Xb;
Xb=(P+Xa*Xa)/(2*Xa);
}while( abs(Xb-Xa) > epsilon);
este método es muy rápido,el paso de acercamiento a la raiz es exponencial pero aún así el método q muestras se ve atractivo ya q es Complejidad lineal y no hay ciclos, otra vez ....sería cuestión de probar

[OSKR]

En cuanto a Lagrange...hay varios métodos numéricos para eso, es facil rápido, no iterativo si no lo qieres, puede ser predeterminado, yo te recomiendo q lo pruebes, solo necesitas pares ordenados de la funcion a tratar, mientras mas uses, mejor aproximación tendrás, revisaré este tema el lunes o más tarde xq tengo q go away now, busca documentación al respecto y pruebas, avisas cualquier cosa

[[Héctor Randolph]]

Bueno, solo intervengo en este hilo para dar un enlace a una librería que tal vez pueda ser util, se trata de una unidad creada para optimizar la manipulación de vector, matrices y quaterniones.


También incluye algunas funciones como estas:

Empezado por Geometry.pas

// trigonometric functions
function ArcCos(X: Extended): Extended;
function ArcSin(X: Extended): Extended;
function ArcTan2(Y, X: Extended): Extended;
function CoTan(X: Extended): Extended;
function DegToRad(Degrees: Extended): Extended;
function RadToDeg(Radians: Extended): Extended;
procedure SinCos(Theta: Extended; var Sin, Cos: Extended);
function Tan(X: Extended): Extended;

No se pierde nada con revisarlo, espero que sea util.

Saludos

[OSKR]

La vaina es q agarres varios puntos reales de la grafica en cuestion representen cambios en su pendiente como por ejemplo puntos criticos y/o punto de inflexión, donde hay rectas puedes agarrar solo el punto del medio para ajustar la curva despues...............:
<X0,Y0>, <X1,Y1>, <Xn,Yn>
G(x)= Y0(X0-X1)(X0-X2)...(X0-XN)/[(Y0-Y1)(Y0-Y2)...(Y0-YN)]+Y1(X1-X0)(X1-X2)...(X1-Xn)/[(Y1-Y0)(Y1-Y2)...(Y1-YN)]+...Yn(...
Y ESO ES TODO, solo predefines los puntos, puedes reducir algebraicamente la expresion y ya tienes una fórmula q arroja unos puntos muy aproximados o iguales a los de la funcion de donde obtuviste los pares ordenados, en cuanto tenga algo de tiempo yo mismo hare la prueba porq ya tengo curiosidad de saber cual es mas rápida

[melon]

Pues da la casualidad que ya hago uso de esa librería, forma parte de GLScene, pasó a llamarse VectorGeometry con el tiempo, y aunque tiene cosas realmente útiles he probado todas esas funciones y no son más rápidas que las que vienen predefinidas en math, aunque pudiera parecerlo puesto que están escritas casi todas en ensamblador, la única función que es sustancialmente más rápida es FastArcTan2 (iterativa), aunque tiene una precisión realmente baja, del orden de 4 grados...
En cuanto al resto, lo cierto es que parece interesante, a ver si saco algo de tiempo y hago algunas pruebas.
Un saludo.

[OSKR]

Tal vez en aqellas funciones se usan métodos iterativos y en cuanto a las lineas del ensamblador es relativo aqello de ser más rápido, depende de más de un factor, supón q tienes una función algebráica-exponencial predefinida, tal vez sea más rápida q una iterativa o dada por aproximaciones. .......nota: Aún no lo he probado.

[mamcx]

Hace unas semanas estaba buscando como hacer Latent Semantic Analysis y Single Value decomposition, y encontre varias librerias de Delphi. Date por google con "Delphi math" y encontraras varias....