Savoir si un point de l'espace est ou n'est pas dans un triangle (de l'espace lui aussi)

Soyez le premier à donner votre avis sur cette source.

Vue 5 521 fois - Téléchargée 370 fois

Description

Voila un principe que j'ai mis au point pour un travaille que je faisais sur DirectX.
Ce code marche pour tous les triangles dans l'espace.

Pour savoir si un point est dans un triangle il faut savoir qu'un triangle c'est trois point A, B, C definit dans E (l'espace).
Soit M le point que nous testerons.

Dans le triangle ABC on a deux repere (A;AB;AC) et (B;BC;BA), bon il y en a d'autre mais ceux la suffiront.

Si on exprime AM dans le repere (A;AB;AC), on aura
AM = alpha * AB + betha * AC
Si M est dans le secteur angulaire BAC, alpha et betha seront positif.
on refait pareille avec BM dans le repere (B;BC;BA) et si M est dans le secteur angulaire ABC alors les coeficients seront positifs

Si un point M se trouve dans le secteur angulair BAC et ABC alors M est dans le triangle ABC.

en bref, voici le code :

Source / Exemple :


Option Explicit

Public Type D3DVECTOR
    X As Double
    Y As Double
    z As Double
End Type
  
Public Function C3D(X, Y, z) As D3DVECTOR ' Pour tracer des vecteur et des
C3D.X = X: C3D.Y = Y: C3D.z = z ' points plus rapidement
End Function
  
Public Sub CoefficientVecteur(VecteurI As D3DVECTOR, VecteurJ As D3DVECTOR, _
            VecteurM As D3DVECTOR, Ret_CoefI, Ret_CoefJ, Ret_IsPossible As Boolean)
' Pour exprimer un vecteur en
' fonction de deux autres
  
Dim Alpha As Double, Betha   As Double ' Les coeficiants des vecteurs
Dim AB As D3DVECTOR, AC As D3DVECTOR, aM As D3DVECTOR
Dim A As Double, B   As Double, C As Double, D As Double, N As Byte
AB = VecteurI: AC = VecteurJ: aM = VecteurM
    If Not AB.X = 0 Then ' On ne peut pas prendre tous les
        A = aM.X / AB.X ' vecteurs dans n'importe quel sens
        B = -AC.X / AB.X ' Ici on doit diviser par AB.x il ne
        N = 1: GoTo CalculeBetha ' donc pas etre egal a Zéro.
    End If
  
' Ce qui donne Alpha = AM.x/AB.x - Betha * AC.X/AB.X
' Avec A = AM.x/AB.x et B = -AC.X/AB.X
  
CalculeAlphaABy:
    If Not AB.Y = 0 Then ' Même probleme ici pour AB.y
        A = aM.Y / AB.Y
        B = -AC.Y / AB.Y
        N = 2: GoTo CalculeBetha
    End If
  
' Ce qui donne Alpha = AM.y/AB.y - Betha * AC.y/AB.y
' Avec A = AM.y/AB.y et B = -AC.y/AB.y
  
CalculeAlphaABz:
    If Not AB.z = 0 Then ' Là egalement pour AB.z
        A = aM.z / AB.z
        B = -AC.z / AB.z
        N = 3: GoTo CalculeBetha
    End If
  
' Ce qui donne Alpha = AM.x/AB.x - Betha * AC.X/AB.X
' Avec A = AM.x/AB.x et B = -AC.X/AB.X
  
Ret_IsPossible = False
Exit Sub
' Si rien est possible et bien tant
' pis on quitte le sub et
' Ret_IsPossible aura la valeur FALSE
  
' On a exprimer Alpha en fonction de Betha, maintenant on termine le calcule
CalculeBetha:
    If Not N = 1 And Not (B * AB.X + AC.X = 0) Then ' Si on n'a pas exprimer Alpha en
        Betha = (aM.X - A * AB.X) / (B * AB.X + AC.X) ' fonction des X
        GoTo CalculeAlpha
    End If
    If Not N = 2 And Not (B * AB.Y + AC.Y = 0) Then ' Si on n'a pas exprimer Alpha en
        Betha = (aM.Y - A * AB.Y) / (B * AB.Y + AC.Y) ' fonction des y
        GoTo CalculeAlpha
    End If
    If Not N = 3 And Not (B * AB.z + AC.z = 0) Then ' Si on n'a pas exprimer Alpha en
        Betha = (aM.z - A * AB.z) / (B * AB.z + AC.z) ' fonction des z
        GoTo CalculeAlpha
    End If
    If N = 1 Then GoTo CalculeAlphaABy
' Si (B * AB.y + AC.y = 0) et que
' (B * AB.z + AC.z = 0) alors on
' essai de definir Alpha en fonction
' d'une autre variable
    If N = 2 Then GoTo CalculeAlphaABz ' Meme explication
    Exit Sub
CalculeAlpha: Alpha = A + B * Betha ' On definit Alpha
Ret_CoefI = Alpha: Ret_CoefJ = Betha ' On renvoit les valeurs
Ret_IsPossible = True ' Les coeficiants existes
End Sub
' Si les coeficiant exist ou pas on peut savoir si un point est coplanaire aux trois autres
  
  
' Pour cette Function Voir l'explication du code
Public Function IsPointInTRGL(TRGLpt1 As D3DVECTOR, TRGLpt2 As D3DVECTOR, _
                TRGLpt3 As D3DVECTOR, PtTest As D3DVECTOR) As Boolean
Dim V1 As D3DVECTOR, V2 As D3DVECTOR, V3 As D3DVECTOR, _
S1 As Byte, S2 As Byte, S3 As Byte, S4 As Byte, S5 As Byte, _
S6 As Byte, Ri As Single, Rj As Single, Possible As Boolean
V1 = CreerVecteur(TRGLpt1, TRGLpt2)
V2 = CreerVecteur(TRGLpt1, TRGLpt3)
V3 = CreerVecteur(TRGLpt1, PtTest)
CoefficientVecteur V1, V2, V3, Ri, Rj, Possible
If Not Possible Then Exit Function ' Si ce n'est pas possible, c'est que
' les points ne sont pas coplanaire donc pas dans le triangle
S1 = Sgn(Ri) + 1: S2 = Sgn(Rj) + 1
V1 = CreerVecteur(TRGLpt2, TRGLpt1)
V2 = CreerVecteur(TRGLpt2, TRGLpt3)
V3 = CreerVecteur(TRGLpt2, PtTest)
CoefficientVecteur V1, V2, V3, Ri, Rj, Possible
If Not Possible Then Exit Function
S3 = Sgn(Ri) + 1: S4 = Sgn(Rj) + 1
If S1 >= 1 Then
    If S2 >= 1 Then
        If S3 >= 1 Then
            If S4 >= 1 Then
                IsPointInTRGL = True
            End If
        End If
    End If
End If
End Function
  
Public Function CreerVecteur(Pt1 As D3DVECTOR, Pt2 As D3DVECTOR) As D3DVECTOR ' Pour crer un vecteur à
CreerVecteur = C3D(Pt2.X - Pt1.X, Pt2.Y - Pt1.Y, Pt2.z - Pt1.z) ' partir de deux points
End Function

Conclusion :


Pour l'utiliser il vaut mieu le mettre dans un module sinon il faut changer les public par des private mais bon ...
Ce code est entierement de moi.
Je n'ai vu aucun code qui definisait un point dans un triangle en fonction de vecteurs. S'ils existe je tien a m'en excuser.

Ce n'est qu'un petit code je prepare pour l'instant un moteur 3D genre TrueVision3D, cela ne va pas trop tarder mais d'ici quelque semaine je mettrais une ebauche quasi definitive (et gratuite contrairement a TrueVision3D) et entierement de moi.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Neron2005
Messages postés
63
Date d'inscription
dimanche 5 novembre 2000
Statut
Membre
Dernière intervention
1 décembre 2013
-
J'oubliais de dire que si l'on veut l'utiliser dans le plan (càd sur la page form), il sufit de mettre la valeur 0 aux coordonées z. C'est juste un rappel mais pas necessairement inutile.
MadM@tt
Messages postés
2215
Date d'inscription
mardi 11 novembre 2003
Statut
Membre
Dernière intervention
16 juillet 2009
-
J'ai adoré la présentation de la source, ça permet de comprendre le fonctionnement sans se casser le crane à déchiffrer le code, ça fait gagner un temps fou et pas tout le monde le fait. Bravo pour ça.

Sinon :
# If S1 >= 0 Then
# If S2 >= 0 Then
# If S3 >= 0 Then
# If S4 >= 0 Then
# If S5 >= 0 Then
# If S6 >= 0 Then
# IsPointInTRGL = True
# End If
# End If
# End If
# End If
# End If
# End If
à remplacer par :
If S1>=0 and S2>=0 and .... Then

Endif

Puis sinon pour tes goto, enfin c'est un avis personnel, mais des fois c'est plus parlant de mettre un mot ou une phrase plutot qu'un numéro

Et c'est marrant le colorateur syntaxique ne reconnait meme pas le mot clé rem... ^^
(PS : je croit que coefficient, ben ça s'écrit comme ça)


Bonne continuation
A+
cs_EBArtSoft
Messages postés
4531
Date d'inscription
dimanche 29 septembre 2002
Statut
Modérateur
Dernière intervention
22 avril 2019
5 -
Tu peux aussi employé PlaneIntersectLine si l'intersection correspond a ton point alors il est bien dans la surface du triangle.

@+
Neron2005
Messages postés
63
Date d'inscription
dimanche 5 novembre 2000
Statut
Membre
Dernière intervention
1 décembre 2013
-
Alors MadM@tt ecrire le code de cette facon :

# If S1 >= 0 Then
# If S2 >= 0 Then
# If S3 >= 0 Then
# If S4 >= 0 Then
# If S5 >= 0 Then
# If S6 >= 0 Then
# IsPointInTRGL = True
# End If
# End If
# End If
# End If
# End If
# End If

permet de gagner du temps (exemple : si S3 < 0, il n'y aurra que trois calcule alors que faire If S1>=0 and S2>=0 and .... Then, il y aurra quoi qu'il arrive 6 calcules).
Si on ne fait cette action qu'une fois, pourquoi pas, mais si on veut comme moi le faire une vingtaine de fois par seconde, c'est toujours bien de gagnez quelques centieme.
us_30
Messages postés
2117
Date d'inscription
lundi 11 avril 2005
Statut
Membre
Dernière intervention
14 mars 2016
7 -
Bonsoir,

Une simple question... Si je comprend bien, le but n'est pas d'en faire une application mathématique, mais de l'utiliser pour de la 3D. Dans ces conditions, les déclarations des variables en Double, ne seraient-elles pas suffisantes en LONG ? (donc plus rapide, et valeurs entières...)

Dans le même thème, il me semble que les lignes :
"Dim Alpha, Betha ' Les coeficiants des vecteurs "
"Dim A, B, C, d, N "
gagneraient à être déclarées avec le type. Actuellement, ces variables sont en Variant, donc peu rapide et non nécessaire ici... et même chose dans "IsPointInTRGL".

Amicalement,
Us.

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.