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.