GPU-RT: Interseccion con el Triangulo

La interseccion del rayo con el triangulo (paradojicamente) es mas complicada que con la esfera, y ademas trae aparejado un nuevo problema: el texture mapping.

Probablemente este es uno de los motivos por el cuales el rasterizer es mas eficiente que el ray-tracing. El triangulo desde el pto de vista del rasterizador, solo tiene que calcular 3 vertices y despues interpola todo. Pero para el raytracing son todos rayos independientes en los cuales tiene que calcular intersecciones.

El mayor problema con la interseccion entre el rayo el triangulo es que algebraicamente podemos hayar facilmente la interseccion entre la recta y el plano. Pero luego tenemos que verificar que el punto este dentro del triangulo.

Afortunadamente, este tema esta sumamente estudiado, y usualmente se usan las coordeandas baricentricas para expresar la posicion de un punto dentro de un triangulo.

(solo la parte que habla del triangulo)
http://en.wikipedia.org/wiki/Barycentric_coordinates_(mathematics)

Pero se los resumo, las coordenas baricentricas de un punto son P, con respecto a un triangulo de vertices A,B y C son, b y g tal que :

P = A*(1-b-g) + B*b + C*g;
con b>=0, g>=0

Y tienen la propiedad que si el punto esta adentro del triangulo se cumple que b+g<=1, de hecho si b+g = 1 esta justo en la frontera del triangulo.

Las coordenadas baricentricas nos resuelven 2 problemas al mismo tiempo: primero si el punto esta adentro del triangulo, y ademas despues nos sirven para interpolar cualquier valor definido en los 3 vertices, para cualquier otro punto del triangulo. Asi es como funciona intermanente la GPU. Lamentablemente nosotros no estamos usando el pipeline, con lo cual lo tenemos que reprogramar a manopla:

Haciendo un poco de cuentas, para calcular la interseccion y las baricentricas necesitamos resolver unos 3 determinantes, afortunadamente la funcion de determinante esta acelerada por hard, y hay una funcion del hlsl.

El codigo queda asi:

// Triangulo
//------------------------------------------
float3 A = tex2D( g_samObj, float2(j+0.5,i+0.5)/OBJ_SIZE);
float3 B = tex2D( g_samObj2, float2(j+0.5,i+0.5)/OBJ_SIZE);
float3 C = tex2D( g_samObj3, float2(j+0.5,i+0.5)/OBJ_SIZE);
float3x3 M = float3x3( B-A,C-A,-D);
float det = determinant(M);
if(det!=0)
{
    float3x3 M3 = float3x3( B-A,C-A,LF-A);
    float b,g,t;
    t = determinant(M3)/det;
    if(t>0 && t<R)
    {
        float3x3 M1 = float3x3( LF-A,C-A,-D);
        b = determinant(M1)/det;
        if(b>=0)
        {
            float3x3 M2 = float3x3( B-A,LF-A,-D);
            g = determinant(M2)/det;
            if(g>=0 && b+g<=1)
            {
                // nota: Ip = A*(1-b-g) + B*b + C*g;
                // coordenadas baricentricas: a , b y g 
                // (a+b+g = 1)
                R = t;
                Ip = LF+D*t;        // punto de interseccion
                objsel = t;
                i_sel = i;
                j_sel = j;
                tipo_sel = 1;
                bc_b = b;
                bc_g = g;
                // calculo la normal
                N = -normalize(cross(B-A,C-A));
            }
        }
    }
}

Mas adelante (en el "pipeline" del raytracing), cuando se necesita calcular el color del pixel, lo unico que se tienen son las coordenadas baricentricas donde el rayo intesecto al triangulo.
Para relacionarlo con la textura, necesitamos mas informacion, asi que seguimos agregando datos a los objetos. El caso del triangulo es uno de los que mas datos requiere: 3 posiciones x 3 vertices + 2 coordenadas uv x 3 vertices, de momento tenemos 4 texturas formato D3DFMT_A32B32G32R32F (llamemosla g_pTexObj,g_pTexObj2, etc) + una textura D3DFMT_X8R8G8B8, (llamada g_pTexObjT)
La textura g_pTexObjT de momento solo usa el canal R para el tipo de objeto (0==esfera, 1==triangulo, etc)
Las texturas g_pTexObj guardan el resto de la info (para el caso del triangulo)
g_pTexObj.x -> coordenada x del primer vertice
g_pTexObj.y -> coordenada y del primer vertice
g_pTexObj.z -> z del primer vertice
g_pTexObj.w -> coordenada u de textura primer vertice

g_pTexObj2.x -> coordenada x del segundo vertice vertice
etc etc..

Las coordendas v de la textura (que no entraban) hubo que meterlas en
g_pTexObj.x = coordenada de textura V del primer vertice
g_pTexObj.y, g_pTexObj.z idem segundo y tercer vertice.

Bueno, cuando llega el momento de tomar el color del pixel de la textura, se acceden a todas estas texturas, y si interpola, usando las baricentricas:

// nota: Ip = A*(1-b-g) + B*b + C*g;
// intersecto en el triangulo
// tomo los datos del objeto
float4 A = tex2D( g_samObj, float2(j_sel+0.5,i_sel+0.5)/OBJ_SIZE);
float4 B = tex2D( g_samObj2, float2(j_sel+0.5,i_sel+0.5)/OBJ_SIZE);
float4 C = tex2D( g_samObj3, float2(j_sel+0.5,i_sel+0.5)/OBJ_SIZE);
float4 D = tex2D( g_samObj4, float2(j_sel+0.5,i_sel+0.5)/OBJ_SIZE);
// tomo las coordenadas uv de cada punto
float2 txA = float2(A.w,D.x);
float2 txB = float2(B.w,D.y);
float2 txC = float2(C.w,D.z);
// interpolo la textura en el triangulo                
float2 tex = txA*(1-bc_b-bc_g) + txB*bc_b + txC*bc_g;
float3 color_obj = tex2D( g_samDef, tex);
float kd = dot(N,g_vLightDir);        // luz diffusa
color_actual = (k_la + (1-k_la)*kd)*color_obj;

Bueno...vamos a tratar de ir llegando a la imagen del wikipedia....sacando las diferencias!!!