Discussion :

[darkman19320]

Bonjour tout le monde!
J'ai un cube dans l'espace. A partir de n'importe quel point de l'espace, je souhaiterais obtenir le point associé à une des faces du cube.
Pour cela je pensais faire une projection orthogonale d'un point 3D sur un plan (une des faces de mon cube) puis projeter le point obtenu dans la face associé à mon plan.

Voici une image résumant (ou tout essaye de rendre compréhensible ce que j'essaye d'expliquer ):


J'ai réussi à obtenir l'équation du plan à partir de trois points d'une des faces:

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
20
21
22
 
public static void getEquationPlane(Vertex3D p1, Vertex3D p2, Vertex3D p3,
	    DoubleBuffer equationPlane) {
  //v0 est le vecteur P1P2
  Vector3D v0 = new Vector3D(p2.getX()-p1.getX(), p2.getY()-p1.getY(), p2.getZ()-p1.getZ());
  //v1 est le vecteur P2P3
  Vector3D v1 = new Vector3D(p3.getX()-p2.getX(), p3.getY()-p2.getY(), p3.getZ()-p2.getZ());
 
  Vector3D n = new Vector3D(v0);
  n.cross(v1);
 
  double A = n.getX(), B = n.getY(), C = n.getZ();
 
  double D = - (A*p1.getX() + B*p1.getY() + C*p1.getZ());
 
  //L'équation du plan :  Ax + By + Cz + D = 0;
 
  equationPlane.put(A);
  equationPlane.put(B);
  equationPlane.put(C);
  equationPlane.put(D);
}

