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

Continuação da segunda parte
Traçando linhas: outro método

Outro método que encontrei para traçar as linhas (e que foi sugerido pelo professor) é aplicar reflexões na linha de forma que sejam resumidas ao caso original, com 0 < m < 1. Analisemos, então, como fazer as reflexões.

É conveniente salientar que os processos de reflexão são relativos a um determinado eixo ou linha. Mas nosso sistema de coordenadas possui apenas coordenadas positivas. Como fazer, então? Adotando um referencial diferente da origem do sistema. Assim, a nossa referência será o primeiro ponto fornecido, e retas traçadas a partir dele.

Analisemos, então, como fazer a reflexão para m > 1. Veja a imagem a seguir.

Dados os pontos (x0, y0) e (x, y), deseja-se mudar este último de tal forma que a inclinação seja menor que 1, transformando-o em (x', y') através da reflexão em torno da reta m = 1, que passa pelo ponto de referência (x0, y0). Observando as distâncias relativas a e b, é fácil deduzir que:

Separando as coordenadas do ponto final, temos:

Nosso algoritmo, assim, deve primeiro refletir os pontos, calcular sua posição, e depois refletir de volta para colocar na tela.

Já para -1 < m < 0, temos:

É óbvio que

E, finalmente, para m < -1, basta aplicar as duas reflexões anteriores: uma para deslocar o ponto final para o quadrante positivo, e outra para reduzir o coeficiente angular.

Para fazer as reflexões em torno da reta m = 1, criei uma função separada, que recebe o ponto de referência e o ponto a ser refletido.

void reflectXY(pixel_t p0, pixel_t* p1) {
    unsigned short int x = p1->x;
    p1->x = p0.x + p1->y - p0.y;
    p1->y = p0.y + x - p0.x;
}

Assim, segue o algoritmo baseado na lógica apresentada.

void DrawLine(pixel_t p0, pixel_t p1) {
    int dx = p1.x - p0.x;
    int dy = p1.y - p0.y;
    
    bool isXYReflected = false, isXReflected = false, isNegXYReflected = false;
    
    if(dx < 0) {        // if x_end < x_start, switch positions
        pixel_t temp = p0;
        p0 = p1;
        p1 = temp;
        dx = -dx;
        dy = -dy;
    }
    
    if(dy > dx) {       // m > 1
        isXYReflected = true;
        reflectXY(p0, &p1);
        int t = dy;     // switch dy and dx
        dy = dx;
        dx = t;
    } else if(dy < 0 && -dy <= dx) {        // -1 < m < 0
        isXReflected = true;
        dy = -dy;
    } else if(dy < 0 && -dy > dx) {         // m < -1
        isNegXYReflected = true;
        p1.y = 2*p0.y - p1.y;       // apply both reflections above
        reflectXY(p0, &p1);
        int t = -dy;
        dy = dx;
        dx = t;
    }
    
    pixel_t cur = p0;
    PutPixel(p0);
    
    int d = 2*dy - dx;            // d_start
    while(cur.x < p1.x) {       // for each x
        if(d < 0) {                 //midpoint BELOW the line
            d += 2*dy;
            cur.x++;
        } else {                    // midpoint ABOVE the line
            d += 2*(dy - dx);
            cur.x++;
            cur.y++;
        }
        interpolateColor(p0, &cur, p1);
        
        if(isXYReflected) {         // reflect back to plot ( m > 1)
            pixel_t temp = cur;
            reflectXY(p0, &temp);
            PutPixel(temp);
        } else if(isXReflected){    // -1 < m < 0
            pixel_t temp = cur;
            temp.y = 2*p0.y - temp.y;
            PutPixel(temp);
        } else if(isNegXYReflected){    // m < -1 (apply both above)
            pixel_t temp = cur;
            reflectXY(p0, &temp);
            temp.y = 2*p0.y - temp.y;
            PutPixel(temp);
        } else 
            PutPixel(cur);
    }
    
    if(isXYReflected)       // end pixel (reflected for |m| > 1), reflect back
        reflectXY(p0, &p1);
    else if(isNegXYReflected) {
        reflectXY(p0, &p1);
        p1.y = 2*p0.y - p1.y;
    }
    PutPixel(p1);
}

O que produz o mesmo resultado visto anteriormente, de um modo bem mais fácil e que não precisa das especializações do algoritmo de Bresenham.


Considerações finais

Como desenvolvi dois algoritmos, seria interessante saber qual dos dois é o mais eficiente. Dado que o primeiro traça diretamente a reta (salvo nos casos em que os pontos forem fornecidos em ordem contrária), creio que seja mais rápido que o segundo, que faz e desfaz reflexões várias vezes ao longo do processo.

A maior dificuldade encontrada foi justamente descobrir o motivo pelo qual o algoritmo de Bresenham não funcionou diretamente para inclinações negativas. Ficou claro que é sempre interessante voltar às equações e verificar o processo, e também testar com valores reais.

Talvez uma possível melhora no algoritmo de Bresenham que eu adaptei seja generalizar as variáveis, de forma que o mesmo cálculo (ou com pequenas trocas de sinal) seja repetido várias vezes ao longo do código. A função de interpolação de cor é um exemplo disso. Mas, como havia dito no corpo da discussão, talvez isso não seja interessante, pois dificulta o entendimento do código.

Já para o algoritmo baseado em reflexões, talvez o maior número de multiplicações e divisões afete, de fato o desempenho. Seria interessante se houvesse outro meio de refletir sem se utilizar dessas operações.