Projeto Virtual Worlds

Computação Gráfica 3D em C

Arquivos Mensais: junho 2014

Dois casos de clipping que parecem complicados (mas não são!)

Um amigo me chama a atenção para os dois casos abaixo:

Caso 1

Caso 1

Caso 2

Caso 2

Em ambos os casos acabaremos com 3 triângulos depois dos recortes. Notem que existem 2 planos de clipping (n1n2). Isso significa que a explicação que dei no último post sobre esse assunto (este aqui) continua válido, basta aplicar as regras um plano por vez. Verifique que no caso 1, por exemplo, se escolhermos primeiro o plano n1, obteremos 2 triângulos. Depois, ambos terão que ser recortados pelo plano n2, (experimente!).

É claro que poderíamos tornar o caso 1 especial. Afinal, basta dividir o quadrilátero formado no primeiro quadrante em dois triângulos. Mas, neste caso, teríamos outros casos “especiais” a considerar (por exemplo, coloque o ponto A, do triângulo do caso 2, no terceiro quadrante, ou seja, atrás de ambos os planos, mantendo os pontos B e C no lugar onde estão!).

 

Anúncios

Shaders!

Você já ouviu falar muito sobre eles. Shaders nada mais são do que pequenos programas que são executados em paralelo no interior de sua placa de vídeo. Toda placa de vídeo moderna possui uma unidade de processamento gráfica (GPU), capaz de processar n rotinas simultâneamente. A placa de vídeo de meu desktop, por exemplo, é uma NVIDIA GeForce GT 635, capaz de processar 384 rotinas em paralelo ( especificação aqui ). Em essência, é isto, somada ao clock, texture fill rate e capacidade de memória que definem o poder de sua placa de vídeo… Memória, sozinha, só te diz o quanto de texturas e buffers a placa suporta, nada mais…

Daqui para frente veremos apenas as características de shaders relativos ao padrão OpenGL. Não muda lá grandes coisas com relação ao DirectX 10, só muda no nome dado aos tipos de shaders.

OpenGL lida com alguns tipos diferentes de shaders:

Vertex Shaders

São programinhas que lidam com os vértices que são fornecidos para a placa de vídeo, via vertex buffer objects, por exemplo. Sempre que receebe um vértice (ou um conjunto deles), a placa de vídeo executa um vertex shader.

Geometry Shader

Um geometry shader é um programinha que lida com um conjunto de vértices simultaneamente. Uma analogia é esta: Enquanto o vertex shader lida com os vértices separadamente, o geometry shader lida com triângulos, separadamente.

Tesselation Shaders (Control & Evaluation)

Esses são dois shaders, adicionados ao OpenGL 4.0, e especializados na operação de tesselation. Lembra-se que falei sobre clipping anteriormente, onde, ao recortar um triângulo o transformamos em dois triângulos? Isso pode ser feito por esses shaders.

Fragment Shader

Depois que um triângulo é rasterizado, ou seja, “preenchido”, o fragment shader é chamado para cada candidato à pixel… Essa é uma distinção importante: Pixels são artefatos visuais, você os vê na tela… fragmentos são pixels que ainda não são visíveis (e podem ser modificados ou descartados!). Este é o shader mais importante de todos. Graças ao paralelismo, minha placa de vídeo pode processar, potencialmente, 384 “fragmentos” de uma vez só…

Compute Shader

Este shader foi adicionado ao OpenGL 4.3. Trata-se de shaders genéricos, disassociados de operações gráficas específicas (pelo menos, em teoria).

Desses shaders os de uso obrigatório são vertex e fragment shaders.

Eis códigos de exemplo para ambos os shaders numa pequena aplicação que desenha um triângulo na tela:

/* simple.vert */
#version 130

in vec3 vrtx;
in vec4 clr;

out vec4 color;

void main()
{
  gl_Position = vec4(vrtx, 1.0);
  color = clr;
}
/* simple.frag */
#version 130

in vec4 color;

void main()
{
  gl_FragColor = color;
}

Os códigos lembram um bocado C, não é? Essa é uma das belezas de GLSL… Além de parecer muito com C, tem alguns atalhos para tipos mais complexos como vetores e matrizes (e também funções especializadas como derivação, produto escalar, vetorial, normalização, etc).

Cada shader tem o seu conjunto de “variáveis intrínsecas”, todas começadas com “gl_”. Vertex shaders são feitos para modificarem variáveis como gl_Position… Os fragment shaders modificam variáveis diferentes (um exemplo é gl_FragColor).

No exemplo acima, o vertex shader com nome “simple.vert” obtém dois atributos do vertex buffer object: A posição do vértice e a cor do mesmo. A função main() simplemente copia o vértice para gl_Position e repassa a cor para a variável de saída color (que será usada como entrada para o fragment shader). Esse é um exemplo simples. Num código mais “real” poderíamos passar matrizes de transformação e criamos algo assim:

gl_Position = ProjectionMatrix * ModelViewMatrix * vrtx;

Com isso poderíamos transladar os vértices, escaloná-los, rotacioná-los, etc… Matrizes e outras constantes são passadas ao shader via tipos especiais de variáveis “in” chamadas uniforms. Essencialmente, são constantes. Atributos sofrem interpolação, como você verá abaixo…

No nosso exemplo, o fragment shader, por sua vez, pega a cor e a copia para gl_FragColor, que será usada para acender um pixel no framenbuffer. Poderíamos passar para o fragment shader informações sobre o vetor de visualização, o vetor de irradiância de fontes luminosas, um intervalo de tempo, etc… tudo para calcular a cor do fragmento (pixel).

