Computação Gráfica

CG é uma área da computação dedicada a criação, armazenamento e manipulação de imagens baseada em modelos matemáticos.

Lecture 1

Iniciaremos nosso curso aprendendo como construir uma imagem.

Portable Pixel Map (PPM)

O formato PPM nasceu no final da década de $80$ para compartilhar imagens facilmente entre diferentes plataformas.

Figure 1. Definição da Wikipedia

Código

Podemos escrever um código em C para construir uma imagem usando o formato PPM. Este objetivo será alcançado através da análise do programa ppm_create.c.

Figure 2. Imagem PPM construída a partir do código "ppm_create.c"

/**
 * \file ppm_create.c
 *
 * \brief Criacao de uma imagem em PPM.
 *
 * \author
 * Petrucio Ricardo Tavares de Medeiros \n
 * Universidade Federal Rural do Semi-Árido \n
 * Departamento de Engenharias e Tecnologia \n
 * petrucio at ufersa (dot) edu (dot) br
 *
 * \version 1.0
 * \date April 2025
 */

#include <stdio.h>

int main(){

  // dimensoes da imagem
  int width = 256;
  int height = 256;

  // Configurando o header do formato PPM
  printf("P3\n %d \t %d\n 255\n", width, height);

  for (int i = 0; i < height; i++){ // Altura
    for (int j = 0; j < width; j++){ // Largura
      printf("%d \t %d \t %d \n", i, j, 63);
    }
  }

  return 0;
}

Descrição do programa

Inserimos na primeira linha do arquivo a biblioteca para lidar com entrada/saída de dados na linguagem C.

#include <stdio.h>

Definimos as dimensões (largura e altura) da imagem que estamos construindo.

int width = 256;
int height = 256;

Em seguida, configuramos o cabeçalho do formato PPM.

printf("P3\n %d \t %d\n 255\n", width, height);

No laço de repetição, percorremos a largura e altura da imagem preenchendo as cores dos pixels.

for (int i = 0; i < height; i++){ // Altura
    for (int j = 0; j < width; j++){ // Largura
      printf("%d \t %d \t %d \n", i, j, 63);
    }
}

Compilação

O processo de compilação é realizado através do compilador GCC através do seguinte comando:

gcc <nome_arquivo>.c -o <nome_executavel>

Este comando criará um arquivo executável e a saída deve ser direcionada para um arquivo com extensão ".ppm".

./<nome_executavel> > output.ppm

Exercício

Construa uma imagem $100 \times 100$ usando o formato PPM com fundo preto que tem apenas 1 pixel vermelho no centro da imagem.
Implemente uma função que altera o valor de um pixel da imagem.
Codifique uma função que salva a imagem no formato PPM.
Crie uma função que inicializa uma imagem com branco.
Construa uma imagem $100 \times 100$ usando o formato PPM com fundo preto e escreva o caractere ' T ' no centro da imagem com alto contraste em relação ao fundo da imagem.

Lecture 2

Nesta parte da disciplina aprenderemos como renderizar um segmento de reta usando as equações vetoriais.

Segmento de reta

Sejam $A = (x_0, y_0, z_0)$ e $B = (x_1, y_1, z_1)$ dois pontos do espaço. Podemos traçar uma equação da reta entre esses dois pontos usando a equação: $r(t) = A + t( B - A)$, onde $t \in [0, 1$].

Figure 3. Segmento de reta

Código

O algoritmo de renderização do segmento de reta está disponível no arquivo linesegment.c.

/**
 * \file linesegment.c
 *
 * \brief Implementação do segmento de reta usando equacoes vetoriais.
 *
 * \author
 * Petrucio Ricardo Tavares de Medeiros \n
 * Universidade Federal Rural do Semi-Árido \n
 * Departamento de Engenharias e Tecnologia \n
 * petrucio at ufersa (dot) edu (dot) br
 *
 * \version 1.0
 * \date May 2025
 */

#include <stdio.h>

#define width 200
#define height 200

unsigned char image[height][width][3];

// Funcao para preencher um pixel na imagem
void putPixel( int x, int y, unsigned char r, unsigned char g, unsigned char b){
  if (( x >= 0 ) && ( x <= width )  && ( y >= 0 ) && ( y <= height )){
    image[x][y][0] = r;
    image[x][y][1] = g;
    image[x][y][2] = b;
  }
}

// Funcao para limpar a imagem
void clearImage(){
  for (int y = 0; y < height; y++)
    for (int x = 0; x < width; x++)
      putPixel(x, y, 255, 255, 255);
}

// Funcao para salvar imagem no formato PPM
void saveImage(){
  // Configurando o header do formato PPM
  printf("P3\n %d \t %d\n 255\n", width, height);

  for (int y = 0; y < height; y++){ // Altura
    for (int x = 0; x < width; x++){ // Largura
      for (int c = 0; c < 3; c++){ // Canal: r, g, b
        printf("%d \t", image[x][y][c]);
      }
      printf("\n");
    }
  }
}

// Algoritmo do Segmento de Reta
void drawLine( int x0, int y0, int x1, int y1 ){
  for (float t = 0.0; t < 1.0; t = t + 0.001){
    putPixel((int)(x0 + (x1 - x0)*t), (int)(y0 + (y1 - y0)*t), 255, 0, 0 );
  }
}

int main(){

  // Limpar a imagem
  clearImage();

  // Executar o algoritmo
  drawLine(0, 0, 200, 200);

  // Salvar a imagem em PPM
  saveImage();

  return 0;
}

Descrição do programa

Iniciamos nosso programa incluindo a biblioteca padrão da linguagem C para gerar entrada/saída de dados.

#include <stdio.h>

Após a declaração da biblioteca, definimos globalmente as dimensões da imagem e a variável da imagem como um array multidimensional que armazena valores de 8 bits sem sinal.

#define width 200
#define height 200

unsigned char image[height][width][3];

