[0:14]Olá, seja bem-vindo a mais uma aula aqui da disciplina de Computação Gráfica, do curso de Engenharia da Computação da Univesp. E a aula de hoje a gente vai falar um pouco sobre estruturas de dados para Computação Gráfica, né? Então, né, a gente já viu bastante aqui da composição e do armazenamento de dados, né? A gente viu o processo de transformação de dados em imagem, né? A gente viu um pouco de processamento de imagem. E hoje a gente vai estudar algumas estruturas de dados que servem para o armazenamento e a manipulação aqui dos dados geométricos utilizados em Computação Gráfica. Então, esse é um modelo geométrico, né, utilizado em Computação Gráfica.
[0:59]Então, repare aqui que eu tenho um conjunto de polígonos aqui definindo o meu objeto, né? E quanto mais próximos aqui de triângulos equiláteros aqui, melhor a minha definição do objeto, né? E mais econômico fica essa, essa minha estrutura de dados. Mas eu tenho que ser capaz de percorrer esses polígonos aqui de maneira relativamente eficiente, né? Então, né, é isso que a gente vai, é, estudar hoje, né? Então, o que que eu tenho que ter numa estrutura de dados, né? O primeiro ponto é a geometria, né? Ou seja, o valores das coordenadas desses objetos para que quando, né, eu for, eh, aplicar um algoritmo de câmera virtual aqui, eles aparecerem na posição correta, né? Eh, eu posso armazenar atributos, né, dos objetos, por exemplo, cor, textura, vetores normais, né, etc., né, que são armazenados também na estrutura de dados. E outra informação importante é a topologia, ou seja, as relações de vizinhança ou de conectividade. Por exemplo, dado um vértice qualquer aqui, quantas faces são incidentes nesse vértice? Ou quais os vértices vizinhos dele, né? Como que eu percorro isso de maneira eficiente, né? Então é disso que trata, né, a aula de hoje que vai falar sobre estrutura de dados para Computação Gráfica. Quais as operações, né, que nós temos que, eh, poder aplicar numa estrutura de dados para que ela seja eficiente, né? Então, primeira operação aqui, o rendering, né? Se você lembra da nossa terceira aula, né, você se lembra na terceira e quarta aula, você se lembra que as operações de render, ou seja, de, eh, desenho aqui dos nossos objetos, né, levavam em consideração vetores normais, levavam em consideração, eh, os, os triângulos que estavam, eh, sendo envolvidos, dentro de um raio de vizinhança, ou seja, né, para cada vértice eu precisava aproximar os vetores normais pelos, o vetor normal no vértice pelos vetores normais dos triângulos vizinhos.
[3:03]Então eu precisava percorrer essa relação de vizinhança de maneira relativamente eficiente. Consultas geométricas, então, por exemplo, quais os vértices de uma determinada face F, né? É uma consulta bastante simples, ou quais as faces do primeiro anel aqui de um determinado vértice, né? O primeiro anel no caso, nós temos um vértice VJ aqui. O primeiro anel são todas as faces incidentes nele, né? Eu posso ter um segundo anel aqui, rodeando, né? O terceiro, posso ter um, um terceiro anel aqui, mais, e assim por diante, né? Mas, eh, basicamente o primeiro anel são todas as faces incidentes no determinado vértice. Quais as faces adjacentes a uma face, né? Por exemplo, se eu tô nessa face aqui, né? Como que eu, eh, pulo aqui para a face imediatamente vizinha dela aqui? Ou como que eu pulo para essa outra vizinha imediata dela aqui, né? Então, são, são consultas que a estrutura de dados precisa atender com relativa eficiência. No que diz respeito a operações, né? Eu posso ter modificações, ou seja, eu posso querer remover ou adicionar vértices ou faces. Então, esse é um exemplo aqui, de, eh, na verdade, remoção aqui, né? Eu tô colapsando um vértice, na verdade, eu tô colapsando esse aqui, né, nesse aqui, ou seja, eu tô deixando o meu objeto aqui com o número menor de vértices, né? Tô fazendo aqui um, um flip de arestas, ou seja, eu tô invertendo aqui, né, essa aresta que tá aqui no meio desse, desse objeto, ela foi invertida para modificar a forma aqui do objeto. É uma operação muito comum em estrutura de dados, né? Então, eh, todas essas são operações que a estrutura de dados deve suportar aqui com relativa facilidade, né? Nós vamos, eh, investigar também como avaliar a performance de uma estrutura de dados. Então, um quesito aqui para ela ter uma boa performance é o tempo de construção, ou seja, quanto tempo eu levo para ler a informação do arquivo e carregar para a memória do computador?
[5:22]É um fator importante para a estrutura de dados, né? Um outro fator importante é o tempo de resposta de uma consulta. Digamos que eu precise saber, dado um vértice, quais são os triângulos incidentes nesse vértice, né? Não é muito eficiente eu procurar na minha lista de triângulos e ficar perguntando, olha, ele tem o vértice 10 na sua lista? O triângulo dois, tem o vértice 10? O triângulo três, tem o vértice 10, né? Se eu tenho 100.000 triângulos no um objeto geométrico, essa consulta fica bastante ineficiente, né? Então, eu preciso responder a essa pergunta, né, ou, ou a essa consulta com relativa rapidez, né? Tempo de realização de uma operação, né? Essas operações que a gente viu agora, como o flip de aresta, né, ou colapso de vértice, ou, eh, eh, acrescentar vértices, ou acrescentar faces, né? Quer dizer, quanto tempo isso leva para ser feito de maneira coerente, ou seja, de maneira que as relações de vizinhança fiquem preservadas, né? É um quesito importante aqui na avaliação do desempenho da estrutura de dados. O último quesito, não menos importante, é o consumo de memória RAM, né? Uma vez que eu carrego isso para a memória do computador, né, isso não pode ocupar muita memória RAM, porque senão o meu, eh, ou seja, eu tenho um, uma quantidade de memória RAM limitada em qualquer computador, né? Por uma hora que ela seja, né, eh, a medida que eu vou carregando uma quantidade de objetos, né, isso não pode crescer indefinidamente. Então, ela tem que ser eficiente no consumo de memória também, né?
[7:03]Bom, alguns exemplos de estrutura de dados, né? Um, um exemplo bastante simples é o face set, né? Basicamente, o conjunto de faces, né, que, eh, armazena simplesmente para cada face as três posições geométricas correspondentes à face. Então, para a primeira face, eu tenho aqui, coordenadas X1, Y1, Z1, do primeiro vértice, coordenadas X2, Y2, Z2 do segundo vértice dessa face, e coordenadas X3, Y3, Z3 do terceiro vértice dessa face, né?
[7:37]Veja que eu tô armazenando aqui apenas triângulos, e há uma redundância do armazenamento, porque o mesmo vértice pode estar contido em cinco ou seis triângulos do, da minha lista de triângulos. Então eu vou estar armazenando esse mesmo vértice, eh, pelo menos cinco ou seis vezes, né? Então isso cria uma redundância no arquivo, o que torna o arquivo maior do que ele precisaria ser, na verdade, né? Então, alguns formatos utilizam essa, essa estrutura, né? O formato STL, por exemplo, né? Mas lembrando que é uma estrutura que tem pouca informação, né? Não possui nenhuma informação de conectividade. Se eu quiser responder alguma das consultas que a gente listou ali na outra slide, eu teria que percorrer todos os triângulos que leva uma quantidade de tempo, né, eh, não recomendável. Outra tipo aqui de estrutura de dados, eu chamo de shared vertex, né, ou, né, numa tradução livre aqui, vértice compartilhado, eh, aonde eu tenho, né, a posição aqui dos vértices, mais uma lista aqui de faces onde cada face contém o índice dos vértices. Então, eu tenho duas listas basicamente, né? Uma lista de coordenadas de vértices, onde são aqui, números reais, X1, Y1, Z1, X2, Y2, Z2, né? Até o XV, YV, ZV, né? E tenho uma lista de triângulos onde cada triângulo aqui, na verdade, guarda três números inteiros, que são, na verdade, a posição dos vértices nessa lista inicial aqui, né? Então, eu guardo, por exemplo, o primeiro triângulo, vai ter os vértices zero, um e dois. Significa que é o vértice na posição zero, na posição um, e na posição dois dessa lista inicial. Então, repare que diminuiu a redundância, ou seja, você não está armazenando mais vértices repetidos, né? Você está trocando vértices repetidos por índices repetidos aqui, que é, é mais eficiente de armazenar, né? Porém, ainda não possui informação de conectividade, né? Ou seja, nós melhoramos aqui na, no armazenamento, né? Essa estrutura ficou mais enxuta, mas ela ainda não tem informação de conectividade, né? O que vai fazer falta nas consultas, né? Ou seja, ainda se eu quiser consultar aqui quantos vértices ou quantas faces são incidentes, eu preciso varrer a lista toda de triângulos, o que ainda é ruim, né? Bom, uma estrutura que contempla essa relação de vizinhança aqui bastante popular, é chamada de half edge, né? Qual a ideia da half edge, né? É, eu vou ter aqui os vértices, onde cada vértice vai armazenar a sua posição, e uma half edge que, entre aspas, sai do vértice, ou seja, uma half edge, uma setinha que aponta, eh, saindo daquele vértice, né, tendo como origem aquele vértice. A half edge, o que que ela vai armazenar? Ela vai armazenar o seu vértice de origem, vai armazenar um índice da, de uma face incidente. Aí, dependendo do, da quantidade de informação que você quer armazenar, ela vai armazenar um, dois ou três índices de half edges, né, respectivamente, a próxima, a anterior e a oposta, né? E a face vai armazenar uma half edge incidente na face, né? Então, só pra gente exemplificar aqui, então, aqui nós temos aqui, né, o vértice, né? Essa half edge aqui, que sai desse vértice, né? Essa pretinha aqui, né?
[11:29]Ela está armazenando a half edge seguinte, né, e a half edge seguinte, ou seja, eu consigo dar a volta, consigo percorrer a face, só perguntando para cada half edge quem é a próxima half edge armazenada. Eh, e eu tenho um ponteiro aqui para half edge oposta também, porque quando eu quero trocar de face, ou seja, quando eu quero ir para a face adjacente, eu posso, né, perguntar para half edge quem é a sua half edge oposta e eu simplesmente pulo de triângulo, né? Eu mudo de face a partir da half edge oposta. Então, isso me permite um percorrimento na estrutura de dados bastante eficiente, né? Eh, facilitando muito aquelas consultas, né, de, ah, dado um vértice, quem são os triângulos que pertencem àquele vértice, né? Eu não preciso mais percorrer a lista toda de triângulos para responder essa consulta, né? Uma outra estrutura, né, bastante popular e bastante eficiente, é chamada de opposite face, né? Ela tem uma filosofia, ou uma implementação um pouco diferente aqui da half edge, né? A ideia também é armazenar em duas listas, onde eu tenho aqui uma lista de vértices, cada um com sua coordenada, né? Então, o vértice zero tem a coordenada X0, Y0, Z0, o vértice um, coordenada X1, Y1, Z1, né, e o vértice dois, né, e assim por diante. Na sua lista de células, né? Nós estamos aqui imaginando que cada célula corresponde a um triângulo, né? Eu vou ter o índice dos vértices correspondentes a cada célula. Então, se eu olhar para a minha imagem aqui, né, a célula zero, corresponde aos vértices zero, um e dois. Então, aqui, tá aqui, né? Zero, um e dois, só para preservar a orientação, né?
[14:24]Célula oposta ao vértice dois, é a célula dois.
[14:30]Então, tá aqui, célula oposta ao vértice três é a célula zero. Então, tá aqui, e célula oposta ao vértice um não tem. Então, é menos um, né? Então, dessa maneira, nós temos a informação de como, eh, trocar de células a partir das células opostas aos vértices.
[14:53]Então, ela, né, só recapitulando, guarda coordenadas, para cada vértice também eu guardo o índice de uma face incidente, e na face, seis informações, três índices de vértices e três índices de faces opostas, né? Então, só pra gente ver como é o percorrimento aqui numa estrutura que o positive face, né? Digamos que eu tenho um objeto simples aqui, né, armazenando nessa estrutura. Eu vou estabelecer o algoritmo de percorrimento nessa estrutura, né? Então, o meu primeiro passo é começar com o vértice inicial aqui. Então, digamos que eu quero aqui, todos os vértices vizinhos ao vértice V0. Primeiro passo é identificar o vértice V0, né? Eh, vou encontrar uma face aqui que contém o vértice V0, porque no vértice tem essa informação. Vou encontrar o vértice V0 na face, né, que é o passo três. Vou considerar o vértice seguinte ao V0, né? Então, esse é o primeiro vértice aqui, a Czinha de verde, né? É o meu primeiro vértice aqui, vizinho ao vértice V0 na minha estrutura, né? A partir daí, vou olhar para a face oposta a V1, dentro da face T0, né? Tô na face T1. Na face T1, vou encontrar o vértice V0 novamente. Vou encontrar o próximo, né, assumindo que a orientação está coerente, né? Do próximo, eu vou olhar para a face oposta, para a face T2, e aí eu vou repetindo isso recursivamente, né? Encontro o vértice T0 nessa face, vou para o próximo vértice, encontro o seguinte, aqui em verde. Vou para a face oposta ao V4, encontro o vértice V0 nessa face, encontro o último vértice vizinho de V.
[17:08]Então, a hora que eu, eh, encontrar aqui, agora, um vértice já marcado, eu finalizo o meu algoritmo que eu já encontrei todos os vértices vizinhos aqui ao vértice V0, né? Sem perguntar para todos os triângulos e fazendo apenas uma operação local, o que custa relativamente barato computacionalmente, né? É que é uma estrutura bastante eficiente e bastante poderosa, né? Por hoje é isso, muito obrigado, e até a próxima.