É importante notar que do vertex shader para o fragment shader existem interpolações. Ou seja, a cor do vértice inicial e final são respeitadas, mas as cores intermediárias são calculadas tomando esses dois como base. E, sim, os vértices também são “interpolados”… eles transformam-se em “linhas” que definem os “cantos” do triângulo! Abaixo temos o resultado com base no código de exemplo (que desenha um triângulo com vértices de cores diferentes). Leia as descrições nos comentários para melhor entendimento do código… No final deste artigo coloco também um link para uma página interessante sobre fragment shaders…

Saída do código de exemplo.

Saída do código de exemplo.

/* Para compilar o exemplo:
$ gcc -O3 -march=native `pkg-config --cflags glfw2 gl` -c exemplo.c
$ gcc -O3 -o exemplo exemplo.o -lm `pkg-config --libs glfw2 gl`
*/
#include <stdlib.h>
#include <stdio.h>
#include <setjmp.h>
#include <GL/glfw.h>
#include <GL/gl.h>

/* Tamanho padrão de nossa janela (framebuffer). */
#define WINDOW_WIDTH 640
#define WINDOW_HEIGHT 480

// Macro usada para atribuir offsets aos Vertex Attribute Pointers.
#define BUFFER_OFFSET(ofs) (NULL + (ofs))

// "Handle" do programa contendo shaders.
static unsigned int shaders_program;

static void InitOpenGL(void);
static char *LoadText(const char *filename);
static int LoadShaders(unsigned int *program);
static unsigned int CreateVAO(void);
static void DrawVAO(int vao, size_t triangles);

int main(void)
{
  /* *** INICIALIZAÇÃO do contexto gráfico usando GLFW 2 *** */
  /* OBS: Por que não uso GLFW 3? Por que não está disponível, por
          default, nos repositórios do Debian ou Ubuntu! E já tive
          problemas ao compilar o GLFW 3 para esses ambientes! */
  if (glfwInit() == GL_FALSE)
  {
    fprintf(stderr, "initializing graphics library");
    exit(EXIT_FAILURE);
  }

  /* O tratamento de eventos é feito "manualmente", daqui pra frente. */
  glfwDisable(GLFW_AUTO_POLL_EVENTS);

  /* Usando o core profile do OpenGL 3.0 (uma de minhas máquinas de teste
     só suporta a versão 3!) */
  glfwOpenWindowHint(GLFW_OPENGL_VERSION_MAJOR, 3);
  glfwOpenWindowHint(GLFW_OPENGL_VERSION_MINOR, 0);

  /* Se a extensão GLX_ARB_create_context_profile não estiver disponível,
     então: ajustar o profile é parcialmente suportado e;
     Se GLX_ARB_create_context_profile não estiver disponível, então usar
     GLFW_OPENGL_CORE_PROFILE fará glfwOpenWindow() falhar! */
  if (glfwExtensionSupported("GLX_ARB_create_context_profile"))
    glfwOpenWindowHint(GLFW_OPENGL_PROFILE, GLFW_OPENGL_CORE_PROFILE);

  /* Se a extensão GLX_ARB_multisample_extension não estiver disponível,
     então ajustar GLFW_FSAA_SAMPLES não tem efeito. */
  glfwOpenWindowHint(GLFW_FSAA_SAMPLES, 4);

  /* Cria a janela. */
  if ( !glfwOpenWindow(WINDOW_WIDTH, WINDOW_HEIGHT,
                       8, 8, 8, 8, /* rgba bits (8 para cada componente) */
                       24,         /* depth buffer bits (prefiro 24, é mais
                                      seguro que seja suportado) */
                       0,          /* Não vamos usar stencil buffer. */
                       GLFW_WINDOW) )
  {
    glfwTerminate();
    fprintf(stderr, "cannot open window");
    exit(EXIT_FAILURE);
  }

  /* Vamos sumir com o mouse. */
  glfwDisable(GLFW_MOUSE_CURSOR);

  InitOpenGL();

  if (LoadShaders(&shaders_program) != 0)
    exit(EXIT_FAILURE);

  CreateVAO();
  glUseProgram(shaders_program);

  for (;;)
  {
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

    /* NOTE: VAO já está "bound", neste ponto. */
    glDrawArrays(GL_TRIANGLES, 0, 3); /* count é o número de vertices, não o de
                                         triângulos! GL_TRIANGLES só indica que
                                         o OpenGL irá desenhar triangulos! */

    glfwPollEvents();

    /* Sai do loop se apertar ESC. */
    if (glfwGetKey(GLFW_KEY_ESC) == GLFW_PRESS)
      break;

    glfwSwapBuffers();
  }

  glfwTerminate();
  return 0;
}

// Initializa OpenGL.
static void InitOpenGL(void)
{
  glViewport(0, 0, WINDOW_WIDTH, WINDOW_HEIGHT);

  glClearColor(0.0f, 0.0f, 0.0f, 1.0f);
  glClearDepth(1.0f);
  glEnable(GL_CULL_FACE);
  glFrontFace(GL_CCW);
  glCullFace(GL_BACK);

  /* Liga o teste de profundidade.
     Desnecessário neste teste! */
  glEnable(GL_DEPTH_TEST);
  glDepthFunc(GL_LESS);
}

// Função auxiliar: Apenas lê um arquivo texto e o coloca num buffer. */
static char *LoadText(const char *filename)
{
  long filesize;
  char *buffer = NULL;
  FILE *fin;
  jmp_buf jb;

  if ((fin = fopen(filename, "rb")) != NULL)
  {
    if (setjmp(jb))
    {
      fclose(fin);
      return NULL;
    }

    fseek(fin, 0L, SEEK_END);

    if ((filesize = ftell(fin)) <= 0)
      longjmp(jb, 1);

    fseek(fin, 0L, SEEK_SET);

    if ((buffer = malloc(filesize + 1)) == NULL)
      longjmp(jb, 1);

    if (fread(buffer, filesize, 1, fin) != 1)
    {
      free(buffer);
      longjmp(jb, 1);
    }

    *(buffer + filesize) = '\0';

    fclose(fin);
  }

  return buffer;
}