Posteriormente, declarei algumas funções úteis para manipulação da imagem. A primeira delas é a função para setar um pixel na imagem.

void putPixel( int x, int y, unsigned char r, unsigned char g, unsigned char b){
  if (( x >= 0 ) && ( x <= width )  && ( y >= 0 ) && ( y <= height )){
    image[x][y][0] = r;
    image[x][y][1] = g;
    image[x][y][2] = b;
  }
}

A segunda função é necessária para preencher a imagem com uma cor de fundo.

void clearImage(){
  for (int y = 0; y < height; y++)
    for (int x = 0; x < width; x++)
      putPixel(x, y, 255, 255, 255);
}

Por fim, a última função é responsável por salvar o array multidimensional em formato PPM.

void saveImage(){
  // Configurando o header do formato PPM
  printf("P3\n %d \t %d\n 255\n", width, height);

  for (int y = 0; y < height; y++){ // Altura
    for (int x = 0; x < width; x++){ // Largura
      for (int c = 0; c < 3; c++){ // Canal: r, g, b
        printf("%d \t", image[x][y][c]);
      }
      printf("\n");
    }
  }
}

O algoritmo de renderização do segmento de reta é implementado em seguida.

void drawLine( int x0, int y0, int x1, int y1 ){
  for (float t = 0.0; t < 1.0; t = t + 0.001){
    putPixel((int)(x0 + (x1 - x0)*t), (int)(y0 + (y1 - y0)*t), 255, 0, 0 );
  }
}

Renderização de modelos 3D

O formato .obj (Wavefront OBJ) é um padrão amplamente utilizado para representar modelos 3D de forma simples e legível. Ele armazena informações sobre vértices (v), normais (vn), texturas (vt) e faces (f), onde cada face é formada por índices que referenciam os vértices previamente definidos. As faces podem ser triangulares ou poligonais e podem incluir referências opcionais a coordenadas de textura e normais no formato f v/vt/vn.

Figure 4. Modelo tridimensional gerado a partir da renderização em wireframe

O processo de renderização do modelo 3D exige arquivos .obj adquiridos livremente no domínio free3d.com. Os modelos utilizados na imagem acima foram wolf.obj, drone.obj e cranio.obj.

Código

A implementação do código de renderização 3D é realizada através dos arquivos: model.h que contém todos os protótipos de funções que serão úteis para manipulação dos modelos 3D, model.c é o arquivo que contém as implementações das funções de manipulação dos modelos 3D e wireframe.c que realiza a execução das funções implementadas.

/**
 * \file model.h
 *
 * \brief Header com protótipos de funções para manipulação de modelo 3D.
 *
 * \author
 * Petrucio Ricardo Tavares de Medeiros \n
 * Universidade Federal Rural do Semi-Árido \n
 * Departamento de Engenharias e Tecnologia \n
 * petrucio at ufersa (dot) edu (dot) br
 *
 * \version 1.0
 * \date May 2025
 */

#ifndef MODEL_H
#define MODEL_H

#define WIDTH 800
#define HEIGHT 800
#define MAX_VERTICES 50000
#define MAX_FACES 50000
#define MAX_FACE_VERTS 32

typedef struct {
  float x, y, z;
} Vertex;

typedef struct {
  int verts[MAX_FACE_VERTS];
  int n;
} Face;

void set_pixel(int x, int y, unsigned char r, unsigned char g, unsigned char b);

void clr();

void save();

void draw_line(int x0, int y0, int x1, int y1);

int load_obj(const char *filename, Vertex *vertices, int *vcount, Face *faces, int *fcount);

void resizing( Vertex v0, Vertex v1 );

void render_faces(Vertex *vertices, Face *faces, int vcount, int fcount);


#endif

/**
 * \file model.c
 *
 * \brief Implementação das funções de manipulação do modelo 3D.
 *
 * \author
 * Petrucio Ricardo Tavares de Medeiros \n
 * Universidade Federal Rural do Semi-Árido \n
 * Departamento de Engenharias e Tecnologia \n
 * petrucio at ufersa (dot) edu (dot) br
 *
 * \version 1.0
 * \date May 2025
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#include "model.h"

unsigned char image[HEIGHT][WIDTH][3];

void set_pixel(int x, int y, unsigned char r, unsigned char g, unsigned char b) {
  if (x >= 0 && x < WIDTH && y >= 0 && y < HEIGHT) {
    image[y][x][0] = r;
    image[y][x][1] = g;
    image[y][x][2] = b;
  }
}

void draw_line(int x0, int y0, int x1, int y1) {
  for (float t = 0.0; t < 1.0; t = t + 0.0001)
    set_pixel((int)x0+(x1-x0)*t, (int)y0+(y1-y0)*t, 0, 0, 0);
}

void clr(){
  for(int i = 0; i < WIDTH; i++)
    for(int j = 0; j < HEIGHT; j++)
      for(int c = 0; c < 3; c++)
        image[i][j][c] = 255;
}

void save(){
  printf("P3\n %d \t %d\n 255\n", WIDTH, HEIGHT);
  for(int i = 0; i < WIDTH; i++){
    for(int j = 0; j < HEIGHT; j++){
      for(int c = 0; c < 3; c++){
        printf("%d \t", image[i][j][c]);
      }
      printf("\n");
    }
  }
}

int load_obj(const char *filename, Vertex *vertices, int *vcount, Face *faces,
             int *fcount) {
    FILE *file = fopen(filename, "r");
    if (!file) {
        perror("Erro ao abrir o arquivo");
        return 0;
    }

    char line[512];
    *vcount = 0;
    *fcount = 0;

    while (fgets(line, sizeof(line), file)) {
        if (strncmp(line, "v ", 2) == 0) {
            if (sscanf(line + 2, "%f %f %f", &vertices[*vcount].x,
                       &vertices[*vcount].y, &vertices[*vcount].z) == 3) {
                (*vcount)++;
            }
        } else if (strncmp(line, "f ", 2) == 0) {
            Face face = {.n = 0};
            char *token = strtok(line + 2, " \n");
            while (token && face.n < MAX_FACE_VERTS) {
                int index;
                if (sscanf(token, "%d", &index) == 1) {
                    face.verts[face.n++] = index;
                }
                token = strtok(NULL, " \n");
            }
            faces[(*fcount)++] = face;
        }
    }

    fclose(file);
    return 1;
}

void resizing( Vertex v0, Vertex v1 ){
  int x0 = (int)((v0.x + 1.0f) * WIDTH / 2.0f);
  int y0 = (int)((1.0f - v0.y) * HEIGHT / 2.0f);
  int x1 = (int)((v1.x + 1.0f) * WIDTH / 2.0f);
  int y1 = (int)((1.0f - v1.y) * HEIGHT / 2.0f);

  draw_line(x0, y0, x1, y1);
}


void render_faces(Vertex *vertices, Face *faces, int vcount, int fcount) {
    for (int i = 0; i < fcount; i++) {
        Face face = faces[i];
        for (int j = 0; j < face.n; j++) {
            Vertex v0 = vertices[face.verts[j] - 1];
            Vertex v1 = vertices[face.verts[(j + 1) % face.n] - 1];
            resizing(v0, v1);
        }
    }
}

/**
 * \file wireframe.c
 *
 * \brief Implementação do arquivo principal de renderização do modelo 3D.
 *
 * \author
 * Petrucio Ricardo Tavares de Medeiros \n
 * Universidade Federal Rural do Semi-Árido \n
 * Departamento de Engenharias e Tecnologia \n
 * petrucio at ufersa (dot) edu (dot) br
 *
 * \version 1.0
 * \date May 2025
 */

