1. Innledning
1.6 Undervisning om kjønns- og seksualitetsmangfold
Malhas simples s˜ao caracterizadas por uma indexa¸c˜ao dos elementos por meio de estru- turas de dados simples, como por exemplo, matrizes. No caso de malhas n˜ao estrutu- radas, a n˜ao uniformidade da decomposi¸c˜ao celular ´e melhor representada por uma es- trat´egia mais sofisticada, que s˜ao as estruturas de dados topol´ogicas [Shephard, 1997]. As estruturas de dados topol´ogicas indexam elementos de uma malha representando rela¸c˜oes de incidˆencia e adjacˆencia entre elementos, garantindo acesso r´apido `as in- forma¸c˜oes.
Estruturas de dados topol´ogicas (EDT) tamb´em s˜ao muito ´uteis em aplica¸c˜oes onde existem deforma¸c˜oes constantes na malha. Elas permitem a movimenta¸c˜ao dinˆamica dos n´os da malha sem modificar sua topologia (conectividade). Neste con- texto, tais estruturas podem representar malhas el´asticas, que podem ser do tipo superficial ou volum´etrica, simples ou mista.
As malhas manipuladas numa simula¸c˜ao podem representar diferentes tipos de elementos, como triˆangulos e quadril´ateros (no caso bidimensional) e tetraedros,
4.2 Estrutura de Dados Topol´ogicas 57 pirˆamides e hexaedros (no caso tridimensional). Existe ainda a possibilidade da com- posi¸c˜ao da malha por diferentes elementos, neste caso a malha denomina-se mista.
Embora existam muitas estruturas de dados topol´ogicas dedicadas `a representa¸c˜ao de malhas volum´etricas, poucas fazem uso formal de operadores topol´ogicos no con- trole dos elementos armazenados, sendo este um ponto de grande interesse na atuali- dade [Nielson, 2000].
As estruturas de dados tridimensionais representam decomposi¸c˜oes celulares vo- lum´etricas. As malhas destas decomposi¸c˜oes s˜ao do tipo poliedral, sendo os tetraedros os mais comuns entre os poliedros utilizados na literatura.
Grande parte das EDTs propostas na literatura indexa os dados de modo a fa- cilitar o acesso `as rela¸c˜oes de vizinhan¸ca e `as buscas feitas na constru¸c˜ao ou leitura de malhas [Kwok et al., 1995], viabilizando o controle de procedimentos adaptati- vos [Bottasso et al., 1998]. Al´em disso, um aspecto importante destas estruturas s˜ao os operadores topol´ogicos utilizados na constru¸c˜ao e manuten¸c˜ao das mesmas [Nielson, 2000].
Deste modo, s˜ao v´arios os trabalhos que desenvolveram estruturas de dados para a representa¸c˜ao dos diversos tipos de malhas, de modo que eles s˜ao diferentes entre si na maneira que eles armazenam os v´ertices, arestas e as faces. Mais especificamente, elas diferem na representa¸c˜ao expl´ıcita ou impl´ıcita das informa¸c˜oes, ou seja, a informa¸c˜ao est´a diretamente dispon´ıvel (expl´ıcita), armazenadas em vetores ou listas ligadas, ou indiretamente dispon´ıvel (impl´ıcita), sendo necess´arias algumas opera¸c˜oes alg´ebricas para buscar a informa¸c˜ao.
A vantagem em se utilizar representa¸c˜oes impl´ıcitas ´e o menor consumo de mem´oria e a maior simplicidade de implementa¸c˜ao dos operadores topol´ogicos, al´em de reduzir a redundˆancia de informa¸c˜oes distribu´ıdas na estrutura de dados. Isso melhora a robus- tez das estruturas, mas a desvantagem ´e a dificuldade de aplic´a-la em decomposi¸c˜oes celulares que envolvem diferentes tipos de c´elulas. Deste modo, na literatura encon- tramos representa¸c˜oes impl´ıcitas com eficientes t´ecnicas de recupera¸c˜ao das rela¸c˜oes
de adjacˆencia usando apenas para malhas triangulares ou tetraedrais[Kettner, 1999] [Boissonnat et al., 2000].
Muitas estruturas de dados topol´ogicas descritas na literatura tˆem operadores espec´ıficos dedicados `a manuten¸c˜ao da consistˆencia topol´ogica dos objetos repre- sentados. Como exemplo, podemos citar a estrutura Winged-Edge de Baumgart [Baumgart, 1975] e a Half-Edge de M¨antyl¨a [Mantyla, 1989], que utilizam os cha- mados operadores de Euler para garantir a integridade de malhas bidimensionais.
A Winged-Edge representa explicitamente os v´ertices, arestas e as faces de uma malha. Cada v´ertice tem armazenadas as arestas em que ele participa, cada aresta tem armazenados os n´os das extremidades, junto com as faces de que participa e as suas arestas antecessoras e sucessoras em rela¸c˜ao `as faces de que participa. Por fim, a lista das faces tem armazenadas as arestas que a formam. Esta representa¸c˜ao facilita as aplica¸c˜oes que necessitam realizar opera¸c˜oes de divis˜ao/mesclagem de c´elulas, pois as modifica¸c˜oes s˜ao realizadas diretamente na estrutura.
Na estrutura Half-Edge, as arestas mant´em informa¸c˜oes de incidˆencia de v´ertices, arestas e faces. Cada aresta ´e decomposta em duas Half-Edges com orienta¸c˜ao indu- zida por sua c´elula incidente. Uma face incidente e um v´ertice incidente s˜ao armaze- nados em cada Half-Edge, e, para cada face e v´ertice, uma Half-Edge ´e armazenada.
Uma estrutura de dados espec´ıfica para malhas triangulares ´e a Corner-Table [Rossignac et al., 2001]. Nesta estrutura, ´e utilizado o conceito de corners para re- presentar a associa¸c˜ao de um triˆangulo a um de seus v´ertices ou, isto ´e, associar um corner ao bordo oposto de um corner, onde cada triˆangulo ´e definido por trˆes corners consecutivos que definem sua orienta¸c˜ao.
Outro exemplo ´e a estrutura Quad-Edge de Guibas e Stolfi
[Guibas and Stolfi, 1985], que emprega um operador denominado splice para o controle topol´ogico de malhas 2–D. Uma extens˜ao da Quad-Edge chamada Facet- Edge foi proposta por Dobkin e Laslo [Dobkin and Laszlo, 1989], de modo a representar complexos celulares que s˜ao subdivis˜oes de uma esfera tridimensional.
4.2 Estrutura de Dados Topol´ogicas 59 Contudo, a Facet-Edge trata somente complexos celulares orient´aveis.
Ainda no contexto bidimensional, Nonato et. al. [Nonato et al., 2008] desenvolve- ram uma estrutura chamada Singular Handle-Edge (SHE), que emprega operadores de Morse no controle topol´ogico dos elementos armazenados.
Uma vers˜ao estendida da Handle-Edge, a Handle-Face, foi proposta por Lopes e Tavares [Lopes and Tavares, 1997] para representa¸c˜ao de malhas volum´etricas for- madas por tetraedros. Esta utiliza o conceito de Half-Face representada por um triˆangulo, cuja orienta¸c˜ao ´e induzida pelo tetraedro a que ela pertence. Bem como a Handle-Edge, esta estrutura utiliza ponteiros para representar os tipos de n´os de cada elemento da malha.
Proposta por De Floriani e Hui [Floriani and Hui, 2003], a estrutura de dados “Non-Manifold Indexed Data Structure with Adjacencies” mostra uma abordagem para tratar opera¸c˜oes de busca na vizinhan¸ca de seus componentes. Por´em, esta estrutura n˜ao permite representar n˜ao-variedades.
Apresentando caracter´ısticas similares `as estrutura Handle-Face, a estrutura Com- pact Half-Face (CHF), proposta por Lage [Lage et al., 2005], foi desenvolvida para re- presentar malhas tetra´edricas usando a caracter´ıstica de escalabilidade de estruturas. Ela ´e composta por quatro n´ıveis de escalabilidade, sendo o n´ıvel zero com menor uso de mem´oria e o n´ıvel trˆes com maior uso de mem´oria, por´em com melhor desempenho de processamento para dados topol´ogicos.
Como visto, s˜ao in´umeras as contribui¸c˜oes de estruturas de dados para representar malhas e cada uma delas possui suas vantagens e desvantagens, seguindo diferentes abordagens. A seguir ser´a brevemente explicada uma estrutura de dados que ´e in- teressante a este trabalho, a Opposite Face [Lizier, 2006], e ser´a mostrada com mais detalhes a Mate Face [Cunha, 2009], a estrutura de dados escolhida e utilizada em todo o desenvolvimento deste trabalho.