/* Carrega, compila e linka os shaders.

   Cada 'shader' precisa ter seu código fonte passado para
   o OpenGL, precisa ser compilado, separadamente, e depois linkado
   um 'programa'.

   Repare que isso é exatamente o que um compilador faz. Ou seja,
   GLSL é uma linguagem compilada. Código específico para a GPU
   é gerado e instalado na placa de vídeo.
*/
static int LoadShaders(unsigned int *program)
{
  char *vertex_shader;
  char *fragment_shader;
  int status;
  int len;
  char log[256];
  unsigned int vs, fs;

  /* Carrega vertex shader do disco. */
  if ((vertex_shader = LoadText("simple.vert")) == NULL)
  {
    fprintf(stderr, "Erro carregando Vertex Shader.\n");
    return -1;
  }

  /* Cria e compila o vertex shader. */
  vs = glCreateShader(GL_VERTEX_SHADER);
  glShaderSource(vs, 1, &vertex_shader, NULL);
  free(vertex_shader); /* Não precisamos mais do código fonte. */
  glCompileShader(vs);

  /* Verifica se houveram erros de compilação. */
  glGetShaderiv(vs, GL_COMPILE_STATUS, &status);

  if (!status)
  {
    glGetShaderInfoLog(vs, sizeof(log) - 1, &len, log);
    fprintf(stderr, "Error compiling vertex shader:\n\t%s\n", log);
    return -1;
  }

  /* Mesma coisa para o fragment shader. */
  if ((fragment_shader = LoadText("simple.frag")) == NULL)
  {
    fprintf(stderr, "Erro carregando Fragment Shader.\n");
    return -1;
  }

  fs = glCreateShader(GL_FRAGMENT_SHADER);
  glShaderSource(fs, 1, &fragment_shader, NULL);
  free(fragment_shader); /* Não precisamos mais do texto carregado. */
  glCompileShader(fs);
  glGetShaderiv(fs, GL_COMPILE_STATUS, &status);

  if (!status)
  {
    glGetShaderInfoLog(fs, sizeof(log) - 1, &len, log);
    fprintf(stderr, "Error compiling fragment shader:\n\t%s\n", log);
    return -1;
  }

  /* Cria um 'programa', adiciona os shaders a ele e os 'linka'. */
  *program = glCreateProgram();
  glAttachShader(*program, vs);
  glAttachShader(*program, fs);

  /* Como GLSL 1.3 (do OpenGL 3.0), aparentemente, não tem "layout"
     nos shaders, então é preciso definir a localização de variáveis
     globais (atributos) dos shaders aqui. Note que 'vrtx' e 'clr' são
     os atributos 'in' do vertex shader, na ordem que eles aparentecem.
  */
  glBindAttribLocation(*program, 0, "vrtx"); /* vertex */
  glBindAttribLocation(*program, 1, "clr"); /* color */

  glLinkProgram(*program);

  /* Verifica se houve erro de 'linkagem'. */
  glGetProgramiv(*program, GL_LINK_STATUS, &status);

  if (!status)
  {
    glGetProgramInfoLog(vs, sizeof(log) - 1, &len, log);
    fprintf(stderr, "Error linking shaders program:\n\t%s\n", log);
    return -1;
  }

  return 0;
}

/* Cria o <em>Vertex Array Object</em> e os <em>Vertex Buffer Objects</em>.
   Para esse exemplo escolhi criar buffers diferentes para
   os vértices e as cores dos vértices. Poderíamos ter criado
   um buffer só com uma estrutura contendo as duas informações. */
static unsigned int CreateVAO(void)
{
  /* Esses arrays vão desaparecer no final da função. */
  float points[] =
  {
    0.0f, 0.5f, 0.0f,
    -0.5f, -0.5f, 0.0f,
    0.5f, -0.5f, 0.0f
  };

  float colors[] =
  {
    0.0f, 0.0f, 1.0f, 1.0f,
    0.0f, 1.0f, 0.0f, 1.0f,
    1.0f, 0.0f, 0.0f, 1.0f
  };

  /* NOTE: Os vértices são definidos no sentido anti-horário, bem como
           a ordem das cores dos vértices. */

  unsigned int vao, vbo[2];

  glGenVertexArrays(1, &vao);
  glBindVertexArray(vao);

  /* Cria 2 buffers objects. Um para conter os vértices e outro para
     as cores dos vértices. */
  glGenBuffers(2, vbo);

  /* Carrega o vbo com os vertices e associa os atributos. */
  glBindBuffer(GL_ARRAY_BUFFER, vbo[0]);
  glBufferData(GL_ARRAY_BUFFER, sizeof(points), points, GL_STATIC_DRAW);
  glEnableVertexAttribArray(0);
  glVertexAttribPointer(0, 3, GL_FLOAT, 0, 0, BUFFER_OFFSET(0));

  /* Carrega o vbo com as cores e associa os atributos. */
  glBindBuffer(GL_ARRAY_BUFFER, vbo[1]);
  glBufferData(GL_ARRAY_BUFFER, sizeof(colors), colors, GL_STATIC_DRAW);
  glEnableVertexAttribArray(1);
  glVertexAttribPointer(1, 4, GL_FLOAT, 0, 0, BUFFER_OFFSET(0));

  /* Neste ponto o Vertex Array Object contém as referências aos buffer
     objects e aos atributos de cada buffer. Se fizessemos:
     glBindVertexArray(0), poderíamos recuperar todas as referências,
     refazendo o bind. Daí, é só chamar glDrawArrays para desenhar.

     Se não me engano, um Vertex Array também contém os binds
     de texturas. */

  /* NOTE: Neste exemplo, ao sair, o VAO continuará "bounded". */

  return vao;
}

