Discussion :

[Albenejean]

Bonjour à tous.

J'ai un petit probleme pour vous.

Voilà, je dispose d'un terrain constitué de point (X, Y, Z), vérifiant les propriétés suivantes:
X est un entier tel que 0<=X<=Xmax
idem pour Z (entier 0<=Z<=Zmax)
0 <= Y <= Ymax (mais pas un entier)

Je lance un rayon et j'aimerai trouver son point d'intersection.

Je suis parti selon la méthode suivante:
_ je calcule l'intersection entre mon rayon et les plans Y=Ymin et Y=Ymax
_ j'obtient une droite dont les équations sont :
X = Xmax - t*(Xmax - Xmin)
Y = Ymax - t*(Ymax - Ymin)
Z = Zmax - t*(Zmax - Zmin)
_ je pars de t=0
_ je cherche le premier point de la droite qui vérifie X entier ou Z entier
_ je calcule les coordonnées de ce points et test pour savoir s'il y a intesection avec les triangle de mon terrain
_ si non, je passe au point suivant vérifiant X entier ou Z entier.

Malheureusement, si ça m'a l'air bon sur le papier, mon code est faux ou ne donne pas le résultat espéré. Bref, j'ai besoin d'aide, soit pour me trouver une méthode plus simple, soit pour m'écrire le code (C++). Merci.

[pseudocode]

_ je cherche le premier point de la droite qui vérifie X entier ou Z entier

Je ne vois pas de raison pour que le point d'intersection rayon/terrain ait un X et un Z entier.

[Nemerle]

Parce que le terrain est un ensemble discontinus de bouts de droite en Y (X et Z sont tj entiers).

Mias je pense comme toi qu'il a mal présenté son problème...

[pseudocode]

Parce que le terrain est un ensemble discontinus de bouts de droite en Y (X et Z sont tj entiers).

??? Et alors ?

C'est pas a toi que je vais apprendre que si un triangle a ses 3 sommets avec des coordonnées entieres ca ne veut pas dire que TOUS les points contenus dans le triangle ont des coordonnées entieres.

[Nemerle]

CE n'est pas le problème ici.........

[pseudocode]

Pourtant ca m'a l'air d'etre son probleme.

C'est un simple algo d'intersection ligne/triangle. Le fait que le triangle ait des coordonnées X et Z (et meme Y) entieres ne permet en rien de prédire le point d'intersection.

pour info, le calcul d'intersection ligne/triangle est dispo ICI

[Albenejean]

Merci pour le lien, je me suis rendu compte (hier soir) que la fonction fournit par DirectX pour l'intersection Triangle-Rayon ne répond pas vraie pour tous les sommets(??).

Je ne vois pas de raison pour que le point d'intersection rayon/terrain ait un X et un Z entier.

Oui, oui, mais avoir X ou Z entier me permettait de définir mes triangles. J'ai changé maintenant.
Mon probleme est de parcourir uniquement les triangles susceptible d'être touché par le rayon et sans en oublier un.

Bon je vais tester en remplaçant la fonction DirectX, pour voir si ça marche mieux. Je vous donne quand même un pseudo code de ce que je fais:

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
PointMax = point d'intersection entre mon rayon et le plan d'équation Y=(HauteurMax de mon terrain)
PointMin = point d'intersection entre mon rayon et le plan d'équation Y=(HauteurMin de mon terrain)
Delta = PointMax - PointMin
 
//définition du sens de parcours selon la direction de mon rayon
if(Delta.x > 0)
  MoveX = 1;
else
  MoveX = -1;
if(Delta.z > 0)
  MoveZ = 1;
else
  MoveZ = -1;
 
//Point va être sur le droite d'équation PointMax - t*Delta
Point = IntersectMax
 
while( t<=1.0f)
{
   // test du triangle { ((int)Point.X, (int)Point.Z); ((int)Point.X+1, (int)Point.Z); ((int)Point.X+1, (int)Point.Z+1)
   // test du triangle { ((int)Point.X, (int)Point.Z); ((int)Point.X, (int)Point.Z+1); ((int)Point.X+1, (int)Point.Z+1)
 
   //on passe aux prochain triangles   
  //on cherche le temps minimal pour passer à une des cases d'à coté
   tx = (PointMax.x - Point.x + MoveX)/Delta.x;
   tz = (PointMax.z - Point.z + MoveZ)/Delta.z;
   if(tx < tz)
      t=tx;
   else
      t = tz;
   if(Delta.x == 0)
      t=tz;
   if(Delta.z == 0)
      t=tx;
   Point = PointMax - Delta * t;
}

Ca à l'air tous simple, mais .... euh... c'est vrai que je suis mal partis avec ses histoires d'entier.