#include "model.h"

int main() {
    Vertex vertices[MAX_VERTICES];
    Face faces[MAX_FACES];
    int vcount, fcount;

    clr();

    // Lê o arquivo OBJ enviado
    if (!load_obj("models/cranio.obj", vertices, &vcount, faces, &fcount)) {
        return 1;
    }

    // Renderiza as faces no framebuffer
    render_faces(vertices, faces, vcount, fcount);

    save();

    return 0;
}

Compilação

O processo de compilação é realizado através do compilador GCC através do seguinte comando:

gcc <nome_arquivo>.c <nome_biblioteca>.c -o <nome_executavel> -lm

Este comando criará um arquivo executável e a saída deve ser direcionada para um arquivo com extensão ".ppm".

./<nome_executavel> > output.ppm

Exercício

Estudar o código acima substituindo o modelo.
Substitua o modelo usado no código por robot.obj.
Implemente uma função para exibir apenas os pontos (nuvem de pontos) ao invés do arramado (veja imagem abaixo).

Figure 5. Nuvem de pontos gerados a partir de um modelo 3D.

Aplique as transformações estudadas no modelo $3D$.

Lecture 3

Digital Differential Analyze (DDA)

Algoritmo clássico de rasterização de linhas. Este algoritmo utiliza a equação da reta para gerar pontos de uma linha entre dois pontos $(x_{0}, y_{0})$ e $(x_{1}, y_{1})$, incrementando em intervalos fixos.

Figure 6. Linha gerada pelo algoritmo DDA

Código

A implementação do algoritmo DDA (disponível no arquivo dda.c) exige conhecimento prévio de alguns detalhes matemáticos da equação da reta.

/**
 * \file dda.c
 *
 * \brief Implementação do algoritmo DDA.
 *
 * \author
 * Petrucio Ricardo Tavares de Medeiros \n
 * Universidade Federal Rural do Semi-Árido \n
 * Departamento de Engenharias e Tecnologia \n
 * petrucio at ufersa (dot) edu (dot) br
 *
 * \version 1.0
 * \date April 2025
 */

#include <stdio.h>
#include <stdlib.h> // abs

#define width 200
#define height 200

unsigned char image[height][width][3];

// Funcao para preencher um pixel na imagem
void putPixel( int x, int y, unsigned char r, unsigned char g, unsigned char b){
  if (( x >= 0 ) && ( x <= width )  && ( y >= 0 ) && ( y <= height )){
    image[x][y][0] = r;
    image[x][y][1] = g;
    image[x][y][2] = b;
  }
}

// Funcao para limpar a imagem
void clearImage(){
  for (int y = 0; y < height; y++)
    for (int x = 0; x < width; x++)
      putPixel(x, y, 255, 255, 255);
}

// Funcao para salvar imagem no formato PPM
void saveImage(){
  // Configurando o header do formato PPM
  printf("P3\n %d \t %d\n 255\n", width, height);

  for (int y = 0; y < height; y++){ // Altura
    for (int x = 0; x < width; x++){ // Largura
      for (int c = 0; c < 3; c++){ // Canal: r, g, b
        printf("%d \t", image[x][y][c]);
      }
      printf("\n");
    }
  }
}

// Algoritmo DDA
void drawDDA( int x0, int y0, int x1, int y1 ){
  // calcula a variacao
  int dx = x1 - x0;
  int dy = y1 - y0;

  // calcula o número de passos de incremento
  int steps = abs(dx) > abs(dy) ? abs(dx) : abs(dy);

  // define o incremento em cada eixo
  float x_inc = (float) dx / steps;
  float y_inc = (float) dy / steps;

  float x = x0;
  float y = y0;

  for (int i = 0; i <= steps; i++){
    putPixel((int)x, (int)y, 255, 0, 0);
    x += x_inc;
    y += y_inc;
  }
}

int main(){

  // Limpar a imagem
  clearImage();

  // Executar o algoritmo DDA
  drawDDA(0, 0, 200, 200);

  // Salvar a imagem em PPM
  saveImage();

  return 0;
}

Descrição do programa

Iniciamos o código inserindo a biblioteca padrão de entrada/saída de dados da linguagem C e a biblioteca stdlib.h para obter o módulo de um número.

