Aplicações: Recorte:

O recorte é a operação que retira da visualização os trechos¹ da imagem que não devem aparecer em tela, como os que estão por trás de outro objeto, ou fora da moldura (viewport) da tela.

O recorte é uma das operações mais importantes na visualização e modelos. Em geral, as APIs gráficas cuidam dessa parte para os desenvolvedores. Mas vale ter em mente que o recorte é um procedimento de Base para a construção de sistemas gráficos, e que durante processos como a rasterização ele é importante para permitir a diminuição do tamanho das imagens (é completamente desnecessário no cotidiano o uso de informações de profundidade em images 2D, se torna apenas um peso a mais para a imagem e o processamento) e remover partes da imagem fora da região de trabalho. Esta parte será abordada aqui, por que este é um artigo voltado para o fundamento matemático do uso de pontos, não (tanto) para as questões de implementação, assim sendo, o recorte é um processo de base para a construção de imagens. Alguns modelos de recorte podem ser mesmo utilizados para avaliar a iluminação² local, ou global.

Diversas transformações geométricas podem ser aplicadas ao corpo do objeto ou ao sistema de coordenadas, implicando assim numa avaliação contínua do recorte de cada um de seus membros. No uso de pontos, os modelos de recorte se resumem a Geometria Discreta (ou à Geometria Computacional³). Para o recorte de 3D a 2D, vamos partir de uma suposição básica para desenvolver o algoritmo:

“A região a ser recortada é interseção das sombras dos polígonos formados pelos pontos no plano paralelo à moldura que tem a maior profundidade em relação ao observador.”

A demonstração desse fato é deixada a critério do leitor, vamos considerar que isto é uma forma de “postulado”. Tendo o nosso postulado em mente, temos que determinar as regiões de interseção dos polígonos, não serão discutidos detalhes detalhes, mas uma abordagem sobre o assunto pode ser lida em [1]⁴. Além disso, temos que determinar quando essas regiões se interceptam, pois neste momento, as superfícies podem trocar de visibilidade.

Tratando um objeto como um conjunto de listas de pontos (lembrando que esta lista é indiferente quanto a orientação, mas não ao sentido no que diz respeito a implementação) podemos simplesmente destacar interseção de dois objetos projetados varrendo sua interseção por regiões de sombra projetada nos eixos. Observemos que se os pontos estão com sua sombra projetada num plano paralelo à moldura a região de interseção é a região comum dessa sombra, mas que no caso de objeto se intersetarem na direção perpendicular a moldura, temos que verificar uma troca de visibilidade. O cálculo dessa interseção é demasiadamente complexo.

Antes e avaliar todas as combinações possíveis, vamos determinar a sombra de um polígono pela sua região de influência (ou caixa envolvente)⁵. Uma form de fazer isso, é determinar uma distância dos pontos ao baricentro, e a partir daí obter os valores das projeções dos pontos mais distantes segundo os eixos coordenados. Ou seja: os pontos de maior valor de x, de y, e de z com relação ao baricentro, e obviamente, os com menor valor. Porém, isto nos daria as coordenadas num sistema local da caixa com origem no baricentro, estamos interessados um sistema global, que seja comum a todos os objetos. Assim sendo, a idéia máxima é avaliar apenas uma diagonal, não buscamos uma região muito aperfeiçoada, apenas uma caixa⁶: a caixa que tem diagonal com os extremos coincidindo com esses pontos será a região máxima de influência do objeto, fora dali, nada terá ver com ele (no que diz respeito a visibilidade pelo menos). As funções max e min determinam os pseudo pontos⁷ de influência de um objeto a partir das coordenadas de seus pontos.

struct ponto max(struct ponto lista[], int tam){
        struct ponto pt;///Ponto de máximo

        int i;

        ///Inicializa o vetor de retorno com um pono da lista
        X(pt) = X(lista[0]);
        Y(pt) = Y(lista[0]);
        Z(pt) = Z(lista[0]);

        ///Varre a lista em busca dos nvos candidatos a máximo
        for (i = 1; i<tam; i++){
                if(X(pt) < X(lista[i]))
                        X(pt) = X(lista[i]);
                if(Y(pt) < Y(lista[i]))
                        Y(pt) = Y(lista[i]);
                if(Z(pt) < Z(lista[i]))
                        Z(pt) = Z(lista[i]);
        }

        return pt;
}

