[ICG] Trabalho 1: Algoritmos elementares de rasterização (parte 1)

O primeiro trabalho da disciplina de Introdução à Computação Gráfica é desenvolver algoritmos elementares de rasterização. Da Wikipédia,

Rasterização é a tarefa de tomar uma imagem descrita em um imagem vetorial e convertê-la em uma imagem raster (pixels ou pontos) para a saída em vídeo ou impressora.

Os algoritmos devem ser desenvolvidos com base em um framework desenvolvido pelo professor, o qual fornece apenas o ponteiro do primeiro byte do frame buffer, ou seja, o primeiro byte do primeiro pixel. O framework é baseado na biblioteca OpenGL, e simula uma memória de vídeo, já que os sistemas operacionais não permitem o acesso direto ao buffer da placa de vídeo física.

"Pintando" os pixels

O primeiro algoritmo a ser desenvolvido, então, deve desempenhar a função de "pintar" os pixels na tela, isto é, converter a localização de um determinado ponto (descrito por coordenadas cartesianas discretas) em um espaço de memória, e escrever suas informações de cor neste espaço.

O sistema de cores utilizado pelos monitores comuns é o RGB, sigla para Red-Green-Blue, os três componentes de cor. Cada um dos componentes (canal) é representado por um número inteiro de 8 bits, o que resulta em 256 níveis possíveis para cada componente. Sendo três componentes, 256*256*256 = 16,78 milhões de cores (aproximadamente) podem ser representadas pelo sistema RGB. Além dos três canais de cor, um canal adicional é utilizado, chamado de Alpha, que descreve a transparência da cor (também em 256 níveis). Quanto aos canais de cores, 0 é a ausência de cor, e 255 é a quantidade máxima daquela cor. Já para a transparência, 0 é a total transparência, e 255 é a opacidade total.

O color buffer é, então, responsável por armazenar as informações de cor de todos os pixels da tela. Cada pixel ocupa, então, 4 bytes neste buffer, sendo 1 byte para cada canal de cor. Sabendo que o color buffer é uma área de memória contígua, ou seja, as informações dos pixels estão armazenadas sequencialmente, e tendo em mãos o endereço de memória do primeiro byte deste buffer, basta converter a posição do pixel na tela em um endereço de memória.

Considerando que a tela possui w pixels de largura e h pixels de altura, e que a origem do sistema de coordenadas esteja localizada no canto superior esquerdo da tela, como na figura abaixo

Os pixels são, assim, endereçados como pontos de coordenadas (x, y), onde x varia entre 0 e w-1, e y varia entre 0 e h-1. Já no color buffer, como o armazenamento é sequencial, a primeira posição corresponde ao primeiro componente do primeiro pixel, como na figura abaixo.

Para a 1ª linha, o endereço do primeiro componente do x-ésimo pixel é 4x(+0), uma vez que cada pixel ocupa quatro espaços na memória. E quanto ao 1º pixel da segunda linha?

Dando continuidade ao raciocínio, o primeiro byte do pixel (0,2) é 4*w*2+0. Percebe-se, então, que a fórmula geral para o endereço de memória do 1º byte de um pixel qualquer (x,y) é

4*w*y + 4*x = 4*(w*y + x)

considerando que o endereço do primeiro byte do buffer (pixel 0,0) seja 0. Caso contrário, basta adicionar o valor deste endereço. Antes de apresentar o algoritmo de conversão, é conveniente fazer a modelagem dos pixels e das cores, isto é, agrupá-los em estruturas de forma que sejam identificáveis ao longo do programa como objetos, para que não sejam apenas variáveis e números aleatórios ao longo do código. Assim, foram criadas as seguintes estruturas:

enum color_t {
 RED = 0, GREEN, BLUE, ALPHA
};

struct pixel_t {
 unsigned char color[4];
 unsigned short int x, y;

};

Cada pixel é uma estrutura composta por duas coordenadas x e y, e um array com os valores de cada canal RGBA. Para poupar espaço, cada componente de cor é armazenado como um char unsigned, que possui exatamente 8 bits. O fato de ambas as variáveis serem unsigned já evita que sejam armazenados valores negativos. Aliás, não evita, mas causará um underflow. O enumerador servirá tanto para determinar o offset no buffer de memória quanto para indexar os componentes do pixel.

