algoritmo heightmap geração?

Question

Eu estava olhando em torno da internet e não consegui encontrar um algoritmo perfeito para este problema em particular:

O nosso cliente tem um conjunto de pontos e dados de peso, juntamente com cada ponto como pode ser demonstrado por esta imagem:

pontos ponderados http://chakrit.net/files/stackoverflow/so_heightmap_points.png

Dos quais, temos um programa de GIS que poderia gerar uma "heightmap" ou uma espécie de dados de terreno a partir desses pontos e seus valores de peso, mas como temos perto de mil pontos de dados e que estes irão mudar ao longo do tempo, gostaria de criar nossas próprias ferramentas para gerar automaticamente estes heightmaps.

Até agora, eu tentei calcular o peso para cada pixel de sua distância para o ponto de dados mais próximo com Sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2) e aplicar peso e fator distância para a cor do ponto de dados para produzir a cor gradiente resultante para esse pixel específico:

heightmap resultar http://chakrit.net/files/stackoverflow/so_heightmap_result.png

Você pode ver que ainda há problemas com certa configuração de pontos de dados eo algoritmo às vezes produzir uma imagem bastante poligonal quando há um monte de pontos de dados. O resultado ideal deveria se parece mais com uma elipse e menos como um polígono.

Aqui está uma imagem de exemplo do artigo do wikipedia em ascensão gradiente que demonstra o resultado que eu quero:

montanhas http://chakrit.net/files/stackoverflow/so_gradient_descent.png

O algoritmo gradiente ascendente não é do meu interesse. O que eu estou interessado em; é o algoritmo para calcular a função original em que a imagem em primeiro lugar, os pontos de dados fornecidos com pesos.

Eu não tenho tido qualquer classe em matemática topológica, mas posso fazer alguma cálculo. Eu acho que pode estar faltando alguma coisa e estou bastante perdida para o que eu deveria digitar nessa caixa de busca do Google.

Eu preciso de alguns ponteiros.

Obrigado!

Answer 1

O que você está procurando é a superfície de interpolação.

Existem alguns produtos para fazer isso (aqui está um )

A função / estriado / outra construção matemática resultante pode, então, ser interrogado para a resolução necessária para fornecer o mapa de altura.

A sua função de interpolação

Sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2) 

É semelhante ao Inverse Distance métodos ponderada, exceto você está aplicando um filtro arbitrário e descartando muitos dos outros pontos de dados.

A maioria destas técnicas dependem de um número razoável de amostras e 'terreno-like' comportamento sustentam os valores.

Eu sugiro usar o peso como a amostra de altura e tentar o simples método de Shepard no segundo link (não filtrar quaisquer pixels para começar), tendo a proporção de uma contribuição pontos de amostra para o valor global altura um ponto de interpolação você pode misturar as cores das amostras nesses índices também colorir o ponto. Use a intensidade (grosso modo a escala de cinza no espaço RGB simples) para apresentar a altura ou adicionar linhas de contorno de preto como a imagem exemplo faz.

Answer 2

Este problema não é tão fácil quanto parece na superfície. Seu problema é que ambos os lados da fronteira de duas regiões precisam ter a mesma altura, o que quer dizer, a altura em um determinado pixel é determinada por mais do que apenas um vizinho mais próximo.

Se eu entendi corretamente, você precisa de pelo menos dois algoritmos (e uma terceira parte do jargão).

Para fazer isso corretamente, você precisa quebrar o avião em um Voronoi tesselation .

Você provavelmente vai querer usar um kd-árvore para ajudá-lo encontrar o vizinho mais próximo. Em vez de tomar O (n ^ 2), isso vai trazê-lo para baixo para O (n log (n)) (o benefício adicional é que a sua fase de geração região Voronoi será rápido o suficiente no desenvolvimento de trabalho na fase de cálculo altura).

Agora que você tem um mapa 2-D indexação de cada ponto de seu vizinho mais próximo i, você precisa atravessar todos os x, ponto y no mapa e calcular a sua altura.

Para fazer isso para um determinado ponto x, y, primeiro agarrar seu vizinho mais próximo i e da vara que em uma lista, em seguida, recolher todas as regiões contíguas no diagrama de Voronoi. Uma maneira fácil é usar inundação preenchimento para encontrar todos os pontos da região, em seguida, olhar ao redor a fronteira e recolher-se as outras identidades.

Usando esta lista de todos os vizinhos mais próximos, agora você tem uma chance de interpolação corretamente! (Veja outras respostas para os regimes de interpolação).