Je pense que le calcul de l'équation du plan est correct mais je ne comprends pas:
1> comment faire pour calculer le projeté orthogonal de n'importe quel points de l'espace?
2> comment faire une translation du projeté vers la face du cube (si et seulement si le projeté n'est pas déjà dans la face).
3> Est-il possible de passer du point A (sur la figure) au point A" en un seul système d'équation (matrice de projection + translation?)?

Merci d'avance.

[Jean Dumoncel]

Bonjour,

(dis-donc, c'est bien de penser aux malvoyants et à ceux qui ont un petit écran, mais elle est un peu énorme ton image...)

Chercher le projeté orthogonal, c'est chercher l'intersection entre le plan et la droite perpendiculaire au plan passant par le point.
Pour l'intersection entre un plan et une ligne :
Subject 5.05: How do I find the intersection of a line and a plane?
(tu peux facilement trouver l'équation paramétrique de la droite en utilisant un vecteur normal à ton plan)

(une remarque au cas ou : on est bien d'accord que les faces de ton cube ne sont pas parallèle aux axes de ton repère?)

[darkman19320]

Merci pour ta réponse.
Mon cube n'est pas forcément parallèle à mon repère.
Je vais essayer ce que tu m'as dit et je vous tiens au courant.

[Nebulix]

le point associé
C'est quoi çà ?

[darkman19320]

Bonjour,
Désolé pour la réponse tardive j'avais un autre projet en cours...
Donc pour répondre à ta question Nebulix, le point associé est en fait le projeté orthogonale de A sur le segment de ma bounding Box ou sur l'une des faces de celle-ci.

Je pense avoir réussi à trouver le projeté orthogonal d'un point sur un plan et le projeté d'un point sur la droite.
Voici le code que j'utilise pour la projection d'un point dans le plan

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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
/**
 * 
 * {@link Plane} defined an equation's plane:
 * Ax + By + Cz + D = 0;
 *
 */
 
 
 /**
     * Get the plane's normal: 
     * n = (A,B,C);
     * @param plane
     * @return the plane's normal vector.
     */
    public static Vector getNormal(Plane plane) {
	return new Vector(plane.A(), plane.B(), plane.C());
    }
 
 /**
     * Compute the minimal distance between the {@link Point} (p) and
     * the {@link Plane} (plane).
     * The algorithm used is:</br>
     * 1) Get the plane's normal n;</br>
     * 2) Compute the dot product between n and p and add D plane's value:</br>
     * 		dist = (n.dot(p) + plane.D())/sqrt(n.dot(n));</br>
     * @param p
     * @param plane
     * @return the distance between the plane and the point.</br> 
     * If the distance is < 0 the the point is not in the same direction
     * as the plane's normal. If the distance is equals to 0 then the point
     * is contained in the plane.
     */
    public static float distancePointPlane(Point p, Plane plane) {
	Vector n = getNormal(plane);
 
	return (float)(Math.abs(n.dot(new Vector(p)) + plane.D())/Math.sqrt(n.dot(n)));		
    }
 
 /**
     * Projected orthogonally the {@link Point} (p) on the {@link Plane}
     * (plane).</br>
     * The algorithm used is:</br>
     * 1) Compute the distance (dist) between the point and the plane. </br>
     * 2) Get the plane's normal (n).</br>
     * 3) Create the new point:</br>
     * Point q = p - n*dist;
     * @param p
     * @param plane
     * @return the point on plane.
     */
    public static Point projectionOrthoPointInPlane(Point p, Plane plane) {
	float dist = distancePointPlane(p, plane);
	Vector n = getNormal(plane);
	n.multiply(dist);
 
	Point pPlane = new Point(p);
	pPlane.remove(n);
	return pPlane;
    }

Et celui-ci pour la projection d'un point sur une droite:

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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
 /**
     * Distance calculation between two points.
     * @param p1
     * @param p2
     * @return the distance between p1 and p2.
     */
    public static double distance(final Point p1, final Point p2) {
	Point p1p2 = remove(p1,p2); //p1-p2;
	return Math.sqrt(Math.pow(p1p2.x(), 2) + Math.pow(p1p2.y(), 2) +
		Math.pow(p1p2.z(), 2));
    }
 
  public static double length(final Line l) {
	return l.a().distance(l.b());
    }
 
  public static Point projectionOrthoPointOnLine(final Point p, final Line l) {
	//Q = P1 + u*(P2-P1);
	//(P3-Q)dot(P2-P1) = 0;
	//(P3-P1-u*(P2-P1))dot(P2-P1) = 0;
	//u = ((x3-x1)*(x2-x1) + (y3-y1)*(y2-y1) + (z3-z1)*(z2-z1))/length(l);
	//Qx = P1x + u*(P2x-P1x);
	//Qy = P1y + u*(P2y-P1y);
	//Qz = P1z + u*(P2z-P1z);
 
	double lengthLine = l.length();
	Vector ap = new Vector(Point.remove(p, l.a()));
	Vector ab = new Vector(Point.remove(l.b(), l.a()));
 
	double u = ap.dot(ab)/(lengthLine*lengthLine);
 
	float qx = (float) (l.a().x() + u*(ab.x()));
	float qy = (float) (l.a().y() + u*(ab.y()));
	float qz = (float) (l.a().z() + u*(ab.z()));
 
	return new Point(qx, qy, qz);
    }

Me serais-je trompé dans mes calculs?

Merci d'avance.


Edit: Après vérification, mes calculs sont corrects (j'ai fait plusieurs test d'appartenance ou non d'un point à une ligne ou un plan et les résultats semblent corrects).

[darkman19320]

Bonjour,
Je pense avoir compris mon problème: le point d'origine (par exemple le point A ou B sur le dessin) n'a pas la profondeur souhaitée.
Pour information, je récupère ce point à partir de la fonction glUnProject de OpenGL (voir Problème affichage de points à partir d'un clic de souris. Je lui passe en paramètre ma matrice de transformation (MODELVIEW_MATRIX), ma matrice de projection (PROJECTION_MATRIX) ainsi que les coordonnées de ma souris (donc en 2D) et un tableau pour récupérer les 3 coordonnées du monde OpenGL.
Je pense que le problème vient de ma matrice de projection.

J'ai pensais à une autre solution: tester la distance entre les coordonnées de la souris et les différentes droites de ma bounding box et prendre la distance la plus petite mais malheureusement le résultat n'est pas concluant... Je crois savoir pourquoi: je teste les coordonnées 2D de ma souris avec les coordonnées 3D de mes droites de la bounding box.

Donc ma question est la suivante: peut-on récupérer les coordonnées 2D (de l'écran donc) à partir des coordonnées 3D (les coordonnées OpenGL)?

Merci d'avance.

[pseudocode]

bonjour,

Une question en passant : quel était le problème de départ qui a donné lieu à tous ces calculs ?

[darkman19320]

Mon problème est le suivant:
Je souhaite effectuer du clipping et donc j'ai besoin d'un plan. A partir d'un clic de souris, je souhaiterais obtenir les coordonnées d'un des trois points nécessaire pour créer le plan. J'aimerais que ces coordonnées soient sur un des segments de ma bounding box ou sur une de ces faces.
Une fois que j'ai mes trois points, je calcule l'équation de mon plan et j'effectue le clipping.

Suis-je assez clair?

[pseudocode]

Mon problème est le suivant:
Je souhaite effectuer du clipping et donc j'ai besoin d'un plan. A partir d'un clic de souris, je souhaiterais obtenir les coordonnées d'un des trois points nécessaire pour créer le plan. J'aimerais que ces coordonnées soient sur un des segments de ma bounding box ou sur une de ces faces.
Une fois que j'ai mes trois points, je calcule l'équation de mon plan et j'effectue le clipping.

Suis-je assez clair?

Ah.

Étant donné que les coordonnées du clic souris sont en 2D il y a deux approches:

a. Projeter le modèles 3D sur l'écran 2D et faire la recherche du point optimal en 2D, puis retourner en 3D.

b. passer les coordonnées du clic en 3D et faire la recherche du point en 3D.


Les deux approches sont jouables. La première me semble plus habituelle si j'en juge les softs de conception 3D que j'ai pu voir.

[darkman19320]

Ok merci.

Pour la première méthode, j'utilise gluProject c'est ça?
Si c'est le cas, peux-tu me dire si la méthode que j'utilise est correcte:

1. Utiliser gluUnProject pour récupérer les coordonnées OpenGL de ma souris
2. Récupérer toutes les coordonnées écran des 8 points de ma bounding box (en utilisant gluProject)
3. Récupérer les coordonnées écran de ma souris (donc peut-être étape 1 non nécessaire)
4. A partir des coordonnées écran (de la souris et des point de la bounding box), chercher le plan le plus proche
5. Si le point projeté dans le plan est à l'intérieur de la face (de la bounding box) associé à ce plan, on récupère les coordonnées 3D avec gluUnProject
6. Sinon rechercher la droite la plus proche du point projeté
7. Si le point projeté sur la droite est à l'intérieur du segment contenu dans cette droite, alors on récupère les coordonnées 3D avec gluUnProject
8. Sinon prendre le point le plus proche du point projeté sur la droite et récupérer les coordonnées 3D de ce point.

Merci

[pseudocode]

Disons que ca me semble logique.

Bon, pour le cas #8, je sais pas trop le résultat que ca va donner. Ca correspondrait au point "A" dans ton image initiale. Dans ce cas, je trouve que c'est dur de trouver ce que voulait faire l'utilisateur.

[darkman19320]

C'est vrai que ca risque d'être bizarre...

Peut-être que je devrais juste faire un picking sur les faces de la bounding box et récupérer le point intersecté non?
Mais si je fais ça l'utilisateur sera obligé de cliqué sur la bounding box... (pas forcément gênant non plus)

[pseudocode]

C'est vrai que ca risque d'être bizarre...

Peut-être que je devrais juste faire un picking sur les faces de la bounding box et récupérer le point intersecté non?
Mais si je fais ça l'utilisateur sera obligé de cliqué sur la bounding box... (pas forcément gênant non plus)

Oui, c'est la méthode la plus usuelle. Avec un bouton ("tab") pour pouvoir choisir un des autres points possibles en cas de solutions multiples

[darkman19320]

Ok merci.
Par contre petite question je voulais faire un picking avec gluPickMatrix mais est-ce que l'on peut récupérer directement les coordonnées des points d'intersections?
Ou peut-on utiliser le color picking et récupérer le point d'intersection?

[pseudocode]

Ok merci.
Par contre petite question je voulais faire un picking avec gluPickMatrix mais est-ce que l'on peut récupérer directement les coordonnées des points d'intersections?

Je ne pense pas que OpenGL sache calculer les intersections entre un rayon et la scène.

Ou peut-on utiliser le color picking et récupérer le point d'intersection?

Heu, je ne pense pas. On peut juste récupérer l'objet mais c'est tout. C'est déjà pas mal. Le calcul d'intersection rayon/box n'est pas très compliqué

[darkman19320]

Merci beaucoup pour tes réponses.

Je ne suis pas trop familier avec le lancer de rayon... Je comprends le principe: à partir d'un point d'origine et d'un vecteur directeur, on calcule l'intersection entre le rayon et le (les) objets à tester.
J'ai plusieurs questions:
1) Comment trouve-t-on le vecteur directeur? C'est à nous de le définir?
Si c'est le cas, pour avoir un rayon parallèle à un plan xOy (en étant dans le repère Oxyz), le vecteur directeur d doit être égal à (0,0,1)?
2) Je n'ai pas compris le code fournis par ce site: Ray-Box Intersection Algorithm.

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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
/*
 * Ray-box intersection using IEEE numerical properties to ensure that the
 * test is both robust and efficient, as described in:
 *
 *      Amy Williams, Steve Barrus, R. Keith Morley, and Peter Shirley
 *      "An Efficient and Robust Ray-Box Intersection Algorithm"
 *      Journal of graphics tools, 10(1):49-54, 2005
 *
 */
 
// (t0, t1) is the interval for valid hits
bool Box::intersect(const Ray &r, float t0, float t1) const {
  float tmin, tmax, tymin, tymax, tzmin, tzmax;
 
  tmin = (parameters[r.sign[0]].x() - r.origin.x()) * r.inv_direction.x();
  tmax = (parameters[1-r.sign[0]].x() - r.origin.x()) * r.inv_direction.x();
  tymin = (parameters[r.sign[1]].y() - r.origin.y()) * r.inv_direction.y();
  tymax = (parameters[1-r.sign[1]].y() - r.origin.y()) * r.inv_direction.y();
  if ( (tmin > tymax) || (tymin > tmax) ) 
    return false;
  if (tymin > tmin)
    tmin = tymin;
  if (tymax < tmax)
    tmax = tymax;
  tzmin = (parameters[r.sign[2]].z() - r.origin.z()) * r.inv_direction.z();
  tzmax = (parameters[1-r.sign[2]].z() - r.origin.z()) * r.inv_direction.z();
  if ( (tmin > tzmax) || (tzmin > tmax) ) 
    return false;
  if (tzmin > tmin)
    tmin = tzmin;
  if (tzmax < tmax)
    tmax = tzmax;
  return ( (tmin < t1) && (tmax > t0) );
}

.
Surtout à quoi correspondent les tmin tmax, tymin, tymax, tzmin et tzmax. Ces variables peuvent-elles nous donner les coordonnées du point d'intersection?

(Désolé pour ces questions certainement très simple à comprendre...)

[pseudocode]

1) Comment trouve-t-on le vecteur directeur? C'est à nous de le définir?

Oui. Généralement c'est le vecteur passant par le point de vue (camera) et le point visé par la souris (=coordonnées 3D dans le plan de l'ecran)

Si c'est le cas, pour avoir un rayon parallèle à un plan xOy (en étant dans le repère Oxyz), le vecteur directeur d doit être égal à (0,0,1)?

heu... oui. Si tant est que j'ai compris ce qu'est un rayon parallèle a un plan.

2) Je n'ai pas compris le code fournis par ce site

C'est un algo pour savoir si un rayon intersecte une box. Mais ca ne donne pas les coordonnées de l'intersection. Le principe habituel c'est de se ramener au cas d'une box alignée sur les 3 axes (axis-aligned box) en appliquant la rotation inverse au rayon.

[darkman19320]

Bonjour,

Merci pour ta réponse. J'ai trouvé quelques papiers sur l'intersection des axes-aligned bounding box (Fast Ray-Axis Aligned Bounding Box Overlap Tests with Plucker Coordinates
, Fast Ray/Axis-Aligned Bounding
Box Overlap Tests using Ray Slopes
) mais je ne comprends pas comment récupérer les coordonnées du point d'intersection à partir des algos décrit...
As-tu des algos à me conseiller?

PS: Je n'ai absolument pas compris l'histoire de rotation inversée du rayon...

[pseudocode]

Merci pour ta réponse. J'ai trouvé quelques papiers sur l'intersection des axes-aligned bounding box (Fast Ray-Axis Aligned Bounding Box Overlap Tests with Plucker Coordinates
, Fast Ray/Axis-Aligned Bounding
Box Overlap Tests using Ray Slopes
) mais je ne comprends pas comment récupérer les coordonnées du point d'intersection à partir des algos décrit...
As-tu des algos à me conseiller?

Tous ces algos font seulement le "test" pour savoir si le rayon intersecte la box (ils retournent true/false). Mais ils ne calculent pas les coordonnées d'intersection.

Tu as un algo basique dans GraphicsGems : http://tog.acm.org/resources/GraphicsGems/gems/RayBox.c

En cas d'intersection (la fonction retourne true) les coordonnées sont retournées dans le tableau coord[]

PS: Je n'ai absolument pas compris l'histoire de rotation inversée du rayon...

Un rayon horizontal qui se dirige vers une Box orienté a 45°, c'est la meme chose qu'un rayon orienté à -45° qui se dirige vers une Box horizontale. C'est juste un changement de repère

[darkman19320]

Merci beaucoup pour tes réponses!!
J'arrive au bout ^^
Il ne me manque plus qu'à corriger les coordonnées de la direction et de l'origine de mon rayon en fonction de la rotation de ma bounding box.
Donc si je ne me trompe pas, il faut que je multiplie les deux vecteurs (origine et direction) par la matrice de rotation au tour d'un axe quelconque?