Visite a página GLSL Sandbox Galery. lá você encontrará uma série de exemplos usando fragment shaders, usando a especificação OpenGL ES, existentes em browsers capazes de renderizar, via WebGL. Ou seja, funciona com qualquer um exceto o Internet Explorer! O que os autores fazem é desenhar um retângulo (QUAD) no framebuffer (canvas) e usar um fragment shader para obter os efeitos desejados (alguns muito interessantes!).

Mudança de base e “bump mapping”

Eis mais uma demonstração do poder das matrizes. Especialmente quanto falamos de mudança de base do sistema de coordenadas (ou, no jargão da álgebra linear: do subespaço vetorial).

Dê uma olhada nas 3 texturas abaixo:

Textura original, mapa de normais e textura modificada.

Textura original, mapa de normais e textura modificada.

A textura da esquerda é a original, parece com um muro de pedra, mas é “achatada” (se você rotacioná-la verá o efeito). A textura do meio, azulada, é, na verdade, um mapa com os vetores normais de cada pixel da textura, usada para causar o efeito final, o da textura da direita, onde o “rejunte” está  num nível abaixo do das pedras.

Cada componente da textura do meio equivale ao comprimento de um vetor numa base bem definida: R corresponde ao vetor associado ao eixo X; G ao Y; e B ao Z. A imagem é azulada porque o vetor Z é o mesmo do vetor normal original. O vetor normal original é o mais proeminente. Os outros dois são usados para modificar o vetor normal original. Por isso as bordas das pedras, nessa textura, têm cores tendendo ao violeta (componente R grande) ou ao “ciano” (componente G grande).

Visualmente, esses vetores correspondem ao diagrama abaixo:

Visualizando os vetores tangente e binormal.

Visualizando os vetores tangente e binormal.

Essa textura central é baseada, ou seja, tem como base do sistema de coordenadas, 3 vetores unitários: O vetor normal original e dois outros, chamados de tangente e binormal (ou bitangente). Tudo o que um shader tem que fazer para obter o vetor original é saber qual é a base e aplicar a mudança de base abaixo:

\displaystyle \vec{N}' = \begin{bmatrix} \vec{t}^T \\ \vec{b}^T \\ \vec{n}^T \end{bmatrix} \cdot \vec{N}

Onde \vec{t} é o vetor tangente, \vec{b} é o binormal e \vec{n} é o normal; obtidos do vertex buffer, junto com os outros atributos do vértice. \vec{N} são as 3 coordenadas obtidas da textura do meio e \vec{N}' é o vetor normal recalculado. Como quem fará esse calculo é o fragment shader, o vetor \vec{N} é obtido da textura via um Sampler. Ou seja, cada pixel da textura é um vetor. Mas, diferente da figura anterior, cada um dos vetores “tangentes” e o vetor “normal” são definidos para cada um dos vértices.

Note que a equação acima, na verdade, é uma conversão de base do sistema de coordenadas original, onde o vetor normal está para outro, baseado na superfície do objeto e \vec{N} “perturba” o vetor normal original… Ainda existe um passo intermediário: Os valores de \vec{N} precisam estar na faixa entre [-1,1], ao invés de [0,1], como acontece com os valores RGB numa textura. Isso pode ser facilmente feito escalonando \vec{N} duas vezes (multiplicando por 2) e subtraindo 1.

Calculando a iluminação:

Ainda não chegamos lá, mas um modelo para calcular iluminação (especialmente iluminação “ambiente”) é através do produto escalar entre o vetor normal e o vetor diretor da fonte de luz. Já que estamos “dando um solavanco” (bumping) os vetores normais de cada pixel, a impressão que ficará é a de que a superfície do objeto texturizado é, de fato, parecida com um muro, com rejunte e tudo. Pode-se enxergar esses “solavancos” na figura simplificada abaixo:

Antes e depois do "solavanco".

Antes e depois do “solavanco”.

O problema do bump mapping:

Nem tudo é perfeito… Bump Mapping tem um problema: A ilusão de profundidade só pode ser mantida em alguns casos. Se a superfície estiver voltada diretamente para a câmera, a ilusão ficará perfeita, mas rotacione a superfície e o encanto se quebra. A figura abaixo ilustra:

Bump Mapping e Parallax Mapping, lado a lado.

Bump Mapping e Parallax Mapping, lado a lado.

Do lado esquerdo temos um cubo texturizado e usando a técnica descrita acima. Do lado direito, temos o mesmo cubo, usando uma técnica diferente, mais complexa, chamada Steep Parallax Mapping.

Em ambos os casos temos o mesmo cubo (liso) com a mesma textura aplicada, mas com diferentes tipos de mapas de vetores normais, usando diferentes técnicas. Descreverei Steep Parallax Mapping assim que entendê-la melhor…

Isso não significa que bump mapping seja ruim… Dê uma olhada, por exemplo, no jogo Watch Dogs. Especialmente nos teclados que aparecem no jogo, sobre mesas… Eles são colocados lá por bump mapping e, ás vezes, dá para perceber o efeito acima… mas, só às vezes! :)

Explicando transformações lineares melhor do que eu poderia fazê-lo…

Veja esse playlist: Clique aqui

Uma outra interpretação de Matrix4x4LookAt

Não causa estranheza que a matriz de transformação usada por Matrix4x4LookAt seja transversa? Num de meus momentos de “meditação” sobre o assunto percebi outra possível interpretação para tal fato. Lembram-se que o produto escalar de um vetor \vec{v} por um vetor unitário \vec{u} nos dá a projeção do primeiro sobre o segundo? E que um produto escalar é definido por:

