algorithme de génération Heightmap?

Question

Je regardais autour de l'Internet et ne pouvait pas trouver un algorithme parfait pour ce problème:

Notre client a un ensemble de points et des données de poids ainsi que chaque point peut être démontré que par cette image:

points pondérés http://chakrit.net/files/stackoverflow/so_heightmap_points.png

Dont, nous avons un programme SIG qui pourrait générer un « heightmap » ou une sorte de données de terrain de ces points et leurs valeurs de poids, mais comme nous avons près d'un millier de points de données et que ceux-ci changeront au fil du temps, nous voudrais créer nos propres outils pour générer automatiquement ces heightmaps.

Jusqu'à présent, je l'ai essayé de calculer le poids pour chaque pixel de sa distance au point de données le plus proche avec Sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2) et en appliquant le poids et le facteur de distance par rapport à la couleur du point de données pour produire la couleur de gradient résultant pour ce pixel particulier:

heightmap résultent http://chakrit.net/files/stackoverflow/so_heightmap_result.png

Vous pouvez voir qu'il ya encore des problèmes avec certaines configurations de points de données et l'algorithme produisent parfois une image plutôt polygonale quand il y a beaucoup de points de données. Le résultat idéal devrait ressemble plus à une ellipse et moins comme un polygone.

Voici un exemple d'image de l'article wikipedia sur l'ascension gradient qui démontre le résultat que je veux:

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

L'algorithme de remontée de gradient n'est pas de mon intérêt. Ce que je suis intéressé; est l'algorithme pour calculer la fonction d'origine dans cette image en premier lieu, à condition que les points de données avec des poids.

Je n'ai pas pris une classe en mathématiques topologiques, mais je peux faire quelques calculs. Je pense que je peux manquer quelque chose et je suis plutôt perdu ce que dois-je entrer dans cette boîte de recherche Google.

J'ai besoin des pointeurs.

Merci!

Answer 1

Ce que vous recherchez est la surface d'interpolation.

Certains produits existent pour le faire (voici un )

La fonction résultante / spline / autre construction mathématique peut alors être interrogé à la résolution requise pour fournir la carte de la hauteur.

Votre fonction d'interpolation

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

est similaire à inverse Distance méthodes pondérée sauf que vous sont l'application d'un filtre arbitraire et à rejeter un grand nombre des autres points de données.

La plupart de ces techniques reposent sur un nombre raisonnable d'échantillons et le comportement « comme terrain » sous-tendant les valeurs.

