Bonjour,

J'ai passé du temps sur internet pour trouver une réponse à ma question. Ce n'est pas la documentation qui manque, mais mes facultés mathématiques de secondaires sont bien loin et je n'arrive pas à appliquer la théorie.

Ma tâche est assez directe: je désire faire rebondir un objet se déplaçant selon un vecteur caractérisé par vitesseX et vitesseY, contre un segment AB d'orientation aléatoire, et définit par deux points avec leurs coordonnées x et y. Je ne désire pas prendre en compte ni la gravité, ni le frottement, ni de rotations, il s'agit juste de trouver le vecteur réfléchis contre cette surface.

Selon ce que j'ai pu voir, la théorie me semble encore relativement intuitive: trouver la normale, obtenir la projection sur la normale, puis multiplier ces différents pour trouver le vecteur réfléchis (Vect2 = Vect1 - 2 * normal * (normal DOT Vect1)).

La seule chose, c'est que tous les exemples de code que j'ai pu trouver utilisent des objets type "Vector2f" qui les affranchissent des calculs internes dont j'ai, au fond, le plus besoin (du genre Vector2f.getNormal() ou Vector2f.dot(Vector2f other)... en pseudo code)... Malheureusement, je ne peux pas faire appel à ces objets et je n'ai à ma disposition qu':

• Un objet avec des coordonnées x et y ainsi que des paramètres speedX et speedY
• Un segment de droite définit par deux points A et B, possédant chacun leurs coordonées Ax:Ay et Bx:By.

Quelqu'un pourrait-il me montrer les opérations algébriques permettant d'aboutir au résultat?

Merci d'avance!

Ps: Pour info, il s'agit d'une petite application 2d pour un projet de recherche en informatique médicale.

-
Edité par gosush 16 mai 2015 à 21:18:11

Salut,

Un segment de droite définit par deux points A et B, possédant chacun leurs coordonées Ax:Ay et Bx:By.

Tu as donc \(d=\sqrt{(x_b-x_a)\^2 +(y_b-y_a)\^2}\) la distance entre tes deux points. Donc tu peux construire le vecteur unitaire tangent à ton segment \(\vec{t}=\dfrac 1d\begin{pmatrix}x_b-x_a\\ y_b-y_a\end{pmatrix}\). Un vecteur normal à ce vecteur tangent est \(\vec n=\dfrac 1d\begin{pmatrix}y_b-y_a\\ x_a-x_b\end{pmatrix}\).

Le vecteur vitesse après rebond \(\vec v_r\) s'exprime en fonction du vecteur vitesse avant rebond \(\vec v_i\) par \(\vec v_r=(-\vec v_i\cdot \vec n)\vec n+(\vec v_i\cdot \vec t)\vec t\) (c'est assez simple à comprendre, on inverse la composante normal pour rebondir, et on garde la composante tangentielle du mouvement initial). Sachant que \(\vec a\cdot\vec b\) est le produit scalaire de \(\vec a\) et \(\vec b\), c'est un nombre qui vaut \(x_ax_b+y_ay_b\). Pour multiplier un nombre par un vecteur, il suffit de multiplier chaque composante du vecteur par ce nombre. Et pour sommer deux vecteurs, il suffit de sommer respectivement les composantes. Avec ça, tu devrais t'en sortir, n'hésite pas à poser des questions.

-
Edité par Anonyme 16 mai 2015 à 22:36:22

Hum merci beaucoup ça parait clair.

Juste deux petites choses. Quand tu dis "d ... la distance entre 2 points", de quelle distance parle tu? De celle séparant les points A et B construisant mon segment contre lequel l'objet doit rebondir? (juste pour bien comprendre...)

Deuxièmement, encore une ignorance algébrique, quand tu dis des choses comme 

1d(yb−yaxa−xb).

je dois bien multiplier  , c'est à dire que j'aboutis à x = 1 * (yb-ya) et y = d * (xa-xb) ?

Excuse le niveau mais il faut bien commencer quelque part

Quand tu dis "d ... la distance entre 2 points", de quelle distance parle tu? De celle séparant les points A et B construisant mon segment contre lequel l'objet doit rebondir?

Oui.

je dois bien multiplier , c'est à dire que j'aboutis à x = 1 (yb-ya) et y = d (xa-xb) ?

Euh non, \(\dfrac 1d\) est un nombre, pas un vecteur ou n'importe quoi d'autre. Donc il faut en fait diviser par \(d\) chacun des composantes, ce qui donne par exemple \(\vec t=\begin{pmatrix}(x_b-x_a)/d\\ (y_b-y_a)/d\end{pmatrix}\).

