PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO GRANDE DO SUL

FACULDADE DE INFORMÁTICA

CURSOS DE CIÊNCIAS DA COMPUTAÇÃO

E SISTEMAS DE INFORMAÇÃO

JÚLIA MARA COLLEONI COUTO

TIAGO MARCELINO

APLICAÇÃO DO ALGORITMO DE PRUSINKIEWICZ NA GERAÇÃO DE QUEBRA

DE SUPERFÍCIES EM JOGOS

Porto Alegre

2010

JÚLIA MARA COLLEONI COUTO

TIAGO MARCELINO

APLICAÇÃO DO ALGORITMO DE PRUSINKIEWICZ NA GERAÇÃO DE QUEBRA

DE SUPERFÍCIES EM JOGOS

Trabalho de conclusão de curso de graduação

apresentado à Faculdade de Informática da

Pontifícia Universidade Católica do Rio

Grande do Sul, como requisito parcial para

obtenção do grau de Bacharel em Sistemas

de Informação e Ciências da Computação.

Orientadora: Profª. Drª. Soraia Raupp Musse

Porto Alegre

2010

JÚLIA MARA COLLEONI COUTO

TIAGO MARCELINO

APLICAÇÃO DO ALGORITMO DE PRUSINKIEWICZ NA GERAÇÃO DE QUEBRA

DE SUPERFÍCIES EM JOGOS

Trabalho de conclusão de curso de graduação

apresentado à Faculdade de Informática da

Pontifícia Universidade Católica do Rio

Grande do Sul, como requisito parcial para

obtenção do grau de Bacharel em Sistemas

de Informação e Ciências da Computação.

Aprovada em _____ de ___________________ de ________.

BANCA EXAMINADORA:

____________________________________

Profª Drª Soraia Raupp Musse

____________________________________

Profª Drª Isabel Manssour

____________________________________

Prof Dr Luiz Gustavo Leão Fernandes

AGRADECIMENTOS

Á nossa orientadora, Profª. Drª. Soraia Raupp Musse, que não apenas nos

ofereceu um trabalho norteado, onde as diretrizes são pré-definidas, mas uma

verdadeira parceria na pesquisa, nos apontado um mundo de possibilidades e

apoiando nossas decisões. Agradecemos imensamente sua generosidade em

compartilhar conhecimentos, discutir idéias e soluções, e sua dedicação ao trabalho

de formação de seus alunos.

Aos nossos pais que nos incentivaram incondicionalmente, depositando em

nós a confiança necessária para enfrentar qualquer dificuldade, e dando-nos o

prazer de compartilhar com eles a alegria de nossas conquistas.

Nem tudo que se enfrenta pode ser

modificado, mas nada pode ser

modificado até que seja enfrentado.

Albert Einstein

RESUMO

Essa monografia apresenta uma adaptação à um algoritmo criado por

Przemyslaw Prusinkiewicz [Runions, 2005], para utilização na geração de crack

surface em jogos 2D. O algoritmo mencionado foi desenvolvido originalmente para

simular o crescimento vascular em folhas de plantas, onde, a partir de nodos são

geradas ramificações pela folha. Neste trabalho, esse algoritmo foi parametrizado

para gerar diferentes formas de cracks. Crack é o nome que se utiliza nessa

monografia para denominar o processo de quebra ou fissura de superfícies.

Esse trabalho propõe uma solução mais realista para o problema de geração

de imagens de quebras de superfícies em jogos 2D, visto que atualmente esse

processo é gerado a partir de texturas, ou seja, substituição da imagem original por

outra imagem onde o objeto aparece já com o resultado intermediário ou final do

crack.

Realizou-se um levantamento dos padrões de quebras de superfícies mais

comuns, bem como um estudo dos algoritmos que podem ser utilizados para

simulação de quebras de superfícies.

Também foi desenvolvido um simulador gráfico para geração de cracks

baseado no algoritmo original de Prusinkiewicz [Runions, 2005]. Os resultados

obtidos através dos experimentos apresentam a possibilidade da aplicação do

algoritmo para geração de quebra de superfícies em jogos, em tempo real.

Palavras-chave: Cracking, computação gráfica, jogos, algoritmos.

APPLYING PRUZINKIEWICZ’S ALGORITHM ON GENERATION OF CRACKING

SURFACES IN GAMES

ABSTRACT

This work presents a new application to an algorithm proposed by Przemyslaw

Prusinkiewicz [Runions, 2005], specifically for using in the generation of crack

surface in 2D games. The cited algorithm was originally developed to simulate the

growth in leaves of vascular plants, where nodes are distributed through the leaf,

generating branches. In this work, we intend to use this algorithm in order to

generate different types of cracks. Crack is the name used in this work to denote the

process of breaking or cracking surfaces.

This work proposes a more realistic solution to the problem of generating

images of broken surfaces in 2D games, because this process is currently applied

using textures.

We conducted a survey of patterns of surface cracks, and a study of

algorithms that can be used for simulation of cracking surfaces.

In addition, we developed a simulator for the generation of cracks based on

original model of Prusinkiewicz [Runions, 2005]. Results show the feasibility of

applying the algorithm to generate cracking surfaces in real-time games.

Keywords: Cracking, graphics computer, games, algorithms.

LISTA DE ILUSTRAÇÕES

FIGURA 1: Exemplo de cracking surface em jogos .................................................. 13

FIGURA 2: Quebra de vidro provocada por um tiro ................................................. 14

FIGURA 3: Padrão de desenvolvimento vascular de folhas ...................................... 16

FIGURA 4: Ilustração do funcionamento do algoritmo .............................................. 18

FIGURA 5: Cracks em um dragão de vidro ............................................................... 21

FIGURA 6 e 7: Alterações no parâmetro kill_distance .............................................. 24

FIGURA 8 e 9: Alterações no parâmetro vein_radius ............................................... 25

FIGURA 10 e 11: Alterações no parâmetro num_interaction .................................... 25

FIGURA 12 e 13: Alterações no parâmetro num_lines_grid e num_columns_grid ... 26

FIGURA 14 e 15: Alterações no parâmetro esp_vein ............................................... 27

FIGURA 16 e 17: Alterações no parâmetro line_growth ........................................... 27

FIGURA 18 e 19: Alterações no parâmetro drawnodes ............................................ 28

FIGURA 20 e 21: Alterações no parâmetro drawconnections ................................... 28

FIGURA 22 e 23: Alterações no parâmetro closepoints ............................................ 29

FIGURA 24 e 25: Alterações no parâmetro background ........................................... 29

FIGURA 26: Tarefas realizadas pelo simulador ........................................................ 31

FIGURA 27: Resultado visual de crack de barro ....................................................... 34

FIGURA 28: Resultado visual de crack de concreto ................................................. 34

FIGURA 29: Resultado visual de crack de vidro ....................................................... 35

FIGURAS 30 a 45: Comparações entre imagens de cracks em barro do simulador e

imagens reais .................................................................................................... 37 a 40

FIGURAS 46 a 53: Comparações entre imagens de cracks em vidro do simulador e

imagens reais .................................................................................................... 41 e 42

FIGURAS 54 a 59: Comparações entre imagens de cracks em concreto do simulador

e imagens reais ................................................................................................. 43 e 44

FIGURAS 60 a 69: Comparações entre as novas imagens de cracks em barro do

simulador e imagens reais................................................................................. 46 a 48

FIGURAS 70 a 75: Comparações entre as novas imagens de cracks em vidro do

simulador e imagens reais................................................................................. 49 e 50

FIGURAS 76 a 81: Comparações entre as novas imagens de cracks em concreto do

simulador e imagens reais................................................................................. 51 e 52

FIGURA 82: Média de avaliação ............................................................................... 53

LISTA DE TABELAS

TABELA 1: Performance do algoritmo para cada padrão de crack ....................... 34

SUMÁRIO

1 INTRODUÇÃO ........................................................................................... 12

1.1 OBJETIVOS ............................................................................................... 15

1.1.1 Objetivo Geral ........................................................................................... 15

1.1.2 Objetivo Específico .................................................................................. 15

