Segundo Trabalho de IA-841 - Introdução à Modelagem de Sólidos - profa. Ting
Alunos: Gustavo Franco Esdras e Leandro Cardoso de Andrade
Método de subdivisão de Doo-Sabin
Subdivisões de superfícies utilizam uma malha de formas poligonais para descrever uma superfície. Estas superfícies são comumente chamadas
de superfícies de subdivisão por serem baseadas em subdivisões binárias de curvas ou superfícies de B-splines uniformes. Em geral, elas são definidas
por uma malha poligonal inicial juntamente com uma operação de subdivisão, ou refinamento, que, dada uma malha poligonal, gerará uma nova malha
que terá um número maior de elementos poligonais e será mais próxima a alguma superfície resultante desejada. Sendo o procedimento de subdivisão
aplicado repetitivamente à malha inicial, pode-se cada vez mais se aproximar da superfície buscada.
Daniel Doo e Malcolm Sabin utilizaram o paradigma de refinamento desenvolvido por George Chaikin e, através de técnicas de refinamento para
superfícies B-spline uniformes bi-quadráticas, conseguiram desenvolver um novo procedimento de definição de superfícies baseado em refinamentos.
Este estudo levou a um procedimento simples pelo qual uma superfície poderia ser desenvolvida através de uma malha poliédrica de pontos.
Procedimento para modificação de B-splines uniformes biquadráticas
Dadas as máscaras de subdivisão geradas pela subdivisão de B-splines uniformes biquadráticas:
Doo e Sabin observaram que os pontos são simplesmente a média de quatro pontos particulares selecionados em um polígono: o vértice para o
qual o novo ponto está sendo definido, os dois edge-points, que são os pontos médios das arestas adjacentes a este vértice no polígono, e o face-point,
que é o ponto médio de todos os vértices do polígono. Isto pode ser observado na seguinte figura:
Procedimento para malhas de topologia arbitrária
Este procedimento pode ser utilizado para especificar um procedimento de refinamento para superfícies de topologia arbitrária. As regras para o refinamento são as seguintes:
Os polígonos gerados através deste passo do refinamento tornam-se o conjunto de polígonos inicial par ao próximo passo. Pode ser notado o aparecimento de corte dos cantos da malha poligonal, de onde deriva o nome deste algoritmo.
Estrutura de dados Winged Edge
A estrutura de dados Winged Edge foi usada, para armazenar a estrutura de dados usada no programa, ou seja, os dados relevantes à criação
do polígono, de forma que facilitasse o desenvolvimento das rotinas do algoritmo Doo-Sabin, além do Winged Edge normal, foram armazenadas informações
extras, como o vértice antigo usado para criar o novo vértice, o mesmo esquema acontecendo para as arestas, e ainda para estas, armazenando já os
centros de cada uma. Abaixo segue um exemplo de como é representada a aresta alada (Winged Edge).
O Winged Edge é representado primeiramente pelo esquema acima, definindo suas arestas linkadas aos vértices a e b, esquerdas e direitas
(AEa, ADa, AEb, ADb), e faces, esquerda e direito, (Fe, Fd), dando assim um sentido de leitura do objeto após sua criação, facilitando então a criação
do algoritmo e otimizando o processo de localização dos vértices necessários para cada cálculos usados no algoritmo.
Implementação
A seqüência abaixo descreve basicamente o método usado para implementar o método Doo-Sabin de subdivisão de polígonos.
1- Armazenar cada “Face”, “Vértices” e "Arestas" das faces (polígonos) do objeto descrito;
2- Calcular o “Face-Point” (media dos pontos, azul escuro) e os “Edge-Points” (media das arestas, verde) ;
a- gerar os novos vértices (azul claro) usando p/ cada um:
- o “face point”, os “edge points” pertencentes ao vértice anterior, e o próprio vértice anterior (vermelho);
3- Conectar os novos vértices gerando novas arestas (amarelas) e uma nova face:
4- Para cada vértice novo, conecte-os aos pontos das faces adjacentes (criando uma nova face, rosa)
Algoritmo
Para a implementação do método e sua visualização utilizando a biblioteca OpenGL, foi desenvolvido um programa computacional em ambiente Borland
C++ Builder 6. Este programa contempla, além da implementação do método de Doo-Sabin, as funções necessárias para o correto funcionamento da
visualização em OpenGL, que permite variar as posições de observação do sólido, variar a maneira de visualização (visualização de arestas, dos polígonos,
das arestas aladas, do polígono antigo, etc.), a criação de sólidos diferentes (tetraedro, octaedro, cubo e mais duas superfícies irregulares), entre outros.
Foi também implementada neste ambiente, todo a estrutura de dados Winged Edge descrita acima. Estas partes do programa, assim como outras funções
que possibilitam seu funcionamento, não serão apresentadas aqui.
A seguir é apresentado o trecho do programa desenvolvido onde é realizado o método de subdivisão de Doo-Sabin:
copia(); // cria uma cópia da estrutura de dados (vértices, arestas e polígonos)
calculaCentros(); // calcula os centros das arestas e polígonos da cópia
removeSolido(); // apaga a estrutura antiga
// Cria os novos vértices, arestas e o polígono referente a cada polígono antes existente
Vertice *v1TempPtr, *v2TempPtr, *v3TempPtr, *v4TempPtr;
int orgA1, orgA2, orgA3, orgA4;
p1Ptr = pFirstPtrC;
for(unsigned int i = 1; i <= poligonosC; i++){
a1Ptr = p1Ptr->giveA();
p2Ptr = newSurfaceR(); // Cria a nova superfície de Doo-Sabin
if(p1Ptr == a1Ptr->giveSe()){ // v2Ptr será o vértice do sentido horário
v1Ptr = a1Ptr->giveVa();
v2Ptr = a1Ptr->giveVb();
}
else{
v1Ptr = a1Ptr->giveVb();
v2Ptr = a1Ptr->giveVa();
}
orgA1 = a1Ptr->giveA();
a2Ptr = ECW(a1Ptr, p1Ptr);
orgA2 = a2Ptr->giveA();
v2TempPtr = newVertex(v2Ptr, a1Ptr, a2Ptr, p1Ptr); // Cria o 1o. vértice de Doo-Sabin
v3Ptr = a2Ptr->giveVa();
if(v3Ptr == v2Ptr){
v3Ptr = a2Ptr->giveVb();
}
a3Ptr = ECW(a2Ptr, p1Ptr);
orgA3 = a3Ptr->giveA();
v3TempPtr = newVertex(v3Ptr, a2Ptr, a3Ptr, p1Ptr); // Cria o 2o. vértice de Doo-Sabin
v4Ptr = a3Ptr->giveVa();
if( v4Ptr == v3Ptr )
v4Ptr = a3Ptr->giveVb();
if( v4Ptr == v1Ptr ){ // o polígono é de 3 lados
v1TempPtr = newVertex(v1Ptr, a3Ptr, a1Ptr, p1Ptr); // Cria o 3o. vértice de Doo-Sabin
newEdge(v1TempPtr, v2TempPtr, p2Ptr, orgA1); // Cria a 1a. aresta de Doo-Sabin
newEdge(v2TempPtr, v3TempPtr, p2Ptr, orgA2); // Cria a 2a. aresta de Doo-Sabin
newEdge(v3TempPtr, v1TempPtr, p2Ptr, orgA3); // Cria a 3a. aresta de Doo-Sabin
}
else{ // o polígono é de 4 lados
a4Ptr = ECW(a3Ptr, p1Ptr);
orgA4 = a4Ptr->giveA();
v4TempPtr = newVertex(v4Ptr, a3Ptr, a4Ptr, p1Ptr); // Cria o 3o. vértice de Doo-Sabin
v1TempPtr = newVertex(v1Ptr, a4Ptr, a1Ptr, p1Ptr); // Cria o 4o. vértice de Doo-Sabin
newEdge(v1TempPtr, v2TempPtr, p2Ptr, orgA1); // Cria a 1a. aresta de Doo-Sabin
newEdge(v2TempPtr, v3TempPtr, p2Ptr, orgA2); // Cria a 2a. aresta de Doo-Sabin
newEdge(v3TempPtr, v4TempPtr, p2Ptr, orgA3); // Cria a 3a. aresta de Doo-Sabin
newEdge(v4TempPtr, v1TempPtr, p2Ptr, orgA4); // Cria a 4a. aresta de Doo-Sabin
}
p1Ptr = p1Ptr->giveNext();
} // Fim do for para todos os polígonos da cópia
// Cria arestas restantes e polígonos sobre os vértices antigos int Va, Vb, Vf, a1, a2;
bool primeiraVez = true;
for(unsigned int v = 1; v <= verticesC; v++){ // Para todos vértices antigos:
p2Ptr = newSurfaceR(); // Cria novo polígono de Doo-Sabin
v1Ptr = giveVC(v);
a1Ptr = v1Ptr->giveA();
a2Ptr = ECW(a1Ptr, v1Ptr); // pega próx aresta no sentido horário ao redor de v1Ptr
a3Ptr = a1Ptr;
do{
for(unsigned int v1 = 1; v1 <= vertices; v1++){ // para todos vértices novos
v2Ptr = giveV(v1);
if( v2Ptr->giveVertOrg() == v ){ // verifica se tem v1Ptr como origem
a1 = a1Ptr->giveA();
a2 = a2Ptr->giveA();
if( (v2Ptr->giveAres1Org() == a1) || (v2Ptr->giveAres2Org() == a1) ){
if( (v2Ptr->giveAres1Org() == a2) ||(v2Ptr->giveAres2Org() == a2) ){
if(primeiraVez){
Va = Vf = v1;
v1 = vertices; // termina o for de vertices novos
}
else{
Vb = v1;
v3Ptr = giveV(Va);
v4Ptr = giveV(Vb);
newEdge(v3Ptr, v4Ptr, p2Ptr, a1);
v1 = vertices; // termina o for de vertices novos
Va = Vb;
}
}
}
}
}
a1Ptr = a2Ptr;
a2Ptr = ECW(a2Ptr, v1Ptr);
primeiraVez = false;
}while( a1Ptr != a3Ptr ); // Fim do while
v3Ptr = giveV(Vb);
v4Ptr = giveV(Vf);
newEdge(v3Ptr, v4Ptr, p2Ptr, a2);
primeiraVez = true;
} // Fim do for para todos vértices da cópia
// Cria os polígonos restantes, ou seja, sobre cada aresta antiga
for(unsigned int a = 1; a <= arestasC; a++ ){ // Para todas arestas antigas
p2Ptr = newSurfaceR(); // Cria novo polígono de Doo-Sabin
for(unsigned int aNova = 1; aNova <= arestas; aNova++ ){ // para cada aresta nova
a1Ptr = giveA(aNova);
if( a1Ptr->giveArestaOrg() == a ) // se tiver "a" como origem
a1Ptr->fillSd(p2Ptr);
}
}
// Faz a associação correta de todas as arestas
for(unsigned int a1 = 1; a1 <= arestas; a1++ ){
a1Ptr = giveA(a1);
for(unsigned int a2 = a1+1; a2 <= arestas; a2++ ){
a2Ptr = giveA(a2);
WING(a1Ptr, a2Ptr);
}
}
Resultados obtidos
Foram criados os seguintes sólidos, sobre os quais foi aplicado o método de subdivisão, com os resultados apresentados a seguir. Cada quadro
novo representa uma iteração do algoritmo. Os sólidos representados em cinza são os antigos, visualizados apenas para efeito de comparação:
Tetraedro
Octaedro
Cubo
Sólido irregular em forma de S:
A seguir, é apresentado um sólido criado com a tentativa de se alcançar, após a subdivisão, uma forma parecida com uma mão humana:
