Ray Tracing
Daniel de Vasconcelos Campos
Tópicos
•
•
•
•
Problema proposto
Análise do problema
Algumas Técnicas Pesquisadas
Algoritmo Implementado
Tópicos
•
•
•
•
Problema proposto
Análise do problema
Algumas Técnicas Pesquisadas
Algoritmo Implementado
Problema Proposto:
• ...” Vejam o programa de traçado de raios que
comentei na aula passada.
A ideia é, sem tirar sua simplicidade, tornálo muito mais eficiente.”
Tópicos
•
•
•
•
Problema proposto
Análise do problema
Algumas Técnicas Pesquisadas
Algoritmo Implementado
Análise do problema :
• Faster Intersection Tests
Usually a large fraction of the compute
time in ray tracing is spent in rayprimitive
intersections. This was already noted in 1980
by Whitted [Whitted80],who reported 95% of
his compute time to be spent on intersection
computations.
Análise do problema :
• Método de Intersecção de primitivas utilizado no
programa :
• Em “object.c”:
double objIntercept( Object* object, Vector origin,
Vector direction )
->Armazena as equações dos planos , e verifica se a
intersecção é interior à primitiva através de
coordenadas baricêntricas.
Análise do problema :
->Não utiliza nenhuma técnica com “Spatial and
Hierarchical Scene Subdivision”.
Análise do problema :
• A priori, duas possibilidades de otimização
levantadas:
1- Melhorar a eficiência para se computar as
intersecções com as primitivas;ou
2- De alguma forma, reduzir o número de
intersecções a serem
computadas.(Introduzindo-se alguma técnica
de estrutura de dados espacial ou de volumes
envolventes ).
Tópicos
•
•
•
•
Problema proposto
Análise do problema
Algumas Técnicas Pesquisados
Algoritmo Implementado
Algumas Técnicas pesquisadas
• Fast, Minimum storage Ray/Triangle
Intersection [ Tomas Möller/Ben Trumbore]
• Ray/Triangle Intersection with Barycentric
Coordinates[Rod Bogart/J.Arenberg]
• Bounding Volumes Hierarchies[4]
• Kd-Trees[5]
Algoritmo levantado para otimização
do programa :
• Reduz significativamente o custo de
armazenamento em memória , evitando
armazenar as equação do plano onde está o
triângulo.
• Não otimiza para todos os tipos de primitivas.
Algoritmo levantado para otimização
do programa :
/**
* Check a ray against a triangle.
* Code by Thomas Akenine-Moller
*/
•
•
•
•
•
•
•
•
•
•
•
•
bool Model::rayTriangleTest( const float tri[ 3 ][ 3 ], const float s[ 3 ], const float d[ 3 ], float &intersection,
float &barU, float &barV ) {
// Thomas Moller's triangle intersection code
float edge1[ 3 ], edge2[ 3 ], tVec[ 3 ], pVec[ 3 ], qVec[ 3 ];
float det, invDet, u, v, tVal;
Utils::sub3f( edge1, tri[ 1 ], tri[ 0 ] );
Utils::sub3f( edge2, tri[ 2 ], tri[ 0 ] );
Utils::cross( pVec, d, edge2 );
det = Utils::dot( edge1, pVec );
Utils::sub3f( tVec, s, tri[ 0 ] );
if ( det > 0.0f ) {
u = Utils::dot( tVec, pVec );
if ( u < 0.0f || u > det )
return false;
Algoritmo levantado para otimização
do programa :
•
•
•
•
•
•
•
•
•
•
•
•
•
return false;
} else
return false;
invDet = 1.0f / det;
tVal = Utils::dot( edge2, qVec ) * invDet;
if ( tVal >= m_epsilon ) {
intersection = tVal;
barU = u * invDet;
barV = v * invDet;
return true;
}
return false;
}
Bounding Volumes
• “A bounding volume is a simple geometric
primitive (usually a box or a sphere) that can
be intersected very quickly. If a ray misses the
bounding volume (which can be checked quite
cheaply), it does not have to be intersected
with the complex primitive at all. Only rays
hitting the bounding volume have to be
checked also against the original primitive”[4]
Bounding Volumes
/**
* Generate the bounding boxes for each object.
*/
void Model::generateBounds() {
for( int objectIndex = 0; objectIndex < m_numObjects; objectIndex++ ) {
float *bounds = m_objects[ objectIndex ].m_bounds;
float *vertices = m_objects[ objectIndex ].m_vertices;
Utils::setf3( bounds, vertices );
Utils::setf3( &bounds[ 3 ], vertices ); // Set bounds to be exactly the first vertex
for( int i = 1; i < m_objects[ objectIndex ].m_numVertices; i++ ) {
if ( bounds[ 0 ] > vertices[ i * 3 ] )
bounds[ 0 ] = vertices[ i * 3 ];
if ( bounds[ 1 ] > vertices[ i * 3 + 1 ] )
bounds[ 1 ] = vertices[ i * 3 + 1 ];
if ( bounds[ 2 ] > vertices[ i * 3 + 2 ] )
bounds[ 2 ] = vertices[ i * 3 + 2 ];
if ( bounds[ 3 ] < vertices[ i * 3 ] )
bounds[ 3 ] = vertices[ i * 3 ];
if ( bounds[ 4 ] < vertices[ i * 3 + 1 ] )
bounds[ 4 ] = vertices[ i * 3 + 1 ];
if ( bounds[ 5 ] < vertices[ i * 3 + 2 ] )
bounds[ 5 ] = vertices[ i * 3 + 2 ];
}
}
}
Referências
• [1]Fast, Minimum storage Ray/Triangle
Intersection [ Tomas Möller/Ben Trumbore]
• [2]Ray/Triangle Intersection with Barycentric
Coordinates[Rod Bogart/J.Arenberg]
• [3]Physically Based Image Synthesis: from
theory to implementation[Matt Pharr and
Greg Humphreys
• [4]Realtime Ray Tracing andInteractive Global
Illumination[Ingo Wald]
Referências
• [5]An Introductory Tutorial on Kd-trees
[Andrew W. Moore]
Tópicos
•
•
•
•
Problema proposto
Análise do problema
Algumas Técnicas Pesquisadas
Algoritmo Implementado