2 FUNDAMENTAÇÃO TEÓRICA ................................................................. 16

2.1 MODELO DE PRZEMYSLAW PRUSINKIEVICZ ........................................ 16

2.1.1 Funcionamento do Modelo ...................................................................... 17

2.2 CRACKING SURFACE .............................................................................. 18

3 MODELO DE QUEBRA DE SUPERFÍCIES............................................... 23

3.1 SIMULADOR DE CRACKING .................................................................... 31

2.1.1 Principais Funções do Simulador ........................................................... 33

3.1 CUSTO COMPUTACIONAL ....................................................................... 33

4 RESULTADOS ........................................................................................... 36

4.1 SURVEY INICIAL ....................................................................................... 36

4.1.1 Cracks em barro ....................................................................................... 36

4.1.2 Cracks em Vidro ....................................................................................... 40

4.1.3 Cracks em Concreto ................................................................................. 42

4.2 SURVEY FINAL .......................................................................................... 43

4.2.1 Cracks em barro ....................................................................................... 44

4.2.2 Cracks em Vidro ....................................................................................... 46

4.2.3 Cracks em Concreto ................................................................................. 49

5 CONCLUSÃO ............................................................................................ 52

REFERÊNCIAS .......................................................................................... 53

12

1 INTRODUÇÃO

A busca pela representação do comportamento real dos elementos da

natureza em computação gráfica é um dos grandes desafios dos desenvolvedores

de jogos. Um dos comportamentos que apresenta dificuldade em prover

representação gráfica fiel é a quebra ou fissura de superfícies. Atualmente esse

processo é feito de maneira estática, a partir da utilização de uma imagem

desenhada (textura), e não gerada dinamicamente.

Nesse trabalho, objetiva-se estudar a viabilidade de adaptar o algoritmo

desenvolvido por Przemyslaw Prusinkiewicz [Runions, 2005] para utilizá-lo no

processo de cracking surface (quebra de superfícies), especificamente em jogos. O

foco é verificar se é possível utilizar esse algoritmo para esse fim, apresentando

algumas características importantes, como por exemplo, processamento em tempo

real e qualidade visual dos resultados.

Przemyslaw Prusinkiewicz1 é pesquisador da Universidade de Calgary, e o

foco de seu trabalho é a modelagem, simulação e visualização do desenvolvimento

das plantas. Ele procura interligar os conceitos de computação gráfica, teoria da

linguagem formal e linguagens de programação com Biologia, Matemática e Física.

A finalidade de seus algoritmos é aplicar conceitos e métodos da Ciência da

Computação para obter uma melhor compreensão do surgimento de formas e

padrões na natureza. Prusinkiewicz recebeu o SIGGRAPH 1997 - Computer

Graphics Achievement Award - por seu trabalho. Seus algoritmos biologicamente

motivados já foram adaptados para outros fins, como simulação de comportamento

de multidões [Rodrigues, 2009], e agora se pretende utilizá-lo para simulação de

cracking surface em jogos.

Cracking surface é o nome utilizado nesse trabalho para designar o processo

computacional de quebra ou fissuras em superfícies. Crack é uma fissura

sistemática na conexão entre os materiais que formam determinado objeto. Essa

fissura forma uma linha contínua. Sua forma varia dependendo do material, da forma

geométrica e de outras variáveis externas. Um crack ocorre quando as tensões

internas do material são maiores que a resistência do mesmo. Ocorre a primeira

1 Curriculum Vitae disponível em http://pages.cpsc.ucalgary.ca/~pwp. Acesso em 25

de junho de 2010.

13

fissura no material devido à tensão, então ocorre uma fissura vizinha, e a próxima, e

isso ocorre num efeito dominó [Gobron, 2000].

Atualmente, nos jogos para computadores, onde há imagens de tiros ou

guerras, há uma deficiência gráfica no que tange as respostas das superfícies

atingidas. Nessas situações, observa-se que o usual é que, um momento após a

superfície ser atingida, a imagem seja substituída por uma textura, como um buraco

por exemplo, ou que a superfície simplesmente desapareça. Observa-se esse

comportamento em jogos como Final Fight Guy, da CAPCOM2, conforme ilustrado

na Figura 1, e no jogo Lethal Inforces, da KONAMI3, conforme Figura 2.

Figura 1. Exemplo de cracking surface em jogos, onde 1 segundo após o

vidro ser atingido por um golpe, a imagem é substituída por uma textura igual

à do vidro da esquerda (imagens extraídas do jogo Final Fight Guy).

2Site oficial http://www.capcom.com. Acesso em 25 de junho de 2010.

3Site oficial http://konami.com. Acesso em 25 de junho de 2010.

14

Figura 2. Quebra de vidro provocado por um tiro (magem extraída do

jogo Lethal Inforces – KONAMI).

Em pesquisas baseadas na leitura de alguns artigos, verifica-se que os

algoritmos desenvolvidos até agora, para resolver esse problema, ainda apresentam

desafios a serem considerados. Alguns dos trabalhos citados nessa monografia

podem simular a quebra de uma superfície, desencadeada por alguma ação, mas

não o fazem em tempo real, e isso é essencial para que sua implementação em

jogos seja viável. É importante citar que num jogo várias outras ações estão

ocorrendo, impactando o custo computacional.

A simulação de cracking, criando a partir dele peças pequenas e interligadas,

dando então mais credibilidade e realismo às cenas, é a principal motivação desse

trabalho. Criar esses fragmentos de maneira realista e em tempo real é desafiador,

dada a complexidade do padrão dos cracks.

Assim, a customização do algoritmo de Prusinkiewicz [Runions, 2005] é a

hipótese adotada nesse trabalho para tentar resolver parte dos problemas.

15

1.1 OBJETIVOS

Listados nessa seção encontram-se os objetivos geral e específicos desta monografia.

1.1.1 Objetivo Geral

O objetivo central deste trabalho é aplicar o algoritmo desenvolvido pelo Dr.

Przemyslaw Prusinkiewicz [Runions, 2005] para utilização em quebra de superfícies,

para jogos.

1.1.2 Objetivos Específicos

Os Objetivos Específicos deste trabalho são:

a) Estudar a lógica e implementação do algoritmo desenvolvido em

[Runions, 2005], bem como outras pesquisas relacionadas à cracking

surface.

b) Propor e desenvolver uma adaptação ao modelo original [Runions,

2005] que possa ser utilizada em quebra de superfícies em jogos.

c) Pesquisar em jogos de computadores imagens que possam ser úteis

contendo resultados de quebra de superfícies, objetivando comparar

os resultados.

d) Avaliação do algoritmo desenvolvido, em relação aos seguintes

parâmetros: tempo computacional e qualidade do aspecto visual.

e) Descrever os modelos e resultados em um trabalho escrito de

pesquisa.

16

2 FUNDAMENTAÇÃO TEÓRICA

Nesse capítulo apresenta-se o modelo original que é utilizado no

desenvolvimento do projeto proposto, bem como uma introdução a alguns trabalhos

relacionados à cracking.

2.1 Modelo de Przemyslaw Prusinkiewicz

No artigo Modeling and visualization of leaf venation patterns [Runions, 2005]

é apresentada uma classe de algoritmos biologicamente motivados para a geração

de padrões de formação vascular das folhas. Sua intenção é a constituição de

imagens realistas que mostrem o processo de desenvolvimento de veias nas folhas

das plantas, objetivando replicar seu padrão visual. Para tanto, foi desenvolvida uma

ampla pesquisa morfológica nas folhas mais comuns encontradas na natureza.

Dessa maneira, encontraram os padrões de formação vascular de folhas que

embasaram o desenvolvimento de seus algoritmos. Esses algoritmos servirão de

base para a implementação do projeto aqui proposto.

“O algoritmo é baseado na hipótese biologicamente plausìvel de que a

vascularização resulta de uma interpolação entre o crescimento da folha, colocação

dos hormônios de auxina e desenvolvimento das veias” [Runions, 2005]. Cabe

esclarecer que a auxina é um hormônio das plantas que promove o crescimento de

