Como posso executar um teste interno de triângulo em malhas poligonais?

10

insira a descrição da imagem aqui Eu tenho três vértices (V1, V2, V3)selecionados aleatoriamente em uma malha regular de triângulo. Para esses três vértices, calculei a distância geodésica e o caminho (usando Dijkstra) entre eles e formei uma superfície em forma de triângulo, como na figura acima.

Agora, eu tenho os vértices que estão em cada caminho e podem calcular distâncias geodésicas de um determinado vértice.

O que eu quero fazer é obter os vértices ou triângulos que estão na área do triângulo. Como posso fazer isso?

mesh triangulation mkocabas
fonte
2
Assumindo que a abordagem barocêntrica faça o que eu acho que faz, seria bastante lento com conjuntos grandes. Imagine um conjunto de 9 milhões de vértices com apenas 9 vértices no conjunto desejado. Por que iterar o conjunto inteiro quando v1, v2 e v3 fornecem todas as informações necessárias? A resposta de preenchimento seria a solução flexível mais rápida. Embora não seja flexível, se você puder assumir que possui linhas como agora na geometria, a linha de varredura seria a abordagem mais rápida.
Andrew Wilson
Você está absolutamente certo sobre questões de desempenho. Eu gostaria de usar essa abordagem em malhas grandes, então o que estou procurando é um método eficiente. Na verdade, não estou familiarizado com os algoritmos de preenchimento de inundação nem de preenchimento de varredura, vou dar uma olhada neles. Obrigado.
Mkocabas
3
Um preenchimento de inundação com um gráfico começaria em um nó, visitaria todos os nós vizinhos se a condição de limite fosse atendida e não visitada, marcaria como visitada e repetisse (recursão). Alteração: marque cada nó no caminho como visitado e inicie a partir de um nó dentro do conjunto. Em seguida, basta usar a verificação de visitação como condição de contorno.
Andrew Wilson
Obrigado pela explicação detalhada. Acho algo de preenchimento de inundação mais razoável, mas quero implementar a linha de preenchimento de inundação e varredura e comparar os desempenhos.
Mkocabas 19/07

Respostas:

4

Existe um método alternativo que se baseia no preenchimento de inundações. Primeiro, organize seus dados de borda em um loop, onde as bordas estão formando um loop no sentido anti-horário. Em seguida, comece em um ponto arbitrário no loop e escolha as arestas que se juntam a esse ponto. Use a aresta do limite de saída e cruze-a com a outra aresta de saída, se apontar na direção da face normal, será uma aresta a ser incluída, se não descartada. A partir dessa borda, continue até atingir uma borda limite; nesse ponto, você encerrará o preenchimento. Continue em um vértice da borda do limite ainda a ser visitado.

joojaa
fonte
Não estou familiarizado com o algoritmo de preenchimento de inundação. Sua explicação me parece um pouco complicada. Poderia, por favor, fornecer uma referência decente para olhar? Obrigado.
Mkocabas
Eu obtive a solução lendo alguns. Obrigado.
Mkocabas
3

Eu já comentei sobre o uso do preenchimento de inundação e como seria melhor, pois é mais flexível, mas outra solução possível é a scanline. (Eu digo possível, porque ele faz muitas suposições sobre sua geometria, mas para o conjunto específico mostrado e muitos similares, ele funcionaria.)

Para o seu exemplo com 3 pontos: encontre o vértice de interseção do segmento v1, v2 e a linha em que v3 está. (O vértice no canto superior esquerdo da v2) Vamos chamar esse vértice v4.

For every vertex pair a,b down v1,v4 and v1,v3 
    For every vertex from a to b
        Mark as in the set
For every vertex pair a,b down v3,v2 and v4,v3
    For every vertex from a to b
        Mark as in the set

insira a descrição da imagem aqui

Isso se chama scanline porque (na imagem acima) você desce as linhas vermelha e verde simultaneamente e depois as linhas vermelha e azul escaneiam simultaneamente as linhas à medida que avança.

Essa solução seria muito rápida se houver um padrão de índice, o que geralmente ocorre. Caso contrário, seria necessário um cálculo para determinar qual vértice vizinho está na linha.

O engraçado é o scanline, o teste bariátrico (na caixa delimitadora do triângulo) e o preenchimento de inundação são formas de desenhar triângulos na renderização em 3D.

Andrew Wilson
fonte
2

Eu acho que você pode calcular algumas coordenadas barricêntricas ligadas à superfície para cada ponto na superfície e usá-las para verificar dentro ou fora do triângulo.

Eu não tenho um algoritmo exato em mãos, mas encontrei este documento a seguir, que parece lidar exatamente com esse tipo de coordenadas.

Coordenadas bariêntricas em superfícies

Dragonseel
fonte
Obrigado pela resposta e pelo documento de referência. Vou tentar implementar o método proposto.
Mkocabas