Answer 3

Você pediu informações sobre algoritmos para 2-D interpolação de dados irregulares, que é uma área bastante complexa. Desde que você diz que tem ArcGIS, I fortemente aconselhar que você interpolate automaticamente no ArcGIS utilizando a sua = built-in apresenta para cálculos automáticos. Estou certo de que será muito mais fácil do que escrever seu próprio algoritmo de interpolação. Já fiz alguns automação de ArcGIS, é bastante simples.

Se você escrever seu próprio código de interpolação - Eu aconselho a não - a primeira coisa é escolher o algoritmo apropriado, pois há vários cada um com suas próprias vantagens e desvantagens. Aqui estão alguns conselhos plagiou a ajuda para o excelente ferramenta de interpolação Surfer (que BTW também pode ser automatizado com bastante facilidade). Há mais algoritmos, estes são apenas os que eu tentei.

• Kriging é um dos métodos mais flexíveis e é útil para gridding quase qualquer tipo de conjunto de dados. Com a maioria dos conjuntos de dados, Kriging com o variograma linear padrão é bastante eficaz. Em geral, nós na maioria das vezes recomendar este método. Krigagem é o método gridding padrão porque gera um bom mapa para a maioria dos conjuntos de dados. Para conjuntos de dados maiores, Kriging pode ser bastante lento. Kriging pode extrapolar valores de grade além da gama Z de seus dados.
• distância Inverse ponderação é rápido, mas tem a tendência de gerar padrões de "olho de boi" de contornos concêntricos em torno dos pontos de dados. Inverse Distância a um Poder não extrapola os valores Z para além do intervalo de dados. Um algoritmo inverso distância ponderação simples é fácil de implementar, mas será slowish.
• Triangulação com interpolação linear é rápido. Quando você usa pequenos conjuntos de dados, Triangulação com interpolação linear gera faces triangulares distintas entre pontos de dados. Triangulação com interpolação linear faz Z valores não Extrapole além do intervalo de dados.
• Método de Shephard é semelhante ao Inverse Distância a um Poder, mas não tendem a gerar padrões de "olho de boi", especialmente quando um fator de suavização é usada. Método de Shepard pode extrapolar valores além do alcance Z de seus dados.

Para implementar os algoritmos: você pode tentar Googling, ou siga os links em algumas das outras respostas. Existem alguns pacotes de SIG de código aberto que incluem interpolação, então talvez você pode extrair os algoritmos deles se você gosta de espeleologia através de C ++. Ou este livro de David Watson é, aparentemente, considerado um clássico, embora seja uma leitura complicado e o código de exemplo é spaghetti Básico !! Mas, pelo que ouvi, é o melhor disponível. Se qualquer outra pessoa no Stack Overflow sabe melhor, por favor, faça-me correto como eu não posso acreditar.

Answer 4

Kriging é um dos métodos pesados ??para fazer isso, especialmente dentro do campo de GIS . Tem vários bons propriedades matemáticas - a desvantagem é que ele pode ser lento dependendo da sua variograma .

Se você quiser algo mais simples, existem muitas rotinas de interpolação que lidar com isso muito bem. Se você pode obter ahold de uma cópia do Numerical Recipes , capítulo 3 é dedicado a explicar muitas variantes para interpolação, e inclui exemplos de código e descrições de suas propriedades funcionais.

Answer 5

é o algoritmo para calcular o função original em que a imagem em primeiro lugar, os pontos de dados fornecidos com pesos.

É possível. Se você começar com pontos únicos você sempre vai acabar com círculos, mas se você ponderar os pontos de dados e levar isso em conta, você pode esmagar os círculos em elipses como na imagem ..

A razão que você está terminando com polígonos é que você está usando uma função discreta em seu cálculo -. Primeiro você encontrar a cor mais próxima, então você determinar a cor

Você deve em vez olhar para algoritmos de gradiente que atribui uma cor para um ponto com base na distância e peso a partir dos três pontos de dados que encerram esse ponto em um triângulo.

Gradient algoritmo

Depende do que você está tentando display. Um algoritmo simplista seria:

Para cada pixel:

• Encontre os três pontos que formam a menor triângulo que rodeiam este pixel

• Conjunto este ponto para o (sistema de cores HSV) cor que é afectada tanto pelo peso e a distância para cada ponto de dados:

  pixel.color = datapoint[1].weight * distance(pixel, datapoint[1]) * datapoint[1].color + datapoint[2].weight * distance(pixel, datapoint[2]) * datapoint[2].color + datapoint[3].weight * distance(pixel, datapoint[3]) * datapoint[3].color