-
Edité par Anonyme 17 mai 2015 à 1:53:43

arf... mon dieu que je suis mauvais! Ok quoiqu il en soit, c'est de mieux en mieux.

J'ai rencontré un problème car comme dans bien des API de développement 2d, le repaire Y est inversé, avec 0 au bord supérieur et les positifs vers le bas. Aussi les segments fournissant les collisions dans mon applications, peuvent avoir n'importe quelle orientation, et n'importe quelle direction, notamment, le point A peut être plus à droite et plus bas que le point B... 

Il y a certainement une façon propre de faire les chose, mais pour avancer un peu, j'ai défini des méthodes pour "normaliser" mes segments, qui retournent l'objet le plus à droite, respectivement le plus à gauche, et l'objet le plus bas (ayant le y le plus positif), respectivement le plus haut (y le moins positif).

Dans mes tests, les distances (ou "normes" si je ne me trompe pas) ont l'air cohérentes (ce qui n'était pas le cas, si j'utilisais simplement getA() ou getB() (qui je le rappelle, peuvent être orientés n'importe comment, et avec l'histoire des y inversés, me grillent passablement le cortex)).

Note que je me trouve dans un objet Segment, qui se charge de retourner son vecteur normal et tangent, comme le propose ton exemple.

Un bout de java:

public float getDistance(){
		
		float powx = (float) Math.pow(getRightestPoint().getX() - getLeftestPoint().getX(),2); 
		float powy = (float) Math.pow(getLowestPoint().getY() - getHighestPoint().getY(), 2);
		float dist = (float) Math.sqrt( (powx+powy) );
		return dist;
	}
	public Point getNormal(){
		float substnx = getLowestPoint().getY()-getHighestPoint().getY();
		float substny = getLeftestPoint().getX()-getRightestPoint().getX();
		float dist = getDistance();
		float nx, ny;
		if(dist > 0){
			nx = substnx/dist;
			ny = substny/dist;
		}else{
			nx = substnx;
			ny = substny;
		}
		return new Point(nx, ny);
		
	}

Ce qui reste un peu flou, bien que cela ne soit probablement pas indispensable pour réaliser cette tâche (je n'ai qu'à faire les calculs bêtement et tester le truc dans tous les sens), c'est que tu dis le "vecteur" tangent et le "vecteur" normal. Hors la formule que tu me proposes retournent finalement un x et un y, ce qui correspond à un point pour moi... où est le point "de référence"?

Je pose la question car dans la méthode getNormal(), je m'attendais à retourner un Vecteur ou Segment, et je me retrouve maintenant à retourner un Point...

Merci infiniment pour ton aide!!!

-
Edité par gosush 17 mai 2015 à 10:59:38

J'ai rencontré un problème car comme dans bien des API de développement 2d, le repaire Y est inversé, avec 0 au bord supérieur et les positifs vers le bas. Aussi les segments fournissant les collisions dans mon applications, peuvent avoir n'importe quelle orientation, et n'importe quelle direction, notamment, le point A peut être à droite et plus bas que le point B...

Aucune importance, les formules que je t'ai données sont indépendantes du repère (c'est l'intérêt des vecteurs ). Tu n'as pas à t'embêter pour savoir quel est le point le plus bas, ou quoique ce soit.

Hors la formule que tu me proposes retournent finalement un x et un y, ce qui correspond à un point pour moi

Un point n'est rien d'autre que la représentation d'un vecteur dans un espace quelconque.

-
Edité par Anonyme 17 mai 2015 à 11:03:37

Merci beaucoup pour ton aide @dri!

J'avance mais j'ai encore quelques problèmes. J'ai fait un test avec plusieurs segments, horrizontal, 45°, vertical et autres.

Je remarque que sur les segments horizontaux ou verticaux, le déplacement de mon objet répond tout à fait à mes attentes. Pour les segments avec une orientation plus diverse, par contre, ca coince. Il y a bien une collision et un changement de cap de mon objet, mais soit l'objet rebondit comme si la surface était parfaitement alignée à un axe X ou Y (et ce n'est pas le cas), ou le traverse...

Voici un bout de code. Pourrais-tu me dire si il y a des choses qui te sautent aux yeux?

La méthode "collide" est appelée seulement lorsque je détecte un changement de "côté" de l'objet par rapport au segment seg. Le vecteur vitesse initial est donné par speedX et speedY. dx et dy représentent les accélérations dans ces deux axes, qui peuvent avoir des valeurs variées en fonction des inputs utilisateur. Raison pour laquelle je les "réinitialise" en fonction du vecteur vitesse résultant (nsx et nsy).

