Moteur 3d, arbre bsp, faces cachees ...

Soyez le premier à donner votre avis sur cette source.

Vue 10 880 fois - Téléchargée 856 fois

Description

================
explications :
================
Cette source montre comment on utilise les arbres BSP.
Les arbres BSP servent a faire de la 3D, maintenant on ne
les utilise plus car par exemple dans DirectX la methode du Z-buffer
est implementee. Avant les cartes graphiques n'etaient pas aussi puissantes,
les jeux 3D existants utilisaient la methode des BSP.

Le probleme est que l'on a une ensemble de triangles que l'on veut
afficher a l'ecran, mais on veut resourdre le probleme des faces cachees
i.e. que on veut voir seulement les triangles qui sont plus proches de nous.
Pour remedier a ce probleme on va "trier" les triangles. Si l'on partage
l'espace en deux partie avec un plan de normale N et qui passe pas P,
alors il y a 3 types de triangles :
1) ceux qui sont du cote positif i.e. PA.N >= 0 & PB.N >= 0 & PC.N >= 0
2) ceux qui sont du cote negatif i.e. PA.N < 0 & PB.N < 0 & PC.N < 0
3) ceux qui sont a cheval entre les deux cotes
pour le troisieme cas, on decoupe le triangle en trois autres triangles
et on se ramene au cas 1 et 2. (N.B. : un produit scalaire positif
signifie que deux vecteurs "sont du meme cote",
i.e. cos(angle)>=0 i.e. angle aigu)

Donc maintenant suppose que l'on est partionne l'ensemble de triangles.
On note D (pour Direction) le sens de notre vue.
Si on regarde dans le meme sans que N, i.e. D.N>=0, alors les triangles
qui sont les plus en arriere sont ceux de la categorie 2, et les plus
en avant sont ceux de la categorie 1. On va donc tracer d'abord ceux qui
sont derrier, puis ceux qui sont devant, a la fin on aura bien les
triangles de devant qui cacherons les triangles de derriere.
Bien-sur on fait cela recursivement : l'ensemble des triangles positifs
sont redecoupe, puis re-redecoupe... idem pour ceux negatifs.
On obtient donc un arbre que l'on nomme BSP.

Cette technique marche, et l'avantage c'est que par exemple dans un jeu
ou l'on veut faire un beau terrain (fixe pendant le jeu), on construit
l'arbre qu'un seule fois, on le met dans un fichier, et puis il suffit de
le charger. De plus la construction n'est pas un operation rapide, surtout
que l'on peut vouloir un arbre "pas trop" deequilibres. Eh oui, l'arbre peut
etre une liste : mini-theoreme : si la fgure est convexe (un sphere par exemple)
alors l'arbre est une liste, car par definition, les triangles sont toujours du
meme cote.

Ce programme permet de decouper grossierement la figure avec des plans
en se fondant sur la matrice d'inertie des sommets des triangles. Donc une sphere
pourra etre decoupee en plusieurs morceaux avant de passer a la decoupe suivant les
plans des triangles, comme cela l'arbre est plus equilibre. Cependant il y a des effets
de multiplication du nombres de triangles, car la decoupe transforme 1 triangle en
3 triangles !

Comme quoi la 3D ca peut devenir des mines de problemes pas si facile a resourdre.

Source / Exemple :


======================================
 les fonctions de l'API de MY3D est :
======================================
InitMy3D        : initialise l'environement 3D
CloseMy3D       : ferme l'environement 3D
PushTransform   : ajoute une tranformation
PopTransform    : supprime une transformation
AddTriangle     : ajoute une triangle
MakeBSP         : construit l'arbre BSP
DestroyBSP      : detruit l'arbre BSP
DrawBSP         : affiche la figure grace a l'arbre BSP

==================================
 les fonctions internes de MY3D :
==================================
dotProduct      : produit scalaire entre deux vecteurs
cmpEigen        : compare deux valeurs propres
eigenValue      : calcule une valeur propre
diag            : diagonalise une matrice 3x3 symetrique
setSymMat       : initialise une matrice 3x3 symetrique
part_space      : partition un ensemble de triangles suivant une plan (gere le decoupage de triangles)
build_triangle  : construit un arbre qu'avec des triangles comme plan de decoupe
build_plane     : construit un arbre en decoupe grossierement (voir matrice d'inertie...) puis passe au mode triangles
cleanBSP        : fonction qui supprime l'arbre BSP recursivement
paintTriangle   : dessine un triangle a l'ecran
paintBSP        : dessine recursivement a l'ecran la figure en gerant les faces cachees

Conclusion :


=============================
renvoi a d'autres sources :
=============================
  • DIAG : diagonalisation de matrices symetriques
  • SPHERE : pour la creation d'une sphere et d'un icosaedre
  • TORUS : pour la creation d'un beignet

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

blouw
Messages postés
4
Date d'inscription
jeudi 3 mars 2005
Statut
Membre
Dernière intervention
13 juillet 2007
-
le calcul de distance ca a po l'air mal
je vais essayer
merki
Saros
Messages postés
921
Date d'inscription
vendredi 20 décembre 2002
Statut
Membre
Dernière intervention
23 septembre 2010
-
Soit on fait une moyenne des distances, soit on créée un arbre BSP, comme ici
Soit on applique le Z-Buffering, plus puissant, plus long
blouw
Messages postés
4
Date d'inscription
jeudi 3 mars 2005
Statut
Membre
Dernière intervention
13 juillet 2007
-
ben en fait j'ai une tit question :
pour les face cachée ca va mais quand tu as plusieurs volumes qui peuvent se superposer comment tu fais pour savoir lequel est devand l'autre ?
Arnaud16022
Messages postés
1329
Date d'inscription
vendredi 15 août 2003
Statut
Membre
Dernière intervention
16 juin 2010
2 -
la tore plante
j'ai un instant cru que tu dessinais les triangles toi meme...en fait non lol mais bon a ce niveau pk pas.
sinon ya plein de trucs que j'aime pas la dedans mais je veux pas m'étendre, je suppose que c'est pasque je trouve ca trop compliqué mdr
sinon bah bon boulot qd meme :p
Arnaud16022
Messages postés
1329
Date d'inscription
vendredi 15 août 2003
Statut
Membre
Dernière intervention
16 juin 2010
2 -
"Les arbres BSP servent a faire de la 3D, maintenant on ne
les utilise plus car par exemple dans DirectX la methode du Z-buffer
est implementee. Avant les cartes graphiques n'etaient pas aussi puissantes,
les jeux 3D existants utilisaient la methode des BSP."
-> faux ! ils sont toujours utilisés... Quake3, par exemple, enregistre ses fichiers de map sous forme d'arbre bsp. ca permet d'accélérer le rendu de maniere scpectaculaire, meme en laissant le z-buffer activé, ce qui est nécessaire car on n'affiche rarement que la map (autres personnages, qui doivent etres cachés si ils sont derriere un mur par ex)

je regarde ton prog de suite
j'ajouterai que je n'ai jamais rien calé aux bsp-trees :D

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.