Savoir si un point (3d) est dans un triangle / pyramide

Soyez le premier à donner votre avis sur cette source.

Vue 6 861 fois - Téléchargée 403 fois

Description

Voici la généralisation directe de ma source pour le cas 2D. Je poste cette source car plusieurs messages circulaient sur ce sujet

Source / Exemple :


' tout se trouve dans le zip, mais voici ici la fonction principale du programme

    ' entrée des données
    For i = 1 To 3
        A(i) = CDbl(txtA(i - 1).Text)
        B(i) = CDbl(txtB(i - 1).Text)
        C(i) = CDbl(txtC(i - 1).Text)
        D(i) = CDbl(txtD(i - 1).Text)
        P(i) = CDbl(txtP(i - 1).Text) - A(i)
        u(i) = B(i) - A(i)
        v(i) = C(i) - A(i)
        w(i) = D(i) - A(i)
    Next
    
    ' pour le triangle, le vecteur w est choisi (arbitrairement) comme u x v
    If optType(0).Value Then
        w(1) = u(2) * v(3) - u(3) * v(2)
        w(2) = u(3) * v(1) - u(1) * v(3)
        w(3) = u(1) * v(2) - u(2) * v(1)
    End If
    
    ' matrice de changement de base
    For i = 1 To 3
        M(i, 1) = u(i)
        M(i, 2) = v(i)
        M(i, 3) = w(i)
    Next
    Inverse M, MInv
    
    ' Q = nouvelles coordonnées du point P
    Q(1) = MInv(1, 1) * P(1) + MInv(1, 2) * P(2) + MInv(1, 3) * P(3)
    Q(2) = MInv(2, 1) * P(1) + MInv(2, 2) * P(2) + MInv(2, 3) * P(3)
    Q(3) = MInv(3, 1) * P(1) + MInv(3, 2) * P(2) + MInv(3, 3) * P(3)
    
    ' vérification de la position du point P
    If optType(0).Value Then Resultat = 2 Else Resultat = 4
    If Q(1) >= -DELTA And Q(2) >= -DELTA And Q(3) >= -DELTA And _
       Q(1) + Q(2) + Q(3) <= 1 + DELTA Then
        If optType(1).Value Or Abs(Q(3)) < DELTA Then
            Resultat = Resultat - 1
        End If
    End If
    
    ' affichage du résultat
    lblResultat.Visible = True
    Select Case Resultat
        Case 1: strResultat = "le point P se trouve dans le triangle ABC"
        Case 2: strResultat = "le point P ne se trouve pas dans le triangle ABC"
        Case 3: strResultat = "le point P se trouve dans la pyramide ABCD"
        Case 4: strResultat = "le point P ne se trouve pas dans la pyramide ABCD"
    End Select
    lblResultat.Caption = strResultat

Conclusion :


L'interface est très rudimentaire, le but étant d'utiliser les fonctions dans vos programmes. Ce code est donc fait uniquement pour comprendre comment ça marche, alors n'essayez pas de rentrer autre chose que des chiffres dans les cases de coordonnées, je n'ai fait aucun contrôle de type de données!