HasColliden est un boolean qui me permet de n'effectuer qu'une seule collision. Puisque la collision est détectée par le changement de côté de l'objet vis à vis du segment, il m'est pour le moment nécessaire pour éviter les rebonds infinis... 

protected void collide(Segment seg){
		if(!hasColliden){
			Point t = seg.getTangentVector();
			Point n = seg.getNormalVector(true);
			
			float dotn = speedX*n.getX() + speedY*n.getY();
			float dott = speedX*t.getX() + speedY*t.getY();
			float nsx = (-n.getX()*(dotn)) + (t.getX()*dott);
			float nsy = (-n.getY()*(dotn)) + (t.getY()*dott);
			
			this.speedX = nsx;
			this.speedY = nsy;
			
			
			
			if((this.speedX>0 && dx<=0) || (speedX<0 && dx>=0) )
				dx = -dx;
			if((this.speedY>0 && dy<=0) || (speedY<0 && dy>=0) )
				dy = -dy;

			

			
			hasColliden = true;
		}
	}

A noter que le côté de mon objet est définit par ce calcul, en fonction de si le nombre obtenu est négatif, positif ou ==0. Selon mes tests, le résultat est cohérent.

	public float getSideOfLine(Point p){
		float r = (b.getX()-a.getX()) * (p.getY()-a.getY()) - (b.getY() - a.getY())*(p.getX()-a.getX());
		return r;
	}

Et puis note encore que je pense que mes vecteurs tangent et normal me semblent juste (ils ont un type java "Point" mais je les considère comme des vecteurs). Ils sont retourné par des méthodes accessoires. 

Voici un screen à l'appui montrant ma scène avec 4 segments (1 horizonal, 1 vertical, un à 45° et 1 avec une pente plus variable). Pour chaque segment, je dessine le vecteur normal en bleu et le vecteur tangent en rouge, et ils ont l'air d'être à la bonne place.

Et puis voici encore deux screens avec des flèches (à la main, mes excuses) pour montrer le résultat obtenu. Le premier screen montre ce qui marche. Avec les segments horizontaux et verticaux, je n'ai pas de problème. Pour les autres segments, lorsque l'objet a un vecteur initial avec un angle (pas horizontal ou vertical), il y a un rebond qui parait cohérent.

Le second screen montre ce qui ne marche pas. Le problème survient lorsque le vecteur initial est parfaitement (ou presque) vertical ou horrizontal et que le rebond se fait sur un segment avec un angle.

Encore une fois, merci infiniment de ton aide!

Frédéric

C'est rigolo, ça. Je pourrais voir le bout de code qui appelle ces deux fonctions ?

Voir EDIT en bas de page avant de tout lire

Bien entendu:

Classe PhysicalObject:

La méthode update est appelé depuis la gameLoop à chaque itération (technique standard si jamais).

Le sol (ground) est une série de points récupéré depuis un loader sous format JSON. Pour le moment, PhysicalObject récupère depuis la classe Ground, *tous* les segments constituant le sol, et les sauve dans un array si (1) la distance de l'objet à la droite est inférieur à un seuil donné et (2) la position de l'objet se projette dans les limites du segment. Sauver les segments potentiels pour une collision me permet d'éviter de garder trop de données en mémoire.

Dans l'array (qui est plutot un hashtable en réalité) où je sauve les segments potentiels, je sauve également à chaque itération le "côté" où se trouve mon objet (pos, neg ou zéro). Puis je regarde si entre 2 itérations le signe du côté a changé, et si c'est le cas, j'appelle collide en lui passant en argument le segment en question.

