Como o algoritmo do funil simples e estúpido funciona?

Respostas:

18

O algoritmo começa com um caminho que você encontrou anteriormente, neste caso, uma lista de triângulos:

caminho

O código na parte inferior da postagem do blog de Mikko constrói a matriz de portais, que é uma lista de segmentos de linha que representam os segmentos de linha entre os polígonos do caminho. Estes são os "portais" pelos quais o caminho suavizado deve passar (ou as arestas do polígono de "vamos rastrear os pontos médios da aresta do polígono"). Observe que a lista de portais começa e termina com segmentos de linha degenerados nos pontos de início e objetivo.

Esta lista de portais é mostrada como os segmentos de linhas pontilhadas em amarelo em suas fotos.

portais

O algoritmo começa com um funil amplo e prossegue movendo iterativamente os lados do funil para a frente ao longo dos pontos laterais do portal (os pontos finais dos segmentos de linha), desde que isso aperta o funil (AD).

algoritmo

Isso significa que cada avanço deve mover as bordas do funil para dentro, isso pode ser verificado com o produto cruzado dos vetores que representam o lado antigo e o potencial novo lado ( P × Q na imagem abaixo; também veja triarea2no código de Mikko). Se um avanço para um lado não apertar o funil, não atualizamos esse lado para a iteração atual dos portais (E).

movendo-se para dentro

O outro caso que precisa ser tratado é quando o funil degenera para um segmento de linha. Para explicar isso, o algoritmo verifica se um dos lados está do lado "errado" usando o produto cruzado novamente, desta vez dos vetores criados pelo ápice do funil e pelos pontos finais do lado direito e esquerdo, respectivamente ( R × S em imagem abaixo).

funil degenerado

Se esse for o caso, o vetor do ápice do funil e o ponto final lateral correto serão adicionados ao caminho suavizado ( R na imagem acima) e o algoritmo será reiniciado com seu ponto final como o novo ápice (FG), a menos que, claro, se é o objetivo.

Eric
fonte
2
@Rolfcore A resposta é clara? Caso contrário, quais partes precisam ser aprimoradas?
Eric
Eu acho que ele esqueceu de aceitar a resposta, essa é muito boa e deve ser votada em série ^^.
GameDeveloper 15/09/2015
Talvez, em particular, entenda que é no movimento F que você não diz que não recomeçamos do zero, porque existe a chance de que um canto apertado, apontando para o sul, possibilite um funil mais apertado; teste e não apenas um. Então nós fazemos isso em G em vez de F .. boa explicação de qualquer maneira :)
GameDeveloper