células em seus tecidos.

Um exemplo inspirador para o desenvolvimento desse trabalho é apresentado

na Figura 3, retirada de [Runions, 2005], que ilustra as veias secundárias e terciárias

formando um padrão reticulado irregular.

Figura 3. Padrão de desenvolvimento vascular de folhas [Runions, 2005]. f, g

e h mostram o impacto visual causado pelo número de auxinas distribuídas

nas folhas em cada passo – quanto maior o número, maior a vascularização.

17

Esses padrões assemelham-se com o que se pretende reproduzir com o

simulador desenvolvido, sendo uma das diferenças o fato de que em uma quebra de

superfìcie, como o vidro, há um ponto central de onde saem as „veias‟ por todos os

lados. Já nas folhas, o crescimento sai do ponto de ligação da folha com o pecíolo

indo a uma direção determinada.

2.1.1 Funcionamento do modelo

A lógica do modelo original é a seguinte: as auxinas são distribuídas pela

folha, e a vascularização ocorre de maneira que as nervuras/veias tendem a se

aproximar desse hormônio. Define-se um ponto inicial de onde se origina a

nervura/veia principal, e distribui-se um determinado número de auxinas na folha. A

partir de então, o algoritmo seleciona as nervuras mais próximas de cada auxina e

calcula vetores direção que indicam o crescimento das nervuras. As auxinas são

eliminadas assim que uma veia chega a uma distância determinada, chamada kill

distance. Quando isso ocorre, inicia-se o processo de criação de auxinas nos pontos

mais distantes da folha, para assim reiniciar o processo de crescimento vascular e

subdivisão dos vasos.

Esse processo é ilustrado na Figura 4: no estado inicial o sistema vascular da

folha, nesse exemplo, é constituído por três nodos (círculos pretos com centros

brancos) e quatro auxinas (círculos vermelhos) (a). Cada auxina é associada ao

nodo que está mais próximo a ela (b, linhas vermelhas), o que estabelece o conjunto

de auxinas que influencia cada nó. São encontrados os vetores direção de cada

nodo (c, setas pretas). Esses vetores são adicionados e sua soma normalizada

novamente (d, setas violetas), fornecendo a base para encontrar os nodos de novo

(d, círculos violeta). Os novos nodos são incorporados ao sistema vascular (e). As

distâncias entre as auxinas e os nodos são verificadas de maneira a eliminar as

muito próximas (f, g). A folha cresce (h); neste exemplo assume-se um crescimento

marginal, por isso as auxinas existentes e os nós de veia não são movidos. Novas

auxinas são colocadas aleatoriamente no interior da folha crescida (i). Auxinas muito

próximas das outras são eliminadas (j) e os nodos próximos a essas auxinas são

identificados (k). Este é o início da próxima iteração da execução do algoritmo, com

estágios (j) e (k), correspondentes aos estádios (a) e (b) da iteração anterior.

18

Figura 4. Ilustração do funcionamento do algoritmo [Runions, 2005].

Para utilização em cracking, ocorrem algumas diferenças. A principal é que o

campo onde é gerado o cracking tem um tamanho fixo, não ocorrendo o crescimento

durante o processo de vascularização como ocorre com as folhas. Outra diferença

está no fato de que serão geradas várias ramificações em direções diversas, e o tipo

de ramificação poderá ser parametrizado, podendo ocorrer cruzamento entre as

linhas secundárias. De qualquer forma, é importante salientar que as definições

sobre a adaptação do modelo original em crack serão feitas durante o

desenvolvimento desse trabalho, especificamente no capítulo 3.

2.2 Cracking Surface

Existem diversos trabalhos na literatura versando sobre cracking surfaces,

sendo alguns deles citados nessa seção.

No artigo de Gobron [Gobron, 2000] são apresentados algoritmos onde a

propagação de cracks é feita automaticamente, usando um método que eles

denominam “fìsico-intuitivo”. Fìsico porque do ponto de vista de um cientista da

computação o modelo pode aparecer bastante teórico, mas o modelo esta longe do

ponto de vista realístico de um físico, por isso é intuitivo. Apresentam-se aqui as

principais idéias desse trabalho.

Segundo os autores, uma das dificuldades é representar o stress que gera os

cracks, visto que ele pode ir a qualquer direção, com intensidades diferentes. Stress

é uma tensão multidirecional nas células formadoras dos materiais, e quando o

19

stress interno do material é maior que a resistência desse material, ocorrem fissuras

e podem ocorrer cracks.

Há uma função recursiva entre stress e crack. Stress gera crack e estes por

sua vez modificam o stress, e o entendimento dessa relação é a chave para a

geração e simulação de qualquer tipo de cracks em qualquer material. Módulos de

fissuras são formados por células instáveis (células que contém uma intensidade de

stress mais forte que a resistência do material). Esses módulos têm direção

determinada, e originam as fissuras.

Determinar a direção inicial do crack não é trivial, então assume-se que ele

sempre inicia com pelo menos duas direções, e quatro padrões de crack são

definidos abaixo [Gobron, 2000]:

“I” é o mais comum, consiste de dois módulos de fissuras propagados em

direções opostas.

“T” são três módulos de fissuras, dois similares ao padrão I e outro ortogonal

a esses.

“Y” também três módulos de fissuras, mas o da direção inicial forma ângulos

de aproximadamente 120°.

“X” é extremamente raro, e consiste de quatro módulos de fissuras orientados

de maneira que formam ângulos de 90°.

Baseados nessas idéias, Gobron e Chiba conseguiram simular imagens

realistas de cracking em materiais diversos, como concreto, cerâmica, barro e vidro.

No artigo [Smith, 2003], é utilizada para a simulação de cracks a linguagem

de programação vv, que é uma extensão de C++. Com esse paradigma de

modelagem é possível representar expressões algébricas que acarretam em

movimentos entre as malhas de polígonos, que formarão os cracks. Segundo os

autores, esse paradigma de modelagem simplifica a implementação de algoritmos

individuais, tratando-os como programas de modelagem para múltiplos propósitos. É

utilizada para a representação gráfica de malhas de polígonos a álgebra vertex-

vertex, que é uma classe de sistemas rotatórios vertex-vertex com uma série de

operações definidas nela, utilizando notação matemática. Utilizam informações como

forma geométrica, topologia e coordenação na seqüência das operações como

parâmetros para a reprodução de cracks. A relação de vizinhança entre os

elementos de uma malha de polígonos e as modificações locais em objetos

estruturados são a essência do desenvolvimento proposto em [Smith, 2003]. Malhas

20

de polígonos são coleções de vértices, nodos reunidos por pares de vértices e

polígonos feitos por seqüências de nodos e vértices. São apresentados alguns

algoritmos de subdivisão que podem ser representados utilizando o modelo de

desenvolvimento proposto por eles. Apresentam algoritmos de inserção de vértices,

de subdivisão de poliedros, o esquema de subdivisão que utiliza loops, o algoritmo

borboleta e o algoritmo de subdivisão . Esses algoritmos são explicados de

maneira mais completa em [Smith, 2006].

O artigo de [Martinet, 2004] apresenta uma abordagem procedural para a

geração de fragmentos e fissuras em materiais como vidro, metal e pedra. Essa

abordagem utiliza a passagem de parâmetros possibilitando a geração de diversos

tipos de fissuras. Seu método também permite controlar as regiões em que as

fissuras se propagam e a forma que os fragmentos podem ter. Seu método utiliza a

Modelagem de Árvore Híbrida, que combina superfícies implícitas como um

esqueleto e malhas de triângulos. Suas fissuras e fragmentos são definidos usando

operações booleanas entre o modelo original e volumes talhados ou máscaras de

fissuras.

O procedimento é realizado em três passos: no primeiro é mapeado o padrão

de fissura em cima do modelo de entrada para gerar um esqueleto. O padrão de

fissura é uma imagem 2D feita em um editor específico. Essa imagem é um gráfico

que define sua geometria e características de ramificação. Os nodos do gráfico

possuem informações sobre a largura e profundidade da fissura no vértice

