RELATÓRIO FINAL DE ATIVIDADES Projeto de Iniciação ...

[Pages:22]RELAT?RIO FINAL DE ATIVIDADES

Projeto de Inicia??o Cient?fica: Visualizador Din?mico para Estruturas de Representa??o de Subdivis?es Planares

Orientador: Prof. Dr. Pedro J. de Rezende Orientado: Fl?vio Ivan da Silva

Resumo Este relat?rio cont?m uma descri??o das atividades realizadas ao longo do ?ltimo ano de trabalho neste projeto de Inicia??o Cient?fica enfocando, para tanto, o cumprimento das atividades previstas no cronograma de execu??o originalmente estabelecido. Al?m das atividades realizadas, este relat?rio cont?m descri??es de aspectos te?ricos e pr?ticos referentes ? implementa??o do visualizador da estrutura Half-Edge, que ? o produto de software gerado ao fim deste projeto.

?ndice: 1. Introdu??o...............................................................................2 2. Cronograma de execu??o.......................................................... 3 3. Descri??o das atividades realizadas.............................................4 4. Manipula??o e descri??o da topologia dos s?lidos representados pela

estrutura de dados Half-edge......................................................6 5. Especifica??o do tipo abstrato de dados Half-edge........................11 6. Descri??o do Visualizador de Subdivis?es Planares ........................16 7. Testes e exemplo de uso.....................................................................1 9 8. Atividades extras.....................................................................22 9. Conclus?o..............................................................................22

1

1. Introdu??o

Em linhas gerais, o projeto que originou esta Inicia??o Cient?fica estabelecia para a mesma os seguintes prop?sitos: estudo e compreens?o da estrutura de dados Half-Edge manipulada pelos operadores de Euler e elabora??o de uma ferramenta de software que permitisse a um usu?rio criar desenhos planares e visualizar, simultaneamente, a constru??o da estrutura Half-Edge correspondente ao desenho criado.

Este relat?rio descreve, portanto, o que foi realizado neste projeto ao longo do ?ltimo ano, isto ?, de agosto de 2004 a julho de 2005. A seguir s?o apresentadas resumidamente as principais atividades deste per?odo.

Durante o segundo semestre do ano de 2004, o orientado cursou um total de 7 disciplinas da gradua??o, totalizando 26 cr?ditos, e obteve uma m?dia ponderada de 7.8. Simultaneamente, realizou estudos focados nos principais t?picos relacionados ao presente projeto. Nas f?rias de ver?o, participou do Programa de Ver?o do IMPA (Instituo Nacional de Matem?tica Pura e Aplicada) no Rio de Janeiro, onde cursou a disciplina "Conceitos B?sicos de Computa??o Gr?fica", obtendo men??o final `A'. Paralelamente, nesse per?odo, foi iniciado o desenvolvimento do Visualizador de Subdivis?es Planares, que era o produto de software a ser constru?do at? o final desta inicia??o cient?fica.

No primeiro semestre de 2005, o orientado cursou outras 6 disciplinas da gradua??o, somando novamente 26 cr?ditos, e ? esperada a obten??o de uma m?dia ponderada de aproximadamente 9.0. ? importante destacar que uma das disciplinas cursadas nesse per?odo ? da p?s-gradua??o do Instituto de Computa??o (oferecida em conjunto com a gradua??o), intitulada "Introdu??o a Vis?o Computacional", cuja men??o final esperada ? tamb?m `A'. Ao mesmo tempo, neste ?ltimo semestre, foi conclu?da a implementa??o do software, conforme planejado.

Ressaltamos tamb?m, neste ponto, que fizemos um pedido de renova??o de bolsa, cujo projeto trata da elabora??o e desenvolvimento de um novo visualizador, aproveitando o conhecimento acumulado neste primeiro ano, e utilizando uma nova modelagem geom?trica para visualizar uma outra estrutura de dados: a Quad-Edge.

Conte?do deste relat?rio: a pr?xima se??o deste relat?rio recupera o cronograma de execu??o estabelecido no projeto original; a seguir, ? descrito em detalhes o cumprimento de cada uma das tarefas contidas neste cronograma. As se??es que se seguem abordam aspectos te?ricos importantes para o correto entendimento do projeto, e tamb?m descrevem o software obtido ao t?rmino desta Inicia??o Cient?fica.

2

2. Cronograma de execu??o

2004

2005

Jul Ago Set Out Nov Dez Jan Fev Mar Abr Mai Jun Jul

Conhecimento de Unix e Linux; Dom?nio da linguagem C++; Familiaridade com OpenGL; Dom?nio do toolkit Qt;

No??es de modelagem geom?trica; Dom?nio do uso dos operadores de Euler; Conhecimento de estruturas de representa??o de modelagem geom?trica; Projeto do m?dulo de interface interativa; Implementa??o do m?dulo da estrutura Half-Edge (e testes); Implementa??o do m?dulo de acionamento de operadores de Euler (e testes); Visualizador da subdivis?o planar gerada por operadores de Euler (e testes); Visualizador da estrutura Half-Edge (e testes); Integra??o de todos os m?dulos; Testes da vers?o final integrada; Relat?rio Final;