public void update(){
		super.update();
		
		//Then (which comes first), browse elligible segments, and see if side changed
		Set<Segment> set = elligibleSegments.keySet();
		Iterator<Segment> it = set.iterator();
		while(it.hasNext()){
			
			Segment seg = it.next();
			float side = elligibleSegments.get(seg);
			float newSide = seg.getSideOfLine(getPhysicalCenter());
			if(side>0){
				if(newSide<=0){
					collide(seg);
					break;
				}
			}else if(side<0){
				if(newSide>=0){
					collide(seg);
					break;
				}
			}else{
				if(newSide != 0){
					collide(seg);
					break;
				}
			}
		}
		
		//First get eligible ground segments
		float distanceThreshold = 200;
		ArrayList<Segment> segments = this.callingScreen.getWorld().getGround().getAllSegments();
		//only save close segments
		elligibleSegments = new Hashtable<Segment, Float>();
		for(Segment seg:segments){
//			System.out.println("Segment: "+seg.toString());
			float d = seg.getDistanceToPoint(this.getPhysicalCenter());
			boolean projectsOnX = false, projectsOnY=false;
			
			if(getPhysicalCenter().getX()>=seg.getLeftestPoint().getX() && getPhysicalCenter().getX() <= seg.getRightestPoint().getX())
				projectsOnX = true;
			if(getPhysicalCenter().getY()>= seg.getHighestPoint().getY() && getPhysicalCenter().getY() <= seg.getLowestPoint().getY())
				projectsOnY = true;
//			System.out.println("distance to obj:"+d+" \t longueur segment:"+seg.getLength());
			//3 conditions: distance less than threshold, and also projection exists within x or y
			if(d<distanceThreshold && (projectsOnX || projectsOnY) ){
				elligibleSegments.put(seg, seg.getSideOfLine(getPhysicalCenter()));
			}
//			System.out.println();
		}
//		System.out.println("---------------------");
		
		
	
		
		
		
		//Apply gravity
		if(this.applyGravity){
			if(!this.isFixed){
				float g = this.weight;
				this.uAddToDY(g);
			}
		}
	}
	
	//Abstract, must be implemented by concrete implementation to add functionalities to collide event
	protected void collide(Segment seg){
		if(!hasColliden){
			Point t = seg.getTangentVector();
			Point n = seg.getNormalVector(true);
			
			float dotn = speedX*n.getX() + speedY*n.getY();
			float dott = speedX*t.getX() + speedY*t.getY();
			float nsx = (-n.getX()*(dotn)) + (t.getX()*dott);
			float nsy = (-n.getY()*(dotn)) + (t.getY()*dott);
			
			this.speedX = nsx;
			this.speedY = nsy;
			
			
			
			if((this.speedX>0 && dx<=0) || (speedX<0 && dx>=0) )
				dx = -dx;
			if((this.speedY>0 && dy<=0) || (speedY<0 && dy>=0) )
				dy = -dy;

			

			
			hasColliden = true;
		}
	}

Si jamais, voici aussi la classe "Segment" qui fait quelques calculs. Note que dans certains cas, je traite les segments parfaitement verticaux et horizontaux à part.

package net.fredericbaroz.paperplane.world;

import net.fredericbaroz.paperplane.util.Point;

public class Segment {
	
	
	private Point a, b;
	
	
	public Segment(Point a, Point b) {
		this.a = a;
		this.b = b;
	}

	
	public float getDistanceToPoint(Point p){
		
		float distance = 0;
		float s = this.getSlope();
		
		if(Float.isInfinite(s)){ // segment is perfectly vertical
			distance = Math.abs(p.getX()-a.getX());
		}else if(s == 0.0f){ //segment is perfectly horrizontal
			distance = Math.abs(p.getY()-a.getY());
		}else{
			float z = -(1/s);
			float i = this.getYIntercept();
			float j = p.getY() - z * p.getX();
			
			float ix = (j-i) / (s-z);
			float iy = (-(j*s) + (i*z)) / (z-s);
			
			Point interceptPoint = new Point(ix, iy);
			Segment distanceSeg = new Segment(p, interceptPoint);
			
			distance =  distanceSeg.getLength();
		}
		
		return distance;
	}
	public float getSideOfLine(Point p){
		float r = (b.getX()-a.getX()) * (p.getY()-a.getY()) - (b.getY() - a.getY())*(p.getX()-a.getX());
		return r;
	}
	
	public float getSlope(){
		return  ((b.getY()-a.getY()) / (b.getX() - a.getX())); 
	}
	public float getYIntercept(){
		//y = sx + i
		//i = y - sx;
		//take 1 point on the line (lets take a)
		float i = a.getY() -(this.getSlope())*a.getX();
		return i;
	}
	
	public float getLength(){
		
		float dx = b.getX() - a.getX();
		float dy = b.getY() - a.getY();
		return (float) Math.sqrt((dx*dx) + (dy*dy));
	}
	