correspondente.

No artigo Generating Surface Crack Patterns [Iben, 2006] são apresentados

alguns métodos de geração de padrões de quebra de superfícies como lama,

cerâmica e vidros, onde o usuário pode controlar as características e aparência da

quebra, manipulando alguns parâmetros pré-estabelecidos. Dessa maneira, é

possível gerar diferentes padrões muito próximos da realidade, se comparados com

imagens do mundo real. Segundo os autores, a quebra de superfícies depende do

material e de fatores externos. A quebra é simulada com a triangulação na superfície

dos objetos.

Apesar dessa implementação ser eficaz em reproduzir quebra de superfícies

com imagens realistas, ela ainda não é eficiente para utilização em tempo real, visto

que para simular a quebra de vidro do dragão representado na Figura 5 por exemplo

21

foram necessárias 2.7 horas de processamento computacional. Nesse caso, o

tempo computacional despendido seria inviável para aplicação em jogos.

Figura 5. Cracks em um dragão de vidro [Iben, 2006]

No artigo de [Shen, 2007], os autores enfrentaram o desafio de representar de

maneira realista os movimentos de fluidos, como o mar, uma pia com água, geléia

caindo sobre um pão, etc. Os resultados podem ser vistos no filme de animação

longa metragem Ratatouille4, da Disney em parceria com a Pixar. Na simulação de

movimento de partículas, como um fluido, o número de partículas é pequeno demais

para dar a aparência de uma superfície contínua. Para resolver isso, foi

desenvolvida uma técnica para simular de maneira eficiente temporal e

espacialmente, superfícies de partículas coerentes, com uma parametrização que

permite visualizar os detalhes de textura, que são posteriormente adicionadas na

composição. Foram construídas funções implícitas que definem os campos de

distância assinados para o fluido de superfícies. Para um ponto de avaliação, a

técnica faz consultas de um conjunto de partículas em uma determinada região de

apoio, em seguida, cria uma partícula de referência com uma posição média

ponderada e raio. A distância entre o ponto de avaliação e o ponto mais próximo da

partícula de referência é atribuída como o valor da função implícita. Usando uma

estrutura de dados hierárquica, por exemplo, uma árvore KD [de Berg, 2008], o

tempo computacional do modelo pode ser significativamente melhorado. Esta função

implícita é então processada por um procedimento de contorno, tais como marching

4 Site oficial http://disneydvd.disney.go.com/ratatouille.html/. Acesso em 25 de junho de 2010.

22

cubes [Lorensen, 1987] que extrai o contorno em uma malha de triângulos. Quando

essa técnica foi aplicada a cada frame em uma simulação de movimento de

partículas, foram extraídas uma seqüência de superfícies para animação de fluidos.

Para criar detalhes de superfícies similares aos que ocorrem na natureza, são

utilizados alguns parâmetros que influenciam na aparência das malhas formadoras

dos objetos.

Todos os artigos citados mostram pesquisas atuais no campo de quebras de

superfícies, e alguns deles contribuíram de alguma maneira para a adaptação do

modelo de [Runions, 2005] no desenvolvimento desse trabalho.

23

3 MODELO DE QUEBRA DE SUPERFÍCIES

O modelo desenvolvido nesse trabalho apresenta algumas modificações em

relação ao modelo original proposto por Prusinkiewicz [Runions, 2005]. A principal

alteração é que no modelo original é utilizado, no cálculo do posicionamento das

auxinas, uma adaptação do algoritmo denominado dart-throwing (lançamento do

dardo) [Cook 1986; Mitchell 1987]. Neste algoritmo, há um gerador aleatório de

amostras e um validador, de forma que os pontos são gerados randomicamente e

dispostos de maneira uniforme sobre a área a ser preenchida. Quando a distância

de um ponto em relação aos demais na área for menor do que um ou mais limites

predefinidos, esse ponto é rejeitado. Satisfeitas as restrições, o ponto é adicionado à

área e o processo continua. Este processo é repetido até que novos pontos não

possam ser adicionados à área, conforme adaptado por [Runions, 2005] para “lançar

dardos” a cada iteração.

No modelo original, para controlar a regularidade do padrão de nervuras, o

usuário define o número de dardos por unidade de área da folha, a cada passo do

algoritmo. O problema é que esse algoritmo é computacionalmente caro, visto que

sua intenção é simular padrões bem próximos da realidade. Por esse motivo, o

algoritmo dart-throwing foi susbtituido por uma estrutura similar a uma malha, de

modo que a área de desenho é dividida em linhas verticais e horizontais e as

auxinas são colocadas na intersecção dessas linhas, ainda de maneira aleatória e

respeitando uma quantidade máxima pré-definida de auxinas. Dessa maneira a

performance aumentou significativamente no processo de criação de auxinas,

conforme mostrado no capítulo 3.2 de custo computacional.

A base para o algoritmo desenvolvido para este trabalho é apresentada em

[Runions, 2005]. O modelo original gera imagens que simulam o crescimento

vascular em folhas de plantas. A partir de um ponto central, chamado de VeinNode,

tem início o crescimento do crack para todos os lados a partir da orientação do

crescimento dos VeinNodes atraídos pelos pontos chamados de auxinas. As

auxinas são espalhadas dentro de uma área quadrada e limitada. Para a geração de

padrões de crack diferentes foram definidos parâmetros que alteram o

comportamento de crescimento e ligação dos nodos.

Os seguintes dados são entradas do modelo:

24

KILL_DISTANCE: Distância mínima entre um VeinNode e uma

auxina para que a auxina seja morta. Quanto menor o seu valor mais

ramificações existirão no modelo, porque as auxinas morrerão mais

tarde; quanto maior esse parâmetro, menos ramificações serão

geradas, conforme ilustrado nas Figuras 6 e 7. Esse parâmetro faz

parte do algoritmo original. Na Figura 6 (à esquerda), o valor de

kill_distance é 0.01, na Figura 7 é 0.1. As auxinas são mostradas como

pontos azuis. Outros parâmetros utilizados na formação dessas figuras:

EspVein = 0.2, Raio VeinNode = 0.9, Número de Iterações = 100,

Número de linhas e número de colunas = 7.

Figuras 6 e 7. Alterações no parâmetro kill_distance

VEIN_RADIUS ou Raio Vein Node: é o raio ao redor da auxina no qual

ela pode afetar os VeinNodes que estão ao seu alcance, a fim de

escolher o mais próximo e influenciar seu crescimento. Esse parâmetro

faz parte do algoritmo original. Quanto menor o valor desse parâmetro,

as imagens apresentam curvas mais suaves, conforme ilustrado na

Figura 8, que foi gerada com vein_radius = 0.5. Já na Figura 9, utiliza-

se vein_radius = 20, formando linhas mais retas. Outros parâmetros

utilizados: EspVein = 0.2, Número de Iterações = 100, Número de

linhas e número de colunas = 20, kill distance = 0.1.

25

Figuras 8 e 9. Alterações no parâmetro vein_radius

NUM_INTERACTION: esse parâmetro indica quantas vezes será

executado o algoritmo principal para criar as ramificações. No algoritmo

original a parada do crescimento se dá pelo término das auxinas

existentes. Na Figura 10, foi atribuído o valor de 100 a esse

parâmetro, dessa maneira gerando mais ramificações. Na figura 11,

sendo atribuído o valor de 10, o crack gerado não tem muitas

ramificações. Outros parâmetros utilizados na formação dessas figuras:

EspVein = 0.2, Raio VeinNode = 0.9, Kill distance = 0.08, Número de

linhas e número de colunas = 20.

Figuras 10 e 11. Alterações no parâmetro num_interaction

NUM_LINES_GRID e NUM_COLUMNS_GRID: esses parâmetros

indicam quantas linhas e colunas terão na área de crescimento (grid).

A área de crescimento é dividida em linhas e colunas, nas quais a

intersecção das mesmas é o ponto de referência para a criação das

auxinas. Esses parâmetros não existem no algoritmo original de

Prusinkiewicz [Runions, 2005], pois o posicionamento das auxinas se