Assim, eis a função elementar de qualquer algoritmo de rasterização:

void PutPixel(pixel_t pixel) {
 int offset = 4*(pixel.x + IMAGE_WIDTH*pixel.y);
 
 if( (pixel.x < IMAGE_WIDTH) && (pixel.y < IMAGE_HEIGHT) ) {
  FBptr[offset + RED  ] = pixel.color[RED];
  FBptr[offset + GREEN] = pixel.color[GREEN];
  FBptr[offset + BLUE ] = pixel.color[BLUE];
  FBptr[offset + ALPHA] = pixel.color[ALPHA];
    }
}

Recebe-se o pixel já formatado como o struct pixel_t, calcula-se o offset dele no frame buffer, e então verifica-se se as coordenadas não excedem o tamanho da tela.

Para facilitar a composição do pixel, isto é, a criação do "objeto" pixel, criei uma função que recebe todos os parâmetros do pixel e um ponteiro para a estrutura destino.

void composePixel(unsigned short int x, unsigned short int y,
                  unsigned char r, unsigned char g, unsigned char b,
                  unsigned char a, pixel_t* pixel) {
 pixel->color[RED  ] = r;
 pixel->color[GREEN] = g;
 pixel->color[BLUE ] = b;
 pixel->color[ALPHA] = a;
 pixel->x = x;
 pixel->y = y;
}

Finalmente, eis o resultado do algoritmo. Executando o código

    pixel_t tempPixel;
    //           x   y    r    g    b    a
    composePixel(20, 30, 255, 255, 255, 255, &tempPixel);
    PutPixel(tempPixel);

Obtém-se o resultado da figura abaixo.

Destaque do pixel no ponto (20,30), de cor (255,255,255)

Observa-se que a tela possui um tamanho de 512x512 pixels. Nos próximos screenshots, só serão exibidas apenas as partes relevantes.

Para testar os componentes de cor, elaborei o código a seguir, que traça faixas de 20 pixels de altura por 256 de largura, mostrando cada um dos níveis de cor.

    pixel_t tempPixel;

    for(int i = 0; i < 60; i++) {       // white line
        composePixel(19, 30+i, 255, 255, 255, 255, &tempPixel);
        PutPixel(tempPixel);
    }

    for(int i = 0; i < 256; i++) {
        int j;
        for(j = 0; j < 20; j++) {        // all levels of RED
            composePixel(20+i, 30+j, i, 0, 0, 255, &tempPixel);
            PutPixel(tempPixel);
        }
        
        for( ; j < 40; j++) {        // all levels of GREEN
            composePixel(20+i, 30+j, 0, i, 0, 255, &tempPixel);
            PutPixel(tempPixel);
        }

        for( ; j < 60; j++) {        // all levels of BLUE
            composePixel(20+i, 30+j, 0, 0, i, 255, &tempPixel);
            PutPixel(tempPixel);
        }
    }

Compilando e executando, obtém-se o resultado abaixo. A linha branca indica o início das faixas de cor.

Resultado do bloco de código anterior, faixas de 20 pixels de altura e 256 pixels de comprimento

Um detalhe curioso é que a parte final (à direita) das barras parece estar desalinhada, não é? Parece que a barra vermelha termina mais cedo que a verde, que por sua vez termina antes da azul. E, realmente, se você olhar mais de perto, essa hipótese se confirma, como pode ser visto na foto a seguir.

Foto macro do monitor. Observe o final desalinhado das barras coloridas.

Se você olhar mais de perto ainda, poderá ver que as cores estão, de fato, desalinhadas. Entretanto, os pixels estão alinhados. O que se vê desalinhado é, na verdade, cada componente do pixel: o componente R está mais à esquerda, o G no meio, e o B está mais à direita. Mas todos fazem parte do mesmo pixel, e a fronteira das barras está na mesma coluna.

Fim das barras ampliado. Pode-se ver a unidade elementar da imagem: o pixel.

Algo que ainda não consegui descobrir como funciona é o valor de alpha. Por mais que eu varie o valor de alpha para a mesma cor de pixel, o tom não muda. Não creio que seja algum problema do meu algoritmo, mas vou procurar a solução. 

Continua na segunda parte