Prepara??o de apresenta??o para o Congresso de Inicia??o Cient?fica;

3

3. Descri??o das atividades realizadas

Inicialmente, foram realizadas atividades de leitura da bibliografia contida no projeto original para aquisi??o de conhecimentos te?ricos sobre Linux, Unix e linguagem de programa??o C++. Por outro lado, foram desenvolvidos programas de complexidade simples e intermedi?ria usando C++ em ambiente Linux, a fim de proporcionar familiaridade com essa linguagem e esse sistema operacional.

Em seguida, foi feito o tutorial do toolkit Qt. ? preciso ressaltar que a realiza??o desse tutorial apresentou-se mais dif?cil e demorada do que o esperado, mas teve o benef?cio de gerar o dom?nio do ambiente Qt, fato esse fundamental para o bom desenvolvimento de v?rias das atividades restantes para a conclus?o do projeto.

J? os estudos da teoria de modelagem geom?trica, operadores de Euler e estruturas de representa??o, atividades seguintes do cronograma, se deram basicamente pelo estudo do livro "Introduction to Solid Modeling", de Marti M?ntyl?. No entanto, foram necess?rios estudos extras em topologia a fim de melhorar a compreens?o sobre o papel da estrutura de representa??o HalfEdge e dos operadores de Euler, sendo que o resultado destes estudos est? descrito na se??o Manipula??o e descri??o da topologia de s?lidos representados pela estrutura de dados Half-edge.

Por outro lado, era de fundamental import?ncia compreender claramente a estrutura de dados Half-edge antes de implement?-la e, para isso, foi gerada uma especifica??o que pode ser vista na se??o Especifica??o do tipo abstrato de dados Half-edge.

Uma vez compreendido o modo como funcionam tanto os operadores de Euler como a estrutura de representa??o Half-Edge, restava utilizar o Qt a fim de implementar os componentes do visualizador; a saber: a interface gr?fica interativa, contendo uma tela dentro da qual o usu?rio poderia criar subdivis?es planares e outra tela dentro da qual poderia, simultaneamente, visualizar a estrutura Half-edge correspondente ?s subdivis?es criadas; a estrutura de dados Half-Edge que armazena a representa??o topol?gica das subdivis?es planares criadas pelo usu?rio; e os operadores de Euler que pudessem ser acionados da interface gr?fica e que levassem uma subdivis?o planar criada pelo usu?rio ? sua representa??o dentro da Half-edge.

Assim, as atividades seguintes do cronograma j? dizem respeito ao desenvolvimento do visualizador propriamente dito e come?am com o projeto do m?dulo de interface interativa. Ap?s a implementa??o da interface, e seguindo o cronograma, ocorreram as atividades de implementa??o dos m?dulos da estrutura Half-Edge e dos operadores de Euler, conclu?ndo assim o primeiro semestre de trabalho neste projeto de inicia??o cient?fica.

No in?cio da segundo semestre de projeto, foi desenvolvido o m?dulo que permitia visualizar uma estrutura de dados Half-Edge, sendo que o principal desafio neste ponto foi readaptar o projeto de Interface proposto

4

anteriormente, e utilizar as funcionalidades providas pelo Qt a fim de desenhar a estrutura de dados de modo hier?rquico, conforme hav?amos planejado, a fim de permitir um maior realismo na sua representa??o visual. Neste ponto ? importante destacar que o curso de computa??o gr?fica, realizado no IMPA e descrito na se??o Atividades extras, contribuiu bastante para a implementa??o dos elementos gr?ficos da tela de interface. Por outro lado, ap?s concluir o m?dulo que permitia o desenho da Half-Edge, foi necess?rio implementar o m?dulo de visualiza??o das subdivis?es planares criadas pelo usu?rio. A se??o Descri??o do Visualizador de Subdivis?es Planares aborda aspectos de interface e de integra??o de todos os m?dulos. Ap?s a integra??o de todos os m?dulos, foi poss?vel testar o primeiro prot?tipo do software produzido, o que permitiu excluir diversos erros n?o identificados at? esse ponto. A se??o Testes e exemplo de uso esclarece melhor como o visualizador pode ser usado. Embora o programa j? contasse, a essa altura, com as funcionalidades inicialmente especificadas, resolvemos tirar proveito da inversibilidade de cada um dos operadores de Euler j? implementados e inserir duas novas funcionalidades que est?o relacionadas e que contribuiriam para significativa melhoria do sistema. Trata-se dos bot?es Undo e Redo, e da grava??o de arquivos contendo subdivis?es planares criadas pelo usu?rio, que poderiam, portanto, ser utilizadas novamente mesmo ap?s o fechamento do programa. Nos ?ltimos dois meses de trabalho produzimos um novo projeto de inicia??o cient?fica para o pr?ximo ano, preparamos o relat?rio final e a apresenta??o para o XII Congresso de Inicia??o Cient?fica da Unicamp.

5

4. Manipula??o e descri??o da topologia de s?lidos representados pela estrutura de dados Half-edge