dá pela utilização do algoritmo de lançamento de dardos(Dart

Throwing). A utilização de linhas e colunas melhorou a performance.

26

Quanto maiores os valores de linhas e colunas mais auxinas serão

criadas na área de crescimento do crack, mas isso gera um aumento

no custo computacional: a Figura 12 levou 0,14 segundos para formar-

se, enquanto a Figura 13 levou 11,439 segundos. Isso é ilustrado na

Figura 12, onde foi utilizado o valor número de linhas e colunas igual a

7, e Figura 13, onde foi atribuído o valor 40. Outros parâmetros

utilizados na formação dessas figuras: EspVein = 0.2, Raio VeinNode =

0.9, Número de Iterações = 100 e Kill distance = 0.08

Figuras 12 e 13. Alterações nos parâmetros num_lines grid e

num_columns_grid

ESPVEIN: define um valor que será aplicado à distância de

um VeinNode (ponto geradono grid) em relação ao que deu origem a

ele. Dependendo do valor atribuído a esse parâmetro, poderão ser

criados VeinNodes muito próximos ou muito distantes, quanto maior

este valor, mais longe será criado o VeinNode. Quando esse parâmetro

recebe um valor pequeno cria pontos mais próximos uns dos outros,

assim como valores altos criam pontos mais distantes. Esse parâmetro

é bastante útil na geração de cracks em barro. Na Figura 14, utiliza-se

espvein = 0.1, enquanto na Figura 15 o valor atribuído a esse

parâmetro é igual a 4.0. Esse parâmetro também causa impacto no

custo computacional, visto que a Figura 14 leva 8,164 segundos para

ser gerada, enquanto a Figura 16 leva 0,198 segundos. Outros

parâmetros utilizados na formação dessas figuras: Raio VeinNode =

0.9, Número de Iterações = 100, Kill distance = 0.08 e Número de

linhas e número de colunas = 20.

27

Figuras 14 e 15. Alterações nos parâmetros esp_vein

LINEGROWTH: é o parâmetro da taxa de crescimento da espessura

das ramificações pai. Cada vez que uma linha se ramifica para linhas

filho, a linha pai é engrossada, recebendo o valor de sua espessura

mais a taxa de crescimento multiplicada pelo número de filhos. Esse

parâmetro é utilizado na Figura 17, onde foi atribuído o valor de 0.5, e

na Figura 16 foi atribuído o valor zero. Para a geração dessas figuras,

foi desmarcado o parâmetro drawnodes, que desenha as auxinas, para

uma melhor visualização do resultado. Outros parâmetros utilizados na

formação dessas figuras: EspVein = 0.2, Raio VeinNode = 0.9, Número

de Iterações = 100, Kill distance = 0.08 e Número de linhas e número

de colunas = 20.

Figuras 16 e 17. Alterações nos parâmetros linegrowth

DRAWNODES: este parâmetro foi criado para que possa ser

visualizado onde estão as auxinas criadas, e caso ele seja marcado na

tela do gerenciador (Desenhar Pontos) ele desenha os pontos

(auxinas) em azul antes de gerar os cracks. Os parâmetros utilizados

28

na formação dessas figuras são: EspVein = 0.2, Raio VeinNode = 0.9,

Número de Iterações = 100, Kill distance = 0.08 e Número de linhas e

número de colunas = 20. Na Figura 18 esse parâmetro, que é um

booleano, recebeu valor falso, enquanto na figura 19 foi marcado como

verdadeiro.

Figuras 18 e 19. Alterações nos parâmetros drawnodes

DRAWCONNECTIONS: este parâmetro é utilizado para

simular cracks de vidro, ligando os pontos de maneira semelhante a

uma circunferência crescente. Ele liga novos VeinNodes a cada

iteração do algoritmo. Os parâmetros utilizados na formação dessas

figuras são: EspVein = 0.2, Raio VeinNode = 100, Número de Iterações

= 80, Kill distance = 0.02 e Número de linhas e número de colunas =

20. Na Figura 20, o parâmetro drawconnections, que é do tipo

booleano, teve atribuído valor falso, enquanto na figura 21 foi marcado

como verdadeiro.

Figuras 20 e 21. Alterações nos parâmetros drawconnections

29

CLOSEPOINTS: Forma “ilhas” aleatórias entre os cracks. Para tanto,

ele liga novos VeinNodes à um VeinNode mais próximo. Os

parâmetros utilizados na formação das Figuras 22 e 23 são: EspVein =

0.2, Raio VeinNode = 100, Número de Iterações = 80, Kill distance =

0.02 e Número de linhas e número de colunas = 20. Na Figura 20, o

parâmetro closepoints, que é do tipo booleano, teve atribuído valor

falso, enquanto na figura 21 foi marcado como verdadeiro.

Figuras 22 e 23. Alterações nos parâmetros closepoints

BACKGROUND: usado para colocar imagens de fundo, conforme

ilustrado na Figura 25; produz imagens mais realistas. A cada vez que

é iniciada a execução do programa, a imagem de fundo é carregada.

Na figura 24, a imagem levou 0,039 segundos, enquanto a figura 25 foi

formada em 1,998 segundos. Parâmetros utilizados na formação das

Figuras 24 e 25: EspVein = 1.0, Raio VeinNode = 0.4, Número de

Iterações = 100, Kill distance = 0.08 e Número de linhas e colunas = 7.

Figuras 24 e 25. Alterações nos parâmetros background

30

A simulação é executada em dois passos: a leitura dos parâmetros de

configuração e a execução do algoritmo principal. Na figura 6 está a arquitetura do

modelo.

Na fase de configuração, o simulador lê os parâmetros do arquivo

"config.xml", que é gerado pelo Gerenciador de Parâmetros. Caso tenha sido

definida uma figura de fundo, no parâmetro BACKGROUND, é nessa fase que a

figura é desenhada.

A fase de criação de auxinas utiliza os parâmetros

NUM_LINES_GRID e NUM_COLUMNS_GRID para criar e posicionar as auxinas na

área de crescimento. A posição base para a criação de uma auxina é o vértice entre

linha e coluna; porém se essa fosse sempre a mesma posição, as imagens de crack

geradas seriam sempre as mesmas. Para isso foi incluído um cálculo randômico

para posicionamento das auxinas ao redor da intersecção de acordo com o número

randômico gerado. Caso o parâmetro DRAWNODES esteja marcado, as auxinas

geradas serão desenhadas na tela em sua posição final.

Na fase de crescimento, é iniciado o loop principal do modelo, onde para cada

auxina "viva" é buscado o VeinNode mais próximo à ela, com uma distância mínima

definida pelo parâmetro VEIN_RADIUS. Depois de encontrado, a auxina modifica o

vetor de influência desse nodo somando o vetor que existe entre a auxina e o

VeinNode ao vetor de influência já existente do próprio VeinNode. Dessa maneira

mais de uma auxina pode influenciar o crescimento de um VeinNode. Após todas as

auxinas terem influenciado algum VeinNode é iniciada a criação de novos

VeinNodes, e para isso todos os que possuem um vetor de influência com tamanho

diferente de zero têm esse vetor normalizado e multiplicado pelo parâmetro

ESPVEIN. Dessa maneira é criado um novo VeinNode na posição encontrada, e

então esse vetor de influência é zerado novamente.

31

Figura 26: Tarefas realizadas pelo simulador

Terminada a fase de crescimento é hora de verificar se alguma auxina deve

ser removida da área de crescimento. Todas as auxinas são verificadas para

descobrir se estão a uma distância igual ou inferior ao parâmetro KILL_DISTANCE;

caso estejam, essa auxina é removida. Quanto mais tarde uma auxina for removida

32

da área de crescimento mais VeinNodes ela irá influenciar em seu crescimento até

que seja removida.

Após terem sido efetuadas as fases de crescimento e destruição de auxinas,

é realizado o desenho das conexões entre os VeinNodes, objetivando formar as

linhas de crack. Nessa fase, caso o parâmetro LINEGROWTH tenha um valor

