Classer les faces d'un solide en fonction de la profondeur en Z

Résolu
Phil_1857 Messages postés 1872 Date d'inscription   Statut Membre Dernière intervention   -  
Phil_1857 Messages postés 1872 Date d'inscription   Statut Membre Dernière intervention   -
Bonjour,

Soit un ensemble de faces définies par les coordonnées des extrémités d'arêtes
(un tableau des points avec leurs coordonnées XYZ, et un tableau des faces, chaque face étant
une liste des no de points tels que définis dans le 1er tableau)

Je cherche le moyen de classer les faces de la plus éloignée à la plus proche en profondeur, donc à obtenir une nouvelle liste ordonnée des no de faces

Les recherches sur le Net renvoient toutes aux algorithmes classiques permettant d'afficher
les faces au fur et à mesure de leur tri, (algorithme du peintre, etc, ...), moi, je veux seulement, dans une 1ere étape, les classer dans l'ordre

J'ai essayé en définissant un champ de rayons suivant Z, et en testant, pour chaque rayon, quelles faces il traverse, la coordonnée en Z de chaque point d'intersection permettant de les réordonner, mais ça n'a pas l'air parfait, notamment la liste résultante varie en fonction de la densité du champ de rayons ....

Si quelqu'un a une idée ..... :-)

Merci d'avance

Configuration: Windows / Edge 93.0.961.38
A voir également:

12 réponses

Réponse 1 / 12
Utilisateur anonyme
 
Tu peux mettre un exemple de quelques faces simple et du résultat attendu
0
Réponse 2 / 12
Phil_1857 Messages postés 1872 Date d'inscription   Statut Membre Dernière intervention   168
 
Bonjour,

Prenons un solide simple: un cube
Il est orienté dans l'espace, donc la vue n'est pas un simple carré

Il s'agit de classer les 6 faces du cube en fonction de leur distance à l'œil de l'observateur
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   1 584
 