Pour savoir si un point P (3D) se trouve dans un triangle ABC, il existe une autre méthode que celle donnée ici:
on projette le triangle ABC et le point P sur les plans XY, XZ et YZ (càd qu'on "oublie" une composante à chaque fois), et on vérifie avec le programme 2D (calculs légèrement plus simples) que la projection de P se trouve les 3 fois à l'intérieur de la projection du triangle.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Vb Lover
Messages postés
221
Date d'inscription
vendredi 30 novembre 2001
Statut
Membre
Dernière intervention
13 février 2010
3 -
ok, je n'ai en effet rien fait pour optimiser la rapidité, c'était simplement pour donner les équations à utiliser. Maintenant, c'est à ça que sert VB france, c'est de mélanger les idées pour avoir un résultat final meilleur!
Neron2005
Messages postés
63
Date d'inscription
dimanche 5 novembre 2000
Statut
Membre
Dernière intervention
1 décembre 2013
-
bon je vien de faire quelque test sur mon ordi de rapidité et ta fonction est 80 fois plus lente que celle de directX, ca s'explique notament par l'utilisation des tableaux alors que directx utilise le type D3DMatrix (m11 m12 m13 ... m43 m44).
sinon tu devrai transforme tes tableau et ca irai beaucoup plus vite.
par ordre de comparaison, 1 000 000 de fois 1.43 secondes en moyenne avec directX.
100 000 fois : 8.32 secondes pour ta fonction.
bon ma fonction est vraisemblablement plus rapide.
Neron2005
Messages postés
63
Date d'inscription
dimanche 5 novembre 2000
Statut
Membre
Dernière intervention
1 décembre 2013
-
Bien sur mais si ta code ne sert qu'a une demonstration elle n'a finalement pas d'interet.
Si j'ai fait cette fonction c'est qu'elle fait parti d'un ensemenble de test de collision en 3D avec un grand nombre de fonction qui utilise directX.
C'est vrai que sortir directX pour une si petite fonction est assez ridicule mais il faut la voir dans l'ensemble.
Vb Lover
Messages postés
221
Date d'inscription
vendredi 30 novembre 2001
Statut
Membre
Dernière intervention
13 février 2010
3 -
ok, ça utilise en effet directX pour faire finalement exactement la même chose que mon programme. Donc à part pour la partie de l'inversion de matrice qui peut-être est plus rapide sous directX (mais j'en doute, car mon programme utilise la réponse explicite qui n'utilise que quelques * et +), il me semble que faire appel à une librairie ne vaut pas la peine... en résumé pour les arguments de Neron2005:

- elle marche sous directX8
mon prog aussi car il n'a même pas besoin de l'utiliser!

- elle est rapide
j'attends un test comparatif entre mon prog et celui de directX8, et sans être chauvin, comme il n'y a que très peu d'opérations avec des matrices, je suis sûr qu'il vaut mieux utiliser mon prog avec quelques opérations très basiques plutôt que de charger toute l'artillerie directX...

- permet une marge d'erreur ca un point ne peut pas exactement etre dans un plan pas en prog du moins
c'est exactement ce que j'ai fait avec la variable "DELTA", qui dans ton cas particulier vaut 0.001 (entre nous on peut quand même travailler avec un peu plus de précision, du genre 10^(-6)...)

bref, de toute façon c'est sympa de montrer qu'on peut utiliser directX, mais j'ajouterais quand même 2 arguments pour ne pas le faire:
1) il n'y a quasiment pas d'opérations matricielles pour ce problème, et pour des choses si simples je doute que directX apporte quelque chose
2) il me semble que ce prog aide plus pour la compréhension mathématique d'un problème donné, plutôt que pour l'utilisation à outrance dans un programme donné (quel programme aurait besoin de savoir 10'000 fois par sec. si un point est dans un triangle ou non?). Ainsi, ne faire recours qu'au fonction de base de VB permet de TOUT comprendre, ce qui n'est pas forcément le cas avec l'appel de librairies externes
Neron2005
Messages postés
63
Date d'inscription
dimanche 5 novembre 2000
Statut
Membre
Dernière intervention
1 décembre 2013
-
Alors si tu t'interesse au directX voila une petit fonction qui resoud becoup de probleme :
- elle marche sous directX8
- elle est rapide
- permet une marge d'erreur ca un point ne peut pas exactement etre dans un plan pas en prog du moins



' Description : Exprime V dans le repere (O,i,j,k)
Public Sub FZ3DVec3Coords( _
VOut As D3DVECTOR, _
O As D3DVECTOR, I As D3DVECTOR, J As D3DVECTOR, k As D3DVECTOR, _
v As D3DVECTOR)


Dim matEq As D3DMATRIX, matSlv As D3DMATRIX

With matEq
.m11 I.X: .m12 J.X: .m13 = k.X: .m14 = 0
.m21 I.Y: .m22 J.Y: .m23 = k.Y: .m24 = 0
.m31 I.z: .m32 J.z: .m33 = k.z: .m34 = 0
.m41 0: .m42 0: .m43 = 0: .m44 = 1
End With
With matSlv
.m11 = v.X - O.X
.m21 = v.Y - O.Y
.m31 = v.z - O.z
.m41 = 0
End With

D3DXMatrixInverse matEq, 1, matEq
D3DXMatrixMultiply matSlv, matEq, matSlv

VOut.X = matSlv.m11
VOut.Y = matSlv.m21
VOut.z = matSlv.m31

End Sub


Private Sub Form_MouseMove(Button As Integer, Shift As Integer, X As Single, Y As Single)

Dim A As D3DVECTOR, B As D3DVECTOR, C As D3DVECTOR
Dim v1 As D3DVECTOR, v2 As D3DVECTOR, v3 As D3DVECTOR, v As D3DVECTOR
Dim VTest As D3DVECTOR

A.X 500: A.Y 0: A.z = 0
B.X 6000: B.Y 500: B.z = 0
C.X 500: C.Y 7000: C.z = 10
VTest.X X: VTest.Y Y: VTest.z = 10

Cls
Line (A.X, A.Y)-(B.X, B.Y)
Line (A.X, A.Y)-(C.X, C.Y)
Line (C.X, C.Y)-(B.X, B.Y)
Me.DrawWidth = 5
PSet (VTest.X, VTest.Y), vbYellow
Me.DrawWidth = 1

D3DXVec3Subtract v1, B, A
D3DXVec3Subtract v2, C, A
D3DXVec3Cross v3, v1, v2
D3DXVec3Normalize v3, v3

FZ3DVec3Coords v, A, v1, v2, v3, VTest

If (v.X + v.Y) <= 1 And v.X >= 0 And v.X <= 1 And v.Y > 0 And v.Y < 1 Then
If Abs(v.z) < 0.001 Then
Caption = "Pt dans le triangle"
' le point est dans le triangle d'une distance < 0.001
Else
Caption = "progection dans triangle, d'une distance au plan de " + CStr(Abs(v.z))
End If
Else
Caption = "Point en dehors du triangle, d'une distance au plan de " + CStr(Abs(v.z))
End If


End Sub

' si quelqu'un a envie de la faire marcher il faut d'abord referencer la DLL de DirectX8.

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.