#include <stdio.h>
#include <stdlib.h> // abs

Após inserir as bibliotecas, optei por definir globalmente as dimensões da imagem e a própria imagem como um array multidimensional do tipo caractere sem sinal para representar cada canal de cor com 8 bits.

#define width 200
#define height 200

unsigned char image[height][width][3];

Posteriormente, codifiquei algumas funções que serão úteis para manipular as imagens PPM. A primeira função foi para setar um valor de cor para um pixel.

void putPixel( int x, int y, unsigned char r, unsigned char g, unsigned char b){
  if (( x >= 0 ) && ( x <= width )  && ( y >= 0 ) && ( y <= height )){
    image[x][y][0] = r;
    image[x][y][1] = g;
    image[x][y][2] = b;
  }
}

A segunda função que implementei que nos ajudará é a função para preencher com branco toda a imagem.

void clearImage(){
  for (int y = 0; y < height; y++)
    for (int x = 0; x < width; x++)
      putPixel(x, y, 255, 255, 255);
}

Por fim, codifiquei uma função específica para salvar o array multidimensional no formato PPM.

void saveImage(){
  // Configurando o header do formato PPM
  printf("P3\n %d \t %d\n 255\n", width, height);

  for (int y = 0; y < height; y++){ // Altura
    for (int x = 0; x < width; x++){ // Largura
      for (int c = 0; c < 3; c++){ // Canal: r, g, b
        printf("%d \t", image[x][y][c]);
      }
      printf("\n");
    }
  }
}

O algoritmo DDA é implementado seguindo os seguintes passos:

Calcular o valor de variação nos eixos x e y;
Encontra a maior variação e adota ela como número de passos do algoritmo;
Define o incremento em cada eixo;
Pinta do ponto inicial até o ponto final incrementando os incrementos em cada eixo.

void drawDDA( int x0, int y0, int x1, int y1 ){
  // calcula a variacao
  int dx = x1 - x0;
  int dy = y1 - y0;

  // calcula o número de passos de incremento
  int steps = abs(dx) > abs(dy) ? abs(dx) : abs(dy);

  // define o incremento em cada eixo
  float x_inc = (float) dx / steps;
  float y_inc = (float) dy / steps;

  float x = x0;
  float y = y0;

  for (int i = 0; i <= steps; i++){
    putPixel((int)x, (int)y, 255, 0, 0);
    x += x_inc;
    y += y_inc;
  }
}

Análise do algoritmo DDA

Table 1. Avaliando vantagens e desvantagens do algoritmo DDA
Vantagens	Desvantagens
Simples de implementar	Usa ponto flutuante
Funciona em qualquer inclinação	Pode causar acúmulo de erros de arredondamento

Exercícios

Implemente uma função que os argumentos são os pontos de um polígono convexo e o retorno é uma imagem PPM.
Edite o código de renderização de modelos 3D para usar o algoritmo DDA.
Utilize a biblioteca time.h da linguagem C e verifique o tempo de execução do algoritmo que utiliza equações vetoriais e DDA.

Lecture 4

Bresenham

Jack Bresenham propôs em 1965 no artigo Algorithm for Computer Control of a Digital Plotter um algoritmo de rasterização de linhas com tipo inteiro. No texto Bresenham’s Algorithm contém uma breve explicação sobre o algoritmo.

Figure 7. Linhas gerada pelo algoritmo de Bresenham

Código

A implementação do algoritmo de Bresenham está disponível no arquivo bresenhamLines.c.

/**
 * \file bresenhamLines.c
 *
 * \brief Implementação do algoritmo bresenham para linhas.
 *
 * \author
 * Petrucio Ricardo Tavares de Medeiros \n
 * Universidade Federal Rural do Semi-Árido \n
 * Departamento de Engenharias e Tecnologia \n
 * petrucio at ufersa (dot) edu (dot) br
 *
 * \version 1.0
 * \date April 2025
 */

#include <stdio.h>
#include <stdlib.h> // abs

#define width 200
#define height 200

unsigned char image[height][width][3];

// Funcao para preencher um pixel na imagem
void putPixel( int x, int y, unsigned char r, unsigned char g, unsigned char b){
  if (( x >= 0 ) && ( x <= width )  && ( y >= 0 ) && ( y <= height )){
    image[x][y][0] = r;
    image[x][y][1] = g;
    image[x][y][2] = b;
  }
}

// Funcao para limpar a imagem
void clearImage(){
  for (int y = 0; y < height; y++)
    for (int x = 0; x < width; x++)
      putPixel(x, y, 255, 255, 255);
}

// Funcao para salvar imagem no formato PPM
void saveImage(){
  // Configurando o header do formato PPM
  printf("P3\n %d \t %d\n 255\n", width, height);

  for (int y = 0; y < height; y++){ // Altura
    for (int x = 0; x < width; x++){ // Largura
      for (int c = 0; c < 3; c++){ // Canal: r, g, b
        printf("%d \t", image[x][y][c]);
      }
      printf("\n");
    }
  }
}

// Algoritmo Bresenham (1º quadrante)
void drawBresenhamLinesIncomplete( int x0, int y0, int x1, int y1 ){

  // calcula a variacao
  int dx = x1 - x0;
  int dy = y1 - y0;

  // calcula o erro
  int D = (2 * dy) - dx;

  int x = x0;
  int y = y0;

  putPixel(x, y, 255, 0, 0);

  while (x < x1){
    x = x + 1;
    if ( D < 0 ){
      D = D + (2 * dy);
    }
    else{
      y = y + 1;
      D = D + (2 * ( dy - dx ));
    }
    putPixel(x, y, 255, 0, 0);
  }

}

