Space colonization for the procedural generation of lightning

Abstract

The procedural generation of geometry within the space of computer graphics has been a topic of study for quite some time, benefiting from a more unpredictable brand of randomness. Similarly, the exploration of lighting as a phenomenon within virtual space has been a field of study of comparable age. Despite its age and early adoption, there is a surprising lack of research in emulating the phenomenon of lighting past its interactions with the world. Most implementations of procedurally generated lightning within video games are based on randomized data trees. When part of the skybox, 2D meshes or textures are randomly selected from a pre-made pool. There are, however, methods based entirely on the dielectric breakdown model, using approximations to solve a Laplacian equation. This dissertation aims to present an alternative approach to the randomized and procedural generation of lightning bolts based on the Space Colonization algorithm. While the algorithm was first conceived for use in botanical applications, modeling the growth of biological structures, the similarities between the results produced by the dielectric breakdown model and botanic modeling algorithms coupled with the visual likeness of a lightning bolt and certain trees, made for solid groundwork upon which to establish this unique approach. As such, this work largely aims to be a first step into this particular realm, showing Space Colonization as a suitable algorithm for this specific purpose. That being said, a large portion of time was spent iterating, modifying and experimenting with ideas that were either discarded or adapted, an effort primarily dedicated towards controlling and stifling the possible growth of branches in ways beyond the reduction of attractors. The original algorithm was altered, focus put especially on the creation of a singular channel at a time, mixing discoveries from previous research with the work done on manipulating Space Colonization. Instead of the venation patterns observed with the original work, the stifling of any growth means that each node has a chance, when created, of sprouting a branch and each branch is, in turn, a different, modified instance of the same underlying concept providing an additional level of control. Effort was equally placed on showcasing different properties inherent to a lightning strike, such as its iterative construction when descending from its origin. In the rendering section, along with recreating the bloom and glow effect seen in previous works, effort was put into recreating the strobing observed in capturing slow-motion footage of lightning bolts with special detail given to this. In addition, parameters were joined with a waypoint system to allow for a great degree of freedom when generating new bolts.

A geração iterativa de geometria no contexto de computação gráfica é um tópico de estudo à já algum tempo apesar de usado em apenas contextos específicos, um ramo que benefícia de um tipo de aleatoriedade imprevisível. Similarmente, a exploração de relâmpagos como um fenómeno em espaço virtual é uma faceta de idade comparável. Apesar disto, o foco quando tratando relâmpagos tem caído marioritariamente nos seus efeitos após impacto. Estudos têm sido conduzidos no âmbito de mitigar o dano causado por estes em fuselagem de aeronaves e analizar o impacto de trovoada em estruturas críticas. No entanto, existe uma falta de investigação sobre a emulação deste fenómeno barra as suas interações com o mundo. A maioria das implementações iterativas em video jogos são baseadas em árvores de dados. Quando fazem parte do cenário, são marioritariamente meshes ou texturas 2D selecionas aleatoriamente de um conjunto. Existem, no entanto, métodos baseados num modelo de colapso elétrico usando apróximações a uma equação de Laplace. Esta dissertação tem como foco apresentar uma alternativa para a geração aleatória e iterativa de relâmpagos baseada no algoritmo de Space Colonization. Apesar deste algoritmo ter sido concebido para uso botânico, modelando o crescimento de estruturas biológicas, as similaridades entre os resultados obtidos pelo modelo de colapso elétrico e estes algoritmos de modelagem, quando considerados com a semelhança entre certos relâmpagos e árvores, constroem uma fundação sólida para o tópico. Neste âmbito, este trabalho é um primeiro passo que tem o intuito de mostrar a capacidade do algoritmo de Space Colonization em simular relâmpagos. Dito isto, uma grande porção do tempo de desenvolvimento dobrou-se sobre a iteração modificação e experimentação de ideias que foram discardadas ou adaptadas, um esforço primariamente dedicado em controlar o crescimento de ramos sem reduzir o número de atratores. O algoritmo original foi alterado, focando especialmente na criação de um único canal e fazendo uso de conhecimento prévio, oriundo de trabalho e investigação feita sobre manipulação de Space Colonization. Em vez de padrões de venação, observados no trabalho original, o impedimento de qualquer crescimento significa que cada nodo tem uma probabilidade, quando criado, de dar origem a um ramo e que cada ramo é uma instância diferente e modificada do mesmo conceito, algo que cria um nível de controlo mais profundo. Um esforço extra foi, também, realizado com o intuito de mostrar todas as propriedades diferentes, inerentes a um relâmpago tal como a construção iterativa durante a sua travessia. Na parte de renderização, foram recriados efeitos de brilho e bloom vistos em trabalhos prévios. Foi também dada especial atenção à recriação do efeito estroboscópico observado durante a análise de imagens em câmera lenta, algo que se tornou no foco principal desta parte. Adicionalmente, a adição de parâmetros foi conjugada com um sistema de pontos que dá um grau superior de liberdade ao utilizador.