Desenho de personagem de desenho animado Descrição gerada automaticamente com confiança baixa

Logotipo Descrição gerada automaticamente

Ícone Descrição gerada automaticamente

 

Computação Gráfica

Trabalho I

 

Prof. Márcio Sarroglia Pinho

Aceleração de Testes de Interseção

Objetivo

Avaliar algoritmos de aceleração do processo de detecção de intersecções entre linhas.

 

Descrição

Devem ser implementados dois algoritmos:

·     Envelopes AABB;

·     Subdivisão Regular do espaço.

 

O trabalho deve ser desenvolvido com base no código que está disponível a seguir.

 

C/C++

 

Windows – Code::Blocks

 

VSCode - Windows e Mac

 

XCode – Mac

 

Python

 

Exemplo em Python

 

Instruções sobre Instalação em Python

Java

 

Exemplo em Java

 

Este código gera um conjunto aleatório de segmentos de reta e exibe-os na tela.

Quando existe uma colisão entre dois segmentos, estes são exibidas na cor vermelha. Do contrário, estes são exibidos em verde.

A figura a seguir mostra um exemplo de execução, no qual foram gerados 100 segmentos de reta.

Pressionando ESPAÇO, o programa gera um novo conjunto de segmentos de reta e atualiza a imagem exibida. Além disto, o programa informa, no console, quantas intersecções ocorreram entre os segmentos gerados.

 

Tela de computador com texto preto sobre fundo branco Descrição gerada automaticamente

Figura - Exemplo de Execução do Programa

 

Deve ser produzido um relatório que demonstre como o algoritmo se comporta na medida em que:

·     aumenta a quantidade de segmentos de reta do cenário;

·     aumenta a quantidade de subdivisões do espaço;

·     aumenta o tamanho dos segmentos de reta que compõem o cenário.

 

O comportamento dos algoritmos deve ser medido com base no número de chamadas da função apresentada a seguir

 

// **********************************************************************

//

// **********************************************************************

bool HaInterseccao(Ponto k, Ponto l, Ponto m, Ponto n)

{

    int ret;

    double s,t;

    ret = intersec2d( k,  l,  m,  n, s, t);

    if (!ret) return false;

    if (s>=0.0 && s <=1.0 && t>=0.0 && t<=1.0)

        return true;

    else return false;

 

}

 

O tamanho dos segmentos de reta é controlado na função init, apresentada a seguir, que executa as chamadas do método geraLinha. O primeiro parâmetro deste método define o valor máximo das coordenadas (X,Y) dos extremos do segmento e o segundo parâmetro define o tamanho máximo do segmento.

 

void init(void)

{

    // Define a cor do fundo da tela (BRANCO)

    glClearColor(1.0f, 1.0f, 1.0f, 1.0f);

   

    srand(unsigned(time(NULL)));

   

    for(int i=0; i< N_LINHAS; i++)

        Linhas[i].geraLinha(MAX_X, 10);

} 

 

Requisitos

 

Deve ser possível fazer entre 2 e 50 subdivisões, tanto na horizontal quanto na vertical, sem a necessidade de recompilar o código.

As estruturas de envelopes e de subdivisão devem ser geradas apenas uma vez, logo após a geração dos segmentos de reta.

 

No caso do algoritmo de subdivisão do espaço:

·     não devem ser feitas busca para localizar que célula se encontra um segmento;

·     não devem ser feitas cópias das retas que compõem o cenário. A estrutura deve armazenar apenas o número do segmento, no vetor de todos os segmentos.

 

Entrega


FIM.