definido, a grossura da linha entre um VeinNode e seus "filhos" será dada pelo valor

do parâmetro multiplicado pelo número de filhos.

As duas últimas fases descritas são o desenho de conexões e o fechamento

de pontos. Essas fases opcionais não fazem parte do algoritmo principal, pois são

implementações feitas para gerar padrões específicos, como vidro e barro. O

desenho de conexões, parâmetro DRAWCONNECTIONS, liga os últimos pontos

gerados para fechar um círculo entre eles, esse círculo foi visto nas figuras de vidro

pesquisadas. O fechamento de pontos, parâmetro CLOSEPOINTS, ocorre com

todos os VeinNodes que não possuam ramificações, neste caso é buscado o

VeinNode mais próximo à outro e desenhada uma ligação entre eles. Esse

comportamento ocorre em todas as iterações da simulação.

Se o número de iterações definidas no parâmetro NUM_INTERACTION tenha

sido alcançado a simulação termina, caso contrário é repetido o processo a partir do

bloco de crescimento.

3.1 Simulador de Cracking

O simulador possui 7 classes, Auxin, ComparerListA, ComparerListB,

ComparerListC, ComparerListD, Simulador e Coordenada. O programa foi

desenvolvido em .net C++, e o gerenciador de parâmetros em C# .net, versão 3.5,

usando a biblioteca OpenGL para gerenciar a parte gráfica do software (classes

glut.h e glu.h), bem como todos as funções de mostrar os resultados na tela.

As classes ComparerListA, ComparerListB, ComparerListC, ComparerListD

são utilizadas para fazer o padrão circular que ocorre nas imagens de crack de vidro.

Como o próprio nome diz, são classes de comparação, que visam ordenar as listas

dos pontos de forma que sejam geradas imagens numa circunferência.

33

Os parâmetros que influenciam na geração dos cracks foram descritos no

capítulo anterior.

3.1.1 Principais funções do simulador

GeraAuxina: Função que diz se deve gerar uma auxina ou não; há 75%

de chance de gerar.

insideCircuference: Método para verificar a existência de um ponto

dentro do alcance de uma circunferência.

DrawLineByDeepness: Método que desenhará as linhas; gera o padrão

de crescimento da espessura da linha, conforme o número de filhos.

DrawWeb: cria o padrão de ligação circular entre os nodos, em cada

iteração do algoritmo, com randomicidade igual a 50 %.

GetLeaveNodes: pega os últimos nodos folhas que não possuem filhos,

nele é utilizado o parâmetro closePoints, gerando as ilhas do padrão de

barro.

Configura: gera um arquivo XML com parâmetros padrão de

inicialização do programa. Caso não haja o arquivo ele cria, caso

contrário carrega as configurações indicadas pelo usuário.

3.2 Custo Computacional

De acordo com os testes realizados com os parâmetros que compõem a

Tabela 1, verifica-se que o custo computacional para a geração de imagens de

cracks de concreto – Figura 28 - é o mais baixo. Um dos motivos é que este padrão

utiliza menos pontos de orientação – auxinas – pois possui um grid de tamanho

menor – 7 linhas por 7 colunas.O padrão gerado para o vidro, ilustrado na Figura 29,

é o mais custoso computacionalmente pois utiliza um grid maior, 20 linhas por 20

colunas, além de utilizar um algoritmo adicional para a geração as circunferências do

vidro. O padão para gerar cracks de barro fica com um valor intermediário.

Para obter estes resultados utilizou-se um netbook com um processador de

1,6 Ghz e 2Gb de memória RAM.

34

Tabela 1: Performance do algoritmo para cada padrão de crack

Padrão

de

crack

Variável

Valor

atribuí

do

Tempo de

execução

em

segundos

Resultado visual

Ba

rro

KILL_DISTANCE 0.08

3,14

Figura 27

VEIN_RADIUS 0.4

NUM_INTERACTION 100

NUM_LINES_GRID 20

NUM_COLUMNS_GRID 20

ESPVEIN 0.8

LINEGROWTH 0.5

DRAWNODES false

DRAWCONNECTIONS false

CLOSEPOINTS false

BACKGROUND false

Con

cre

to

KILL_DISTANCE 0.08

0,78

Figura 28

VEIN_RADIUS 0.4

NUM_INTERACTION 100

NUM_LINES_GRID 7

NUM_COLUMNS_GRID 7

ESPVEIN 1

LINEGROWTH 1

DRAWNODES false

DRAWCONNECTIONS false

CLOSEPOINTS false

BACKGROUND false

Vid

ro

KILL_DISTANCE 0.02

VEIN_RADIUS 100

NUM_INTERACTION 80

35

NUM_LINES_GRID 20

6,59

Figura 29

NUM_COLUMNS_GRID 20

ESPVEIN 0,03

LINEGROWTH 0

DRAWNODES false

DRAWCONNECTIONS true

CLOSEPOINTS false

BACKGROUND false

36

4 RESULTADOS

Nesse capítulo, apresentam-se alguns resultados de imagens geradas pelo

simulador, que foram avaliados por 84 voluntários. O grupo de pessoas que

respondeu às duas pesquisas são parecidos: colegas da Faculdade de Informática,

amigos e familiares dos autores e da orientadora. O objetivo da avaliação foi

identificar como estava a aceitação das imagens geradas pelo simulador, bem como

saber o que deveria ser revisado objetivando a geração de cracks mais realistas.

4.1 Survey Inicial

Foi feita uma pesquisa inicial, à qual 48 participantes responderam entre os

dias 24 de maio a 04 de junho de 2010, às seguintes questões:

1. Similaridade entre as imagens de crack em barro reais e as do

simulador

2. Similaridade entre as imagens de crack em vidro reais e as do

simulador

3. Similaridade entre as imagens de crack em concreto reais e as do

simulador

Foi escolhido realizar simulação de cracks de barro, vidro e concreto devido a

facilidade de encontrar-se imagens desses três tipos disponíveis na internet.

Como resposta às perguntas, havia uma escala de 1 a 5, onde 1 significa

“Totalmente Diferente” e 5 significa “Muito semelhante”. As imagens de comparação

estavam hospedadas em http://crackingsurface.blogspot.com/, e havia um formulário

do Google Docs armazenando as respostas. Também foi enviado por email um

arquivo do tipo apresentação de slides para melhor visualização das imagens.

Abaixo, as figuras avaliadas na primeira etapa da pesquisa. Foram colocadas lado a

lado imagens do simulador imagens reais para a avaliação.

4.1.1 Cracks em barro

Para geração das imagens de barro, utiliza-se os seguintes parâmetros:

EspVein: 0.8

NumIteration: 100

VeinRadius: 0.4

37

KillDistance: 0.08

NumLinesGrid: 20

NumColunsGrid: 20

DrawNodes: false

BackGround: barro.bmp ou false (quando o fundo é branco).

Mostra-se as comparações entre cracks de barro do simulador e reais da

Figura 30 até a Figura 45.

Imagens do Simulador Imagens Reais

Figura 30

Figura 315

Figura 32

Figura 336

5Disponível em

http://www.maureenwilksdigitalfineart.com/Original%20Photos/Mud%20Cracks%2002.JPG.

6Disponível em

http://2.bp.blogspot.com/_cXPcg6ZxQ7U/SLQJTfIiAsI/AAAAAAAAAmY/R8SYKU0_6Kc/s400/cracks.jp

g

38

Imagens do Simulador Imagens Reais

Figura 34

Figura 357

Figura 36

Figura 378

Figura 38

Figura 399

7Disponível em http://upload.wikimedia.org/wikipedia/commons/2/2c/Desiccation-cracks_hg.jpg

8Disponível em http://www.pensionriskmatters.com/uploads/image/Cracks.jpg

9Disponível em http://neriah-stock.deviantart.com/art/Nasty-Cracks-IV-82744169

39

Imagens do Simulador Imagens Reais

Figura 40

Figura 4110

Figura 42

Figura 4311

10

Disponível em http://www.public-domain-photos.com/free-stock-photos-3/miscellaneous/cracks-in-

dry-mud-2.jpg.