// Algoritmo Bresenham ( todos os quadrantes )
void drawBresenhamLines( int x0, int y0, int x1, int y1 ){
  // calcula a variacao absoluta
  int dx = abs(x1 - x0);
  int dy = abs(y1 - y0);

  // indica a direcao da reta
  int sx = (x0 < x1) ? 1 : -1; // direção de x
  int sy = (y0 < y1) ? 1 : -1; // direção de y

  // calcula o erro
  int erro = dx - dy;

  while (1) {
    putPixel(x0, y0, 250, 0, 0);

    // Quando a condicao for alcancada finaliza o loop
    if (x0 == x1 && y0 == y1) break;

    // atualiza o erro
    int erro2 = 2 * erro;

    if (erro2 > -dy) { // verifica se o erro esta acima
      erro -= dy;
      x0 += sx;
    }

    if (erro2 < dx) { // verifica se o erro esta abaixo
      erro += dx;
      y0 += sy;
    }
  }
}



int main(){

  // Limpar a imagem
  clearImage();

  // Executar o algoritmo DDA
  //drawBresenhamLinesIncomplete(0, 0, 200, 200);

  drawBresenhamLines(20, 20, 80, 20);
  drawBresenhamLines(20, 20, 20, 80);
  drawBresenhamLines(20, 80, 80, 80);
  drawBresenhamLines(80, 20, 80, 80);

  // Salvar a imagem em PPM
  saveImage();

  return 0;
}

Descrição do programa

Neste momento, estaríamos repetindo todo o processo descrito anteriormente. Para evitar redundância, descreveremos apenas o conteúdo que adicionamos ao arquivo. Sendo assim, falaremos sobre a função drawBresenhamLinesIncomplete. Esta função é descrita no texto Bresenham’s Algorithm.

void drawBresenhamLinesIncomplete( int x0, int y0, int x1, int y1 ){

  // calcula a variacao
  int dx = x1 - x0;
  int dy = y1 - y0;

  // calcula o erro
  int D = (2 * dy) - dx;

  int x = x0;
  int y = y0;

  putPixel(x, y, 255, 0, 0);

  while (x < x1){
    x = x + 1;
    if ( D < 0 ){
      D = D + (2 * dy);
    }
    else{
      y = y + 1;
      D = D + (2 * ( dy - dx ));
    }
    putPixel(x, y, 255, 0, 0);
  }

}

Na função drawBresenhamLines, incluimos todos os quadrantes como sugerido no artigo supracitado.

void drawBresenhamLines( int x0, int y0, int x1, int y1 ){
  // calcula a variacao absoluta
  int dx = abs(x1 - x0);
  int dy = abs(y1 - y0);

  // indica a direcao da reta
  int sx = (x0 < x1) ? 1 : -1; // direção de x
  int sy = (y0 < y1) ? 1 : -1; // direção de y

  // calcula o erro
  int erro = dx - dy;

  while (1) {
    putPixel(x0, y0, 250, 0, 0);

    // Quando a condicao for alcancada finaliza o loop
    if (x0 == x1 && y0 == y1) break;

    // atualiza o erro
    int erro2 = 2 * erro;

    if (erro2 > -dy) { // verifica se o erro esta acima
      erro -= dy;
      x0 += sx;
    }

    if (erro2 < dx) { // verifica se o erro esta abaixo
      erro += dx;
      y0 += sy;
    }
  }
}

Exercícios

Edite o código de renderização de modelos 3D para usar o algoritmo Bresenham.
Utilize a biblioteca time.h da linguagem C e verifique o tempo de execução do algoritmo que utiliza equações vetoriais, DDA e Bresenham.

Lecture 5

Vamos inserir uma câmera virtual e realizar uma projeção em perspectiva.

Câmera Virtual e Projeção

A câmera virtual posiciona o observador no espaço tridimensional para que a projeção em perspectiva converta esses pontos 3D em uma imagem plana 2D, simulando o efeito realista onde objetos mais distantes parecem menores. Para fazer isso, vamos reutilizar o código de [renderização] de modelos 3D.

Figure 8. Modelo tridimensional gerado a partir da renderização da cena usando câmera virtual e projeção em perspectiva

Necessitamos encontrar os vetores ortonormais $\vec{n}$, $\vec{u}$ e $\vec{v}$ que fazem parte do sistema de coordenadas da câmera virtual.

Figure 9. Cálculo dos vetores n, u e v

$\vec{n} = \frac{P_{eye} - P_{at}}{\mid P_{eye} - P_{at} \mid}$

$P_{eye}$: Posição da câmera no mundo
$P_{at}$: Posição para onde a câmera é apontada

$\vec{u} = \frac{\vec{v}_{up} \times \vec{n}}{\mid \vec{v}_{up} \times \vec{n} \mid}$

$v_{up}$: Indica a posição "para cima" da câmera

$\vec{v} = \vec{n} \times \vec{u}$

Posteriormente, todos os pontos do modelo 3D é transformado para o sistema de coordenadas da câmera e aplicamos a projeção em perspectiva:

$x' = \frac{x d}{z + d}$

$y' = \frac{y d}{z + d}$

Código

A implementação do código é realizada através dos arquivos: camera.h que contém todos os protótipos de funções que serão úteis para manipulação dos modelos 3D, câmera virtual e projeção em perspectiva, camera.c é o arquivo que contém as implementações das funções dos protótipos e render.c que realiza a execução das funções implementadas.

/**
 * \file camera.h
 *
 * \brief Header com protótipos de funções para manipulação de modelo 3D, câmera
 * e projeção em perspectiva.
 *
 * \author
 * Petrucio Ricardo Tavares de Medeiros \n
 * Universidade Federal Rural do Semi-Árido \n
 * Departamento de Engenharias e Tecnologia \n
 * petrucio at ufersa (dot) edu (dot) br
 *
 * \version 1.0
 * \date Oct 2026
 */

#ifndef CAMERA_H
#define CAMERA_H

#define WIDTH 800
#define HEIGHT 800
#define MAX_VERTICES 50000
#define MAX_FACES 50000
#define MAX_FACE_VERTS 32