bonjour,
comment définis-tu la distance entre un point (l'oeil) et une face?
est-ce la distance entre le point de référence et le point le plus proche de la face?

surtout, tu n'as pas expliqué pourquoi tu faisais cela, donc impossible de suggérer des alternatives.
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   1 584 > yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention  
 
je ferais ainsi, sans savoir si c'est approprié par rapport à ton objectif:
pour chaque face, je calculerais les coordonnées du point "central" de la face, en faisant la moyenne des coordonnées des points de la face.
ensuite je calculerais les distances entre l'oeil est ces points centraux (soit la vraie distance, soit la coordonnée Z).
ensuite je trierais pour obtenir le classement.

j'ai choisi le point "central" parce que cela me semble le plus élégant. aucune idée si c'est le bon choix dans ton cas.

plus j'y pense, moins ce classement me semble avoir un sens. une face peut-elle en traverser une autre?
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   1 584
 
ton exemple est incomplet: il manque le résultat attendu.
0
Réponse 3 / 12
Utilisateur anonyme
 
ha oui c'est un peu plus clair.

Mais seulement sur la coordonnées Z, je ne sais pas si c'est réaliste. Sur un seul et même volume pourquoi pas mais si tu as plusieurs volumes... 



Z1


                                                                         Z2
O


On voit que Z1 est plus prêt que Z2 de O, pourtant si on ne se base que sur delta z, on trouvera le contraire.
0
Réponse 4 / 12
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   Ambassadeur 1 584
 
fais-tu cela dans ce contexte, afin de t'assurer de traiter chaque face avant toutes les faces qui vont la cacher?
et les faces peuvent-elles se traverser, ou pas?
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Réponse 5 / 12
Phil_1857 Messages postés 1872 Date d'inscription   Statut Membre Dernière intervention   168
 
Bonjour yg_be,

Ah, je vois que tu m'as percé à jour :-) :-)
C'est bien le contexte, et ça fonctionne bien sauf dans certaines orientations

Effectivement, je prenais le centre de gravité de chaque face en Z pour faire le classement, mais c'est un peu trop simpliste comme méthode, il y a des cas où le CDG d'une face qui est à l'arrière est devant celui d'une face qui est normalement devant la 1ere, et donc le résultat est bizarre:


La face arrière étant longue son CDG est plus proche de l'œil que celui de la petite face marquée d'une flèche, donc supposée être dessinée par dessus, d'où le petit segment en trait fort qui devrait être en pointillés ....
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   1 584
 
je ne parviens pas à identifier les deux faces que tu mentionnes. pourquoi ne nous montres-tu pas les coordonnées des cdg?

surtout, je me demande pourquoi tu utilises la coordonnée en Z pour faire le classement. il me semble que tu devrais utiliser la coordonnée sur la bissectrice entre les axes X et Z.

il me semble qu'il y a une incohérence entre le calcul que tu fais pour représenter ton volume en 2D et le système d'axes que tu utilises pour le classement du plus loin au plus proche.
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   1 584
 
expliqué autrement:
tu ne nous explique pas comment tu fais la représentation en 2D.
est-ce une projection orthogonale dans un plan?
dans quel plan? est-ce vraiment le plan des axes XY?
0
Réponse 6 / 12
Phil_1857 Messages postés 1872 Date d'inscription   Statut Membre Dernière intervention   168
 
Oui le système d'axe que tu vois, c'est le repère du solide, moi je parle du repère caméra, la caméra étant l'œil de l'observateur devant l'écran, et donc XY est dans le plan de l'écran et Z pointe vers l'observateur

Je calcule donc les coordonnées du centre de gravité de chaque face dans le repère caméra, et j'utilise la coordonnée en Z pour savoir laquelle est la plus éloignée et laquelle est la plus proche, c'est ce que tu indiquais plus haut:
"pour chaque face, je calculerais les coordonnées du point "central" de la face"

"je ne parviens pas à identifier les deux faces que tu mentionnes"
la 1ere est dans le plan XY du repère que tu vois, et la 2eme est la face horizontale pointée par la flèche rouge
Donc on voit bien que cette grande face arrière en L a son CDG plus proche que celui de cette petite face ...
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   1 584
 
donc, quand tu écris XYZ, cela n'a rien à voir avec le XYZ du dessin que tu montres?

je me demande si il est possible de faire le classement que tu souhaites
il est certainement possible d'ordonner deux faces superposées, mais je me demande si cela permet de créer un ordre, tel que la distance que tu cherchez à calculer.
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   1 584 > yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention  
 
je confirme que je pense impossible de faire un classement:
je peux imaginer un ensemble de faces, A, B, C, D,
avec A plus proche que B
B plus proche que C
C plus proche que D
D plus loin que A.

tu n'as pas précisé s'il s'agissait d'un seul volume.
0
Réponse 7 / 12
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   Ambassadeur 1 584
 
je pense illusoire de classer, et je propose plutôt ceci: 
- tu as une liste des arêtes visibles et une liste des arêtes invisibles, ainsi qu'une liste des faces traitées
      (ces listes sont vides au départ)
- tu fais une boucle sur toutes les faces,
      - pour toutes les arêtes de la liste des arêtes visibles, 
          si l'arête visible a une intersection (2D) avec une des arêtes de la face, 
            	si l'arête est entièrement derriere (3D) la face, 
                      elle devient invisible (elle change de liste)
		si l'arête n'est pas entièrement devant (3D) la face, 
              tu découpes l'arête visible en deux arêtes 
                 (supprimer l'arête originale de la liste des arêtes visibles, 
                   et ajouter les nouvelles, l'une visible, l'autre invisible)
      - pour toutes les arêtes de la face en cours d'ajout, 
               pour toutes les faces de la liste des faces traitées,
			si l'arête a une intersection (2D) avec une des arêtes de la face,
				si l'arete est entièrement derriere la face, 
                      tu ajoutes l'arete dans la liste des aretes invisibles, 
					  et tu avortes la boucle interne 
                      (passant à l'arete suivante de la face en cours d'ajout)
				si l'arete n'est pas entièrement devant la face, 
                         tu découpes l'arete en deux, 
                                l'une visible, l'autre invisible.
					tu ajoutes l'invisible dans la liste des aretes invisibles, 
                         et tu continues avec la partie visible 
                          (au lieu de continuer avec l'arete de départ)
		tu ajoutes l'arete dans la liste des aretes visibles
0
Réponse 8 / 12
Phil_1857 Messages postés 1872 Date d'inscription   Statut Membre Dernière intervention   168
 
Bonjour yg_be

Pour répondre a ton message de 18h12, effectivement le XY n'est pas celui du repère, c'est le plan de l'écran et donc le Z pointe vers ton œil

Et donc je faisais mon classement en calculant le CDG de chaque face avec les coordonnées l'écran, ce qui fonctionne pour un cube, mais pas dans le cas de mon solide en L

Je vais tester ton algo, à ce propos, problème d'indentation:
la dernière ligne est vraiment est au niveau de la ligne
"pour toutes les arêtes de la face en cours d'ajout" ?

" et tu continues avec la partie visible " : tu continue où, en fait ?
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   1 584
 
en effet, mauvaise indentation, et clarification de l'utilisation de la parie visible 

- tu as une liste des arêtes visibles et une liste des arêtes invisibles, ainsi qu'une liste des faces traitées
      (ces listes sont vides au départ)
- tu fais une boucle sur toutes les faces,
      - pour toutes les arêtes de la liste des arêtes visibles, 
          si l'arête visible a une intersection (2D) avec une des arêtes de la face, 
            	si l'arête est entièrement derriere (3D) la face, 
                      elle devient invisible (elle change de liste)
		si l'arête n'est pas entièrement devant (3D) la face, 
              tu découpes l'arête visible en deux arêtes 
                 (supprimer l'arête originale de la liste des arêtes visibles, 
                   et ajouter les nouvelles, l'une visible, l'autre invisible)
      - pour toutes les arêtes de la face en cours d'ajout, 
               areteajoutee=indice de boucle
               pour toutes les faces de la liste des faces traitées,
			        si areteajoutee a une intersection (2D) avec une des arêtes de la face,
				        si areteajoutee est entièrement derriere la face, 
                              tu ajoutes areteajoutee dans la liste des aretes invisibles, 
					             et tu avortes la boucle interne 
                                    (passant à l'arete suivante de la face en cours d'ajout)
				        si areteajoutee n'est pas entièrement devant la face, 
                             tu découpes areteajoutee en deux, 
                                l'une visible, l'autre invisible.
					            tu ajoutes l'invisible dans la liste des aretes invisibles, 
                                areteajoutee=la partie visible 
               tu ajoutes areteajoutee dans la liste des aretes visibles
0
Réponse 9 / 12
Phil_1857 Messages postés 1872 Date d'inscription   Statut Membre Dernière intervention   168
 
Bonjour yg_be

Excuse-moi de revenir là-dessus, mais je suis un peu long à la détente en ce moment :-)

2 questions:

"tu ajoutes areteajoutee dans la liste des aretes visibles" semble être au même niveau que

"pour toutes les faces de la liste des faces traitées,", donc on n'ajoute qu'apres avoir parcouru toute la boucle, c'est ça ? (et non pas à chaque tour)

Ensuite, à quel stade ajoute-t-on une face dans liste des faces traitées ?
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   1 584
 
en effet, en n'ajoute arreteajoutee dans la liste des arretes visibles que si, après avoir parcouru toutes les faces deja traitée, elle est toujours visible.

et l'ajout de la face dans liste des faces traitées est restée dans mon clavier: il faut le faire tout à la fin de la boucle "sur toutes les faces".
0
Réponse 10 / 12
Phil_1857 Messages postés 1872 Date d'inscription   Statut Membre Dernière intervention   168
 
Holà yg_be,

Je me remet seulement à notre affaire, et pour être sur que l'on traite bien les bons objets au bon endroit, que penses-tu de ce pseudo code (pseudo python ...) : ? 
faces = liste des faces
visible_edges = []
invisible_edges = []
used_faces = []

k 0-> faces_nb
    j 0 -> visible_edges_nb
        face_poly = get_face_polygon(faces[k])
        intersection_pt = intersect(visible_edges[j], face_poly)

            if(intersection_pt != None)
                if(is_behind(visible_edges[j],faces[k])
                    invisible_edges.append(visible_edges[j])
                    remove_edge_from_visible_edges(visible_edges[j])
                else
                    e1,e2 = split_edge(visible_edges[j], intersection_pt)
                    remove_edge_from_visible_edges(visible_edges[j])
                    add_edge_to_visible_edges(e1)
                    add_edge_to_invisible_edges(e2)

    face_edges = edges_of_face(face[k])
    j 0 -> face_edges_nb
            added_edge = j
            i 0 -> used_faces_nb
                face_poly = get_face_polygon(used_faces[i])
                intersection_pt = intersect(face_edges[added_edge], face_poly)

                if(intersection_pt != None)
                    if(is_behind(face_edges[added_edge],used_faces[i])
                        invisible_edges.append(face_edges[added_edge])
                        break to next j
                    else
                        e1,e2 = split_edge(face_edges[added_edge], intersection_pt)
                        add_edge_to_visible_edges(e1)
                        add_edge_to_invisible_edges(e2)

            if(is_visible(face_edges[added_edge])): add_edge_to_visible_edges(face_edges[added_edge])

    used_face.append(face[k])
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   1 584
 
je pense plutôt ceci: 
faces = liste des faces
visible_edges = []
invisible_edges = []
used_faces = []

k 0-> faces_nb
    j 0 -> visible_edges_nb
        face_poly = get_face_polygon(faces[k])
        intersection_pt = intersect(visible_edges[j], face_poly)

            if(intersection_pt != None)
                if(is_behind(visible_edges[j],faces[k])
                    invisible_edges.append(visible_edges[j])
                    remove_edge_from_visible_edges(visible_edges[j])
                else
                    e1,e2 = split_edge(visible_edges[j], intersection_pt)
                    remove_edge_from_visible_edges(visible_edges[j])
                    add_edge_to_visible_edges(e1)
                    add_edge_to_invisible_edges(e2)

    face_edges = edges_of_face(face[k])
    j 0 -> face_edges_nb
            added_edge = face_edges[j]
            i 0 -> used_faces_nb
                face_poly = get_face_polygon(used_faces[i])
                intersection_pt = intersect(added_edge, face_poly)

                if(intersection_pt != None)
                    if(is_behind(added_edge,used_faces[i])
                        invisible_edges.append(added_edge)
                        break to next j
                    else
                        e1,e2 = split_edge(added_edge, intersection_pt)
                        added_edge=e1
                        add_edge_to_invisible_edges(e2)

            add_edge_to_visible_edges(face_edges[added_edge])

    used_face.append(face[k])
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   1 584 > yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention  
 
et la ligne 8 peut sortir de la boucle en j, je pense.
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   1 584 > yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention  
 
par ailleurs, les deux boucles en j ne traitent pas le cas où l'arrête est entièrement à l'intérieur (2D) de la face. dans ce cas, il faut aussi agir si elle est derrière (3D) la face.
0
Réponse 11 / 12
Phil_1857 Messages postés 1872 Date d'inscription   Statut Membre Dernière intervention   168
 
En fait, pour moi, la proc is_behind() cherche si l'arête est entièrement derrière (3D) la face
sinon, c'est qu'il y en a une partie devant, c'est le else du test


Ca, c'est bizarre:

added_edge est une arête (et non un indice de liste), et en fin de boucle i, tu fais:

add_edge_to_visible_edges(face_edges[added_edge]) : donc added_ddge traité comme un indice ...
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   1 584
 
j'ai négligé, en effet, de changer la ligne 37.
add_edge_to_visible_edges(added_edge)
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   1 584
 
il faut tester is_behind() même si il n'y a pas d'intersection et que l'arête est entièrement à l'intérieur (2D) de la face.
0
Réponse 12 / 12
Phil_1857 Messages postés 1872 Date d'inscription   Statut Membre Dernière intervention   168
 
0

Discussions similaires

ordre alphabetique sous word
raro -
gogo -

27 réponses
A quoi sert CPU-Z ?
mathilde15 -
fabul -

1 réponse
Samsung Z Flip 4 s'éteint lorsque je le plie.
BOBJENNY -
Tinoon -

4 réponses
Remplir une cellule (texte) en fonction d'une autre (texte).
SOMUM -
SOMUM -

4 réponses
Code source couleur de fond
Mehdi-Amg -
Techno01 -

9 réponses