Esta se??o descreve como se d? a representa??o da topologia de s?lidos atrav?s da estrutura de dados Half-edge, bem como define os operadores necess?rios ? cria??o e manipula??o dessa representa??o topol?gica, que s?o os operadores de Euler.

4.1. Representa??o de S?lidos

A representa??o de um s?lido para fins computacionais requer um modelo matem?tico que transforme o s?lido em uma representa??o armazen?vel em alguma estrutura de dados. Isso ? ilustrado pela figura a seguir:

S?lido

Modelo Matem?tico

Representa??o

Estrutura de Dados

A id?ia central neste projeto ? criar uma aplica??o que permita armazenar e visualizar informa??es referentes ? topologia de subdivis?es planares, tamb?m chamadas de s?lidos planares. Assim, para qualquer s?lido planar criado pelo usu?rio, deve ser usado um modelo matem?tico que permita obter uma representa??o, de tamanho finito, de sua topologia para armazen?-la numa estrutura de dados. Para alcan?ar esse objetivo, ser? utilizado como modelo matem?tico o modelo de fronteira, cuja representa??o resultante ser? armazenada na estrutura de dados Half-edge.

Al?m disso, ? importante observar que a representa??o de um s?lido obtida do modelo de fronteira pode conter informa??es geom?tricas associadas a fim de permitir uma visualiza??o da topologia do s?lido representado.

4.2.Modelo de fronteira

O modelo de fronteira cria uma representa??o para a topologia de um s?lido atrav?s da descri??o da sua superf?cie de contorno como sendo um conjunto de faces poligonais. Cada face poligonal tamb?m ? descrita por suas curvas de contorno as quais, por sua vez, s?o descritas por uma cadeia de arestas cujos extremos s?o dois v?rtices. Dessa forma, o modelo de fronteira faz uma descri??o de todas as faces, arestas e v?rtices de um s?lido, e tamb?m uma descri??o de como estes elementos est?o relacionados entre si no que diz respeito a adjac?ncias.

6

Duas considera??es se fazem necess?rias a respeito do modelo de fronteira: a primeira ? que as faces em que o modelo divide a superf?cie externa de um s?lido n?o s?o necessariamente pol?gonos de arestas retas, podendo ocorrer que as arestas de contorno destes pol?gonos sejam curvas; a segunda ? que o modelo de fronteira pode armazenar informa??es sobre curvas que descrevem arestas e coordenadas de v?rtices de modo a permitir uma visualiza??o (geom?trica) da topologia do s?lido representado.

4.3.Manipula??o da Estrutura de Dados

Na pr?tica, o armazenamento da topologia de um s?lido dentro da estrutura de dados ? feito de maneira direta conforme mostrado na figura abaixo:

S?lido

operadores topol?gicos

Estrutura de Dados

Portanto, ? necess?rio um conjunto de operadores topol?gicos que criem uma representa??o para a topologia de um s?lido recebido como entrada e a armazenem na estrutura de dados Half-edge. Al?m disso, esses operadores devem ser gerais o suficiente para permitir o armazenamento da topologia de qualquer s?lido.

Assim, para se chegar a um conjunto de operadores topol?gicos que respeitem essas condi??es, ? necess?rio descobrir operadores que funcionem de maneira independente e permitam: a cria??o da topologia de um novo s?lido; a altera??o desta topologia inserindo ou removendo elementos como arestas e v?rtices; e, por fim, a remo??o da topologia de um s?lido de dentro de uma Half-edge.

Isso ? obtido, no entanto, dividindo os operadores topol?gicos buscados em duas categorias distintas: locais e globais. Os operadores locais s?o aqueles que alteram a topologia de apenas uma parte de um s?lido, ao passo que os globais alteram globalmente sua topologia.

7

4.3.1.Operadores topol?gicos locais

Para um pol?gono cuja fronteira ? uma cadeia de arestas ligadas duas a duas por v?rtices, e cujo n?mero de v?rtices ? maior do que tr?s, pode-se definir a seguinte opera??o: escolha dois v?rtices n?o adjacentes por aresta e crie uma nova aresta com extremos nos v?rtices escolhidos, formando duas novas cadeias de arestas distintas. A seguir tem-se uma visualiza??o desta opera??o:

V

V

1

2

V

V

1

2

V

V

4

3

V

V

4

3

Supondo que este pol?gono seja a face de um determinado s?lido no modelo de fronteira, ? facilmente observ?vel que o efeito desta opera??o ? local, resultando apenas na divis?o desta face em duas novas faces.

Analogamente, a opera??o inversa faz a jun??o de duas faces em uma, conforme mostra a figura abaixo:

V

V

1

2

V

V

1

2

V

V

4

3

V

V

4

3

Dessa forma, foram obtidos dois operadores topol?gicos locais e, na busca por outros operadores ser? introduzido o conceito de modelo de fronteira

dual. Modelo dual ? aquele obtido a partir da convers?o dos v?rtices do modelo original em faces do modelo dual, sendo que as arestas incidentes

em um v?rtice do modelo original s?o convertidas em arestas de contorno da face correspondente do modelo dual.

8

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download