typedef struct {
  float x, y, z;
} Vertex;

typedef struct {
  int verts[MAX_FACE_VERTS];
  int n;
} Face;

typedef struct {
  int x, y;
} Point2D;

typedef struct {
  Vertex Peye;
  Vertex Pat;
  Vertex Vup;
  float d;
} Camera;

void set_pixel(int x, int y, unsigned char r, unsigned char g, unsigned char b);

void clr();

void save();

void draw_line(int x0, int y0, int x1, int y1);

int load_obj(const char *filename, Vertex *vertices, int *vcount, Face *faces, int *fcount);

static Vertex sub( Vertex a, Vertex b );
static float dot( Vertex a, Vertex b );
static Vertex cross( Vertex a, Vertex b );
static Vertex normalize( Vertex v );

void resizing( Vertex p, Camera cam, Point2D *out );

void render_faces(Vertex *vertices, Face *faces, int vcount, int fcount, Camera cam);


#endif

/**
 * \file camera.c
 *
 * \brief Implementação das funções de manipulação do modelo 3D, câmera
 * e projeção em perspectiva.
 *
 * \author
 * Petrucio Ricardo Tavares de Medeiros \n
 * Universidade Federal Rural do Semi-Árido \n
 * Departamento de Engenharias e Tecnologia \n
 * petrucio at ufersa (dot) edu (dot) br
 *
 * \version 1.0
 * \date Oct 2026
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#include "camera.h"

unsigned char image[HEIGHT][WIDTH][3];

void set_pixel(int x, int y, unsigned char r, unsigned char g, unsigned char b) {
  if (x >= 0 && x < WIDTH && y >= 0 && y < HEIGHT) {
    image[y][x][0] = r;
    image[y][x][1] = g;
    image[y][x][2] = b;
  }
}

void draw_line(int x0, int y0, int x1, int y1) {
  for (float t = 0.0; t < 1.0; t = t + 0.0001)
    set_pixel((int)x0+(x1-x0)*t, (int)y0+(y1-y0)*t, 0, 0, 0);
}

void clr(){
  for(int i = 0; i < WIDTH; i++)
    for(int j = 0; j < HEIGHT; j++)
      for(int c = 0; c < 3; c++)
        image[i][j][c] = 255;
}

void save(){
  printf("P3\n %d \t %d\n 255\n", WIDTH, HEIGHT);
  for(int i = 0; i < WIDTH; i++){
    for(int j = 0; j < HEIGHT; j++){
      for(int c = 0; c < 3; c++){
        printf("%d \t", image[i][j][c]);
      }
      printf("\n");
    }
  }
}

int load_obj(const char *filename, Vertex *vertices, int *vcount, Face *faces,
             int *fcount) {
    FILE *file = fopen(filename, "r");
    if (!file) {
        perror("Erro ao abrir o arquivo");
        return 0;
    }

    char line[512];
    *vcount = 0;
    *fcount = 0;

    while (fgets(line, sizeof(line), file)) {
        if (strncmp(line, "v ", 2) == 0) {
            if (sscanf(line + 2, "%f %f %f", &vertices[*vcount].x,
                       &vertices[*vcount].y, &vertices[*vcount].z) == 3) {
                (*vcount)++;
            }
        } else if (strncmp(line, "f ", 2) == 0) {
            Face face = {.n = 0};
            char *token = strtok(line + 2, " \n");
            while (token && face.n < MAX_FACE_VERTS) {
                int index;
                if (sscanf(token, "%d", &index) == 1) {
                    face.verts[face.n++] = index;
                }
                token = strtok(NULL, " \n");
            }
            faces[(*fcount)++] = face;
        }
    }

    fclose(file);
    return 1;
}

static Vertex sub( Vertex a, Vertex b ){
  return (Vertex) {a.x - b.x, a.y - b.y, a.z - b.z};
}
static float dot( Vertex a, Vertex b ){
  return (a.x * b.x) + (a.y * b.y) + (a.z * b.z);
}
static Vertex cross( Vertex a, Vertex b ){
  return (Vertex){
    a.y * b.z - a.z * b.y,
    a.z * b.x - a.x * b.z,
    a.x * b.y - a.y * b.x
  };
}
static Vertex normalize( Vertex v ){
  float tam = sqrt( dot(v, v) );
  if ( tam > 0.0 ) {
    v.x = v.x / tam;
    v.y = v.y / tam;
    v.z = v.z / tam;
  }
  return v;
}

void resizing( Vertex p, Camera cam, Point2D *out ){

  // Calcular os vetores ortonormais u, v e n
  Vertex n = normalize( sub( cam.Peye, cam.Pat ) );
  Vertex u = normalize( cross( cam.Vup, n ) );
  Vertex v = cross( n, u );

  // Aplicar na matriz view
  Vertex p_eye = sub( p, cam.Peye );
  float x_cam = dot( u, p_eye );
  float y_cam = dot( v, p_eye );
  float z_cam = dot( n, p_eye );

  float w = z_cam + cam.d;
  if ( w < 0.1f ) return;

  float x_proj = x_cam * cam.d / w;
  float y_proj = y_cam * cam.d / w;

  out->x = (int)((x_proj + 1.0f) * WIDTH / 2.0f);
  out->y = (int)((1.0f - y_proj) * HEIGHT / 2.0f);
}


void render_faces(Vertex *vertices, Face *faces, int vcount, int fcount, Camera cam) {
    for (int i = 0; i < fcount; i++) {
        Face face = faces[i];
        for (int j = 0; j < face.n; j++) {
            Vertex v0 = vertices[face.verts[j] - 1];
            Vertex v1 = vertices[face.verts[(j + 1) % face.n] - 1];
            Point2D p0, p1;
            resizing( v0, cam, &p0);
            resizing( v1, cam, &p1);
            draw_line(p0.x, p0.y, p1.x, p1.y);
        }
    }
}

/**
 * \file render.c
 *
 * \brief Implementação do arquivo principal de renderização do modelo 3D, câmera
 * virtual e projeção em perspectiva.
 *
 * \author
 * Petrucio Ricardo Tavares de Medeiros \n
 * Universidade Federal Rural do Semi-Árido \n
 * Departamento de Engenharias e Tecnologia \n
 * petrucio at ufersa (dot) edu (dot) br
 *
 * \version 1.0
 * \date Oct 2026
 */

