# Master's dissertation - Rober Marcone Rosi .
# All formulas and numbers were replaced by "x".
# Puntuation and capitalization were removed.
# Last edited on 1998-11-08 08:04:46 by stolfi

em computação gráfica objetos tridimensionais são freqüentemente
modelados pela técnica de representação de fronteira que consiste em
descrever a superfície de cada objeto como a união de faces retalhos
de superfícies planas ou curvas as faces são limitadas por arestas
segmentos de retas ou curvas cujos extremos são os vértices do
objeto
na implementação de algoritmos que manipulam tais objetos a
experiência aconselha separar os aspectos topológicos que dizem
respeito aos contatos entre os vértices arestas e faces e os
aspectos geométricos que incluem as coordenadas dos vértices a forma
das arestas e das faces etc veja a figura esta separação facilita
o desenvolvimento e depuração de algoritmos e a modelagem dos
objetos
informalmente as relações topológicas entre as faces arestas e
vértices de um objeto podem ser descritas por meio de um modelo de
colagem nesse modelo cada face do objeto é representada por um
polígono simples no plano cada lado do qual está decorado com uma
seta longitudinal e um rótulo cada rótulo aparece em exatamente dois
lados no mesmo polígono ou em polígonos diferentes entende-se que
esses dois lados unidos como indicado pelas setas constituem uma
única aresta do objeto entende-se também que a forma e o tamanho dos
polígonos não tem relação nenhuma com a forma e tamanho das faces
correspondentes do objeto
a figura é um modelo de colagem que descreve a topologia das arestas
vértices e faces de um cubo como o da figura note que esse mesmo
modelo de colagem descreve também a topologia da representação de
fronteira do sólido da figura
a topologia definida por um modelo de colagem pode ser bastante
difícil de visualizar por exemplo o modelo de colagem da figura
com apenas uma face e duas arestas descreve a topologia das faces
arestas e vértices do objeto ilustrado na figura a superfície em
questão é a garrafa de klein que tem a peculiaridade de possuir um
único lado
compare este exemplo com o modelo de colagem da figura que descreve o
objeto da figura a superfície neste caso é um toro que tem dois
lados
as figuras e demonstram que a topologia de um objeto complexo com um
número grande de faces e arestas é praticamente impossível de
visualizar sem algum auxilio computacional
esta dificuldade nos motivou a desenvolver um programa para a
visualização automática da topologia de complexos celulares
arbitrários a entrada deste programa é uma estrutura de dados que
representa a topologia de um complexo como nas figuras e a saída é
uma realização geométrica bonita da mesma como nas figuras e
esta representação consiste de uma superfície de forma específica
mergulhada no espaço x e de uma divisão da mesma em faces vértices
e arestas correspondentes aos elementos do complexo com as mesmas
relações de adjacência esta superfície pode ser então desenhada por
ferramentas padrões de computação gráfica
para resolver este problema automaticamente é preciso primeiro
definir o conceito de representação bonita informalmente o que
se quer é uma superfície que em primeiro lugar permita a
visualização fácil da topologia do complexo celular e em segundo
lugar seja esteticamente agradável
de modo geral para satisfazer estes objetivos a superfície precisa
ser suave e bem distribuída no espaço na medida do possível ela não
deve cruzar a si mesma e as faces e arestas devem ter formas simples
e tamanhos similares
note a diferença entre a topologia do complexo as relações de
adjacência entre faces vértices e arestas e a topologia da
superfície que se resume na sua orientabilidade e conectividade
para uma boa visualização da primeira não basta que a topologia da
superfície seja fácil de entender é preciso também que as arestas e
faces pintadas sobre a superfície sejam simples e bem separadas e
que suas adjacências sejam claramente visíveis
em particular mesmo que um complexo celular tenha superfície
homeomorfa a uma esfera sua melhor representação não é
necessariamente uma esfera geométrica por exemplo a estrutura do
complexo da figura fica mais fácil de visualizar numa superfície
alongada como em~ do que na esfera~
a fim de quantificar estes critérios definimos uma função numérica
da geometria da superfície chamada de energia e que mede as
características indesejáveis da mesma curvatura auto-intersecções
sobreposições variância do tamanho dos elementos etc uma vez
definida esta função o problema passa a ser determinar dentre
todas as representações geométricas do complexo dado aquela que tem
energia mínima
o problema de desenho bonito de grafos no plano tem recebido
bastante atenção devido ao grande número de aplicações projeto de
vlsi bancos de dados algoritmos de animação linguagens visuais
gerência de redes ferramentas para desenvolvimento de software etc
apesar do nosso problema não ser o mesmo que o de desenho de grafos em
x ou x dimensões a solução apresentada usa técnicas semelhantes às já
usadas com sucesso nesta área e por outro lado espera-se que
algumas das idéias aqui abordadas possam vir a ser úteis também para
a visualização de tais grafos
este trabalho tem grandes semelhanças com certas técnicas de relaxação
usadas em projeto industrial para o amaciamento de juntas e cantos
fairing e filleting em modelos de sólidos em moreton dada
uma forma inicial para a superfície o ajuste entre os retalhos
polinomiais é feito usando-se técnicas padrões de otimização
não-linear baseadas no método do gradiente entretanto nessas
aplicações o objetivo é obter uma superfície suave interpolando certas
curvas com forma e posição dadas portanto esses trabalhos usam uma
função energia mais simples que a usada aqui não têm que lidar com
topologias muito complicadas e partem de uma solução inicial bastante
próxima à desejada
outro programa semelhante ao nosso trabalho é o surface evolver
desenvolvido por brakke trata-se de um programa para o estudo da
evolução de superfícies sujeitas a forças tais como tensão
superficial forças elásticas pressão etc contudo as energias
usadas nesse trabalho foram escolhidas por sua significância
matemática e física não por seus efeitos visuais além disso as
energias implementadas pelo surface evolver não são suficientes para a
solução dos problemas que nós estamos apresentando já que elas
dependem apenas da forma da superfície e não do grafo desenhado sobre
ela
nosso trabalho também está relacionado com o problema
de calcular a configuração espacial de uma molécula de proteína
a partir da seqüência de seus aminoácidos
a relação vem do fato que a energia estética aqui abordada
é qualitativamente semelhante à energia físico-química
que determina as posições relativas dos átomos na molécula
ambas tem centenas de variáveis de natureza geométrica e inúmeros
mínimos locais separados por barreiras elevadas
portanto parece razoável supor que quaisquer técnicas de
minimização que são boas para um destes problemas também
são úteis para o outro
a idéia geral de usar funções energia para quantificar a
feiúra de um desenho aparentemente tornou-se popular após o artigo
de kamada de fato algumas das funções energias que nós usamos são
similares às molas do modelo adotado por kamada outras funções
energia são similares a energia de dobramento geralmente tomada como
a integral do quadrado da curvatura da superfície que é
freqüentemente a única energia considerada nos estudos sobre
superfícies minimais
antes de mais nada precisamos definir precisamente o conceito de
complexo celular vamos supor conhecidos os seguintes conceitos
elementares de topologia espaço topológico conjunto aberto e
fechado subespaço vizinhança ponto de acumulação limite e
homeomorfismo ou eqüivalência topológica as definições podem ser
encontradas no apêndice ou em textos introdutórios de topologia de
conjuntos
um espaço topológico x é compacto se toda seqüência infinita de pontos
de x tem um ponto de acumulação em x
uma variedade topológica bidimensional é um espaço
topológico x no qual todo ponto tem uma vizinhança que é
homeomorfa a x
informalmente uma variedade topológica bidimensional compacta é
um espaço topológico equivalente a um subconjunto do
x para algum x topologicamente fechado e de diâmetro finito
e que é bidimensional ao redor de qualquer de seus pontos a esfera
x a superfície de um toro e o plano projetivo são exemplos
típicos
por outro lado a superfície de um cilindro de comprimento
infinito não é compacta ela contém seqüências infinitas de pontos
cujo limite não está na superfície pelo mesmo motivo um
hemisfério sem os pontos do equador ou uma fita de möbius sem
os pontos da borda também não são compactos se incluirmos os
pontos da borda estes conjuntos tornam-se compactos mas deixam
de ser variedades pois um ponto na borda não tem nenhuma
vizinhança que seja um disco
no que segue usaremos o termo variedade para significar variedade
topológica bidimensional compacta
informalmente um complexo celular é um grafo desenhado sobre
uma variedade de tal forma que toda face seja um pedaço
simples da mesma sem furos ou alças mais formalmente
um segmento aberto de um espaço
topológico x é um subespaço de x homeomorfo
à reta real x
um disco aberto de x
é um subespaço de x homeomorfo ao plano x
um complexo celular é uma partição de uma
variedade numa coleção finita de elementos cada um dos
quais é um ponto vértice um segmento aberto
aresta ou um disco aberto face da variedade
se x é um complexo celular denotaremos o conjunto de
seus vértices por x o das arestas por x e o das
faces por x
dizemos que x é conexo se a variedade subjacente é conexa
as componentes conexas de x correspondem de maneira óbvia
às componentes da variedade subjacente neste trabalho
consideramos apenas complexos celulares conexos para visualizar
um complexo geral com as nossas ferramentas é necessário
aplicá-las a cada componente conexa separadamente
vamos definir agora o modelo de colagem de um complexo celular que
será adotado por nós neste trabalho
um modelo de colagem consiste de
um conjunto x de polígonos cada um dos quais é um disco fechado cuja
fronteira é dividida num número finito de segmentos lados e pontos
cantos
uma função bijetora contínua x cujo o domínio e imagem são a união de
todos os lados desses polígonos a função x deve ser sua própria
inversa x para todo lado x deve-se ter x e a restrição de x ao lado x
deve ser um homeomorfismo entre x e x
dizemos que um modelo de colagem como o acima representa um complexo
celular x sobre uma variedade x se existir uma função contínua x que
mapeia cada polígono x no fecho de uma face distinta x de x cada lado
de x numa aresta de x incidente a essa face e cada canto de x num
vértice incidente a essa face tal que x é um homeomorfismo quando
restrita ao interior de x e tal que x se e somente se x para dois
pontos quaisquer x x nos lados de x
em topologia prova-se que todo complexo celular pode ser representado
por um modelo de colagem e vice-versa
para facilitar a descrição de algoritmos que trabalham com complexos
celulares é conveniente definir funções que permitem caminhar no mapa
de um elemento para os elementos vizinhos neste trabalho usaremos as
funções definidas em com pequenas modificações
seja x uma aresta de um complexo celular
existem exatamente duas maneiras de definir uma orientação
longitudinal sobre x que
são as duas maneiras de ordenar os pontos de x de forma
compatível com sua topologia
podemos indicar uma destas direções por uma seta sobre qualquer ponto
da aresta outra maneira de visualizar a orientação de uma aresta é
imaginar um observador minúsculo andando sobre a superfície ao longo
da aresta a direção longitudinal diz em que sentido ele está
caminhando veja a figura
da mesma forma para cada aresta x de um complexo celular
existem exatamente duas maneira de definirmos uma orientação
transversal sobre a ou seja duas maneiras possíveis de definir o
lado esquerdo e o lado direito da aresta numa vizinhança
suficientemente pequena da mesma
novamente imagine um observador minúsculo caminhando em uma
aresta sobre uma superfície portanto a orientação diz em que
lado da aresta está seu pé esquerdo ou seja sobre que lado da
superfície ele está andando veja a figura
portanto cada aresta do complexo tem exatamente quatro combinações de
orientação longitudinal e transversal possíveis note que isto é
verdade mesmo que os dois extremos da aresta incidam no mesmo vértice
ou que os dois lados da aresta pertençam à mesma face a partir de
agora chamaremos de arco do complexo a uma aresta com uma determinada
orientação longitudinal e transversal
para um arco x podemos definir sem ambigüidade graças à sua orientação
longitudinal o vértice de origem x e o vértice de destino x
analogamente usando a orientação transversal podemos definir a face
esquerda x e a face direita x da aresta note que podemos ter x ou x
se x é uma aresta orientada denotaremos por x a aresta com orientação
simétrica que consiste da mesma aresta x mas com as duas orientações
longitudinal e transversal invertidas note que apesar de termos
invertido as orientação transversal continuamos do mesmo lado da
superfície
denotaremos também por x o resultado de inverter apenas
a orientação transversal da aresta orientada x mantendo a
orientação longitudinal neste caso nosso observador minúsculo
passa para o outro lado da superfície mas continua andando no
mesmo sentido ao longo da aresta veja a figura
seja x a origem de um arco x a orientação transversal de
x considerada em pontos arbitrariamente próximos a x
define um sentido de rotação em torno de x considere todos
os arcos com origem x que definem
o mesmo sentido de rotação podemos distinguir o próximo arco
com mesma origem que x x como sendo o arco
seguinte a x no sentido anti-horário da orientação transversal de x
as funções x e x são suas próprias inversas e a inversa da função x é
x esta última chamada x devolve o arco anterior com mesma origem
que o argumento no sentido horário da orientação transversal de x
a partir das funções acima podemos definir o próxima arco com mesma
face esquerda e o arco anterior com mesma face esquerda
respectivamente por x e x informalmente x e x são os arcos que
seguem e precedem x respectivamente quando percorremos a fronteira
da face x no sentido que concorda com a orientação longitudinal de
x a figura ilustra estas e outras funções que serão definidas nas
próximas seções
informalmente a subdivisão baricêntrica de um complexo celular x é
obtida inserindo-se um novo vértice x no meio de cada aresta de x
um novo vértice x no meio de cada face x e ligando-se este último a
todos os vértices originais e novos na fronteira dessa face x por
novas arestas dentro da face x veja a figura
mais formalmente uma subdivisão baricêntrica de x é outro complexo
celular x mais refinado tal que
toda aresta de x incide em dois vértices distintos
toda face de x incide em três vértices distintos e três arestas
distintas
todo vértice de x é um vértice de x
toda aresta x de x é a união de um vértice x e
duas arestas x x de x incidentes em x
toda face x de x é a união de um vértice x de x e de um número par de
arestas e outras tantas faces de x todas distintas e incidentes em x
note que os vértices de x podem ser divididos em três tipos os que
são vértices de x vértices primais tipo v os que pertencem a
arestas de x vértices mediais tipo e e os que pertencem a faces de
x vértices duais tipo f
note também que cada aresta de x liga dois vértices de tipos
diferentes portanto temos três tipos de arestas ve vf e ef as
arestas de tipo ve são partes de arestas de x as demais estão
contidas nas faces de x finalmente note que cada face de x é
incidente a exatamente um vértice de cada tipo
com isso podemos afirmar que uma face de x é homeomorfa a um
triângulo planar onde cada canto representa um vértice e cada lado
representa uma aresta de x
informalmente um isomorfismo x entre dois complexos celulares é uma
bijeção entre os elementos desses complexos que preserva todas as
relações de incidência e adjacência
mais precisamente sejam x e x dois complexos celulares e x e x as
respectivas funções de percurso dizemos que x é isomorfo a x se
existe uma bijeção x dos arcos de x para os arcos de x tal que x para
todo arco x note que esta condição estabelece também uma bijeção
entre os vértices e faces dos complexos que podem ser identificados
com as órbitas de x e de x respectivamente
um complexo celular abstrato é definido como sendo uma classe de
equivalência de complexos celulares isto é o conjunto de todos os
complexos celulares que são isomorfos a um complexo dado
informalmente o dual de um complexo celular x é um complexo x que tem
as mesmas relações de incidência e adjacência que x exceto que os
papéis dos vértices e faces estão trocados
mais formalmente dois complexos celulares x e x numa mesma
superfície x são duais estritos se toda face de x contém um único
vértice de x e vice-versa e os dois complexos admitem uma subdivisão
baricêntrica comum x
neste caso forçosamente os vértices de x são os vértices de tipo f
de x e cada aresta de x consiste de um vértice de tipo e de x mais
as duas arestas de x de tipo ef incidentes a esse vértice
a figura mostra um complexo x linha cheia e seu dual linha
tracejada note que cada aresta não dirigida de x cruza somente sua
respectiva aresta dual e que cada vértice primal está na sua
correspondente face dual e vice-versa
podemos notar que para todo complexo existem infinitos complexos que
são seus duais estritos entretanto prova-se que todos esses duais
são isomorfos entre si e mais ainda se o complexo x é isomorfo a x
todo dual estrito de x é isomorfo a todo dual estrito de x portanto
todo complexo abstrato x tem um único complexo abstrato dual x
seja x um complexo celular e x um dual estrito de x a cada aresta
orientada e dirigida x de x existe uma única aresta orientada e
dirigida de x que cruza x da direita para a esquerda e é cruzada por x
da esquerda para a direita vamos denotar essa aresta orientada e
dirigida por x
informalmente x é obtida rodando-se x x no sentido anti-horário ao
redor do ponto de cruzamento da aresta x com sua aresta dual do ponto
de vista do observador que anda sobre a aresta veja a figura
como a relação entre x e x é simétrica esta definição também vale
para as arestas de x ou seja se x é um arco de x x é um arco de x
que cruza x da direita para a esquerda
segue-se daí que x para todo arco de x ou x e portanto x para toda
aresta x a inversa de x pode ser definida como x e será chamada por
nós de x
a partir das funções acima podemos definir para uma dada aresta x
as seguintes funções veja a figura
x é o primeiro arco encontrado ao avançarmos para a aresta seguinte a
x na fronteira da face x no sentido anti-horário x
x é o primeiro arco encontrado ao avançarmos para a aresta anterior a
x na fronteira da face x no sentido horário x
x é o primeiro arco encontrado ao avançarmos para a aresta seguinte a
x ao redor de x no sentido anti-horário x
x é o primeiro arco encontrado ao avançarmos para a aresta anterior a
x ao redor de x no sentido horário x
é fácil ver que a partir de qualquer arco inicial x podemos atingir
todas os arcos orientados na componente conexa do complexo que contém
x usando combinações apropriadas de x x e x
outra observação a ser feita é que todas as funções já definidas até
aqui exceto x podem ser obtidas por combinações de x e x pois
encontram-se na literatura muitas estruturas de dados destinadas a
representar a topologia de complexos celulares de modo geral todas
estas estruturas usam um registro para cada elemento do complexo
vértice aresta ou face com apontadores para os elementos
adjacentes assim as funções de percurso da seção se reduzem a
seguir apontadores e modificações locais na topologia do complexo
correspondem a modificações locais nos nós e apontadores da estrutura
neste trabalho decidimos adotar a estrutura de dados quad-edge essa
estrutura é similar às estruturas winged edge e half-edge amplamente
usadas em cad e computação gráfica mas tem sobre elas a vantagem de
permitir a representação de complexos celulares não-orientáveis como
a garrafa de klein ou o plano projetivo
além disso a estrutura quad-edge permite também representar complexos
celulares com vértices de grau x figura múltiplas arestas unindo o
mesmo par de vértices fig arestas com origem e destino no mesmo
vértice fig e faces incidentes múltiplas vezes ao mesmo vértice
fig na verdade esta generalidade é também uma desvantagem pois
exige cuidados especiais na modelagem da superfície como será visto
mais adiante
por outro lado a estrutura quad-edge exige que toda face seja
topologicamente equivalente a um disco sem buracos esta restrição
é às vezes inconveniente por necessitar a introdução de arestas
sem significado geométrico mas
simplifica bastante a representação e o manuseio da estrutura
na estrutura quad-edge cada aresta x do complexo celular é
representada por um grupo de oito arcos que correspondem às quatro
orientações da aresta x e às quatro orientações da aresta dual
para construir a estrutura de dados nós selecionamos arbitrariamente
uma arco canônico em cada grupo desta forma qualquer arco x pode ser
escrita como x onde x é o arco canônico do grupo a que x pertence
assim as oito possíveis orientações de x podem ser representadas na
estrutura de dados por um registro x dividido em quatro partes x x
x x x corresponde a aresta x e guarda uma referência para o x uma
aresta genérica x é então representada pela tripla x
para qualquer arco x pertencente ao grupo x é possível calcular x a
partir dos campos x através das identidades
na figura a parte mostra a representação de um registro para uma
aresta mostra um complexo celular e a estrutura de dados para o
complexo
uma maneira óbvia de modelar a geometria da superfície seria modelar
cada face do complexo por um retalho polinomial implícito ou
paramétrico com restrições de continuidade entre retalhos adjacentes
entretanto as faces do complexo podem ter número arbitrário de lados
colados entre si de maneira arbitrária em geral não é possível
representar a topologia destas colagens com um único retalho
polinomial de grau limitado
para contornar essa dificuldade introduzimos o conceito de
ladrilhamento de um complexo celular x que é uma
subdivisão da superfície de x em retalhos mais simples os
ladrilhos dada uma subdivisão baricêntrica de x x
podemos definir o ladrilho de uma aresta x de x como sendo a união
de quatro faces triangulares de x que têm uma das duas
arestas ve de x que são partes da aresta x como um de
seus lados
topologicamente o ladrilhamento substitui o complexo celular original
por um novo complexo celular x sobre a mesma superfície cujas faces
tem todas quatro arestas
assim cada ladrilho pode ser visto como um quadrilátero colado por
seus lados a outros quatro ladrilhos possivelmente a si próprio os
vértices de um ladrilho são alternadamente vértices de x e de x o
dual estrito de x existe exatamente um ladrilho x para cada aresta
x do complexo a aresta x e sua dual x são as duas diagonais do
ladrilho veja a figura
portanto em vez de considerar a superfície como uma união de faces
ela é considerada como uma união de ladrilhos uma vez que cada
ladrilho tem apenas quatro lados e portanto quatro ladrilhos
vizinhos ele pode ser modelado em princípio por um objeto geométrico
de complexidade finita o problema reduz-se então à atribuir geometria
a cada ladrilho garantido continuidade suavidade não
interferência e outras qualidades visuais como veremos no cap
em computação gráfica superfícies curvas são quase que universalmente
representadas por superfícies polinomiais paramétricas portanto é
natural pensarmos em representar cada ladrilho por um retalho
quadrangular de superfície deste tipo ou seja pelo conjunto onde x
x e x são polinômios nos parâmetros x e x em particular quando os
polinômios são de grau x temos os retalhos de bézier
infelizmente este modelo geométrico introduz algumas dificuldades
bastante sérias em primeiro lugar observe que para que a
superfície toda seja contínua precisamos escolher os polinômios de
tal forma que os retalhos de ladrilhos adjacentes estejam colados no
espaço ou seja que os valores das funções x x e x de um retalho
sejam iguais aos valores das funções do outro retalho ao longo de sua
fronteira comum
além disso se quisermos que a superfície seja suave sem pontas
ou quinas precisamos garantir a igualdade também do plano
tangente ao longo dessa fronteira para
garantir que estas restrições tenham solução qualquer que seja a
topologia do complexo precisamos usar polinômios de grau bastante
elevado pelo menos x em cada um dos parâmetros x e x
estas restrições de continuidade e suavidade se traduzem em restrições
algébricas complicadas sobre os coeficientes dos polinômios em
questão por exemplo a continuidade do plano tangente entre dois
retalhos vizinhos de grau x equivale a x equações envolvendo uma
centena de determinantes distintos
finalmente precisamos também excluir singularidades geométricas
cúspides no interior de cada retalho esta condição corresponde a
exigir que três polinômios de grau x em x e x não se anulem ao mesmo
tempo
como se pode ver é bastante difícil manter todas estas restrições
satisfeitas durante o processo de otimização da energia sem mencionar
o fato que as funções de energias mais importantes como a integral da
curvatura veja seção são bastante difíceis de calcular a partir dos
coeficientes dos polinômios
em vista destas dificuldades decidiu-se modelar cada ladrilho por uma
superfície poliédrica especificamente por uma malha de x
quadriláteros cada um dos quais dividido em quatro triângulos
planos veja a figura
desta forma substituímos o complexo celular original x com x
arestas por um complexo mais refinado uma triangulação x da
superfície com x arestas e x faces triangulares cada uma destas
faces será modelada por um triângulo geométrico plano com lados
retilíneos
ao adotarmos este modelo temos que desistir da condição de
continuidade do plano tangente em vez disso nos contentamos em
minimizar os ângulos entre triângulos vizinhos
o valor apropriado de x depende da estrutura do complexo para os
complexos que usamos nos nossos testes conseguimos resultados
satisfatórios com x
o algoritmo de ladrilhamento divide-se em três etapas a construção
dos ladrilhos a colagem dos mesmos e a eliminação de triângulos
degenerados a seguir vamos discutir detalhadamente cada etapa deste
algoritmo
na etapa de construção montamos para cada aresta x do complexo x
dado um ladrilho triangulado como ilustrado na figura este ladrilho
tambem é modelado pela estrutura quad-edge note que o exterior do
ladrilho é modelado por uma face adicional completando uma
esfera essa face é eliminada automáticamente pelo processo de colagem
veja seção
uma diagonal do ladrilho consistindo de x arestas da triangulação
representa a aresta x do complexo original e a outra diagonal
representa a aresta dual de x os quatro cantos do ladrilho
representam alternadamente vértices de x e centros de faces de x
nesta etapa construímos uma tabela que associa a cada arco x do
complexo original x um arco x do ladrilho correspondente como
ilustrado na figura
note que as arestas representadas com linha tracejada estão no lado de
baixo do ladrilho especificamente se x é a seqüência de arcos na
diagonal do ladrilho que representam o arco x então x definimos
também a função x
na etapa de colagem unimos o ladrilho de cada arco x do mapa original
com o ladrilho do arco x juntando pares de vértices correspondentes
ao longo dos lados apropriados e eliminando arestas paralelas veja
a figura
mais precisamente as arestas a serem identificadas são x no ladrilho
de x e x no ladrilho de x onde x x e e para x
note-se que para colar as arestas x e x temos que retirar da
triangulação uma dessas duas arestas em nosso programa
convencionamos retirar a aresta x
em princípio a colagem deve ser aplicada a todos os pares de arcos x
do complexo primais e duais entretanto note que ao colarmos x com
x estamos na verdade colando os quatro pares portanto se aplicamos a
colagem a um destes pares devemos evitar de aplicá-la aos outros
três
no caso de complexos orientáveis esta condição pode ser trivialmente
satisfeita basta limitar a enumeração às arestas dirigidas e
orientadas primais de um lado do complexo isto é todas os arcos
que podem ser atingidos de um arco inicial x por aplicações múltiplas
de x e x
entretanto no caso de complexos não orientáveis esta abordagem não
funciona pois é possível atingir x por combinações de x e x para
tratar esses casos é necessário acrescentar um teste no início do
algoritmo de colagem que retorna imediatamente se os lados a colar já
estão colados
segue abaixo a descrição detalhada do processo de colagem de dois
ladrilhos
nessa descrição usamos a operação fundamental de edição da estrutura
quad-edge denotada por x não cabe aqui descrever o efeito geral
desta operação para nossos fins basta saber que x modifica os
apontadores x de forma a juntar os vértices de origem das arestas
dirigidas e orientadas x e x se eles forem distintos ou separá-los
se forem o mesmo vértice
mais precisamente se antes da operação temos x e x depois dela
teremos x e x ao mesmo tempo os apontadores x da subdivisão dual
são atualizados de forma a separar as faces x e x se elas forem a
mesma face ou juntá-las se elas forem distintas veja a
figura para mais detalhes sobre o operador x veja o artigo de guibas
e stolfi
o processo de colagem de dois ladrilhos pode ser descrito então pelo
procedimento gluepatch abaixo ele usa um procedimento auxiliar
identify definido mais adiante
na etapa de colagem é possível que um ladrilho tenha que ser colado
consigo mesmo isto ocorre em casos onde temos x x ou x nesse
caso o complexo refinado vai conter pares de triângulos degenerados
triângulos distintos incidentes nos mesmos três vértices veja a
figura
pares de triângulos degenerados são indesejáveis pois eles são sempre
coincidentes quaisquer que sejam as coordenadas atribuídas aos
vértices e resultam em descontinuidades e abas pendentes na
superfície
portanto após a colagem de todos os ladrilhos precisamos localizar e
eliminar quaisquer pares de triângulos que tenham se tornado
degenerados este processo pode ser feito de maneira eficiente
graças ao seguinte resultado
seja x uma triangulação qualquer obtida por ladrilhamento de um
complexo celular x com ladrilhos de ordem x
se x só teremos pares de triângulos degenerados se algum ladrilho
tiver sido colado a si mesmo e nesse caso os dois triângulos degenerados
pertencem ao mesmo ladrilho
prova sejam x e x dois triângulos de x que depois de colados possuem
três vértices comuns x a colagem só pode ter identificado dois desses
vértices pois pelo menos um vértice de cada triângulo é interior ao
ladrilho portanto x e x tinham pelo menos um vértice interior em
comum antes da colagem assim eles pertencem ao mesmo ladrilho
isto ainda não prova que o ladrilho foi colado consigo mesmo pois a
identificação dos vértices de x e x poderia ter acontecido por via
indireta o ladrilho x que contém x e x é colado com x x é colado com
x que é colado com o ladrilho x precisamos portanto provar que a
colagem foi direta x com x
cada um desses vértices pode estar no canto do ladrilho vértice
de tipo c ou num dos lados do ladrilho vértice de tipo
l ou no interior do ladrilho vértice de tipo i veja a figura
na verdade só as cinco combinações de tipos ilustradas na fig são
possíveis
antes da colagem x e x tinham um ou dois vértices em comum
a colagem só identifica vértices de tipo c com vértices de
tipo c e vértices de tipo l com vértices de tipo
l portanto a colagem deve ter identificado um ou dois
pares de vértices cada um de tipo l-l ou tipo c-c
na figura temos todas as possíveis
posições relativas dos triângulos x e x antes da colagem e
que satisfazem estas condições note que devido a topologia de
nossos ladrilhos podemos concluir que os casos x a x
na figura não ocorrem e que os casos
x e x só ocorrem para x assim todas as possibilidades
que restam incluem uma identificação de um vértice l do
ladrilho com outro vértice l do mesmo ladrilho mas
vértices de tipo x só são identificados aos pares portanto isto
só ocorre por colagem direta de um ladrilho consigo mesmo
fim da prova
a partir deste teorema podemos identificar facilmente os pares de
triangulos degenerados criados pela colagem para ladrilhos com ordem
x especificamente todo par x que vai se tornar degenerado é um dos
dois tipos x e x ou x e x onde x e x para algum arco x
primal ou dual do complexo de partida tal que x veja figura
podemos concluir também o seguinte uma vez que cada ladrilho tem x
lados ele pode ser colado consigo mesmo no máximo duas
vezes portanto podemos ter no máximo x pares de triângulos
degenerados por ladrilho formando x grupos de x triângulos e nenhuma
aresta da triangulação x é comum aos x grupos
a operação de limpeza consiste na eliminação dos x triângulos
indicados na figura e a identificação das arestas x e x esta limpeza
deve ser repetida para todo canto de ladrilho adjacente a dois lados
que foram colados entre si
note que se um ladrilho contem dois grupos de triângulos degenerados
as duas arestas x e x de um grupo não ocorrem no outro grupo portanto
o princípio da colagem de arestas aos pares é respeitado note também
que a limpeza não identifica novos pares de vértices que já não
estejam identificados portanto ela não introduz novos pares de
triângulos degenerados
assim a eliminação simultânea de todos os pares de triângulos
degenerados produz uma triangulação sem nenhum par de triângulos
degenerados portanto a eliminação dos triângulos degenerados pode
ser feita em paralelo com a colagem sempre que colamos dois lados
adjacentes x e x de um mesmo ladrilho eliminamos os x triângulos
degenerados e identificamos as arestas x e x
a figura ilustra este processo com a triangulação parcial que
resulta da colagem de um ladrilho de dimensão x figura a si
próprio especificamente da borda inferior com a borda esquerda
figura
note que em conseqüência da eliminação das arestas duplicadas que
surgem depois da colagem obtemos dois pares de triângulos degenerados
adjacentes ao vértice x figura a figura mostra o resultado da
eliminação destes x triângulos
para produzir a imagem final da triangulação x de um complexo celular
x nós usamos técnicas tradicionais de computação gráfica cada face
da x é desenhada como um triângulo plano as arestas da triangulação
que correspondem a pedaços de arestas do mapa original são
representadas por cilindros e os vértices entre essas arestas são
representados por esferas de mesmo raio as esferas internas que
representam os vértices internos ao ladrilho têm a finalidade de
proporcionar suavidade às articulações dos cilindros que representam
as arestas além disso os vértices extremos da diagonal de cada
ladrilho que representam vértices do complexo celular dado são
representados por uma esfera de raio maior que as demais
para diferenciarmos quais arestas da triangulação pertencem as arestas
primais e duais do complexo original dividimos cada ladrilho em x quadrantes
quartilhos e rotulamos os triângulos com números x como indicado na
figura a representação da aresta primal por definição
é o conjunto de arestas que separam x e x da mesma forma a aresta dual
pode ser representada pelo conjunto de arestas que separam x e x
esta abordagem funciona porque os triângulos que sobreviveram ao
processo de eliminação de triângulos degenerados seção são
suficientes para visualizar as arestas e faces do complexo
original especificamente segue do teorema a seguinte proposição
para qualquer ladrilhamento de ordem x depois do processo de limpeza
ainda temos para cada ladrilho
pelo menos quatro triângulos um em cada quartilho
pelo menos uma aresta de x na fronteira entre cada dois quartilhos
adjacentes
como já vimos nosso objetivo é resolver o seguinte problema dada
uma triangulação topológica x determinar uma configuração geométrica
para a mesma isto é as coordenadas de seus vértices x de
maneira que a superfície obtida esteja próxima do que definimos como
representação bonita
nossa intenção neste capítulo é definir funções numéricas da geometria
da superfície energias que medem as características indesejáveis da
mesma ou seja o quanto a superfície está distante de uma
representação que definimos como bonita
uma vez que cada ladrilho é modelado por uma rede de triângulos
planos a forma da superfície e portanto sua energia depende apenas
das coordenadas dos x vértices dos triângulos
definimos portanto uma configuração da superfície como sendo uma
tupla de x pontos x do x uma função energia é então uma função real
de x argumentos reais
para maior versatilidade nossa implementação permite especificar
individualmente se cada vértice é fixo ou variável um vértice
variável possui a propriedade de poder alterar suas coordenadas de uma
configuração geométrica para a outra a capacidade de manter certos
vértices fixos permite usar nossa ferramenta para projeto de juntas
suaves entre superfícies dadas filetes chanfros etc
dentre as funções energia que estudamos as que produziram melhores
resultados isoladamente ou em combinação foram as seguintes
energia de dobramento x mede os ângulos diedrais entre faces
adjacentes minimizar x tende a tornar a superfície mais plana e
distribuir uniformemente a curvatura entre todas as arestas
energia de excentricidade x mede a assimetria dos comprimentos e
direções das arestas incidentes em cada vértice minimizar x tende a
tornar a superfície mais plana e os triângulos vizinhos a cada vértice
mais uniformes
energia de ângulos x mede irregularidades nas direções das arestas
incidentes em cada vértice minimizar x tende a evitar pontos de
trançamento definidos mais adiante desdobrar a superfície e
igualar os ângulos entre as arestas adjacentes
energia de proximidade x mede a proximidade entre pares de
triângulos minimizar x tende a evitar a superposição de partes
não-adjacentes da superfície e fazer com que as intersecções da
superfície com si mesma sejam transversais em vez de rasantes
energia de espalhamento x mede a distância entre os vértices e a
origem do x minimizar x tende a limitar a extensão da superfície
desfavorecendo soluções com vértices excessivamente espalhados
energia de áreas de ladrilhos x mede a diferença entre a área de um
quartilho na superfície e sua área nominal uma constante minimizar
esta energia tende a deixar as arestas do complexo original x bem
espaçadas e manter a área total da superfície constante
de modo geral cada uma das energias acima atinge seu mínimo em
configurações degeneradas pouco interessantes por exemplo uma
configuração que minimiza a energia de proximidade x tem
todos os vértice infinitamente distantes uns dos outros a que
minimiza a energia de espalhamento x tem todos os vértices
na origem este problema pode ser enfrentado através
de duas técnicas tradicionais de otimização
uma maneira é restringir a minimização a um subconjunto adequado de
configurações por exemplo poderíamos considerar apenas
configurações normalizadas x tais que
soluções degeneradas também podem se evitadas fixando-se um número
suficiente de vértices da triangulação
outra maneira clássica de evitar soluções degeneradas é usar uma
função de penalidade que assume valores elevados nas configurações
degeneradas no nosso caso podemos usar as próprias energias como
função de penalidade cada uma das energias só penaliza um tipo de
defeito da superfície mas algumas destas energias têm efeitos opostos
entre si não existe nenhuma configuração que seja ótima para todas as
energias ao mesmo tempo
portanto é possível obter configurações interessantes minimizando uma
energia mista que consiste numa combinação linear de duas ou mais
energias assim por exemplo uma configuração que minimiza x com x
tem seus vértices a distâncias finitas e relativamente uniformes
este assunto será examinado mais a fundo na seção
no restante deste capítulo examinaremos mais detalhadamente as
principais funções de energia que testamos e seus efeitos sobre a
superfície final também abordaremos sem muitos detalhes outros
tipos de energias que estudamos mas não chegamos a usar
definimos a energia de dobramento de uma aresta x como sendo o
quadrado do ângulo diedral externo x entre as faces adjacentes a essa
aresta multiplicado pelo comprimento x da aresta a energia de
dobramento total x da configuração é a soma destas energias parciais
para todas as arestas da triangulação
intuitivamente podemos supor que cada aresta x é uma mola
bidimensional cuja posição de repouso acontece quando as faces
adjacentes a x formam um único plano o gradiente desta energia é a
resultante das forças exercidas por essas molas sobre as faces
adjacentes a cada uma das arestas da triangulação
o ângulo diedral x da aresta pode ser calculado pela fórmula onde x é
o vetor definido pela aresta x isto é x e x e x são os vetores
definidos pelas arestas adjacentes x e x
nossa implementação permite especificar separadamente para cada aresta
de x se a mesma se comporta como uma mola como descrito em ou se
ela se comporta como uma dobradiça sem mola
assim podemos usar nossa ferramenta para problemas em que a borda é
articulada para o caso em que as arestas possuem atributo de mola ou
engastada caso contrário
o custo elevado da função x necessária para obter o ângulo x a partir
do valor de x nos levou a substituir a mesma pela aproximação esta
aproximação dá resultados satisfatórios mesmo para ângulos grandes
pois x é uma função crescente de x para todo x entre x e x veja o
gráfico na figura
observe que a energia de dobramento apesar de definida em termos
puramente locais tem um efeito global a curvatura total da
superfície acaba sendo distribuída sobre todas as arestas de maneira
mais ou menos uniforme na minimização numérica observa-se um
processo de difusão em que a curvatura flui de regiões de relevo
acidentado picos depressões e dobras para regiões mais
planas este comportamento é uma característica comum a várias das
funções energia que veremos a seguir
a energia de excentricidade x mede o quanto cada vértice x esta longe
do baricentro do conjunto x de seus vizinhos considerados como tendo
a mesma massa
o gradiente desta energia é uma força que atrai cada vértice para o
baricentro de seus vizinhos com magnitude proporcional à distância
entre esses dois pontos
intuitivamente minimizar esta energia tende a aplainar a superfície
e uniformizar os comprimentos das arestas que saem de cada vértice a
superfície se comporta como uma rede cujas arestas são fios elásticos
com comprimento de repouso nulo
esta energia não pode ser usada sozinha em triangulações sem vértices
fixos pois seu único mínimo é uma configuração degenerada que tem
todos os vértices no mesmo ponto
qa energia de ângulos x é calculada comparando-se os ângulos
entre as x arestas que incidem num determinado vértice com
o ângulo ideal x
mais precisamente sejam x os vértices vizinhos a um vértice x dado
a direção normal à superfície no vértice x é por definição a do
vetor que é equivalente
obtida a normal x calculamos as projeções x dos vetores x sobre um
plano perpendicular a x e definimos x como sendo o ângulo entre os
vetores x e x a energia de ângulos do vértice x é então
a energia de ângulos da configuração é a soma de x sobre todos os
vértices x
intuitivamente podemos supor que a normal de cada vértice x é o eixo
de uma dobradiça com x asas planas separadas por molas que tendem
a igualar os ângulos entre as asas cada vizinho de x está restrito à
asa correspondente mas pode se deslocar livremente sobre a mesma o
gradiente da energia é a resultante das forças exercidas por essas
molas sobre os vértices da triangulação
a motivação para projetar as arestas sobre o plano tangente em vez de
medir os ângulos sobre a própria superfície é penalizar vértices de
trançamento que são vértices x cujos vizinhos projetados num plano
tangente perfazem mais de uma volta em torno de x ou nenhuma
volta tais vértices ocorrem quando a superfície contem
auto-intersecções por exemplo as representações da garrafa de klein
e do toro ilustradas na figura
a energia de proximidade x é calculada como se a superfície estivesse
coberta de cargas elétricas que se repelem entre si o valor de x é a
energia potencial desse sistema de cargas elétricas
o gradiente desta energia é a resultante das forças de repulsão
entre todas essas cargas minimizar x significa afastar os
triângulos uns dos outros o que tende a evitar a superposição de
partes distintas da superfície e fazer com que as intersecções da
superfície com si mesma sejam transversais em vez de rasantes
o ideal seria calcular x supondo que a carga está uniformemente
espalhada sobre a superfície infelizmente isso tornaria o cálculo
da energia muito complicado e dispendioso em vista disso decidimos
aproximar a distribuição uniforme por uma coleção de cargas discretas
posicionadas no baricentro de cada triângulo assim a energia
elétrica pode ser calculada pela fórmula onde x é a energia potencial
entre as duas cargas associadas aos triângulos x e x a aproximação
mais simples para este termo corresponderia a supor duas cargas
pontuais unitárias situadas nos baricentros desses triângulos ou seja
onde x é o baricentro do triângulo x entretanto esta definição
introduz um grande número de mínimos locais em que a superfície está
arbitrariamente trançada mas onde as cargas estão intercaladas
isto é cada superfície passa pelos buracos entre as cargas da outra
veja fig para destrançar essas configurações seria necessário
aproximar temporariamente algumas cargas aumentando a energia
elétrica
a fim de contornar este problema sem aumentar muito o custo
decidimos calcular esta energia supondo que a carga elétrica de cada
triângulo está espalhada no espaço de tal forma que a energia do par
é dada pela fórmula onde o parâmetro x mede o raio aproximado da nuvem
de carga do triângulo x
os parâmetros x devem ser grandes o bastante para que a união das
nuvens de carga elétrica cubra toda a superfície sem deixar buracos
nosso programa define x a partir dos vértices x x x do triângulo x
segundo a fórmula onde x é um parâmetro ajustável pelo usuário nos
nossos testes adotamos x
a motivação para cargas nebulosas pode ser compreendida
considerando-se o exemplo da figura na configuração esquematizada na
figura com duas superfícies trançadas a energia de proximidade é
localmente mínima neste caso usando cargas pontuais há poucas
esperanças que um método de otimização consiga destrançar às
superfícies para isso seria necessário transpor uma barreira de alta
energia a figura ilustra duas cargas nebulosas nos vértices x e
x note que dentro destas áreas a repulsão entre as duas superfícies
não cresce consideravelmente a medida que os outros vértices se
aproximam de x ou x isto é mesmo que um vértice se sobreponha à
outro a energia de proximidade não será infinita isto permite que
uma superfície atravesse a outra
a desvantagem deste modelo de cargas nebulosas tridimensionais é
que a repulsão entre dois triângulos próximos entre si é mais fraca do
que a esperada para cargas distribuídas na superfície dos mesmos e
varia mais lentamente em função da distância entre eles em
conseqüência a minimização da energia elétrica fica menos eficiente
na eliminação de intersecções e sobreposições da superfície
as figuras e representam o comportamento da energia elétrica de dois
ladrilhos respectivamente paralelos em função da distância cruzados
em função do ângulo cruzados em função da posição do cruzamento em
cada uma das figuras o gráfico mostra a variação de x para x
diferentes valores de x x x e x neste último note que
para cargas mais concentradas x a função energia tem vários mínimos
locais separados por barreiras altas de energia
uma alternativa para este modelo seria considerar cargas discretas
nebulosas centradas nos vértices em vez dos baricentros dos
triângulos entretanto a equação de euler implica que o número x de
triângulos é aproximadamente o dobro do número x de vértices
portanto ao usar os triângulos estamos distribuindo a carga mais
uniformemente sobre a superfície
a energia de espalhamento x é por definição a soma dos quadrados das
distâncias dos vértices à origem o gradiente desta energia é uma
força que atrai cada vértice para a origem proporcionalmente à
distância
a energia de espalhamento não pode ser usada sozinha pois seu único
mínimo é a configuração degenerada onde todo vértice está na origem
como já vimos ela é útil em combinação com outras energias
especialmente x nessas combinações ela age como uma função de
penalidade evitando que os vértices se afastem infinitamente uns dos
outros
para definir a energia de área de ladrilhos x dividimos cada ladrilho
do mapa original em quatro quartos de ladrilho quartilhos
pelas arestas primal e dual correspondentes como mostrado na figura
cada quartilho corresponde a uma parte bem definida da superfície que
consiste de todos os triângulos provenientes daquela parte do ladrilho
que sobreviveram à operação de limpeza veja seção
a energia x é então definida comparando-se a área x de cada quartilho
na configuração corrente com sua área nominal x uma constante
segundo a fórmula e somando-se esse termo para todos os quartilhos
a figura mostra o comportamento desta fórmula
em função da área x
note que x torna-se infinita sempre que qualquer das
áreas x tende a zero portanto ao incluir x na fórmula
da energia com qualquer peso positivo estamos garantindo que todo
quartilho tem área não-nula
o gradiente desta energia é uma espécie de pressão bidimensional
que tende a manter a área de cada quartilho igual a x o
comportamento intuitivo de cada quartilho não tem semelhança com
materiais físicos comuns ele resiste a mudança de área como um
tecido mas é totalmente indiferente a mudanças de forma
outras energias que consideramos mas que não deram resultados
satisfatórios são
energia de compressão de triângulos x que mede a discrepância entre a
área corrente x de cada triângulo de x e sua área nominal x uma
constante minimizar esta energia significa forçar que as áreas dos
triângulos se aproximem o máximo das respectivas áreas nominais
energia de desigualdade de áreas de triângulos x que mede a
discrepância entre as áreas de dois triângulos x x adjacentes a
cada aresta x minimizar x significa tornar as áreas de todos os
triângulos próximas entre si
energia de deformação de triângulos x mede a discrepância entre os
ângulos dos triângulos e seus ângulos nominais esta energia é
semelhante à energia de ângulos x exceto que os ângulos são medidos
entre as arestas em vez de entre suas projeções no plano tangente
energia elástica de arestas x calculada supondo-se que cada aresta é
um fio elástico que puxa ou empurra os vértices extremos com tensão
que depende da discrepância entre o comprimento corrente da aresta e
seu comprimento nominal x
estas energias tem um problema comum elas obrigam os ladrilhos a se
comportarem como retalhos de pano que podem ser dobrados mas resistem
a mudança de forma isto faz com que as juntas entre os ladrilhos
virem quinas e saliências da superfície
além disso as energias x e x permitem triângulos finos e compridos
desde que tenham a área especificada controlar apenas as áreas dos
triângulos não garante que as faces do complexo tenham formas
homogêneas para que isso seja verdade estas energias devem ser
usadas em conjunto com uma ou mais energias que penalizem a deformação
dos triângulos a energia de excentricidade seria uma boa opção de
restrição para esse caso
para usar estas funções energia eficazmente é desejável que elas não
dependam do número de triângulos usados em cada ladrilho mas apenas
da topologia e geometria da superfície
para formalizar esta idéia vamos introduzir o conceito de duplicação
de uma triangulação x trata-se de outra triangulação x que é obtida
de x dividindo-se cada aresta x em duas metades ligadas por um novo
vértice médio x e dividindo-se cada triângulo em x novos triângulos
por meio de novas arestas que ligam os vértices médios consecutivos na
sua fronteira veja a figura
note que se x foi obtida por ladrilhamento de um complexo celular com
ladrilhos de ordem x como descrito no capitulo x a duplicação de x
praticamente equivale a ladrilhar o mesmo complexo com ladrilhos de
ordem x note porém que a disposição dos triângulos no ladrilho é
ligeiramente diferente
suponha que x é uma configuração de x que corresponde a um mínimo
local de uma certa combinação de energias considere a seguinte
operação de refinamento geométrico x construa a duplicação x de x
x atribua a cada vértice médio x de x a media aritmética das
posições dos extremos de x e x partindo desta configuração
encontre uma configuração x de x que seja mínimo local da mesma função
energia
para que os resultados da minimização de energia sejam previsíveis e
controláveis é necessário que a forma das superfícies x e x sejam
semelhantes e mais ainda é desejável que as configurações obtidas de
x por refinamentos geométricos repetidos convirjam rapidamente para
uma configuração limite bem definida e próxima a x com uma energia
finita e não nula
não é nossa intenção determinar rigorosamente as condições matemáticas
que garantam esta convergência nos limitaremos a ajustar as
constantes que aparecem na definição de cada função energia de tal
maneira que seus valores não variem substancialmente quando efetuamos
um refinamento geométrico de uma configuração otimizada
para estimar os valores típicos de cada energia vamos supor uma
configuração de referência hipotética x cujos vértices estão próximos
a uma esfera de raio x e cujos triângulos são aproximadamente
eqüiláteros e de tamanho uniforme de modo que todos os ângulos
comprimentos áreas etc serão aproximadamente iguais vamos denotar
por x x x e x o número de triângulos arestas vértices e
quartilhos de x respectivamente
obviamente este modelo é uma aproximação muito grosseira das
configurações ótimas reais mesmo para complexos com poucas arestas e
topologia esférica portanto esta abordagem vai fornecer apenas o
comportamento assintótico das energias em função do raio aproximado x
e dos números x x x e x que é tudo o que queremos as constantes
de proporcionalidade vão depender da topologia do complexo
nas análises a seguir usaremos o fato que numa triangulação
de de uma esfera ou de qualquer superfície com topologia fixa
temos x e x
a energia de dobramento é a soma de x termos cada um dos quais é o
comprimento de uma aresta vezes o quadrado do ângulo diedral externo
correspondente
supondo-se que que os triângulos sejam aproximadamente iguais a área
média x de cada triângulo será aproximadamente x o comprimento médio
das arestas será então x
a distância entre os centros de dois triângulos será proporcional ao
comprimento médio das arestas ou seja x vista do centro da esfera
esta distância corresponde a um ângulo de x radianos supondo-se que
os triângulos sejam aproximadamente tangentes à esfera concluímos que
este é também o ângulo diedral médio x entre faces adjacentes ou
seja x
portanto esperamos que assim para tornar a energia de dobramento da
configuração ótima independente de x basta multiplicar a fórmula de x
pelo fator x
numa triangulação ótima espera-se que a energia excêntrica x seja
devida exclusivamente à curvatura da superfície isto é cada vértice
x está no ponto da superfície mais próximo do baricentro x de seus
vizinhos
na nossa configuração de referência já vimos que a distância média
entre o vértice x e seus vizinhos é x essa distância vista do centro
da esfera corresponde a um ângulo típico x portanto a distância
típica de x à superfície da esfera será x concluímos que para
manter x independente de x basta multiplicar a fórmula pelo fator
x
a fórmula energia x já é praticamente invariante sob refinamento
geométrico pois ela leva em conta as áreas dos quartilhos que são
pouco afetadas por essa operação
entretanto é conveniente acrescentar à formula de x um fator x
onde x é o número de quartilhos esta precaução torna x independente
do número de arestas do complexo original seu valor passará então a
medir consistentemente a variação média de área por quartilho
além disso é aconselhável definir a área ideal x de um quartilho como
sendo x onde x é uma constante esta escolha de x faz com que a
energia x seja nula quando a superfície tiver área total x com
retalhos de mesmo tamanho
supondo-se que a distância quadrática média de cada vértice à origem
seja x concluímos imediatamente portanto é conveniente acrescentar
à formula desta energia o fator de normalização x
na seção justificamos a fórmula da energia de proximidade x como
sendo uma aproximação da energia potencial de uma distribuição
contínua de cargas elétricas sobre a superfície da configuração
portanto o refinamento da triangulação deveria apenas tornar essa
aproximação mais exata ou seja o valor de x deveria ser
assintoticamente independente de x
entretanto a fórmula que usamos para x na seção supõe que cada
triângulo tem carga total unitária qualquer que seja seu tamanho
isso significa que a carga total espalhada sobre a superfície é
proporcional a x e portanto a energia potencial cresce
assintoticamente como x
concluímos que para tornar x invariante sobe refinamento é preciso
acrescentar à fórmula um fator x
a análise teórica do comportamento assintótico desta energia parece
ser bastante difícil entretanto testes empíricos nos levaram a
concluir que quando uma configuração ótima é refinada e re-otimizada
o valor desta energia cresce proporcionalmente ao número de triângulos
ou vértices isto é o valor médio de cada parcela o desvio médio
de cada ângulo relativo ao ângulo ideal não é alterado pelo
refinamento
portanto para manter esta energia invariante sob refinamento é
necessário acrescentar à fórmula o fator x
embora como vimos seja necessário o uso de uma energia mista não
existe uma única combinação fixa de energias que produz bons
resultados para qualquer complexo celular
a escolha da combinação mais adequada parece ser um problema muito
difícil no estado atual dos nossos estudos os pesos de cada energia
só podem ser determinados por tentativa e erro
uma solução parcial para este problema seria controlar interativamente
os pesos pense em um painel de controle onde você possa controlar a
dose com que cada energia irá influenciar no resultado final do
processo de otimização outra solução mais avançada seria utilizar
técnicas de aprendizagem automática para deduzir os pesos ótimos a
partir de uma coleção de exemplos de realizações bonitas
fornecidas pelo usuário deixaremos esses melhoramentos para
trabalhos futuros
para ilustrar a dificuldade da escolha adequada dos pesos vamos
considerar o caso de uma mistura simples das energias de dobramento x
e proximidade x
sozinha a energia de proximidade não leva em conta a suavidade da
superfície portanto a energia de proximidade deve ser usada sempre
em combinação com alguma outra energia que favoreça superfícies
suaves como a energia de curvatura ou a excêntrica mesmo assim
dependendo dos pesos com que as energias são combinadas pode ocorrer
o que denominamos de efeito abacaxi vértices deslocados
alternadamente para dentro e para fora da superfície média suave
veja a figura
para entender a origem deste problema considere uma triangulação
plana com apenas um vértice variável veja figura
os gráficos na figura mostram respectivamente as energias x x bem
como sua combinação x em função do parâmetro x da figura
note que em a segunda derivada x e em a segunda derivada x
portanto para uma energia x tem-se que se x há dois mínimos com x
se x há um único mínimo em x
se o mínimo ocorrer no ponto x a minimização de x sobre a superfície
toda resultará no que pode ser chamado de fenômeno abacaxi caso
contrário se o mínimo ocorre em x tem-se uma superfície suave sem
ondulações
neste capítulo descreveremos as várias técnicas de minimização de
energia que experimentamos no decorrer deste trabalho
vamos classificar os algoritmos de otimização usados por nós em dois
grupos x os genéricos e exatos e x os específicos e heurísticos
os algoritmos do primeiro grupo são genéricos porque encaram a
minimização da função energia como um problema genérico de otimização
não-linear dada uma função x de x em x encontrar um vetor x que
minimiza o valor de x isto é se aplicam a qualquer função não
dependendo da natureza da mesma além disso são exatos pois se
fossem rodados por tempo suficiente e em um ambiente ideal onde
não houvessem problemas de precisão convergiriam para um mínimo
local
os algoritmos do segundo grupo são específicos porque são
especializados para as nossas funções energias e são heurísticos pois
nem sempre convergem e se convergem não convergem necessariamente
para um mínimo local estes algoritmos aplicam repetidamente certas
operações de ajuste local que afetam apenas um vértice e seus
vizinhos cada um destes ajustes procura minimizar apenas um tipo de
energia sem se preocupar com os outros tipos e além disso é
geralmente baseado num modelo qualitativo da energia portanto o
ajuste pode aumentar a energia em vez de diminuí-la
a experiência mostra que os métodos heurísticos funcionam muito bem
no início da otimização quando a configuração ainda está muito
distante do mínimo desejado por isso a melhor estratégia é usar
algumas iterações das heurísticas para gerar a forma inicial
aproximada e a partir desta forma inicial continuar otimizando
usando algoritmos exatos até atingir um ótimo local
na verdade a configuração obtida aplicando apenas os métodos heurísticos
em geral já é visualmente muito boa
um mínimo local de uma função x é um ponto x de x tal que x para todo
x em uma vizinhança de x o ponto x é um mínimo global se x para todo
x em x
identificar um mínimo local é um problema clássico de análise
numérica para o qual existem muitos algoritmos confiáveis e uma vasta
teoria matemática infelizmente as funções energia que queremos
otimizar têm uma estrutura bastante complexa com um grande número de
mínimos locais separados por descontinuidades e barreiras de alta
energia os métodos de otimização genéricos e exatos geralmente param
no primeiro mínimo local encontrado portanto encontrar um mínimo
local não é suficiente precisamos encontrar um ponto com energia
baixa se não o mínimo global pelo menos um mínimo local com
energia comparável
este é um problema muito mais difícil de caráter principalmente
combinatório métodos gerais eficientes para este problema
recozimento simulado algoritmos genéticos redes neurais são
bastante recentes e portanto bastante imprevisíveis não existe ainda
nenhuma teoria que permita prever seu desempenho em problemas
complexos como o nosso na verdade é fácil provar que o problema
geral de otimização combinatória que esses métodos pretendem
resolver é np-completo ou pior portanto tudo o que se pode esperar
desses métodos é que eles sejam eficientes para as funções típicas
de uma certa aplicação
entretanto estes métodos gerais de otimização combinatória parecem
ser pouco aplicáveis ao nosso problema eles pressupõem uma
codificação discreta efetiva dos estados do problema combinatório
isto é os mínimos locais e que é impraticável devido à complexidade
das nossas funções energia além disso a experiência com estes
métodos indica que provavelmente eles seriam demasiados lentos para
nossas necessidades
em vista dessas dificuldades e incertezas decidimos não investir
tempo nestes métodos em seu lugar usamos um técnica trivial de
randomização que consiste em aplicar as técnicas de otimização
local a x configurações iniciais geradas aleatoriamente e
dentre as configurações resultantes devolver a que tem energia
mínima
os métodos de otimização local que serão abordados neste trabalho são
de um tipo bem conhecido em minimização irrestrita são os métodos de
descida ou métodos de minimização direcional
todos estes métodos têm o mesmo passo central a partir de uma
configuração corrente x eles escolhem uma direção x na qual a função
x provavelmente diminui e procuram encontrar um escalar x tal que x
seja menor que o mínimo encontrado até o momento os vários métodos
de otimização diferem entre si pela maneira de escolher x x e x
em nosso trabalho fizemos uso de quatro desses métodos minimização
coordenada a coordenada que denotaremos por coord descida pelo
gradiente grad o método do simplexo de nelder-mead simplex e o
método das direções principais de powell e brent praxis nas
próximas seções vamos descrevê-los em linhas gerais sem descer a
detalhes de implementação
neste método de otimização o ponto x é a configuração de menor
energia encontrada até o momento e as direções x são os próprios
eixos de coordenadas x x nessa ordem repetidas circularmente para
cada direção x o comprimento do passo x é determinado aplicando-se um
método de minimização unidimensional à função energia como por
exemplo o método de brent
ou seja a cada iteração o método coord ajusta apenas uma coordenada
de um vértice da triangulação ele modifica a primeira coordenada x
do primeiro vértice até encontrar um mínimo da função em seguida ele
varia a segunda coordenada x procurando um novo mínimo e o mesmo para
a coordenada x estes ajustes são aplicados a todos os vértices um
de cada vez circularmente
eventualmente à medida que a configuração se torna mais macia
estas otimizações unidimensionais ficam cada vez menos eficientes
pois passa a ser necessário mover vários vértices simultaneamente
para obter diminuições significativas da energia em geral para
funções do x se suas segundas derivadas são muito maiores
em algumas direções do que em outras e essas direções não coincidem
com os eixos das coordenadas os passos acima serão muito pequenos em
comparação com a distância entre x e o mínimo procurado
para atenuar este problema depois de cada x iterações do método
acima fazemos uma iteração extra usando a direção diagonal x a
experiência indica que este passo avança significativamente na direção
do mínimo pois de certa forma ele resume e extrapola a informação
sobre x que foi coletada pelos x passos anteriores
apesar de sua simplicidade o método coord mostrou-se bastante eficaz
para nosso problema como veremos na seção a razão é que para muitas
energias dobramento espalhamento excentricidade etc a energia
de uma configuração aleatória é dominada por termos que dependem da
posição de cada vértice em relação a seus vizinhos nesse caso a
otimização da energia para um único vértice causa uma grande
diminuição na energia total assim as otimizações unidimensionais do
método coord aplicadas no início proporcionam grandes diminuições da
energia a um custo relativamente pequeno
o gradiente de uma função x de x para x é o vetor o método de
descida pelo gradiente grad tenta seguir a trajetória x definida
pela equação diferencial partindo da configuração inicial x até
atingir um ponto onde x que com probabilidade x será um mínimo
local de x note que esta equação obriga a configuração a evoluir
sempre na direção de maior decrescimento da energia
mais precisamente o método grad segue a trajetória~ acima usando um
simples integrador de euler para equações diferenciais
ordinárias este método consiste em calcular cada nova configuração x
a partir da configuração anterior x pela fórmula o passo x é
escolhido automaticamente pelo integrador de modo a tentar manter o
erro de integração limitado
de modo geral algoritmos de otimização que usam o gradiente
convergem mais rapidamente do que algoritmos que usam apenas o valor
da função suas principais desvantagens são a sensitividade a
estrutura miscroscópica da função como por exemplo os
falsos mínimos locais criados por erros de arredondamento
e a necessidade de se calcular o gradiente da função x
à primeira vista o cálculo do gradiente de funções complexas como
as que usamos pode parecer excessivamente dispendioso entretanto
bauer e strassen mostraram que aplicando-se
sistematicamente a regra da cadeia a cada operação é possível
calcular o gradiente de qualquer função matemática a um custo bem
modesto apenas três ou quatro vezes o custo de calcular a própria
função com a técnica de bauer e strassen o custo de se calcular o
gradiente é quase sempre compensado pela aceleração da convergência
que pode ser obtida com o mesmo
o método do simplexo de nelder-mead que denotaremos pela sigla
simplex é um algoritmo clássico de otimização não-linear que não
exige o cálculo do gradiente a idéia deste método é calcular o valor
da função energia nos vértices de um simplexo x-dimensional isto é
em x pontos do x e caminhar com esse simplexo na direção
aproximada do mínimo movendo um vértice de cada vez
no algoritmo de nelder-mead o progresso do simplexo é feito através
de três operações básicas reflexão expansão e contração a figura
mostra estas três operações para o caso bi-dimensional
nesta figura x representa o vértice correspondente ao maior valor da
função objetivo os pontos x x x e x são calculados da seguinte
forma onde x x e x são parâmetros do método os valores sugeridos
pelos autores são x x x nos nossos testes entretanto obtivemos
melhores resultados com x x x o método parte de um simplexo
inicial executando a seqüência de passos abaixo até que atinja o
critério de parada estabelecido
as principais vantagens deste método são a facilidade de programação e a sua
aplicabilidade a funções bastante genéricas suas principais desvantagens
são a convergência relativamente lenta e a possibilidade do simplexo encolher
numa direção até ficar contido num hiperplano do x o que restringiria a
busca a esse hiperplano
na verdade na nossa implementação do método nelder-mead
modificamos o algoritmo de propósito de forma a permitir o uso de um
simplexo sub-dimensional cujo número de vértices x é menor que o
número de variáveis x
a motivação para esta mudança é diminuir o custo do algoritmo pois o
custo de um passo é proporcional ao produto x e o número de passos
necessários para atingir o mínimo com uma precisão fixa cresce
rapidamente com x mesmo os complexos mais simples produzem
triangulações contendo várias centenas de vértices o que significa
que a função energia tem milhares de parâmetros por exemplo no caso
de uma configuração com x vértices teríamos x variáveis o
simplexo completo teria x pontos e seu armazenamento exigiria uma
matriz de x elementos aproximadamente x megabytes de memória com
nosso algoritmo modificado poderíamos tratar esta configuração
usando por exemplo um simplexo sub-dimensional com apenas x pontos
reduzindo o tamanho da matriz para x elementos aproximadamente x
megabyte
naturalmente esta mudança restringe a busca do mínimo a um sub-espaço
do x que consiste das combinações afins dos x vértices do simplexo
inicial este sub-espaço quase que certamente não contém o mínimo
global da função energia entretanto quase todas as configurações do
espaço completo x tem energia alta para qualquer definição
interessante de suavidade as superfícies suaves são um
subconjunto muito pequeno de x portanto se as configurações
escolhidas para formar o simplexo inicial forem previamente
amaciadas nossa modificação estará de certa forma concentrando a
busca numa parte especialmente interessante do x na seção
veremos algumas técnicas que podem ser usada para esse amaciamento
do simplexo inicial
o método de otimização que designamos por praxis é baseado no
algoritmo das direções principais de powell posteriormente melhorado
por brent
o método original de powell trabalha com um conjunto de x
configurações x e x direções x inicialmente as direções x são os
vetores da base canônica e x é uma configuração inicial dada o
método parte de um ponto inicial x e repete a seqüência de passos
abaixo até que a função pare de decrescer
infelizmente há um problema com o método acima devido ao fato dele
descartar em cada estágio a direção x o conjunto de direções tende
a ficar linearmente dependente quando isto acontece a busca do
mínimo da função fica restrito a um subespaço do x a versão proposta
por brent que nós usamos resolve este problema mantendo os vetores x
ortogonais durante o processo todo este ajuste naturalmente aumenta
o custo de cada iteração mas os ganhos em robustez e velocidade de
convergência compensam este custo
nesta seção descrevemos os testes que efetuamos para comparar o
desempenho dos métodos descritos acima
a triangulação utilizada nestes testes que denominamos tetra foi
obtida a partir de um complexo celular com topologia de tetraedro
modelado com ladrilhos de ordem x a triangulação resultante veja a
figura tem x vértices x faces e x arestas
em todos os casos a função energia utilizada foi uma combinação das
energias x e x os testes foram realizados numa estação de trabalho
sun sparcstation xx
apesar dos livros texto recomendarem o método de descida pelo
gradiente como tendo convergência mais rápida no início de nossos
testes nós evitamos usá-lo pois acreditavamos que o cálculo do
gradiente das nossas funções energia seria muito complexo e demorado
e que os métodos sem gradiente teriam mais chances de ultrapassar as
numerosas barreiras entre os mínimos locais dessas funções
assim implementamos e testamos inicialmente apenas o método do
simplexo de nelder-mead simplex o método das direções principais de
powell e brent praxis e o método de minimização coordenada a
coordenada coord é possível que o comportamento do simplex seja
devido as simplificações que adotamos infelizmente não tivemos tempo
para investigar este item
as figuras e abaixo mostram a evolução da energia da melhor
configuração obtida por cada método em função do tempo de
processamento em segundos este tempo inclui tanto os cálculos da
função energia quanto o tempo gasto pelo próprio algoritmo de
otimização
na figura os três métodos foram aplicados a uma configuração inicial
aleatória da triangulação tetra onde cada coordenada era um número
aleatório independente uniformemente distribuído entre x e x na
figura os três métodos foram aplicados a uma configuração inicial
previamente amaciada pelos métodos heurísticos descritos na seção
como se pode notar nos dois testes o método coord progrediu muito
mais rapidamente que os outros dois este resultado foi bastante
inesperado na verdade nossa intenção ao implementar o método coord
era usá-lo apenas como ponto de referência nas comparações pois a
literatura dá a entender que ele é muito mais lento que os outros
dois
a explicação para este resultado paradoxal está nas peculiaridades da
nossa função objetivo todas as funções energia que usamos são somas
de um grande número de termos sendo que cada termo depende de apenas
alguns poucos vértices da configuração a rotina que calcula a
energia leva esse fato em conta e só recalcula um termo se os
vértices envolvidos mudaram de posição desde a chamada anterior
portanto no teste do método coord onde apenas um vértice muda de
cada vez cada cálculo da função energia era aproximadamente x vezes
mais rápido do que nos testes de praxis e simplex
para confirmar esta explicação mostramos nas figuras e os mesmos
dados das figuras e mas usando como abscissa o número de chamadas da
rotina de cálculo da energia em vez do tempo de processamento como
se pode ver sob este critério o método praxis é realmente melhor
como diz a literatura
note-se que os métodos praxis e simplex exigem memória proporcional a
x para uma função de x variáveis enquanto que o método coord usa
memória proporcional a x apenas no nosso caso onde x está na casa
dos milhares esta é uma consideração importante em parte por este
motivo e em parte pelos resultados acima desistimos de utilizar os
métodos praxis e simplex
numa segunda etapa de testes comparamos o desempenho do método de
descida pelo gradiente grad e minimização coordenada a coordenada
coord
da mesma forma que o teste anterior as figuras e mostram a evolução
da energia da melhor configuração obtida por cada método em função do
tempo de processamento em segundos ainda como no teste anterior o
gráfico da figura corresponde a uma configuração aleatória enquanto o
outro corresponde a uma configuração previamente amaciada
como se pode notar partindo de uma configuração aleatória o método
grad leva muito mais tempo para se aproximar de um mínimo local a
razão é que nas vizinhanças de uma configuração aleatória a função
possui muitos picos e vales que atrapalham o funcionamento do método
grad nessas condições a maior velocidade de cálculo da função
propiciada pelo método coord faz com que este seja o mais rápido dos
dois
já no segundo gráfico onde os métodos partem de uma configuração
amaciada com pouco mínimos locais a convergência do método grad é
mais rápida que a do coord como diz a literatura
esta análise é confirmada pelas duas figuras seguintes e que
mostram a evolução da energia em função do número de iterações
quando a comparação se faz por este critério vemos que o método grad
é o melhor mesmo partindo de uma configuração aleatória
em resumo no limite das nossas experiências acreditamos que o método
coord é o mais eficiente para configurações aleatórias enquanto que o
método grad é melhor para configurações suficientemente amaciadas
os métodos simplex e praxis parecem ser muito menos eficientes que
ambos
os métodos heurísticos são especializados para nosso problema em dois
sentidos em primeiro lugar eles pressupõem que os argumentos da
função energia são coordenadas dos vértices de uma triangulação e
utilizam as relações de vizinhança entre esses vértices em segundo
lugar cada um desses métodos tenta minimizar uma função energia
específica
todos os métodos heurísticos que usamos são iterativos e locais a
cada passo eles ajustam a posição de um vértice e possivelmente de
seus vizinhos imediatos uma aplicação completa de um método
heurístico consiste em efetuar este ajuste uma vez para cada vértice
da triangulação
estes métodos heurísticos são apenas aproximados eles geralmente
reduzem rapidamente a energia de configurações muito irregulares
mas têm efeito contrario em superfícies próximas do mínimo ou seja
a configuração obtida usando-se um método heurístico tem energia
baixa mas não se encontra num mínimo local portanto os métodos
heurísticos são úteis apenas no inicio da otimização para gerar um
ponto de partida para os métodos exatos além disso geralmente não
vale a pena aplicar mais do que algumas dezenas de iterações desses
métodos
a heurística de desdobramento consiste em ajustar um vértice x de cada
vez mantendo os demais fixos movendo-o para uma posição que
aproximadamente minimiza a energia de dobramento das arestas da
estrela de x a união dos triângulos incidentes a x
para tornar o cálculo praticável restringimos a nova posição do
vértice x à reta x onde x é o baricentro dos vértices vizinhos x e x
é a normal aproximada da superfície no vértice x calculada a partir
desses vizinhos pelas fórmulas da seção veja a figura
o parâmetro x é escolhido de modo que ao deslocar x para x estamos
minimizando aproximadamente os ângulos diedrais externos às arestas
x
mais exatamente para cada aresta x calculamos o ângulo diedral
externo x entre a face x e a face x oposta à aresta x vetores x e x
perpendiculares a esses dois triângulos são dados pelas fórmulas
a energia de dobramento da aresta x seria mínima nula se o ângulo
entre as faces x e x fosse zero portanto no que diz respeito a esta
aresta o valor ideal do parâmetro x deveria ser
veja a figura note que x aproxima bem x para valores pequenos de x
o valor escolhido para o parâmetro x é a média dos valores ideais x
apropriados para cada aresta ponderados pelos comprimentos das
arestas
esta heurística tende a distribuir a energia de dobramento de maneira
mais uniforme dentro da estrela de x ou seja a amaciar a
superfície na vizinhança de x
ao aplicar-se essa heurística para todos os vértices repetidas vezes
a energia de dobramento espalha-se por difusão em toda a superfície
assim a convergência é relativamente lenta intuitivamente por
analogia com processos físicos de difusão podemos prever que o número
de iterações necessárias para se obter uma configuração com qualidade
determinada aumenta com o quadrado do diâmetro x da triangulação no
sentido da teoria de grafos por sua vez para complexos típicos o
número de vértices tende a ser proporcional ao quadrado do diâmetro
portanto esperamos que o número de iterações seja proporcional ao
número de vértices x e o tempo total proporcional a x
a heurística de ângulos consiste em ajustar os ângulos entre as x
arestas que incidem num vértice x com o ângulo ideal x esta
heurística é aplicada a cada vértice x da triangulação mantendo-o
fixo e movendo os vértices vizinhos a x
as novas posições dos vértices vizinhos são obtidas de modo que a
projeção da sua respectiva aresta sobre o plano x que possui como
normal o vetor x seja a que aproximadamente reduz a energia de
ângulos o vetor x é a normal aproximada da superfície no vértice x
como na heurística de desdobramento segue abaixo a descrição
detalhada de como obter a nova posição dos vértices x
seja x o conjunto dos vértices vizinhos de x numerados a partir de um
vizinho x escolhido aleatoriamente
definimos eixos x e x sobre o plano x veja figura da seguinte forma
então para todo vizinho x calculamos as projeções x e x do vetor x
respectivamente sobre a normal x e sobre o plano x com esses dados
calculamos a projeção ideal x do mesmo vetor supondo que ela tem
o mesmo comprimento que x mas forma ângulo x com o eixo x a nova
posição de x é então onde x um parâmetro da heurística é um número
entre x e x nos nossos testes verificamos que um valor adequado
para x é x
um efeito colateral das heurísticas descritas acima é mudar
ligeiramente o tamanho da configuração portanto a aplicação repetida
de uma tal heurística sem maiores cuidados levaria no limite a uma
configuração degenerada com todos os vértices coincidentes ou no
infinito para corrigir este problema após cada ciclo completo de uma
heurística nós aplicamos uma etapa de normalização que amplia ou
reduz a configura cão de modo a manter seu tamanho e posição
constante
mais precisamente se os vértices são x a normalização consiste em
efetuar os cálculos abaixo
vale a pena observar que todas as heurísticas que usamos são puramente
euclidianas isto é operações de translação rotação ou mudança de
escala de x têm o mesmo efeito se aplicadas antes ou depois da
heurística portanto as etapas de normalização não alteram a forma da
configuração limite das heurísticas mas apenas mantêm seu tamanho