Discussion :

[b4u]

Bonjour,

voici mon problème: étant donnés
- un terrain à deux dimensions (défini par un buffer de W * H éléments),
- une caméra (définie par ses coordonnées (x, y) sur le terrain et son orientation (angle a)),
- et son champ de visibilité (calculé a partir de la position et l'orientation de la caméra),

comment calculer la "meilleure position" P de la caméra sur le terrain, pour un angle a fixé?


définition de "meilleure position": un couple de coordonnées (x, y) qui génère un champ de visibilité dont les points appartiennent tous au terrain,
ou bien, s'il existe un ensemble E de points du champ de visibilité en dehors du terrain, que le point de E le plus proche de la caméra soit à une distance la plus éloignée possible de la caméra.

je ne vois pas bien comment aborder la partie en rouge...
voila des schémas pour aider a se représenter les données:
angle = 0

angle = a


légende:
rectangle noir --> le terrain
la croix --> un couple de coordonnées de la caméra
points bleus --> points du champs de visibilités appartenant au terrain
points verts --> points du champs de visibilités sortant des limites du terrain

merci pour votre aide


[Edit: reformulation du problème]
Pour un angle donné, comment calculer la (une) position de la caméra telle que son champ de vision contienne le plus de points possibles appartenant au terrain (la surface bleue sur les dessins), sans intersecter les bords du terrain auxquels la caméra tourne le dos?

[PRomu@ld]

s'il existe un ensemble E de points du champ de visibilité en dehors du terrain, que le point de E le plus proche de la caméra soit à une distance la plus éloignée possible de la caméra.

J'ai du mal à comprendre l'énoncé. Et notament cette partie :

que le point de E le plus proche de la caméra soit à une distance la plus éloignée possible de la caméra

Tu as une reformulation ou quelque chose dans ce genre ?

[b4u]

c'est vrai que c'est pas clair...
en fait, il faut trouver la position de la caméra qui génère la meilleure visibilité possible, c-à-d s'il existe des points du champ de vision qui sortent du terrain, alors il faut que ces points la (en verts sur les schémas) soient le plus éloigné possible de la caméra.

[La première idée qui me vient est de parcourir TOUS les points du terrain (pour un angle fixé), et de retenir a chaque fois quels points du champ de vision sortent du terrain, puis de sélectionner la meilleure position de la caméra... mais ça me parait très peu efficace de parcourir le terrain en entier!]

[souviron34]

ben tu dois aussi avoir l'ouverture, non ? (c'est-à dire l'angle obtus parant de la position de la caméra et déteminant ton point de vue ) .

Donc c'est une règle de trois..

Admettons que tu sois avec un alpha de 45 degrés et une ouverture de 90.
Ton point optimal sera le coin en bas à gauche... Tu verras tout.

Si maintenant ton angle est de 0, toujours avec une ouverture de 90, ton point optimal serait au milieu du côté bas.. Tu ne verras ni sommet bas gauche ni sommet bas droit, mais 2/3 du carré.

Donc il te faut trouver cet algorithme... Qui me semble relativement simple...

PAr contre, effectivement ta 2ième condition est assez étrange.

[Graffito]

Bonjour,

Faut-il optimiser ou peut-on se contenter d'un calcyul systématique sur toutes les régions de l'espace ?

J'aurai peut-être une solution, mais je dois vérifier (réfléchir un peu) si elle peut s'adapter au problème.
Si c'est le cas, je posterai plus tard un petit schéma expliquant en 2D la technique.

[Graffito]

Autre question :
Y a-t-il sur le terrain des formes "bizarres" dans les coupes verticales style cheminées de féés :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
       + ----+
      /       \
     +--   +--+
       |   |
       |    \ 
------+      +-------

[b4u]

ben tu dois aussi avoir l'ouverture, non ? (c'est-à dire l'angle obtus parant de la position de la caméra et déteminant ton point de vue ) .

en théorie oui il y a un angle d'ouverture (angle focal), car le champ de vision est en fait la zone du plan passant par le terrain, projetée à l'écran grâce à une projection perspective... maintenant en pratique, pour des raisons d'optimisation, je ne peux déterminer l'ensemble des points du champ de vision que par interpolation linéaire (je trouve un premier point grâce a la position de la caméra, puis chaque point est calculé à partir du précédent).

Admettons que tu sois avec un alpha de 45 degrés et une ouverture de 90.
Ton point optimal sera le coin en bas à gauche... Tu verras tout.

Si maintenant ton angle est de 0, toujours avec une ouverture de 90, ton point optimal serait au milieu du côté bas.. Tu ne verras ni sommet bas gauche ni sommet bas droit, mais 2/3 du carré.

D'accord mais comment déterminer ceci sans vérifier la visibilité pour chaque point du terrain? Par exemple pour angle == 0, comment éliminer d'un coup toute la partie "haute" du terrain?

PAr contre, effectivement ta 2ième condition est assez étrange.

c'est pour prendre en compte le cas ou des points du champ de vision sont en dehors du terrain, mais je reconnais que c'est mal formulé

[b4u]

Bonjour,

Faut-il optimiser ou peut-on se contenter d'un calcyul systématique sur toutes les régions de l'espace ?

Je ne sais pas, tout dépend de la complexité du calcul pour une région donnée. Mais comme je travaille sur un système avec des capacités matérielles très limitées j'aimerais éviter de parcourir tout le terrain pour arriver à la solution... enfin il faudrait tester. Et une solution optimisée est plus élégante, mais ce n'est pas la priorité

J'aurai peut-être une solution, mais je dois vérifier (réfléchir un peu) si elle peut s'adapter au problème.
Si c'est le cas, je posterai plus tard un petit schéma expliquant en 2D la technique.

Merci

[b4u]

Autre question :
Y a-t-il sur le terrain des formes "bizarres" dans les coupes verticales style cheminées de féés :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
       + ----+
      /       \
     +--   +--+
       |   |
       |    \ 
------+      +-------

Non, pas de particularités de ce type le terrain est simplement une map composée de tiles, donc un "rectangle" de pixels de dimension (w * 16, h * 16), avec des tiles de 16x16 pixels.

[souviron34]

en théorie oui il y a un angle d'ouverture (angle focal), car le champ de vision est en fait la zone du plan passant par le terrain, projetée à l'écran grâce à une projection perspective... maintenant en pratique, pour des raisons d'optimisation, je ne peux déterminer l'ensemble des points du champ de vision que par interpolation linéaire (je trouve un premier point grâce a la position de la caméra, puis chaque point est calculé à partir du précédent).



D'accord mais comment déterminer ceci sans vérifier la visibilité pour chaque point du terrain? Par exemple pour angle == 0, comment éliminer d'un coup toute la partie "haute" du terrain?


c'est pour prendre en compte le cas ou des points du champ de vision sont en dehors du terrain, mais je reconnais que c'est mal formulé

Justement, quand je parlais d'ouverture, c'est que tu n'aurais pas besoin de tout calculer, mais juste les intersections avec les côtés, qui du coup te donnent la surface concernée...


Dans le cas que je citais avec 45 degrés, ton intersection est l'angle lui-même, côté gauche et côté bas, donc TOUT le carré est visible.

Dans l'autre cas, par exemple milieu côté gauche et milieu côté droit...

C'est juste ce que je voulais dire..

Et , à vue de nez (je n'ai pas approfondi), mais la trajectoire du meilleur point devrait être un arc de cercle ou de courbe du second degré , tangent au bord bas à un point déterminé par cette ouverture.

[Graffito]

Bonjour,

Le principe d'optimisation auquel je pense consiste à découper l'espace en cubes de taille de plus en plus petite (à chaque pas de traitement, on réduira de moité le coté des cubes).

Si le nombre de points vu de toutes ses arètes est identique, il sera inutile de découper le cube en morceaux, sinon on le divisera en 8 sous-cubes et on traitera les arètes non encore traitées de chaque sous-cube.

De cette façon, on ne traitera en détail que les zones limites où il y a des changements de visibilité.
La figure ci-dessous donne un aperçu (2D) des calculs et découpages à quelques pas de traitement.

Pièce jointe 12915
On évitera évidemment de traiter/découper tout sous-cube dont la meilleure visibilité sur les arètes est moins bonne que la meilleure visibilité trouvée à ce moment-là :
- point(s) calculés au début du process et ayant à priori une bonne visibilté (centre de la zone, à l'altitude max), sur les autres sous-cubes déjà traités.
- Max pour tous les sous-cubes traités du minimum de visibilité calculée sur ses arètes.

[pseudocode]

Hum... ca fait 5 fois que je relis l'énoncé et je ne comprend toujours pas.

Tel que je vois le probleme, a l'instar de souviron34, c'est un déplacement le long de la Longueur du terrain.

- angle [0...90] -> position dans un coin

- Angle = 180 -> Au milieu de la Longueur

- Entre les 2, une jolie equation de trigo sur laquelle je vais mediter...

[Graffito]

J'avoue que je n'ai rien compris non plus à la partie rouge :

s'il existe un ensemble E de points du champ de visibilité en dehors du terrain, que le point de E le plus proche de la caméra soit à une distance la plus éloignée possible de la caméra.

[pseudocode]

J'avoue que je n'ai rien compris non plus à la partie rouge :

J'ai traduit ca par: "ne pas avoir une tête de spéctateur au premier plan !"

Bref il faut que la position de la camera soit "dans" ou "sur le bord" du terrain.

[Graffito]

Bref il faut que la position de la camera soit "dans" ou "sur le bord" du terrain.

Si le "terrain" est une surface, je dirai "sur" ou "au-desssus avec une limitation d'altitude".

[b4u]

s'il existe un ensemble E de points du champ de visibilité en dehors du terrain, que le point de E le plus proche de la caméra soit à une distance la plus éloignée possible de la caméra.

Bon on est d'accord, ça ne veut rien dire

Justement, quand je parlais d'ouverture, c'est que tu n'aurais pas besoin de tout calculer, mais juste les intersections avec les côtés, qui du coup te donnent la surface concernée...


Dans le cas que je citais avec 45 degrés, ton intersection est l'angle lui-même, côté gauche et côté bas, donc TOUT le carré est visible.

Dans l'autre cas, par exemple milieu côté gauche et milieu côté droit...

C'est juste ce que je voulais dire..

Et , à vue de nez (je n'ai pas approfondi), mais la trajectoire du meilleur point devrait être un arc de cercle ou de courbe du second degré , tangent au bord bas à un point déterminé par cette ouverture.

ok, tu as bien fait d'avoir insisté là-dessus, ça me permet maintenant de mieux cerner et exprimer le problème. Je vais éditer mon post de départ avec une reformulation de l'énoncé.

Bonjour,

Le principe d'optimisation auquel je pense consiste à découper l'espace en cubes de taille de plus en plus petite (à chaque pas de traitement, on réduira de moité le coté des cubes).

je vais regarder ce que tu me proposes plus en détail (dans ce présent cas ce sera plutôt des carrés que des cubes, mais ça ne change rien au fond). Merci

Si le "terrain" est une surface, je dirai "sur" ou "au-desssus avec une limitation d'altitude".

effectivement le terrain est un plan, et la caméra est à altitude fixe au dessus de ce plan. Le champs de vision est en deux dimension (vu qu'il est composé uniquement de points appartenant au plan passant par le terrain).

[souviron34]

Edit: reformulation du problème
Pour un angle donné, comment calculer la (une) position de la caméra telle que son champ de vision contienne le plus de points possibles appartenant au terrain (la surface bleue sur les dessins), sans intersecter les bords du terrain auxquels la caméra tourne le dos?

je ré-itères ce que j'ai dit ci-dessus http://www.developpez.net/forums/sho...7&postcount=10

à mon avis c'est un arc de cercle passant par le point central du côté bas, et donc les intersections avec les côtés droit et gauche sont déterminés par l'ouverture.

Fais un dessin, ça marche...

[maamar]

je pense, qu'il faut voir les algorithmes de niveaux de details (LOD)
il se peut qu'ils sont utile dans votre cas,
essaie aussi de chercher par ce mot clé : View Frustrum

pour cela je vous invite à visiter les sites suivants :

http://www.vterrain.org/LOD/Implementations/index.html
http://lodbook.com/