11Disponível em http://pespmc1.vub.ac.be/Photos/MudCracks.jpg

40

Imagens do Simulador

Imagens Reais

Figura 44

Figura 4512

Figuras 30 a 45: comparações entre imagens de cracks em barro do

simulador e imagens reais

4.1.2 Cracks em vidro

Com os parâmetros geram-se as imagens de cracks de vidro representadas

nas Figuras 46, 48, 50 e 52:

EspVein: 2

NumIteration: 100

VeinRadius: 0.9

KillDistance: 0.08

NumLinesGrid: 20

NumColunsGrid: 20

DrawNodes: false

BackGround: false

As Figuras 47, 49, 51 e 53 mostram as imagens reais de cracks de vidro que

foram utilizadas na comparação.

12

Disponível em http://pespmc1.vub.ac.be/Photos/HumiditySeepingCracks1405-W.jpg

41

As notas que foram atribuídas pelos participantes às imagens de vidro

utilizadas nessa pesquisa inicial, mostraram que essa era a maior deficiência do

modelo, fazendo com que na segunda parte da pesquisa o tenha sido incluído o

padrão de circunferência.

Imagens do Simulador Imagens Reais

Figura 46

Figura 4713

Figura 48

Figura 4914

13

Disponível em http://www.faqs.org/photo-dict/photofiles/list/2134/2794cracks.jpg.

14Disponível em

http://image.shutterstock.com/display_pic_with_logo/98964/98964,1245494257,3/stock-photo-there-is-

a-broken-car-glass-of-windscreen-with-hole-in-picture-center-32348800.jpg

42

Imagens do Simulador Imagens Reais

Figura 50

Figura 5115

Figura 52

Figura 5316

Figuras 46 a 53: comparações entre imagens de cracks em vidro do

simulador e imagens reais

4.1.3 Cracks em concreto

Para imagens de cracks de vidro utilizam-se os seguintes parâmetros:

NumIteration: 100

VeinRadius: 0.4

KillDistance: 0.08

15

Disponível em

http://www.istockphoto.com/file_thumbview_approve/9820572/2/istockphoto_9820572-broken-car-

glass-of-windscreen.jpg

16Disponível http://farm4.static.flickr.com/3039/2312963468_15636583df.jpg.

43

NumLinesGrid: 7

NumColunsGrid: 20

DrawNodes: false

BackGround: false

Com esses parâmetros, consegue-se gerar as Figuras 54, 56 e 58. As Figuras

55, 57 e 59 mostram comparativos com imagens de cracks de concreto reais.

Imagens do Simulador Imagens Reais

Figura 54

Figura 5517

Figura 56

Figura 5718

17

Disponível em http://th.physik.uni-frankfurt.de/~hossi/Bilder/BR/cracks_small.jpg.

18Disponível em

http://primerestorationinc.com/images/ConcreteRestoration&Repair/CrackedConcreteSample.jpg

44

Imagens do Simulador Imagens Reais

Figura 58

Figura 5919

Figuras 54 a 59: comparações entre imagens de cracks em concreto do

simulador e imagens reais

Como resposta às imagens de barro, houve média igual a 3,17, o número que

mais se repetiu (moda) foi 4, e o desvio padrão foi 1,00. Isso significa que os

resultados foram satisfatórios, concentrando-e entre os números 2,17 (imagens

parcialmente semelhantes) e 4,17 (muito semelhantes).

Como resposta às imagens de crack em vidro, tivemos uma média de 2,46,

com uma moda de 2 e desvio padrão de 1,21; foi a média de notas mais baixa,

porém foi também a de maior desvio padrão, ou seja, houve maior discordância

entre as respostas dadas. As avaliações concentraram-se entre 0,71 e 4,71, ou seja,

de imagens totalmente diferentes a muito semelhantes,

Para as imagens de concreto, tivemos uma maior aceitação, com média de

3,70, moda de 4 e desvio padrão de 1,15. As avaliações variaram de 2,55 a 4,85,

sendo avaliadas como parcialmente semelhantes a muito semelhantes.

4.2 Survey Final

Após analisarmos as respostas dadas sobre as imagens do simulador na

primeira fase da pesquisa, foram feitas alterações no simulador, com o intuito de

19

Disponível em http://www.elated.com/res/Image/imagekits/137/cracks-in-rocks-2.jpg.

45

deixar as imagens mais realistas. À essa segunda pesquisa, 38 participantes

responderam entre os dias 06 a 19 de junho de 2010, às mesmas questões feitas

anteriormente. A seguir, colocamos as imagens que foram enviadas por email para

análise dos participantes da pesquisa.

Para melhorar as imagens geradas, foram incluídos os parâmetros

NumColumnsGrid (para geração de imagens com número de colunas diferente do

número de linhas), LineGrowth (para engrossar a linha pai cada vez que ele tiver um

filho) e DrawConnections (para gerar o padrão de ilhas entre os nodos filhos).

4.2.1 Cracks em barro

Para geração das Figuras 60, 62, 64, 66 e 68 mostradas a seguir, foram

utilizados os seguintes parâmetros:

EspVein: 0.8

NumIteration: 100

VeinRadius: 0.4

KillDistance: 0.08

NumLinesGrid: 20

NumColunsGrid: 20

DrawNodes: false

BackGround: marrom.bmp, cinza.bmp ou bege.bmp

LineGrowth: 0.5

DrawConnections: false

ClosePoints: false

As Figuras 61, 63, 65, 67 e 69 são as imagens reais selecionadas para

comparação. As referências bibliográficas são repetidas a partir daqui porque as

imagens reais utilizadas na segunda parte do survay são as mesmas da primeira

parte.

46

Imagens do Simulador Imagens Reais

Figura 60

Figura 6120

Figura 62

Figura 6321

20

Disponível em

http://www.maureenwilksdigitalfineart.com/Original%20Photos/Mud%20Cracks%2002.JPG.

21Disponível em

http://2.bp.blogspot.com/_cXPcg6ZxQ7U/SLQJTfIiAsI/AAAAAAAAAmY/R8SYKU0_6Kc/s400/cracks.jp

g

47

Imagens do Simulador Imagens Reais

Figura 64

Figura 6522

Figura 66

Figura 6723

22

Disponível em http://www.pensionriskmatters.com/uploads/image/Cracks.jpg.

23Disponível em http://neriah-stock.deviantart.com/art/Nasty-Cracks-IV-82744169.

48

Imagens do Simulador Imagens Reais

Figura 68

Figura 6924

Figuras 60 a 69: comparações entre as novas imagens de cracks em

barro do simulador e imagens reais

4.2.2 Cracks em vidro

Para geração das Figuras 70, 72 e 74 mostradas a seguir, foram utilizados os

seguintes parâmetros:

EspVein: 0.3

NumIteration: 80

VeinRadius: 100

KillDistance: 0.02

NumLinesGrid: 20

NumColunsGrid: 20

DrawNodes: false

BackGround: C:\ vidro.bmp

LineGrowth: 0 (para linhas pretas) ou 0.5 (para linhas brancas)

DrawConnections: false (para linhas pretas) ou true (para linhas

brancas)

ClosePoints: false

24

Disponível em http://pespmc1.vub.ac.be/Photos/MudCracks.jpg.

49

Para comparação com as imagens do simulador, foram utilizadas as Figuras

71, 73 e 75.

Imagens do Simulador Imagens Reais

Figura 70

Figura 7125

Figura 72

Figura 7326

25

Disponível em http://www.faqs.org/photo-dict/photofiles/list/2134/2794cracks.jpg.

50

Imagens do Simulador Imagens Reais

Figura 74

Figura 7527

Figuras 70 a 75: Comparações entre as novas imagens de cracks em

vidro do simulador e imagens reais

4.2.3 Cracks em concreto

Para geração das Figuras 76, 78 e 80 mostradas a seguir, foram utilizados os

seguintes parâmetros:

EspVein: 1

NumIteration: 100

VeinRadius: 0.4

KillDistance: 0.08

26

Disponível em