	public Point getA(){
		return a;
	}
	public Point getB(){
		return b;
	}
	public Point getLeftestPoint(){
		if(a.getX()<=b.getX())
			return a;
		else
			return b;
	}
	public Point getRightestPoint(){
		if(a.getX() > b.getX())
			return a;
		else
			return b;
	}
	public Point getLowestPoint(){
		if(a.getY()>=b.getY())
			return a;
		else
			return b;
	}
	public Point getHighestPoint(){
		if(a.getY() < b.getY())
			return a;
		else
			return b;
	}
	public float getYByX(float x){
		float r = 0;
		float width = (b.getX() - a.getX());
		float percentX = 0;
		if(width>0)
			percentX =  (x - a.getX()) / width;
		else
			percentX = 0;
		if(percentX<0)
			percentX = 0;
		if(percentX>1)
			percentX = 1;
				
			
		r = a.getY() + ((b.getY()-a.getY()) * percentX);
		
		return r;
	}
	public float getXByY(float y){
		float r = 0;
		float height = (b.getY() - a.getY());
		float percentY = 0;
		if(height>0)
			percentY = (y-a.getY()) / height;
		else 
			percentY = 0;
		if(percentY <0)
			percentY = 0;
		if(percentY > 1)
			percentY = 0;
		r = a.getX() + ((b.getX()-a.getX()) * percentY);
		return r;
	}
	
	public Point getMiddlePoint(){
		
		float width = (b.getX()-a.getX());
		float midx=0,midy=0;
		
		if(width!=0){
			midx = a.getX() + (width/2);
			midy = this.getYByX(midx);
		}else{//verticalline
			midx = a.getX();
			midy = a.getY()+( (b.getY()-a.getY()) /2);
		}
		
		return new Point(midx, midy);
	}
	public Point getNormalVector(){
		return this.getNormalVector(false);
	}
	public Point getNormalVector(boolean inverse){
		float x=0,y=0;
		if(inverse){
			x = -(b.getY() - a.getY()) / getLength();
			y =  -(a.getX() - b.getX()) / getLength();
		}else{
			x = (b.getY() - a.getY()) / getLength();
			y =  (a.getX() - b.getX()) / getLength();
		}
		return new Point(x, y);
	}
	public Point getTangentVector(){
		return this.getTangentVector(false);
	}
	public Point getTangentVector(boolean inverse){
		float x=0,y=0;
		if(inverse){
			x = -(b.getX() - a.getX()) / getLength();
			y =  -(b.getY() - a.getY()) / getLength();
		}else{
			x = (b.getX() - a.getX()) / getLength();
			y =  (b.getY() - a.getY()) / getLength();
		}
		return new Point(x, y);
	}
	
	
	
	
	public String toString(String name){
		return name+"/ "+a.toString("a")+" to "+b.toString("b");
	}
	public String toString(){
		return this.toString("S");
	}
}

EDIT : Humm, j'ai analysé plus précisément ce qui se passait lors d'une collision. Je pense que le problème ne vient pas des questions arithmétique mais plutot d'un problème de logique au niveau de mes accélération et vitesses... Je laisse en suspens le temps de régler ce problème et je redis.

-
Edité par gosush 24 mai 2015 à 14:43:11

Il y a des petites choses qui me paraissent inutilement compliquées dans ton code, ça rend la lecture plus difficile. Mais du coup, qu'est-ce qui te fait dire ceci :

Humm, j'ai analysé plus précisément ce qui se passait lors d'une collision. Je pense que le problème ne vient pas des questions arithmétique mais plutot d'un problème de logique au niveau de mes accélération et vitesses...

?

Que représentent dx et dy ?

Sinon, en effet

            Point t = seg.getTangentVector();
            Point n = seg.getNormalVector(true);
             
            float dotn = speedX*n.getX() + speedY*n.getY();
            float dott = speedX*t.getX() + speedY*t.getY();
            float nsx = (-n.getX()*(dotn)) + (t.getX()*dott);
            float nsy = (-n.getY()*(dotn)) + (t.getY()*dott);

Ici, tu as \modelatex_ouvretoi{ V' = (\vec{v} \cdot \vec{u}) \vec{u}  - (\vec{v} \cdot \vec{n}) \vec{n} \modelatex_fermetoi, peu importe le sens des vecteurs u et v, et c'est bien ce que tu as, donc il n'y a pas de soucis là dessus.

Par contre, tu testes ta collision lorsque ton objet traverse le segment, mais si à t=0 il est sur le segment, que tu changes sa vitesse, et qu'à t=1 il est encore sur le segment, l'objet se reprend encore une collision dans l'autre sens, ce qui peut engendrer le glitch de droite. Pour régler ça, Box2D calcule le "time of collision" (pas besoin de traduction je pense), et applique les modifications au temps trouvé, puis resimule le temps de différence qui reste. 

Si je peux me permettre de te donner des conseils,

1) simplifie ton code, crée des fonctions pour manipuler les vecteurs et donner plus de sens à tes équations.

2) évite de normaliser le vecteur normal/tangentiel tant que tu n'en as pas besoin (par exemple, lorsque tu n'as besoin que du signe).

-
Edité par danman 25 mai 2015 à 10:23:05