Eu estou usando + aqui, mas você precisa para determinar o 'média' algoritmo adequado para sua aplicação.

-Adam

Answer 6

interpolação de superfície parece ser um problema difícil e matemática. Outra forma, mais barata de fazer isso é:

For each pixel:
For each point:
pixel.addWeight(weight(point, pixel))

def addWeight(w):
totalweight += w
numberofweights += 1
weight = totalweight / numberofweights

função peso Exemplo:

def weight(point, pixel):
return point.weight * 1/(1 + sqrt((point.x - pixel.x)^2 + (point.y - pixel.y)^2))

É uma abordagem bastante força bruta, mas é simples.

Answer 7

Eu implementei algo assim no Winamp AVS há um tempo atrás. Ele usa um "metaballs" abordagem do tipo de cálculo da distância ao quadrado inverso (para evitar a sqrt de velocidade) de cada ponto de dados, capping-la (por exemplo a 1,0), e tendo uma soma dessas distâncias para cada ponto da grelha 2D. Isto vai dar uma cor / map suavemente alturas diferentes.

Se você quiser olhar o código, a sua no preset "Glowy" do meu J10 AVS pacote .

EDIT: Só de olhar para ele eu adicionei algum outro jazz para torná-la mais bonita, a parte que é mais importante é:

d1=s/(sqr(px1-rx)+sqr(py1-ry));
d2=s/(sqr(px2-rx)+sqr(py2-ry));
d3=s/(sqr(px3-rx)+sqr(py3-ry));
d4=s/(sqr(px4-rx)+sqr(py4-ry));
d5=s/(sqr(px5-rx)+sqr(py5-ry));
d6=s/(sqr(px6-rx)+sqr(py6-ry));
d=d1+d2+d3+d4+d5+d6;

O que leva a soma para os 6 pontos. Tudo o resto feito para os valores de saída vermelhos, verdes e azuis é para torná-la mais bonita. 6 pontos não é muito, mas tenha em mente que eu estava tentando fazer esta corrida em tempo real em uma grade de 320x200 em uma máquina de 400 MHz quando era novo (o que faz em ~ 20fps). :)

Substitua o vermelho =, = verde e azul = ... linhas com vermelho = D; etc ... para ver o que quero dizer. Toda a beleza vai embora e você é deixado com uma imagem em tons de cinza de problemas variados bolhas ao redor dos pontos de dados.

Outro edit: eu esqueci de dizer "s" é o peso compartilhado por todos os pontos, mudando-o para cada um dá pesos individuais para cada ponto, por exemplo, d1 = 2 / (...) e D2 = 1 / (...) daria d1 duas vezes quanto muito altura no seu centro como D2. Você também pode querer limitar a expressão na parte inferior com algo como d1 = 2 / max (..., 1,0) para alisar fora os topos dos pontos de modo que eles não pico no infinito no meio. :)

Desculpe pela confusão da resposta ... Achei que postar o exemplo de código seria bom o suficiente mas em uma inspeção meu código é confuso e difícil de ler. : (

Answer 8

Eu sei que isso é muito uma questão antiga, mas eu metida ao tentar resolver um problema semelhante.

Há um projeto open source chamado Surfit que implementa exatamente esse tipo de funcionalidade.

Answer 9

Você está procurando por algo que Blender chamadas " metaballs " ( Wikipedia artigo com ligações , exemplo ). Pense nisso desta maneira:

Seus objetos são cones que furam para fora do chão. Eles são todas as parábolas e o peso diz o quão longe eles ficar fora da terra. Alternativamente, torná-los todos a mesma altura e ajuste o "achatamento" da parábola em conformidade, por isso um grande peso faz com que o cone muito ampla, enquanto um baixo peso torna nítida. Talvez até mesmo ambos a um certo grau.

Eu sugiro que você implementar isso e ver como fica.

Em seguida, você precisa para pendurar um pano ou uma folha de borracha sobre o resultado. O pano vai esticar por uma certa quantia e ele geralmente pendem devido à gravidade. Os cones mantê-lo.

Enquanto você estiver perto do centro de um cone, a coordenada Z é apenas a posição na superfície do cone. Como você deixar o centro de cone, a gravidade começa a puxar para baixo e a influência de outros cones cresce.