\displaystyle\vec{v}\cdot\vec{u}=v_x\cdot u_x+v_y\cdot u_y+v_z\cdot u_z

Assim, faz todo sentido obter as projeções de um vetor \vec{v} sobre os eixos do novo sistema de coordenadas através da multiplicação da matrix transversa M^T, não é? Com isso você obtem os novos valores de (x,y,z) do vetor no novo sistema de coordenadas:

\vec{{v_x}'}=\vec{v}\cdot\vec{v_{side}} \\  \vec{{v_y}'}=\vec{v}\cdot\vec{v_{up}} \\  \vec{{v_z}'}=-\vec{v}\cdot\vec{v_{fw}}

Ou, de forma matricial:

\displaystyle \vec{v'} = \begin{bmatrix} \vec{side}^T \\ \vec{up}^T \\ -\vec{fw}^T \\ 1 \end{bmatrix} \cdot \vec{v}

Simples assim.

Explicando Matrix4x4LookAt

No código de Matrix4x4LookAt, no último artigo, eu disse que ao multiplicar a matriz transposta composta pelos vetores sideup e -forward obtemos uma “reorientação” do sistema de coordenadas view. Mas, por quê?

A coisa toda pode ser entendida assim: Considere que uma transformação geométrica sobre um vetor v qualquer é dada por:

\displaystyle \vec{v'} = M\vec{v}

Onde \vec{v'} é o vetor transformado (reposicionado), M é a matriz de transformação e \vec{v} é o vetor original. Se usarmos uma matriz de identidade, temos (exemplo em 2D):

\displaystyle \vec{v'} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \cdot \vec{v}

\displaystyle \begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} x \\ y \end{bmatrix}

Uma matriz nada mais é do que uma coleção de vetores. No caso da matriz de identidade os vetores são [1 0]T e [0 1]T:

\displaystyle \vec{i} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}\,\quad \vec{j} = \begin{bmatrix} 0 \\ 1 \end{bmatrix}\,\quad \begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} \vec{i} & \vec{j} \end{bmatrix} \cdot \begin{bmatrix} x \\ y \end{bmatrix}

O primeito vetor é o alinhado com o eixo x e o segundo, com o eixo y. A transformação acima é chamada “identidade” porque, no fim das contas, \vec{v'} será idêntico ao vetor \vec{v}.

Acontece que também podemos fazer uma transformação “contrária” (M^{-1}\cdot\vec{v'}=\vec{v}), ou seja, se a matriz estava sendo multiplicada do lado direito, ela passa pro lado esquerdo “dividindo”, mas como a divisão de matrizes ou vetores e matrizes não é definida, temos que inverter a matriz. Qualquer um que já tenha estudado algebra linear sabe que calcular uma matriz inversa é uma tarefa um pouco chata. Envolve alguns passos. Só que podemos usar um atalho em alguns casos: Quando uma matriz é composta de vetores unitários e perpendiculares entre si, então sua inversa é idêntica à sua transposta. Este é o caso de sistemas de coordenadas que nos interessam. O sitema de cordenada view é composto de 3 vetores “diretores”, perpendiculares entre si e o “novo” sistema de coordenadas – o da câmera – também (sideup-forward)…

No contexto da função Matrix4x4LookAt, podemos entender o uso da matriz transposta da seguinte maneira: Do lado esquerdo da equação teríamos uma transformação do vetor final, com relação à câmera, e do lado direito, uma ou mais transformações em relação ao sistema de coordenadas view. Como estamos interessados apenas no valor final de \vec{v'}, temos:

\displaystyle M_{lookup}\cdot\vec{v'}=M_{view}\cdot\vec{v}

\displaystyle \vec{v'} = M_{view}\cdot M^{T}_{lookup}\cdot\vec{v}

Pronto! Basta agora “afastar” a câmera de acordo com as coordenadas do vetor eye e a transformação está completa:

\displaystyle \vec{v'} = M_{translate}\cdot M_{view}\cdot M^{T}_{lookup}\cdot\vec{v}

Rotinas que foram retiradas do OpenGL 3+

O modo core profile do OpenGL retirou uma série de rotinas do seu repertório. Dentre elas, as rotinas de manipulação de matrizes (que foram colocadas à cargo dos shaders) e as rotinas da GLU (GL Utilities).

Lidar com matrizes é algo muito útil em computação gráfica. Permite uma maneira unificada e centralizada de realizar transformações geométricas, por exemplo. Como OpenGL “jogou fora” essas rotinas, provavelmente porque é mais fácil que o desenvolvedor use alguma biblioteca externa para evitar as limitações das pilhas de matrizes, temos que implementar nossas próprias. A primeira é a multiplicação de matrizes.

Vale lembrar que OpenGL lida, por padrão, com matrizes orientadas por coluna. Ou seja, diferente do padrão de C, onde matrizes são orientadas por linha (o incremento de um ponteiro que aponta para uma matriz apontará para o próximo item da linha). Uma maneira de visualizar a multiplicação de matrizes orientadas por coluna (column major) é este:

Coluna de A e linha de B, multiplicadas, dá item em C.

Coluna de A e linha de B, multiplicadas, dá item em C.

E, também, só para lembrar, a ordem da multiplicação é da direita para esquerda. Isso é assim porque a multiplicação de uma matriz por um vetor é feita assim:

\displaystyle \begin{bmatrix}x'\\y'\\z'\\w'\end{bmatrix}=\begin{bmatrix}m_1&m_5&m_9&m_{13}\\m_2&m_6&m_{10}&m_{14}\\m_3&m_7&m_{11}&m_{15}\\m_4&m_8&m_{12}&m_{16}\end{bmatrix}\cdot\begin{bmatrix}x\\y\\z\\w\end{bmatrix}

E matrizes podem ser encaradas como sendo um vetor de vetores. Cada coluna (mas matrizes column major) é um vetor.

A rotina de multiplicação de matrizes “padrão” é algo mais ou menos assim:

void Matrix4x4Multiply(float *mOut, const float *m1, const float *m2)
{
  int i, c, r;

  for (c = 0; c < 4; c++)
    for (r = 0; r < 4; r++)
    {
      mOut[c*4+r] = 0.0f;
      for (i = 0; i < 4; i++)
        mOut[c*4+r] += m1[c*4+i] * m2[i*4+r];
    }
}

Isso ai funciona muito bem, mas eis uma rotina um pouco mais veloz, usando SSE. Se você debugar a função abaixo, ela faz exatamente o que a função acima faz, mas usa 2 loops, ao invés de 3 – a rotina acima realiza 16 inicializações, 64 multiplicações e 64 adições. A rotina abaixo faz 16 adições e 16 multiplicações (de blocos de 4 floats):

void Matrix4x4Multiply(float *mOut, const float *m1, const float *m2)
{
  int i, j;
  __m128 a_column, b_column, r_column;

  for (i = 0; i < 16; i += 4)
  {
    b_column = _mm_set1_ps(b[i]);
    a_column = _mm_load_ps(a);
    r_column = _mm_mul_ps(a_column, b_column);

    for (j = 1; j < 4; j++)
    {
      b_column = _mm_set1_ps(b[i+j]);
      a_column = _mm_load_ps(&amp;a[j*4]);
      r_column = _mm_add_ps(_mm_mul_ps(a_column, b_column), r_column);
    }

    _mm_store_ps(&amp;out[i], r_column);
  }
}

Eis a rotina que substitui a glLoadIdentity(). Trata-se de uma simples cópia de 4 blocos de 4 floats, usando SSE:

void Matrix4x4Identity(float *m)
{
  static __m128 t[4] = { { 1.0f, 0.0f, 0.0f, 0.0f },
                         { 0.0f, 1.0f, 0.0f, 0.0f },
                         { 0.0f, 0.0f, 1.0f, 0.0f },
                         { 0.0f, 0.0f, 0.0f, 1.0f } };
  __m128 *p = (__m128 *)m;
  int i;

  for (i = 0; i < 4; i++)
    p[i] = t[i];
}

Uma função que não tem equivalente direto nas rotinas do OpenGL, mas é útil na manipulação de operações com matrizes, é a transposição. Transposição é uma transformação de uma matriz onde linhas viram colunas (e vice versa). A rotina pode ser implemtnada com dois loops, mas, usando SSE, e um pequeno macete, fica mais rápido:

void Matrix4x4Transpose(float *mOut, const float *mIn)
{
  __m128 m[4], t[4];

  m[0] = _mm_load_ps(mIn);
  m[1] = _mm_load_ps(mIn + 4);
  m[2] = _mm_load_ps(mIn + 8);
  m[3] = _mm_load_ps(mIn + 12);

  t[0] = _mm_unpacklo_ps(m[0], m[1]);
  t[1] = _mm_unpacklo_ps(m[2], m[3]);
  t[2] = _mm_unpackhi_ps(m[0], m[1]);
  t[3] = _mm_unpackhi_ps(m[2], m[3]);

  _mm_store_ps(mOut,      _mm_movelh_ps(t[0], t[1]));
  _mm_store_ps(mOut + 4,  _mm_movehl_ps(t[1], t[0]));
  _mm_store_ps(mOut + 8,  _mm_movelh_ps(t[2], t[3]));
  _mm_store_ps(mOut + 12, _mm_movehl_ps(t[3], t[2]));
}

As rotinas glFrustum, gluPerspective e gluLookAt também sumiram do OpenGL (do GL Utilities). Como todas as três são, de fato, manipulação de matrizes (as duas primeiras manipulam a matriz de projeção, a última, a matriz ModelView), ei-las:

/* Frustum projection Matrix. */
void Matrix4x4Frustum(float *mOut, float l, float r, float b, float t, float n, float f)
{
  float rml = r - l;
  float tmb = t - b;
  float fmn = f - n;
  float n2 = 2.0f * n;

  mOut[1] = mOut[2] = mOut[3] =
  mOut[4] = mOut[6] = mOut[7] =
  mOut[12] = mOut[13] = mOut[15] = 0.0f;

  mOut[0] = n2 / rml;

  mOut[5] = n2 / tmb;

  mOut[8] = (r+l) / rml;
  mOut[9] = (t+b) / tmb;
  mOut[10] = -(f+n) / fmn;
  mOut[11] = -1.0f;

  mOut[14] = -(f * n2) / fmn;
}

/* Substitui gluPerspective (cria um frustum 'simétrico'). */
void Matrix4x4Perspective(float *mOut, float fov, float aspectratio, float n, float f)
{
  float xmax, ymax;

  ymax = n * tanf(DEG2RAD(fov));
  xmax = ymax * aspectratio;
  Matrix4x4Frustum(mOut, -xmax, xmax, -ymax, ymax, n, f);
}

/* Substitui gluLookAt */
void Matrix4x4LookAt(float *mOut, const float *mIn, const float *eye, const float *target, const float *up)
{
  float fw[3], side[3], _up[3];
  float matrix2[16], resultMatrix[16];

  Vector3Sub(fw, target, eye);
  Vector3SelfNormalize(fw);

  /* o vetor 'side' aponta para a esquerda da câmera. */
  Vector3Cross(side, fw, up);
  Vector3SelfNormalize(side);

  /* _up é, necessariamente, unitário! E é recalculado aqui
     para evitar o inconveniente de termos um vetor 'up' não
     perpendicular aos vetores 'forward' e 'side'. */
  Vector3Cross(_up, side, fw);

  /* Poderia inserir os 3 vetores via função Vector3Copy, sobre uma
     matriz de identidade, mas assim parece ser mais rápido. */
  matrix2[0] = side[0];
  matrix2[4] = side[1];
  matrix2[8] = side[2];

  matrix2[1] = _up[0];
  matrix2[5] = _up[1];
  matrix2[9] = _up[2];

  /* Note que se a câmera está orientada para (0,-1,0), então 'target' terá
     um componnte z menor que o de 'eye'. O vetor 'forward' será negativo,
     por isso temos que invertê-lo. */
  matrix2[2] = -fw[0];
  matrix2[6] = -fw[1];
  matrix2[10] = -fw[2];

  matrix2[3] = matrix2[7] = matrix2[11] = 
  matrix2[12] = matrix2[13] = matrix2[14] = 0.0f;
  matrix2[15] = 1.0f;

  Matrix4x4Multiply(resultMatrix, mIn, matrix2);

  /* Aproveita 'matrix2' para criar a matriz de translação. */
  Matrix4x4Identity(matrix2);
  matrix2[3] = -eye[0];
  matrix2[7] = -eye[1];
  matrix2[11] = -eye[2];
  Matrix4x4Multiply(mOut, resultMatrix, matrix2);
}

A função Matrix4x4Frustum simplesmente implementa a matriz padrão do frustum genérico do OpenGL:

\displaystyle \begin{bmatrix}\frac{2n}{r-l} & 0 & \frac{r+l}{r-l} & 0 \\ 0 & \frac{2n}{t-b} & \frac{t+b}{t-b} & 0 \\ 0 & 0 & -\frac{f+n}{f-n} & -\frac{2fn}{f-n} \\ 0 & 0 & -1 & 0 \end{bmatrix}

A função Matrix4x4Perspective implementa exatamente o que gluPerspective faz: Ela cria um frustum simétrico, baseado no campo de visão (field of view), em graus, e no “aspect ratio” do plano “near” (4:3, 16:9, etc). Essa função calcula os valores do retângulo visível do plano near [os pontos (left, bottom) e (right, top)], onde a câmera aponta exatamente para o centro do retângulo, e chama Matrix4x4Frustum.

A função Matrix4x4LookAt é um pouco mais complicada… Ela calcula a translação para um novo sistema de coordenadas baseado nos 3 eixos onde a câmera está. Primeiro, calculamos o vetor que vai da posição da câmera (coordenada eye) para o alvo (target) e o chamamos de fw (de “forward”). Esse vetor é normalizado porque precisamos de um vetor unitário para compor o novo sistema de coordenadas. Neste ponto temos os vetores fwup e precisamos do terceiro vetor,, perpendicular a esses dois, que chamaremos de side. Por isso os produtos vetoriais. De posse dos 3 vetores, montamos a matriz transposta da matriz abaixo:

\displaystyle M_{lookAt}=\begin{bmatrix}s_x & up_x & -fw_x & 0 \\s_y & up_y & -fw_y & 0 \\s_z & up_z & -fw_z & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}

Essa matriz (ou, melhor, sua transposta) “reorienta” o sistema de coordenadas de visualização. Precisamos afastar a câmera para a posição desejada e, por isso, uma matriz de translação final é usada:

\displaystyle T=\begin{bmatrix}1&0&0&-eye_x\\ 0&1&0&-eye_y\\ 0&0&1&-eye_z\\ 0&0&0&1\end{bmatrix}\cdot T_{view}\cdot\begin{bmatrix}s_x&s_y&s_z&0\\up_x&up_y&up_z&0\\-fw_x&-fw_y&-fw_z&0\\0&0&0&1\end{bmatrix}

A matriz T_{view}, inicial, geralmente é uma identidade.

Notou também que recalculamos o vetor \vec{up}? Isso torna a precaução de usar a dica da projeção de \vec{up} sobre \vec{forward} (aqui) desnecessária.

Usando papel e tesoura – recortando triângulos…

Imagine que você tenha um objeto complexo, feito com milhares de triângulos, por exemplo, este:

Mesh complexo de triângulos - formando um terreno.

Mesh complexo de triângulos – formando um terreno.

Parte dos triângulos no mesh não são visíveis para a câmera, como você pode observar. O que se deve fazer, neste caso, é recortar parte do mesh e desenhar apenas aqueles triângulos que são, de fato, visíveis. Este é um dos motivos da existência das rotinas de frustum culling. O frustum é uma figura trapezoide imaginária que existe na frente da câmera. Uma de seuas funções é usar os 6 planos que o definem para recortar os objetos que estão total ou parcialmente no seu interior e “jogar fora” todo o resto.

Uma nota de rodapé: Podemos usar sub-frustums, definidos por “portais” no mapa (que consta numa BSP) para determinar a visibilidade de objetos nas diversas regiões do mapa, a partir da posição da câmera, e recortar aqueles que não são visíveis, descartando-os.

Mas, ainda temos um problema: O que fazer com aqueles triângulos que são apenas parcialmente visíveis? Temos que pegar a tesoura e recortá-los para que caibam na parte vísivel, jogando fora as arestas! Neste processo de recorte alguns, senão muitos, triângulos que formam um objeto serão transformados em quadriláteros, como mostrado na figura abaixo:

Triângulo recortado por plano. Área cinza é descartada.

Triângulo recortado por plano. Área cinza é descartada.

O recorte é feito contra um dos planos do frustum. O que está dentro do frustum pode ser visto, o que está fora, não.

Na figura acima, ao ser recortado pelo plano o triângulo ABC é “transformado” no quadrilátero ABB’A’ (node o sentido anti-horário!). A mesma coisa não acontece se apenas um vértice do triângulo estiver do lado de “dentro” do frustum:

Triângulo recortao por plano. Área cinza é descatada.

Triângulo recortao por plano. Área cinza é descatada.

Sempre que temos apenas um dos vértices dentro do frustum vamos obter um triângulo, no recorte. Como regra geral, se apenas um vértice encontra-se do lado de fora do frustum, acabamos com um quadrilátero. Mas, como estamos lidando apenas com triângulos, precisaremos transformar um polígono (no caso, um quadrilátero) em um conjunto de triângulos. Esse processo chama-se tesselation. No nosso caso, fazer isso é simples. Basta escolher um dos vértices originais dentro do frustum e um dos novos vértices, no lado oposto, que está sobre o plano de clipping:

"Tesselando" o quadrilátero em 2 triângulos.

“Tesselando” o quadrilátero em 2 triângulos.

Outra coisa que você pode notar é que, não importa como os triângulos estejam dispostos, precisaremos obter dois novos vértices em dois dos lados (edges), exceto em um único caso: Se um dos vértices estiver precisamente sobre o plano de clipping. Neste caso, a área resultante também não precisará passar pelo processo de tesselation, já que a área “branca” continuará sendo um triângulo. A maneira de resolver essa possibilidade é considerar que se a distância do vértice ao plano for menor ou igual a zero, então ele está “atrás” do plano, deixando um vértice à frente o outro atrás.

Claro, que se todos os 3 vértices estiverem na frente do plano, nenhum clipping é necessário!

Bem… cadê o código para realizar o clippingtesselation? Você não vai encontrá-lo no código em C do projeto…. Isso é tarefa para os shaders. Se processarmos cada triângulo da cena sequencialmente, o tempo gasto será excessivo e os shaders são processos que executam em paralelo. No caso, os geometry shaderstesselation shaders operam em conjuntos de vértices. Se sua placa de vídeo pode usar 1024 shaders, por exemplo, cerca de 1024 triângulos podem ser clippadostesselados (se é que esses verbos existem) ao mesmo tempo.

Depois de explicar todos os tipos de shaders e seus funcionamentos, explicarei como implementar clipping.

Um raio interceptando um plano

Uma rotinazinha útil para ser usada com BSPs é a de interceptação de um raio com um plano. Um “raio” é definido aqui como um ponto no sistema de coordenadas associado com um vetor que dá uma direção. A equação é essa aqui:

\displaystyle \vec{r}=\dot{q}+t\vec{v}

Onde t é um valor usado para escalonar o vetor unitário \vec{v}. E \dot{q} é a posição inicial do raio.

Nós vimos, anteriormente, que um plano também segue uma equação:

\displaystyle \vec{n}\cdot\dot{p}+d=0

Como queremos encontrar um ponto \dot{r} que está exatamente sobre a superfície do plano, substituímos a equação do raio na do plano e temos:

\displaystyle \begin{matrix}\vec{n}\cdot\dot{r}+d=0,\\\vec{n}\cdot(\dot{q}+t\vec{v})+d=0,\\\vec{n}\cdot\dot{q}+t(\vec{n}\cdot\vec{v})+d=0,\\t(\vec{n}\cdot\vec{v})=-(\vec{n}\cdot\dot{q}+d),\\t=\frac{-(\vec{n}\cdot\dot{q}+d)}{\vec{n}\cdot\vec{v}}\end{matrix}

Note que o numerador é a equação do plano, que equivale à chamada a função PlageGetDistanceFromPoint(). Assim, a equação para encontrar um ponto do raio de intercepta um plano é:

\displaystyle p_{intercept} = \dot{p}+\vec{v}\cdot\frac{-(\vec{n}\cdot\dot{q}+d)}{\vec{n}\cdot\vec{v}}

Onde \dot{p} é a coordenada inicial do raio, \vec{v} é o vetor unitário que dá a direção do raio e \vec{n} e ‘d’  fazem parte da equação do plano.

Isso nos dá o ponto p_{intercept}. Mas, existem dois detalhes: O produto escalar \vec{n}\cdot\vec{v}, se for zero, nos diz que o vetor direcional do raio é paralelo ao plano (chama-se vetor coplanar) e, portanto, não pode haver intersecção – este é o primeiro teste. O segundo teste é o numerador … se a distância do ponto \dot{q} até o plano for zero, significa que ele já está localizado no plano!

O primeiro teste faz todo sentido: Se um vetor qualquer for perpendicular a um vetor unitário, isto significa que o cosseno do ângulo entre eles é zero! Isso nos dá uma rotina útil para o módulo plane.c:

int PlaneInterceptedRay(float *vout, const float *plane, 
                        const float *pos, const float *vdir)
{
  float d, du;
  float u[3];

  /* Precisamos do vetor unitário de direção para calcular a escala. */
  Vector3Normalize(u, vdir);

  if ((du = Vector3Dot(plane, u)) == 0.0f)
    return -1;  /* coplanar? */

  /* Pertence ao plano? */
  if ((d = -PlaneGetDistanceFromPoint(plane, pos)) == 0.0f)
  {
    Vector3Copy(vout, pos);
    return 0;
  }

  Vector3Scale(vout, u, (d / du));
  Vector3Add(vout, pos);

  return 0;
}

Você pode estar se perguntando qual é a utilidade de descobrirmos um ponto de uma linha que intercepta um plano… Posso citar pelo menos dois: Recorte e visibilidade. Recorte é uma maneira de nos livrarmos de pedaços de triângulos que não são visíveis e quanto à visibilidade, diversos algorítmos podem usar isso: O desenho de sombras, por exemplo, depende da interceptação de feixes de luz com o plano onde a sombra aparecerá!