Discussion :

[gragaou]

Bonjour, je me confronte aujourd'hui pour l'une de mes unités d'enseignement à la réalisation de l'algorithme de QuickHull en 3D.

Cependant je n'arrive pas à voir comment réaliser une des étapes :

Quand on sélectionne une face de notre polyèdre et que l'on cherche le point le plus éloigné, comment une fois celui ci identifié, peux t-on savoir, qu'un point, des faces adjacentes, à la face en cours de traitement, ont "la vision" sur le point le plus éloigné?

Plus d'infos : http://www.cse.unsw.edu.au/~lambert/...quickhull.html ( Part Three Dimensions )

Merci d'avance.

[gragaou]

Ci dessous quelques pistes que j'ai pu explorer sans trouver de réponses concrètes :

• Avec le volume signé
• Angle entre deux plans
• Intersection de droite et d'un triangle (espace)
• Transformation vers un plan

[sweetasnz]

Plus d'infos : http://www.cse.unsw.edu.au/~lambert/...quickhull.html ( Part Three Dimensions )

Bonjour,
en comparant la méthode 2D et 3D, c'est vrai que le texte est un peu flou concernant la suppression du "point qui serait vu par les autres triangles" en 3D et même en 2D, aucune précision n'est donnée quant au verbe "see" (pas très explicite...)
Est-ce ton seul support pour implémenter cette algo?
Si c'est le cas, tu risques de passer du temps à programmer qq chose de faux ... je te conseille donc de voir si tu ne peux pas t'en procurer un autre.

Bon courage

[gragaou]

Je ne la trouve pas si flou que cela en fait . Ce n'est pas la démarche de l'algorithme que je ne comprends mais plutot la méthode mathématique permettant cela.

[sweetasnz]

Ci dessous quelques pistes que j'ai pu explorer sans trouver de réponses concrètes :

• Avec le volume signé
• Angle entre deux plans
• Intersection de droite et d'un triangle (espace)
• Transformation vers un plan

Ok,
En premier lieu, j'aurais penché plus pour le volume délimité d'un coté par le plan du triangle. Donc si un point appartient à plusieurs volumes... tu supprimes tous les triangles correspondants...
Pour moi cela reste pas très clair néanmoins, même avec une formation orientée calcul scientifique.
As tu accès à des bases de données d'articles scientifiques publiés qui utiliseraient cette méthode? cela pourrait s'avérer utile si plusieurs concepts sont utilisés (comme ceux que tu cites dans ta liste).
Dans tous les cas, cela reste un problème d'optimisation.

par exemple :
http://www.google.fr/url?sa=t&rct=j&...GBWlpvNbNWE5-w

[gragaou]

Donc si un point appartient à plusieurs volumes... tu supprimes tous les triangles correspondants...

Dans QuickHull en 3D toutes les faces de notre polyèdre sont des triangles (avant post traitement) . Et lors du moment où l'on traite cette face on fait :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
/* f la face que l'on traite, pts l'ensemble des points "au-dessus" 
du demi-espace défini par le face f */ 
 
Procédure traitement_face (face f, ensemble pts)
 
    further := point_le_plus_eloigné_de_f /* appartenant à pts */
 
    pour toute les faces adjacentes à f faire :
        si le point non commun de la face adjacente "a la vision" sur further
        ajouter cette face à la liste a supprimer
    fin faire
 
    supprimer f + la liste des faces a supprimer
 
    ajouter des faces (triangles) entre further et les points consécutifs des faces supprimées
    (sauf les points qui formaient l'adjacence entre les faces supprimées) /* ambigü mais je voit la démarche*/
 
Fin procédure