#include "camera.h"

int main() {
    Vertex vertices[MAX_VERTICES];
    Face faces[MAX_FACES];
    int vcount, fcount;

    clr();

    // Lê o arquivo OBJ enviado
    if (!load_obj("models/wolf.obj", vertices, &vcount, faces, &fcount)) {
        return 1;
    }

    // Constroi uma câmera
    Camera cam = {
      .Peye = {0, 0, -0.5},
      .Pat = {0, 0, 0},
      .Vup = {0, 1, 0},
      .d = 5.0
    };

    // Renderiza as faces no framebuffer
    render_faces(vertices, faces, vcount, fcount, cam);

    save();

    return 0;
}

Descrição do programa

O primeiro passo consiste em incluir duas definições de estruturas no arquivo camera.h: A primeira (1) representa um ponto 2D (par ordenado) e a segunda (2), o sistema de coordenadas da câmera virtual. Este último requer a posição do observador no espaço tridimensional ($P_{eye}$), o ponto de mira ($P_{at}$), o vetor de orientação "para cima" ($V_{up}$) e a distância até a cena ($d$).

typedef struct {
  int x, y;
} Point2D;

typedef struct {
  Vertex Peye;
  Vertex Pat;
  Vertex Vup;
  float d;
} Camera;

Neste código, declaramos (camera.h) e implementamos (camera.c) funções auxiliares para o cálculo dos vetores de câmera, como subtração de vetores (sub), produto escalar (dot), produto vetorial (cross) e normalização (normalize).

static Vertex sub( Vertex a, Vertex b );
static float dot( Vertex a, Vertex b );
static Vertex cross( Vertex a, Vertex b );
static Vertex normalize( Vertex v );

static Vertex sub( Vertex a, Vertex b ){
  return (Vertex) {a.x - b.x, a.y - b.y, a.z - b.z};
}
static float dot( Vertex a, Vertex b ){
  return (a.x * b.x) + (a.y * b.y) + (a.z * b.z);
}
static Vertex cross( Vertex a, Vertex b ){
  return (Vertex){
    a.y * b.z - a.z * b.y,
    a.z * b.x - a.x * b.z,
    a.x * b.y - a.y * b.x
  };
}
static Vertex normalize( Vertex v ){
  float tam = sqrt( dot(v, v) );
  if ( tam > 0.0 ) {
    v.x = v.x / tam;
    v.y = v.y / tam;
    v.z = v.z / tam;
  }
  return v;
}

A função de resizing é modificada para receber um ponto 3D, a estrutura da câmera virtual definida anteriormente e atualizar um ponteiro com o resultado da projeção em perspectiva.

void resizing( Vertex p, Camera cam, Point2D *out );

A implementação da função resizing pode ser encontrada no arquivo (camera.c). O processo inicia-se com o cálculo dos vetores ortonormais u, v e n da câmera virtual. Em seguida, cada ponto p da nuvem é transformado para o sistema de coordenadas da câmera e submetido à projeção em perspectiva. Por fim, realiza-se o mapeamento das coordenadas projetadas originalmente no intervalo $[-1,1$] para a resolução final da imagem $width \times height$.

void resizing( Vertex p, Camera cam, Point2D *out ){

  // Calcular os vetores ortonormais u, v e n
  Vertex n = normalize( sub( cam.Peye, cam.Pat ) );
  Vertex u = normalize( cross( cam.Vup, n ) );
  Vertex v = cross( n, u );

  // Aplicar na matriz view
  Vertex p_eye = sub( p, cam.Peye );
  float x_cam = dot( u, p_eye );
  float y_cam = dot( v, p_eye );
  float z_cam = dot( n, p_eye );

  float w = z_cam + cam.d;
  if ( w < 0.1f ) return;

  float x_proj = x_cam * cam.d / w;
  float y_proj = y_cam * cam.d / w;

  out->x = (int)((x_proj + 1.0f) * WIDTH / 2.0f);
  out->y = (int)((1.0f - y_proj) * HEIGHT / 2.0f);
}

Na função render_faces, adicionamos o argumento Camera cam como pode ser observado abaixo:

void render_faces(Vertex *vertices, Face *faces, int vcount, int fcount, Camera cam);

Na implementação da função render_faces, para cada par de vértices (v0 e v1) que forma uma aresta, a função chama resizing, a qual aplica a transformação de câmera, projeção em perspectiva e o mapeamento de viewport. O resultado são coordenadas 2D na tela (p0 e p1). Por fim, a função draw_line é chamada para traçar a linha 2D na tela, conectando os pontos projetados p0 e p1, renderizando assim o aramado do modelo 3D.

void render_faces(Vertex *vertices, Face *faces, int vcount, int fcount, Camera cam) {
    for (int i = 0; i < fcount; i++) {
        Face face = faces[i];
        for (int j = 0; j < face.n; j++) {
            Vertex v0 = vertices[face.verts[j] - 1];
            Vertex v1 = vertices[face.verts[(j + 1) % face.n] - 1];
            Point2D p0, p1;
            resizing( v0, cam, &p0);
            resizing( v1, cam, &p1);
            draw_line(p0.x, p0.y, p1.x, p1.y);
        }
    }
}

No arquivo render.c, adicionamos uma câmera e passamos como argumento da função render_faces.

// Constroi uma câmera
Camera cam = {
  .Peye = {0, 0, -0.5},
  .Pat = {0, 0, 0},
  .Vup = {0, 1, 0},
  .d = 5.0
};