struct ponto min(struct ponto lista[], int tam){
        struct ponto pt;///Ponto de mínimo

        int i;

        ///Inicializa o vetor de retorno com um pono da lista
        X(pt) = X(lista[0]);
        Y(pt) = Y(lista[0]);
        Z(pt) = Z(lista[0]);

        ///Varre a lista em busca dos nvos candidatos a máximo
        for (i = 1; i<tam; i++){
                if(X(pt) > X(lista[i]))
                        X(pt) = X(lista[i]);
                if(Y(pt) > Y(lista[i]))
                        Y(pt) = Y(lista[i]);
                if(Z(pt) > Z(lista[i]))
                        Z(pt) = Z(lista[i]);
        }

        return pt;
}

A função regiao a seguir cria uma matriz 4x4 onde os valores dos vetores linha são os máximos e mínimos⁸ dos objetos inseridos.

mat regiao(struct ponto max1, struct ponto max2, struct ponto min1, struct ponto min2){

        mat res;

        res.l1 = max1.posO;
        res.l2 = min1.posO;
        res.l3 = max2.posO;
        res.l4 = min2.posO;

        return res;
}

O vetor da primeira linha (l1) é o primeiro ponto de máximo inserido, e partindo disso é fácil entender os demais. Agora precisamos determinar a partir dessa matriz (que não tem uma concepção matricial no universo matemático, mas sim de parte de um subespaço vetorial, ainda que poderia ser utilizada, pois a idéia de dependência linear entre as linhas da matriz nos possibilitaria verificar, dentre mais, colinearidade entre os pontos. Mas nada disso será utilizado aqui.

Precisamos agora determinar a partir de operações booleanas formas de se obter a região comum ambos (interseção), a região de diferença ou a região formada por ambos unidos.

A interseção é formada pelas menores coordenadas, pensemos nela como a menor caixa envolvente que contém pontos comuns de A e B.

mat micRegIntersecao(mat regiao){
        struct ponto ptmax, ptmin;

        ///A interseção é formada pelas menores coordenadas dos máximos e maiores dos mínimos

        ///Máximos
        X(ptmax) = (regiao.l1.x <= regiao.l3.x ? regiao.l1.x : regiao.l3.x);
        Y(ptmax) = (regiao.l1.y <= regiao.l3.y ? regiao.l1.y : regiao.l3.y);
        Z(ptmax) = (regiao.l1.z <= regiao.l3.z ? regiao.l1.z : regiao.l3.z);

        ///Mínimos
        X(ptmin) = (regiao.l2.x >= regiao.l4.x ? regiao.l2.x : regiao.l2.x);
        Y(ptmin) = (regiao.l2.y >= regiao.l4.y ? regiao.l2.y : regiao.l2.y);
        Z(ptmin) = (regiao.l2.z >= regiao.l4.z ? regiao.l2.z : regiao.l2.z);

        mat A;

        ///Passa os vetores para a matriz mantendo a relação de máximos em
        ///linhas ímpares e mínimos em pares, mas repetindo os máximos e minimos

        A.l1 = ptmax.posO;
        A.l3 = ptmax.posO;
        A.l2 = ptmin.posO;
        A.l4 = ptmin.posO;

        return A;
}

A união é formada pelo menor dos mínimos e o maior dos máximos

mat micRegUniao(mat regiao){
        struct ponto ptmax, ptmin;

        ///A união é formada pelas maiores coordenadas dos máximos e menores dos mínimos

        ///Máximos
        X(ptmax) = (regiao.l1.x >= regiao.l3.x ? regiao.l1.x : regiao.l3.x);
        Y(ptmax) = (regiao.l1.y >= regiao.l3.y ? regiao.l1.y : regiao.l3.y);
        Z(ptmax) = (regiao.l1.z >= regiao.l3.z ? regiao.l1.z : regiao.l3.z);

        ///Mínimos
        X(ptmin) = (regiao.l2.x <= regiao.l4.x ? regiao.l2.x : regiao.l2.x);
        Y(ptmin) = (regiao.l2.y <= regiao.l4.y ? regiao.l2.y : regiao.l2.y);
        Z(ptmin) = (regiao.l2.z <= regiao.l4.z ? regiao.l2.z : regiao.l2.z);

        mat A;

        ///Passa os vetores para a matriz mantendo a relação de máximos em
        ///linhas ímpares e mínimos em pares, mas repetindo os máximos e minimos

        A.l1 = ptmax.posO;
        A.l3 = ptmax.posO;
        A.l2 = ptmin.posO;
        A.l4 = ptmin.posO;
        
        return A;
}

Agora, a carga de trabalho para determinar o cruzamento diminui enormemente trabalhando apenas nessas regiões. As funções abaixo determinam o cruzamento de arestas de pontos, seria mais natural pensar em primeiro determinar se os pontos se cruzam, depois determinar seu ponto de cruzamento, mas por facilidade de implementação, vamos fazer ambos de uma só vez. A idéia base para determinar a interseção dos pontos é descobrir se o valor do parâmetro de interseção está entre 0 e 1. Sabemos da Geometria Analítica que o segmento de reta r que une dois pontos A e B pode ser parametrizada como:

A interseção de dois segmentos é um caso particular de sistema linear, onde tendo dimensão 3x3, pode ser facilmente resolvido pelo uso de matrizes. Porém, é ainda mas fácil determinarmos se um par de retas r e s se intersetam buscando o valor do parâmetro t para o qual r=s. Para o r dado, e s:

busquemos t satisfazendo r=s, com um pouco de algebra chegamos a conclusão:

Partindo daí, temos que:

• Testar se A-C+D-B⁹

• Testar se A-C não é 0, pois se A-C+D-B for zero também, temos retas coincidentes, se apenas A-C+D-B for zeros, temos retas paralelas.

• Testar se pois caso contrário, os segmentos não se intersetam.

Observe que o que temos é um conjunto de pontos, o que temos que fazer é obter uma forma de manter o sentido dessas operações por meio de operandos escalares. Uma forma de fazer isso é parametrizar a equação:

O significado geométrico da parametrização é a componente dos vetores formadores dos pontos¹⁰ em cada um dos eixos coordenados, sendo assim, podemos trabalhar individualmente com cada componente:

Esta parametrização facilita e tanto nosso trabalho, pois podemos avaliar separadamente a inteseção em cada um dos eixos, que para nós interessa avaluar a interseção nos eixos do plano de projeção (geralmente xy) e no exo de altura (eixo z).

O algoritmo que realiza este trabalho é:

vet micSegIntersesao(struct ponto A, struct ponto B, struct ponto C, struct ponto D){
        float nume=0.0, denom =1.0;
        vet v;

        ///para x
        nume = X(A)-X(C);
        denom = nume + X(D)-X(B);
        
        if (denom == 0){//testa denominador sendo 0
                if(nume != 0)//Se o numerador tabém for zero
                        v.x = inf;//Retorna o valor infinito se a razão for indeterminada ([R*]/0)
                else
                        v.x = nan;//Retorna o valor "não é número" se a razão for impossível (0/0)
        }
        else
                v.x = nume/denom;//Retorna a razão se for [R]/[R*]

        ///para y
        nume = Y(A)-Y(C);
        denom = nume + Y(D)-Y(B);
        
        if (denom == 0){//testa denominador sendo 0
                if(nume != 0)//Se o numerador tabém for zero
                        v.y = inf;//Retorna o valor infinito se a razão for indeterminada ([R*]/0)
                else
                        v.y = nan;//Retorna o valor "não é número" se a razão for impossível (0/0)
        }
        else
                v.y = nume/denom;//Retorna a razão se for [R]/[R*]

        ///para z
        nume = Z(A)-Z(C);
        denom = nume + Z(D)-Z(B);
        
        if (denom == 0){//testa denominador sendo 0
                if(nume != 0)//Se o numerador tabém for zero
                        v.z = inf;//Retorna o valor infinito se a razão for indeterminada ([R*]/0)
                else
                        v.z = nan;//Retorna o valor "não é número" se a razão for impossível (0/0)
        }
        else
                v.z = nume/denom;//Retorna a razão se for [R]/[R*]

        return v;
}

Particulamente, estamos interessados em avaliar a inteseção com cada um dos eixos, de forma a determinar as combinações de intersçãoque satisfazem nossa condição de interferência. Tendo os pontos de inteseção e cada uma das direções, podemos restringir o domínio de qualquer do tipos de interpolação estudados no artigo ao intervalo em que o segmento intercepta a curva, n ocaso de curvas de Bézir ou splines de Bézier, uma boa aproximação é parar o parâmetro no maior dos que deve ser recortados.