Je suggère d'utiliser le poids que l'échantillon de hauteur et d'essayer la méthode simple de Shepard dans le deuxième lien (ne pas filtrer les pixels pour commencer) en prenant la proportion d'un échantillon contribution de points à la valeur globale de la hauteur à un point d'interpolation vous pouvez mélanger les couleurs des échantillons dans ces rapports pour colorer aussi le point. Utiliser l'intensité (en gros le niveau de gris dans l'espace de simples RGB) pour afficher la hauteur ou ajouter des lignes de contour en noir comme l'image par exemple le fait.

Answer 2

Ce problème n'est pas aussi facile qu'il regarde la surface. Votre problème est que les deux côtés de la frontière de deux régions doivent avoir la même hauteur, qui est-à-dire la hauteur à un pixel donné est déterminé par plus d'un seul voisin le plus proche.

Si je comprends bien, vous avez besoin d'au moins deux algorithmes (et un troisième morceau de jargon).

Pour ce faire correctement, vous devez briser le plan en Voronoi tesselation .

Vous allez probablement vouloir utiliser un kd-tree pour vous aider trouver le plus proche voisin. Au lieu de prendre O (n ^ 2), cela ramener à O (n log (n)) (l'avantage est que votre phase de génération de région Voronoi sera assez rapide dans le développement pour travailler sur la phase de calcul de la hauteur).

Maintenant que vous avez une carte 2-D indexation chaque point à son voisin le plus proche i, vous devez marcher à travers tous les x, y point sur la carte et calculer sa hauteur.

Pour ce faire que pour un point donné x, y, tout d'abord saisir son voisin le plus proche i et bâton dans une liste, puis collecter toutes les régions contiguës sur le diagramme Voronoi. Un moyen facile est d'utiliser d'inondation remplissage pour trouver tous les points dans la région, alors regardez autour la frontière et de recueillir les autres identités.

En utilisant cette liste de tous les voisins les plus proches, vous avez maintenant un coup de feu à interpoler correctement! (Voir d'autres réponses pour les régimes d'interpolation).

Answer 3

Vous avez demandé des informations sur les algorithmes de 2-D interpolation des données irrégulières, ce qui est tout à fait un domaine complexe. Puisque vous dites que vous avez ArcGIS, I conseille fortement vous interpoler automatiquement dans ArcGIS en utilisant son intégré caractéristiques pour les calculs automatiques. Je suis sûr que sera beaucoup plus facile que d'écrire votre propre algorithme d'interpolation. Je l'ai fait une automatisation d'ArcGIS, il est assez simple.

Si vous écrivez votre propre code d'interpolation - je vous conseille de ne pas - la première chose est de choisir l'algorithme approprié car il y a plusieurs chacun avec leurs propres avantages et inconvénients. Voici quelques conseils de l'aide chipé pour l'excellent outil d'interpolation Surfer (qui BTW peut également être automatisée assez facilement). Il y a plus d'algorithmes, ce ne sont que ceux que je l'ai essayé.

• krigeage est l'une des méthodes plus souples et est utile pour mailler presque tous les types de jeu de données. Avec la plupart des ensembles de données, krigeage avec le variogramme linéaire par défaut est tout à fait efficace. En général, nous recommandons le plus souvent cette méthode. Krigeage est la méthode par défaut de mailler, car il génère une bonne carte pour la plupart des ensembles de données. Pour les ensembles de données plus importants, krigeage peut être assez lent. Krigeage peut extrapoler les valeurs de la grille au-delà de la gamme Z de vos données.
• inverse pondération de la distance est rapide mais a tendance à générer des « oeil de boeuf » modèles de contours concentriques autour des points de données. Distance inverse à une puissance n'extrapole pas les valeurs Z au-delà de la plage de données. Un algorithme de pondération simple distance inverse est facile à mettre en œuvre, mais sera slowish.
• Triangulation avec interpolation linéaire est rapide. Lorsque vous utilisez de petits ensembles de données, avec interpolation linéaire Triangulation génère des faces triangulaires distinctes entre des points de données. Triangulation avec interpolation linéaire n'extrapole pas les valeurs Z au-delà de la plage de données.
• Méthode de Shephard est similaire à la distance inverse à une puissance, mais n'a pas tendance à générer des motifs « œil de bœuf », surtout quand un facteur de lissage est utilisé. Méthode de Shepard peut extrapoler des valeurs au-delà de la gamme Z de vos données.

Pour mettre en œuvre les algorithmes: vous pouvez essayer googler, ou suivre les liens dans quelques-unes des autres réponses. Il y a quelques paquets SIG open-source qui comprennent l'interpolation, alors peut-être que vous pouvez extraire les algorithmes d'eux si vous aimez spéléo à C ++. Ou ce livre de David Watson est apparemment considéré comme un classique, bien qu'il soit une lecture délicate et le code de l'échantillon est spaghettis de base !! Mais, d'après ce que je l'entends, il est le meilleur disponible. Si quelqu'un d'autre sur Stack Overflow sait mieux, s'il vous plaît ne me corriger comme je ne peux pas croire non plus.

Answer 4

krigeage est l'une des méthodes lourdes pour ce faire, en particulier dans le domaine des SIG . Il a plusieurs propriétés mathématiques belles - l'inconvénient est qu'il peut être lent en fonction de votre variogramme.

Si vous voulez quelque chose de plus simple, il y a beaucoup de routines d'interpolation qui gèrent ce bien. Si vous pouvez obtenir Ahold d'une copie de Recettes numériques , chapitre 3 est consacré à expliquer de nombreuses variantes pour l'interpolation, et comprend des exemples de code et la description de leurs propriétés fonctionnelles.

Answer 5

  

est l'algorithme pour calculer la   fonction d'origine en ce que l'image en   Tout d'abord, les points de données fournies   avec des poids.

Il est possible. Si vous commencez avec des points simples, vous finirez toujours avec des cercles, mais si vous le poids des points de données et de prendre cela en compte, vous pouvez écraser les cercles dans des ovales comme dans l'image ..

La raison pour laquelle vous se retrouver avec des polygones est que vous utilisez une fonction discrète dans votre calcul -. Tout d'abord, vous trouvez la couleur la plus proche, vous déterminez la couleur

Vous devriez plutôt regarder dans les algorithmes de gradient qui attribue une couleur pour un point en fonction de la distance et le poids des trois points de données qui enserrent ce point dans un triangle.

algorithme gradient

Cela dépend de ce que vous essayez d'afficher. Un algorithme simpliste serait:

Pour chaque pixel:

• Trouvez les trois points qui forment le plus petit triangle qui entourent ce pixel

• Définir ce point à la couleur (système de couleurs HSV) qui est affectée par le poids et la distance à chaque point de donnée:

  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

J'utilise +, mais vous devez déterminer l'algorithme « en moyenne » adapté à votre application.

-Adam

Answer 6

Interpolation de surface semble être un problème difficile et mathématique. Une autre façon de le faire est moins cher:

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

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

Fonction Exemple de poids:

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

Il a tout à fait l'approche de la force brute, mais il est simple.

Answer 7

Je mis en œuvre quelque chose comme ça dans Winamp AVS il y a un certain temps. Il utilise une approche de type « metaballs » de calcul de l'inverse au carré distance (pour éviter la sqrt pour la vitesse) à partir de chaque point de données, le recouvrement il (par exemple à 1,0), et en prenant une somme de ces distances pour chaque point sur la grille 2D. Cela vous donnera une carte couleur / hauteur variable en douceur.

Si vous voulez regarder le code, son dans le préréglage « Glowy » de mon J10 AVS Emballez .

EDIT: Il suffit de regarder ce que j'ajouté un autre jazz pour le faire paraître plus jolie, la partie qui est la plus importante est:

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;

qui prend la somme des 6 points. Tout fait d'autre pour les valeurs de sortie rouge, vert et bleu est de rendre plus jolie. 6 points est pas grand-chose, mais garder à l'esprit que je tentais de faire cette course en temps réel sur une grille 320x200 sur une machine 400MHz quand il était neuf (ce qu'il fait à ~ 20fps). :)

Remplacez les = rouge, vert et bleu = = ... avec des lignes rouges = d; etc ... pour voir ce que je veux dire. Tous les joliesse disparaît et il ne vous reste une image demi-teinte de blobs variant en douceur autour des points de données.

Une autre edit: j'ai oublié de dire « s » est le poids partagé pour tous les points, changer pour chacun d'eux donne des poids individuels à chaque point, par exemple d1 = 2 / (...) et d2 = 1 / (...) donnerait d1 deux fois plus de hauteur en son centre comme d2. Vous pouvez également limiter l'expression en bas avec quelque chose comme d1 = 2 / max (..., 1.0) pour lisser les sommets des points afin qu'ils ne culminent pas à l'infini au milieu. :)

Désolé pour le désordre de la réponse ... Je pensais que l'affichage de l'exemple de code serait assez bon mais mon code d'inspection est de lire confus et difficile. : (

Answer 8

Je sais que cela est tout à fait une vieille question, mais je suis tombé sur tout en essayant de résoudre un problème similaire.

Il y a un projet open source appelé Surfit qui implémente exactement ce type de fonctionnalité.

Answer 9

Vous cherchez quelque chose que appels de Blender " metaballs " ( Wikipedia article avec des liens , exemple ). Pensez-y de cette façon:

Vos objets sont des cônes qui collent hors du sol. Ils sont tous et le poids des paraboles indique dans quelle mesure ils collent hors du sol. Vous pouvez également faire tous la même hauteur et régler la « platitude » de la parabole en conséquence, si un grand poids rend le cône très large tandis qu'un faible poids rend forte. Peut-être même à la fois à un certain degré.

Je vous suggère de mettre en œuvre cela et voir à quoi il ressemble.

Ensuite, vous devez accrocher un chiffon ou d'une feuille de caoutchouc sur le résultat. Le tissu étirera par un certain nombre et il se bloque généralement en raison de la gravité. Les cônes garder.

Tant que vous êtes à proximité du centre d'un cône, la coordonnée Z est que la position sur la surface du cône. En quittant le centre du cône, la gravité commence à tirer vers le bas et l'influence des autres cônes se développe.