appartenance d'un triangle à un rectangle [clipping] - Algo - Programmation
Marsh Posté le 27-10-2004 à 19:02:42
Ben ton triangle est entierement dans ton rectangle ssi les trois points sont dans le rectangle
Marsh Posté le 27-10-2004 à 20:34:38
matafan a écrit : Ben ton triangle est entierement dans ton rectangle ssi les trois points sont dans le rectangle |
Marsh Posté le 28-10-2004 à 17:51:47
matafan a écrit : Ben ton triangle est entierement dans ton rectangle ssi les trois points sont dans le rectangle |
Je ne veut pas tester si le triangle est entièrement dedans mais si il y a une partie de ce triangle dans le rectangle, dans tous les cas de figures (que le triangle soit entièrement dedans, qu'il contienne quelques point ou meme si le triangle contient le rectangle).
Marsh Posté le 28-10-2004 à 18:55:18
Point point1, point2, point3;
if (point1.y>point2.y) alors swap(point1,point2);
if (point2.y>point3.y) alors swap(point2,point3);
if (point1.y>point2.y) alors swap(point1,point2);
bool ok = not ( (point1.y<0 && point3.y<0) || (point1.y>maxY && point3.y>maxY));
A partir de là, tu fais ton occlusion classique.
Si tu n'as pas besoin de les afficher toi-même, alors teste que tous les points ne sont pas sous 0 ou au dessus de maxX.
Si à tout hasard maxX est une puissance de 2 et que ton processeur est en complément à 2, alors
ça s'optimise avec un ou logique sur le bit immédiatement au dessus de la taille max.
Marsh Posté le 01-11-2004 à 20:11:27
L'algo que j'ai décrit plus haut n'est pas bon. Apres un peu de réflexion, on voit qu'il ne marche pas.
J'ai trouvé le vrai algo de Warnock, les cas dépendent selon si le polygone fait une intersection evc le rectangle, le contient ou est contenu.
Une vrai description de l'algo ici :
http://www.inrialpes.fr/movi/peopl [...] ise/c6.pdf
http://www.evl.uic.edu/aej/488/lecture10.html
Marsh Posté le 02-11-2004 à 09:19:41
ya des bon algos de "clipping"... faudrait que je les retrouve
Marsh Posté le 02-11-2004 à 14:04:52
moktar1er a écrit : ya des bon algos de "clipping"... faudrait que je les retrouve |
Oui, il y a aussi :
- l'algorithme du peintre (tous dessiner en partant du plan le plus profond), trop long pour une aplli sur un mobile (la méthode pour dessiner un pixel est gourmande).
- le Z-buffer mais gourmand en mémoire.
- les BSP-Trees, mais qui ne servent que si on a un mouvement de caméra.
Il y en a d'autres mais pour la 3D, pour savoir quelles faces afficher sur des polygones.
Mais si tu as d'autres algos à me proposer, je suis preneur.
Marsh Posté le 02-11-2004 à 14:23:47
Cohen-Sutherland ou Sutherland-Hodgeman pour du fenêtre rectangulaire
sinon Cyrus-Beck pour du fenêtrage à polygone convexe
Marsh Posté le 02-11-2004 à 14:26:54
Cohen-sutherland, c'est du solide, de l'eprouvé, de l'efficace
j'l'avais utiliser du tps ou je faisais du SVG en java sur PDA (bonjour les perfos) et j'avais pas eu a m'en plaindre. Par contre, je sais pu si j'etais passé en virgule fixe pour cette partie ou pas. Je pourrais regarder ce soir si tu veux
Marsh Posté le 02-11-2004 à 17:05:03
J'ai trouvé un algo (http://www.cc.gatech.edu/grads/h/H [...] code1.html), mais il se sert de 2 nombres réels a un moment.
Merci beaucoup néanmoins, je vais continuer mes recherches.
Marsh Posté le 03-11-2004 à 21:34:53
Bon mon cohen-suther truc etait bien en java, 100%entier, virgule fixe (16:16). Par contre fallait caster en long avant la div, sinon ca faisait overflow et ca rendait ca :
pour une clipping sur un edge horizontal, par exemple, j'avais ca: (m_iVal etant l'ordonnée de l'axe)
Code :
|
end.x & cie etant des entier en virgule fixe
Marsh Posté le 09-02-2005 à 15:57:38
J'ai ceci comme algorithme de détection d'intersection d'un triangle et d'un rectangle :
FP.intersects(xa1, ya1, xa2, ya2, xb1, yb1, xb2, yb2) rend vrai si les segments a1-a2 et b1-b2 font une intersection.
t.a référence le point a du triangle, t.a.x son abscisse ....
x, y, width et height sont respectivement l'abscisse du rectangle, son ordonnée, sa largeur et sa hauteur.
Code :
|
En gros : un triangle et un rectangle font une intersection si un des cotés du triangle fait une intersection avec un des cotés du rectangle.
Seulement voila, le code de cet algo qui me semble juste (j'ai surement tort) ne fonctionne pas, alors que le raisonnemnt ci dessus me semble très correct
Marsh Posté le 16-02-2005 à 16:38:49
je n'ia aps de solution a ton problème, mais juste que si le triangle contient le rectangle comme dis dans les premiers posts, aucun coté est en intersection avec d'autres....
donc ton raisonnement en bon mais qu'en partie....
Marsh Posté le 16-02-2005 à 16:52:10
J'aurai du dire, mais ce n'est plus la meme question. C'est dans le meme cadre mais pour ce dernier pôst, je cherche juste si un triangle et un rectangle font une intersection.
Marsh Posté le 26-10-2004 à 11:28:42
Salut, je travaille nen ce moment sur des algos 2D et j'ai un problème sur le "Hidden Surface Removal".
J'utilise l'algorithme de Warnock dont voici l'algo :
Dans mon algorithme, je prends des triangles comme polygones uniquement.
Mais je ne sais pas comment tester si un triangle a des points dans une région ou pas (la région étant un rectangle).
Par contre, j'ai de fortes contraintes pour cet algo (c'est du développement sur téléphone portable) :
- Il faut que mes algo utilisent unquement des entiers
- Les performances de l'algo doivent etre optimales.
Donc je ne put pas tester l'appartenance de chaque point du triangle, ni en définir les équation de droite des cotés (ce ne sont pas des entiers).
Message édité par yo c spi le 02-11-2004 à 14:10:54
---------------
J.C. Farinet