Discussion :

[zenux]

Bonjour,

J'ai besoin de déterminer l'enveloppe convexe à partir des 8 points du champ de vision et un autre point placé de façon quelconque; le tout en 3d.

Quel est l'algorithme le plus rapide et qui convient pour la 3d ?

-Un algorithme naïf, en O(n3)
-Un algorithme incrémental, en O(nlogn)
-L'algorithme de Graham, en O(nlogn)
-L'algorithme adaptatif dit "gift wrapping" ou de Jarvis, en O(nh)
-Quickhull, en O(nlogn)
-Un autre algo que je n'ai pas cité ?
-Un algo spécialement adapté pour ce que je veux faire ?

Autre question : que signifie O(nh) ?

Merci d'avance

[screetch]

O(nh) est une complexité en O(n x h) ou h represente en general la hauteur. dans le cas qui t'interesse, h represente le nombre de points appartenant effectivement a l'enveloppe convexe.

l'algorithme le plus efficace est en general le quickhull, sauf si tu te retrouves avec un tres grand nombre de points (un nuage) et une enveloppe composée de quelques points. dans ce cas le gift wrap est beaucoup plus rapide.

je n'ai pas compris ce que tu voulais dire par "déterminer l'enveloppe convexe à partir des 8 points du champ de vision et un autre point placé de façon quelconque; le tout en 3d." c'est quoi les 8 points du champ de vision ?

[Camel LowFilter]

il doit parler des 8 points du frustum de camera , plus un 9eme

(dans ce cas c'est le quickhull)

[zenux]

Merci pour ta réponse.

Le champ de vision en 3d est en forme de trapèze avec un "near clip plane" formé de 4 points et un "far cli plane" formé de 4 points : http://wwweic.eri.u-tokyo.ac.jp/comp...pect.ratio.gif
Quant au point quelconque, c'est en fait la position d'une lumière.

Ensuite j'aimerais obtenir une enveloppe convexe avec ces 4+4+1 points.

Le but : si un objet 3d se trouve en dehors de cette enveloppe convexe, alors je ne suis pas obligé d'afficher son ombre (culling d'ombres).

[screetch]

dans ce cas un simple test de direction par rapport aux plans sufirait

ton frustum est delimité par 6 plans. pour qu'un point soit a l'interieur il suffit de verifier qu'il est bien du meme coté du plan que le frustum

pour cela on calcule le produit vectoriel OA, OX ou O est un point du plan (c'est egalement un point du frustum), A est un point tel que OA est la normale du frustum, X est le point que tu cherches

a faire sur les 6 plans

[zenux]

Soit j'ai mal compris ce que tu m'a dit soit tu as oublié quelque chose : un objet 3d en-dehors du frustum peut avoir son ombre à l'intérieur du frustum.

Il me semble que ce que tu me décrit, c'est du culling d'objet 3d.

Si je n'ai rien compris, merci de bien vouloir me ré-expliquer parce que une solution plus simple que le quickhull ne me dérangerais pas dutout

[screetch]

ah non je pensais que tu voulais verifier si la lumiere etait dans le frustum, c'est moi qui n'ai pas compris desole