Spelling suggestions: "subject:"dijkstra s algorithm"" "subject:"dijkstras s algorithm""
1 |
GERAÇÃO PROCEDURAL DE CENÁRIOS 3D DE CÂNIONS COM FOCO EM JOGOS DIGITAIS / GERAÇÃO PROCEDURAL DE CENÁRIOS 3D DE CÂNIONS COM FOCO EM JOGOS DIGITAIS / PROCEDURAL GENERATION OF 3D SCENES FEATURING CANYONS FOCUSED ON DIGITAL GAMES / PROCEDURAL GENERATION OF 3D SCENES FEATURING CANYONS FOCUSED ON DIGITAL GAMESCarli, Daniel Michelon de 05 March 2012 (has links)
This Master s thesis proposes a non-assisted procedural method for 3D canyons scenes
generation based on techniques of computer graphics, computer vision and graph search
algorithm. In order to define all the features to be reproduced in our scenes, we have
analyzed several images of real canyons and have categorized them in two canyon features
models: a recursive and an ordinary one. The proposed approach manipulates a
heightmap, created using Perlin noise, in order to imitate the geological features formation
previously analyzed. Several parametrizations are used to guide and constraint the
generation of terrains, canyons features, course of river, plain areas, soft slope regions,
cliffs and plateaus. This work also uses the Mean Shift algorithm as mechanism of segmentation
to define regions of interest. A binary mask, with plain areas, is defined based
on a threshold operation by a given data set provided by the Mean Shift algorithm. Thereafter
a connected-component labeling algorithm is executed using the previously binary
mask. This algorithm finds all plains centroids. Right after that, the Dijkstra s algorithm
is performed in order to connect all plain areas, creating a valid path between the centroids.
The Dijkstra s algorithm is executed again to define the river s course. Finally, a
Gaussian smoothing operation is applied to interpolate the soft slope regions. The combination
of all those techniques produces as a result automatically generated feature-rich
canyons. / Esta dissertação propõe um método procedural não assistido, baseado em técnicas de
computação gráfica, visão computacional e busca em grafos, para a geração de cenários
3D de cânions com foco em jogos digitais. Para definir as características a serem reproduzidas,
foram analisadas diversas imagens de cânions reais chegando-se em dois modelos,
um comum e outro recursivo. A abordagem proposta manipula um reticulado gerado com
ruído de Perlin, moldando assim as características inerentes a essa formação geológica.
São levadas em conta as diversas parametrizações necessárias para permitir que o algoritmo
construa cânions com curso de rio, áreas de planícies, regiões de encosta suave,
estruturas de penhascos e, por fim, planaltos nas regiões mais altas. Para atingir o resultado
final, o trabalho utiliza o algoritmo Mean Shift como mecanismo de segmentação,
definindo dados e regiões de interesse. Munido dos dados do algoritmo de clusterizacao,
é definido um limiar para a criação de uma máscara binária com a definição das planícies.
Em um segundo momento, um algoritmo de rotulação de componentes conectados é executado,
extraindo-se os centróides de cada planície. Por sua vez, o algoritmo de Dijkstra
encaixa-se na definição de rotas que conectam estas planícies. O algoritmo de Dijkstra
é, então, executado novamente, tendo por base uma função de custo de inclinação, para
definir o curso do rio. Por fim, uma filtragem espacial baseada em um filtro Gaussiano
é aplicada para interpolar as regiões de encostas de declive suave. A combinação dessas
técnicas gera terrenos com grande variabilidade e com as características inerentes à
formação geológica de cânions.
|
2 |
Teorie grafů - implementace vybraných problémů / Graph theory - implementation of selected problemsStráník, František January 2009 (has links)
This work is intended on identification with basic problems from the graphs theory area. There are the basic conceptions as well more complicated problems described. The one part of this work is specialized in working of individual types of graphs. It starts with single linked list through double linked list after as much as trees which represented the simplest graphs textures. The other part of this work devotes to the whole graph and describes more complicated problems and their resolution from the theory graphs area. Among these problems belongs to searching in graphs help by Depth First Search and Breadth First Search methods. Then searching the shortest way help by the specific algorithms as are: Dijkstra´s algorithm, Floyd-Warshall´s algorithm and Bellman-Ford´s algorithm. The last part is devoted to problems with searching minimal frames of graphs with usage Kruskal´s algorithm, Jarnik´s algorithm and Boruvka´s algorithm methods.
|
Page generated in 0.0674 seconds