// Renderiza as faces no framebuffer
render_faces(vertices, faces, vcount, fcount, cam);

Exercícios

Edite o código de câmera virtual e projeção com novas posições de câmera e distância d e verifique seu resultado.

Lecture 6

Aprendendo a construir curvas e superfícies do zero.

Curvas e superfícies

Na computação gráfica, curvas e superfícies são a base essencial para dar forma, suavidade e realismo a qualquer modelo 3D.

Figure 10. Curva de hermite

Bézier

Dados 3 pontos ($P_0$, $P_1$ e $P_2$), geramos duas retas $R_1$ e $R_2$, respectivamente, entre $P_0$ e $P_1$ e entre $P_1$ e $P_2$. Ao realizar a interpolação entre $R_1$ e $R_2$ usando para isto os pesos $t$ e $1 - t$, temos uma curva:

$R_1 : (1 - t)P_0 + t P_1$ e $R_2 : (1 - t)P_1 + t P_2$ resulta em: $C_1: (1-t) R_1 + t R_2$

$C_1(t): (1-t)^2 P_0 + 2t(1 - t)P_1 + t^2 P_2, \quad t \in [0, 1]$

Hermite

Uma curva de Hermite é definida por seus pontos extremos, denominados $P_1$ e $P_2$, e por dois vetores tangentes, $T_1$ e $T_2$, que determinam a direção e a intensidade da curva nesses pontos. O vetor $T_1$ indica como a curva parte de $P_1$, enquanto $T_2$ define como ela chega até $P_2$.

$H(t) = h_1(t)P_1 + h_2(t)P_2 + h_3(t)T_1 + h4(t)T_2, \quad t \in [0, 1]$

onde:

$h_1(t) = 2t^3 - 3t^2 + 1$

$h_2(t) = -2t^3 + 3t^2$

$h_3(t) = t^3 - 2t^2 + t$

$h_4(t) = t^3 - t^2$

Código

A implementação da curva de Hermite para demonstrar como desenhar uma curva está disponível no arquivo hermite.c.

#include <stdio.h>

#define width 500
#define height 500

typedef struct{
  float x, y;
}Point;

unsigned char img [width][height][3];

void px( int x, int y, unsigned char r, unsigned char g, unsigned char b ){
  if ((x >= 0) && (x <= width) && (y >= 0) && (y <= height)){
    img[x][y][0] = r;
    img[x][y][1] = g;
    img[x][y][2] = b;
  }
}

void clr(){
  for (int i = 0; i < width; i++)
    for (int j = 0; j < height; j++)
      px( i, j, 255, 255, 255 );
}

void save(){
  printf("P3 \n %d \t %d \n 255 \n", height, width );
  for (int i = 0; i < width; i++){
    for (int j = 0; j < height; j++){
      for (int c = 0; c < 3; c++){
        printf("%d \t", img[i][j][c]);
      }
      printf("\n");
    }
  }
}

float h1( float t ){ return 2*(t*t*t) - 3*(t*t) + 1; }
float h2( float t ){ return -2*(t*t*t) + 3*(t*t); }
float h3( float t ){ return (t*t*t) - 2*(t*t) + t; }
float h4( float t ){ return (t*t*t) - (t*t); }

Point hermite( float t, Point p0, Point p1, Point t0, Point t1 ){
  Point result;
  result.x = h1(t) * p0.x + h2(t) * p1.x + h3(t) * t0.x + h4(t) * t1.x;
  result.y = h1(t) * p0.y + h2(t) * p1.y + h3(t) * t0.y + h4(t) * t1.y;

  return result;
}

int main(){
  clr();

  Point p1 = {100, 100};
  Point p2 = {300, 300};
  Point t1 = {200, 0};
  Point t2 = {0, 200};

  for (float t = 0.0; t <= 1.0; t = t + 0.001){
    Point h = hermite( t, p1, p2, t1, t2 );
    px( (int)h.x, (int)h.y, 255, 0, 0 );
  }

  save();
}

Descrição do programa

Iniciamos nossa implementação adicionando uma estrutura para ponto 2D:

typedef struct{
  float x, y;
}Point;

Para evitar redundância, descreveremos apenas o conteúdo que adicionamos ao arquivo. Sendo assim, discutiremos sobre a função hermite e algumas funções de base h1, h2, h3 e h4. As funções de base são dadas pela própria definição de hermite com um parâmetro $t \in [0, 1]$.

float h1( float t ){ return 2*(t*t*t) - 3*(t*t) + 1; }
float h2( float t ){ return -2*(t*t*t) + 3*(t*t); }
float h3( float t ){ return (t*t*t) - 2*(t*t) + t; }
float h4( float t ){ return (t*t*t) - (t*t); }

A função hermite recebe como argumento os dois pontos que delimitam a curva, as tangentes nos pontos inicial e final e, por fim, um parâmetro flutuante t que varia de zero até 1. O retorno é um ponto dentro da curva definida por hermite.

Point hermite( float t, Point p0, Point p1, Point t0, Point t1 ){
  Point result;
  result.x = h1(t) * p0.x + h2(t) * p1.x + h3(t) * t0.x + h4(t) * t1.x;
  result.y = h1(t) * p0.y + h2(t) * p1.y + h3(t) * t0.y + h4(t) * t1.y;

  return result;
}

Na função main, precisamos definir os pontos, suas tangentes e adicionar um laço para fazer o parâmetro $t$ percorrer o intervalo $[0, 1]$ com pequenos incrementos. Para cada valor de $t$ a função hermite é chamada e o ponto é plotado.

Point p1 = {100, 100};
Point p2 = {300, 300};
Point t1 = {200, 0};
Point t2 = {0, 200};

for (float t = 0.0; t <= 1.0; t = t + 0.001){
  Point h = hermite( t, p1, p2, t1, t2 );
  px( (int)h.x, (int)h.y, 255, 0, 0 );
}