http://image.shutterstock.com/display_pic_with_logo/98964/98964,1245494257,3/stock-photo-there-is-

a-broken-car-glass-of-windscreen-with-hole-in-picture-center-32348800.jpg.

27Disponível em

http://www.istockphoto.com/file_thumbview_approve/9820572/2/istockphoto_9820572-broken-car-

glass-of-windscreen.jpg.

51

NumLinesGrid: 7

NumColunsGrid: 7

DrawNodes: false

BackGround: C:\ concreto.bmp

LineGrowth: 1.0

DrawConnections: false

DrawPoints: false

Para comparação, utiliza-se as Figuras 77, 79 e 81.

Imagens do Simulador Imagens Reais

Figura 76

Figura 7728

Figura 78

Figura 7929

28

Disponível em http://th.physik.uni-frankfurt.de/~hossi/Bilder/BR/cracks_small.jpg.

29Disponível em

http://primerestorationinc.com/images/ConcreteRestoration&Repair/CrackedConcreteSample.jpg.

52

Imagens do Simulador Imagens Reais

Figura 80

Figura 8130

Figuras 73 a 78: comparações entre as novas imagens de cracks em

concreto do simulador e imagens reais

Para melhorar a aparência das imagens de barro, foi utilizado o parâmetro

LINEGROWTH, que engrossa a linha pai a cada filho que ele tem. Com a utilização

desse parâmetro, a média baixou de 3,17 para 2,71, sendo o valor 2 o número mais

repetido e tendo 1,25 como desvio padrão. Isso significa que as notas concentraram-

se entre 1,46 e 3,96 variando de “totalmente diferentes” a “muito semelhantes”.

Pode-se supor, analisando as respostas, duas coisas: ou o parâmetro que engrossa

a linha pai não ficou bem colocado nesse tipo de crack, ou as imagens de vidro e

concreto ficaram melhores que anteriormente, fornecendo uma nova referência de

avaliação para as pessoas que responderam,e baixando o conceito para os cracks

de barro.

Em relação às imagens de crack em vidro, com a utilização do parâmetro

DRAWCONNECTIONS para gerar o padrão de circunferência ao redor dos cracks.

Dessa maneira, a média subiu de 2,46 na primeira pesquisa para 3,45, sendo 4 o

valor mais repetido e tendo um desvio padrão de 1,11. A maior concentração de

notas ficou entre os valores 2,34 e 4,56, sendo considerados semelhantes à muito

semelhantes.

Quanto às imagens de concreto, representadas nas Figuras 73 a 78,

continuaram sendo as imagens melhor avaliadas, com média de 3,97, moda igual a

30

Disponível em http://www.elated.com/res/Image/imagekits/137/cracks-in-rocks-2.jpg.

53

4 e desvio padrão de 0,88. As avaliações variaram de 3,09 a 4,86, sendo avaliadas

como semelhantes a muito semelhantes.

Mostram-se dois gráficos, Figuras 59 e 60, onde visualiza-se uma melhora

significativa nas avaliações dos padrões de vidro e concreto, e também uma

diferença observada no padrão de barro.

Figura 82: Média de avaliação atribuída aos cracks

54

5 CONCLUSÃO

Nesse trabalho foi proposto um modelo para simulação de geração de

cracking surface em jogos. Aspectos como apresentação visual e similaridade com

cracks reais são abordados.

O custo computacional melhorou ao remover-se o algoritmo dart throwing. Ao

utilizar-se de um algoritmo para dividir a área de distribuição das auxinas como uma

malha de linhas horizontais e verticais, houve melhora significativa n a performance

de geração das imagens.

A partir de pesquisas iniciais realizadas com algumas pessoas, descobriu-se

que os padrões gerados pelo simulador precisavam ser aprimorados para que

pudessem reproduzir fielmente imagens de cracks. A pesquisa e o desenvolvimento

baseados no algoritmo de Prusinkiewicz [Runions, 2005] mostraram que é possível a

utilização desse algoritmo para uso em geração de cracks surface em jogos, mas

para tanto foi necessário um trabalho de aprimoramento e otimização.

Uma das melhorias que foram feitas em relação à proposta dessa monografia,

foi fazer com que as ramificações fossem desenhadas com linhas em substituição

aos pontos. Outra melhoria implementada e que gerou bastante diferença visual foi o

acréscimo do parâmetro LINEGROWTH, que permite que sejam gerados cracks com

linhas pais mais grossas que as linhas filho. Também o parâmetro

DRAWCONNECTIONS permitiu que fossem gerados padrões de cracks de vidro

bastante semelhantes com os reais.

Ao iniciar-se esse trabalho, tinha-se a hipótese de que o algoritmo de

Prusinkiewicz [Runions, 2005] poderia ser utilizado para geração de cracks em

materiais como vidro, barro e concreto. Concluímos que a adaptação desse

algoritmo para a geração de cracks é viável, e que com as modificações estruturais

que foram implementadas, o modelo referenciado pôde ser utilizado para simulação

de cracking surface em jogos.

55

REFERÊNCIAS

[Bohn, 2005] Bohn, S; Platkiewicz, J; Andreotti, B; Adda_Bedia, M; Couder, Y. Hierarchical crack pattern as formed by successive domain divisions. II From disordered to deterministic behavior. Physical Review E 71, 2005.

[Cook, 1986] Cook, R. L.. Stochastic sampling in computer graphics. In: ACM Transaction on Graphics 5, 1, pp 225–240, 1986.

[de Berg, 2008] de Berg, Mark et al. Computational Geometry: Algorithms and Applications, 3rd Edition, pp 99-101. Springer, 2008.

[Gobron, 2000] Gobron, Stéphane; Chiba, Norishige. Crack pattern simulattion based on 3D surface cellular automata. In: Proc. Of the International Conference on Computer Graphics, pp. 153-162, 2000.

[Iben, 2006] Iben, Haylen N.; O‟Brien, James F.. Generating Surface Crack Patterns. In: ACM SIGGRAPH Symposium on Computer Animation, 2006.

[Lorensen, 1987] Lorensen, William E; Cline, Harvey E.: Marching Cubes: A high resolution 3D surface construction algorithm. In: Computer Graphics, Vol. 21, Nr. 4, July 1987

[Martinet, 2004] Martinet, Aurélien; Galin, Eric; Desbenoit, Brett; Akkouche, Samir; Alpes, Artis–GRAVIR INRIA Rhône; Lyon 1, LIRIS CNRS UCB. Procedural Modeling of Cracks and Fratures. In: International Conference on Shape Modeling and Applications, pp 346-349, 2004.

[Mitchell, 1987] Mitchell, D. 1987. Generating antialiased images at low sampling densities. In Computer Graphics, vol. 21, 65–78. (Proceedings of SIGGRAPH 1987)

[Rodrigues, 2009] Rodrigues, Rafael; Paravisi, Marcelo; Bicho, Alessandro; Jung, Claudio; Magalhaes, Leo Pini; Musse, Soraia. Tree Paths: A New Model for Steering Behaviors. In IVA 2009 – Intelligent Virtual Agents, Amsterdam.

[Runions, 2005] Runions, Adam; Fuhrer, Martin; Lane, Brendan; Federl, Pavol; Rolland−Lagan, Anne−Gaëlle; Prusinkiewicz, Przemyslaw. Modeling and visualization of leaf venation patterns. ACM Transactions on Graphics 24(3), pp. 702−711, 2005.

[Shen, 2007] Shen, Chen; Shah, Apurva. Extracting and parametrizing temporally coherent surfaces from particles. In: ACM SIGGRAPH 2007 Sketches.

[Smith, 2003] Smith, Colin; Prusinkiewicz, Przemyslaw; Samavati, Faramarz. Local Specification of Surface Subdivision Algorithms. In: Proceedings of AGTIVE 2003, vol. 3062 of Lecture Notes in Computer Science, pp 313-327.

[Smith, 2006] Smith, Colin. On Vertex-Vertex Systems and Their Use in Geometric and Biological Modelling. Tese submetida à Universidade de Calgary como requisito parcial para obtenção de doutorado em filosofia, 2006.