simplification de terrain

Version imprimable

08/04/2007, 00h15
Invité

simplification de terrain

Salut

J'ai un MNT (modèle numérique de terrain) dont je me sert pour afficher une vue 3D (openGL + C#) du dit terrain. Les données sont stockées dans un tableau 2D et chaque élément représente une altitude. Ce données sont ensuite utilisées pour afficher mon terrain en 3D à l'aide de TRIANGLE_STRIP.
Jusque-là tout va bien.
Les problèmes commence si j'utilise des MNT de grande taille. 700 x 480 points, soit 336'000 points.
Je suis donc à la recherche d'un algorithme permettant de simplifier ces terrains. J'ai trouvé pas mal de documents chez mon amis google, mais dans la plupart des cas ça reste très théorique, alors que je cherche plutôt un cas pratique que je puisse utiliser dans mon projet.
08/04/2007, 22h47
pseudocode

Citation:

Envoyé par JuTs

Je suis donc à la recherche d'un algorithme permettant de simplifier ces terrains. J'ai trouvé pas mal de documents chez mon amis google, mais dans la plupart des cas ça reste très théorique, alors que je cherche plutôt un cas pratique que je puisse utiliser dans mon projet.

Qu'est-ce que tu veux dire par "simplifier" ? réduire la taille de ton tableau 2D ? Dans ce cas tu va perdre en niveau de détail.

Un bon compromis entre taille et detail, c'est utiliser la technique du mipmapping. Mais je ne sais pas si on peut faire une implémentation efficace (memoire, fluidité) en openGL + C#.
09/04/2007, 01h10
souviron34

j'aurais bien un algo, si ce que tu veux c'est diminuer la mémoire existante, mais vu que c'est de l'optimisation, ça dépend beaucoup du langage, et du fait de savoir si c'est bien ça que tu veux....

Il faudrait savoir : sous quel OS tu travailles ?

en effet, sur tous les *n*xoides, en général aucun problème, à cause du système de swap. Sur Windows, c'est beaucoup plus limité..
09/04/2007, 02h47
Invité

> pseudocode

quelque chose dans ce genre là : http://eldeann7.chez-alice.fr/DEA/index.htm
mais pas forcément aussi complexe

> souviron34

Je suis sous Windows XP
09/04/2007, 12h36
souviron34

je reprends donc le commentaire de pseudocode :

que veux-tu simplifier ?

le nombre d'éléments ?
la taille de la matrice ?
le volume des données dans le programme ?
09/04/2007, 13h05
Invité

Le nombre d'éléments (triangles) affichés
09/04/2007, 13h24
souviron34

OK..

Ben je crois qu'alors tu n'as pas trop le choix de faire quelques maths....

Je suppose que tu n'as pas le choix de la méthode avec laquelle la triangulation est faite au départ ?

En tous cas, il y a une méthode de triangulation qui permet d'enlever les triangles un par un, sans tout recalculer ("incremental delete and build algorithm").

Il te faudra donc faire effectivement une simplification du maillage. Mais avec cette méthode je pense que tu peux la faire "égalitaire" (contrairement au dernier exemple de la page que tu as citée, qui part d'un coin) :

tu prends le premier sommet intérieur, tu élimines les triangles autour, en gardant le périmètre. Puis tu sautes à l'extérieur de ce périmètre pour reprendre le premier point intérieur, etc...

Tu devrais déjà arriver en une passe à diminuer d'un facteur 6 en gros.. Et si ça suffit pas tu itères...

Et sinon, tu prends les méthodes données par tes références, mais tu ne pourras pas te passer d'algos assez complexes....
09/04/2007, 13h56
pseudocode

Citation:

Envoyé par JuTs

Le nombre d'éléments (triangles) affichés

Ah ok. C'est de la simplification de mesh...

Bon, si la partie mathematique theorique ne t'interesse pas trop, voici de quoi plonger directement dans le code:

http://www.melax.com/polychop/gdmag.pdf
09/04/2007, 14h26
Invité

Citation:

Envoyé par souviron34

Je suppose que tu n'as pas le choix de la méthode avec laquelle la triangulation est faite au départ ?

Non, il s'agit d'un fichier ArcInfo ASCII grid ( http://en.wikipedia.org/wiki/ESRI_grid )

Citation:

Envoyé par souviron34

En tous cas, il y a une méthode de triangulation qui permet d'enlever les triangles un par un, sans tout recalculer ("incremental delete and build algorithm").

Il te faudra donc faire effectivement une simplification du maillage. Mais avec cette méthode je pense que tu peux la faire "égalitaire" (contrairement au dernier exemple de la page que tu as citée, qui part d'un coin) :

tu prends le premier sommet intérieur, tu élimines les triangles autour, en gardant le périmètre. Puis tu sautes à l'extérieur de ce périmètre pour reprendre le premier point intérieur, etc...

Tu devrais déjà arriver en une passe à diminuer d'un facteur 6 en gros.. Et si ça suffit pas tu itères...

Il y a plus qu'à essayer :mrgreen:

Citation:

Envoyé par souviron34

Et sinon, tu prends les méthodes données par tes références, mais tu ne pourras pas te passer d'algos assez complexes....

Je vais déjà commencer par quelque chose de simple. J'essaierai peut-être quelque chose de plus approfondi si j'ai le temps nécessaire
10/04/2007, 02h25
kromartien

Waouhh ! J'avais vu un truc comme ça quand je furetais sur la création de jeux vidéos libres.
Génération de texture 3D purement aléatoire, puis lissage à l'aide de l'algorithme approprié.
Désolé, je ne me souviens pas de la référence. Il ne me semble pas que ce soit une triangulation pure et simple. En fait, le problème de la texture est le suivant :

(1)
ou elle est directement générée aléatoirement avec un nombre de points qui ne doit pas bouger, auquel cas on fait un algo de sélection de points caractéristiques (sélection aléatoire, ou avec critère sur la valeur (altitude) du point, ou simplement sélection des points à intervalles réguliers), puis reconstruction par interpolation entre les points sélectionnés.

(2)
ou elle est générée aléatoirement et alors on interpole entre chaque point créé aléatoirement en subdivisant la texture, mais ça donne quelque chose de vraiment chaotique.

La méthode (1) permet un contrôle assez fin (par choix des points caractéristiques) je crois de la nature de la texture : pentes raides, arrondies, fort/faible vallonement, etc

Excusez, ce message est hors sujet. Je le laisse quand même pour mémoire
16/04/2007, 21h43
Invité

Bon, j'ai finalement tenté d'appliquer la méthode indiquée dans l'article de pseudocode.

J'ai tenté de l'appliquer à un simple cube (comme dans l'article) ainsi que sur le modèle du lapin. ça fonctionne plutôt bien. Par contre quand je l'applique à mon terrain, les résultats sont nettement moins bon. le script à plutôt tendance à supprimer de grande bandes de triangle sur les bord du terrain. seuls quelques vertex sont fusionnés au milieu. Je vais essayer de débugger mais je n'ai vraiment aucune idée pourquoi cela ne fonctionne pas avec mon terrain. Si quelqu'un à une hypothèse.

Remarque : pour le code, j'ai utilisé la source du script de l'article. On peut le trouver sur le site de gdmag.com

Citation:

Envoyé par JuTs

Si quelqu'un à une hypothèse.

Peut-etre que la fonction de calcul du cout favorise les bords car il y a moins de triangles adjacents ? :roll:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
float ComputeEdgeCollapseCost(Vertex *u,Vertex *v) {
	// if we collapse edge uv by moving u to v then how 
	// much different will the model change, i.e. how much "error".
	// Texture, vertex normal, and border vertex code was removed
	// to keep this demo as simple as possible.
	// The method of determining cost was designed in order 
	// to exploit small and coplanar regions for
	// effective polygon reduction.
	// Is is possible to add some checks here to see if "folds"
	// would be generated.  i.e. normal of a remaining face gets
	// flipped.  I never seemed to run into this problem and
	// therefore never added code to detect this case.
...

17/04/2007, 00h36
souviron34

je vous signale que c'est en partie ce que j'avais prévu ;)

Citation:

Il te faudra donc faire effectivement une simplification du maillage. Mais avec cette méthode je pense que tu peux la faire "égalitaire" (contrairement au dernier exemple de la page que tu as citée, qui part d'un coin) :

:yaisse2:

Citation:
Envoyé par pseudocode
Peut-etre que la fonction de calcul du cout favorise les bords car il y a moins de triangles adjacents ? :roll:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 float ComputeEdgeCollapseCost(Vertex *u,Vertex *v) { // if we collapse edge uv by moving u to v then how // much different will the model change, i.e. how much "error". // Texture, vertex normal, and border vertex code was removed // to keep this demo as simple as possible. // The method of determining cost was designed in order // to exploit small and coplanar regions for // effective polygon reduction. // Is is possible to add some checks here to see if "folds" // would be generated. i.e. normal of a remaining face gets // flipped. I never seemed to run into this problem and // therefore never added code to detect this case. ...
Effectivement c'était ça. J'ai modifié le code de façon à ce qu'un vertex qui se trouve sur le bord de mon terrain ne puisse pas être supprimé.

Dernier problème : le temps d'exécution.

Dans la fonction de recherche du vertex ayant le coût minimum il est écrit :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 private TOVertex MinimumCostEdge() { // Find the edge that when collapsed will affect model the least. // This funtion actually returns a Vertex, the second vertex // of the edge (collapse candidate) is stored in the vertex data. // Serious optimization opportunity here: this function currently // does a sequential search through an unsorted list :-( // Our algorithm could be O(n*lg(n)) instead of O(n*n) TOVertex tmp = vertices[0]; for (int i = 0; i < vertices.Count; i++) { if (vertices[i].pObjdist < tmp.pObjdist) { tmp = vertices[i]; } } return tmp; }
Le problème est que je ne vois pas comment faire. Si je trie les élément de ma liste, les indices ne seront plus les même (non ?). Or comme la liste de triangle contient les indice dans la liste des vertex pour chaque triangle, ceux-ci seront changés aussi.

17/04/2007, 17h22
ol9245

tu crée un dictionnaire et tu le trie ?
tu accède aux données via le dictionnaire trié ?
OL
17/04/2007, 17h58
souviron34

Citation:

Envoyé par JuTs

...Le problème est que je ne vois pas comment faire. Si je trie les élément de ma liste, les indices ne seront plus les même (non ?). Or comme la liste de triangle contient les indice dans la liste des vertex pour chaque triangle, ceux-ci seront changés aussi.

Ce que j'ai fait dans des cas pareils était de créer un tableau indexé : un tableau de structure contenant l'adresse de l'élément et son numéro dans le tableau. Tu tries là-dessus, et tu passes dans le tableau par :

Exemple :

tu as un tableau par exemple reel : tableau[MAX_VALEURS]

tu crée une structure :

PointeurElement { adresse_element , numero )

Puis un tableau de telles structures :

tableau_structures

Tu l'initialises en stockant au fur et à mesure les paramètres.

Tu fais ton tri.

Puis tu passes dans le tableau d'origine avec :

tableau[tableau_structure[i].numero]
19/04/2007, 21h50
Invité

Ok je vais voir si je peux faire quelque chose selon ce principe.

Est-ce qu'il y a un moyen (via Visual Studio, ou autre) de savoir quelle partie(s) du code occupent le plus de temps ?
23/04/2007, 15h22
Invité

Bon, j'ai essayé d'utiliser une liste triée mais ce n'est pas mieux. En fait j'ai déjà mesuré le temps occupé par chacune des méthodes. La méthode s'occupant de rechercher le vertex ayant le coût le plus faible occupe seulement 1.5 - 2% du temps d'exécution (en gros 0.5 à 1 seconde). Et le tri prends plus de temps que cela.

Par contre je me demande si utiliser des objets List<T> est un bon choix. Est-ce qu'il n'y aurait pas quelque chose de plus performant ?