Bonjour à tous,

J'ai un modèle 3D décrit par sa surface découpée en triangles. Pas forcément convexe.
Je cherche à déterminer si chaque face est éclairée par ma source ou non. La source est située à l'infini (tous les rayons sont donc parallèles). Seulement, je ne vois pas d'algorithme simple sans complexité élevée (genre O(n²)). Par ailleurs, utiliser le gpu serait un plus.
Est-ce possible d'utiliser opengl pour ça ? Rendre chaque face, et utiliser une fonction pour connaitre lesquelles ne sont pas entièrement cachées ?
Comment faire dans ce cas ?

Merci !

(je précise : il existe des algos plus complexes genre z buffer etc. mais dans ce cas je préfère utiliser une implémentation déjà faite et autant utiliser celle d'opengl si possible)

Indice : l'algo de OpenGL c'est un Zbuffer !
Moi je le ferai en raytracing, mais ça sera pas forcément du temps réel.
Et il n'y a pas d'algo "simple" parce que c'est un problème compliqué.
Par contre je suis pas sur d'avoir bien compris ce que tu veut faire avec ton histoire de face éclairée, tu peut détailler ?

C'est surprenant comme besoin, j'ai du mal à imaginer ce que ca apporte. C'est un exercice pour un cours ?
 
Sinon, ce que tu cherches à faire, ca ressemble à ce qu'on doit faire pour faire des shadow map, peut-être que tu voudras regarder un peu de documentation à ce sujet.
 
Sinon, naïvement, oui, je partirais sur un rasterizer avec z-buffer à une résolution que tu considères comme acceptable. Si tu écris dans ton "framebuffer" l'index de la face (ce serait plutôt quelque chose à faire dans un stencil buffer cela dit). Une fois que tu as tout dessiné il ne te reste plus qu'à traverser ton frame/stencil buffer pour collecter tous les index des faces qui sont au moins partiellement visibles. Les index que tu ne trouves pas sont ceux des faces complètement cachées.
 
(au passage, un rasterizer avec z-buffer, c'est pas si complexe que ca)
 

Merci pour vos réponses !
 
J'explique pourquoi j'en ai besoin :
 
Je fais des simulations qui nécessitent de savoir si la face d'un astéroïde est éclairée ou non par le soleil (source à l'infini donc). Les formes d'astéroïdes ne sont pas forcément convexes (sans quoi je pourrais faire ça très simplement), et sont décrites par un "triangle mesh".
 
Si je peux éviter du raytracing c'est bien. Ta solution m'intéresse theshockwave, mais je ne suis pas sûr de savoir techniquement comme la réaliser, faut que je regarde comment fonctionne le stencilbuffer.
 
Au passage : vous savez comment fonctionne la méthode avec octree ? Pour un autre besoin mon objet est dans un octree mais celui-ci est aligné avec des axes fixes donc je ne sais pas si ça aide
 
 

 
J'ai déjà implémenté un raytracer, mais je n'ai jamais écris la traversé de l'octree (ou KD-Tree).
Le raytracing c'est vraiment pas compliqué, il faut juste pomper la formule pour les intersections triangles-rayons sur wikipedia !
Tu comptes gérer comment le fait qu'une face soit à moitié éclairée par le soleil ?

soit je les suppose éclairées à 100 % en sachant que l'erreur commise sera d'autant plus faible que la résolution de la surface (nombre de faces) est élevée
soit, en fonction de la méthode, il existe un moyen d'estimer la fraction de surface éclairée.
 
j'ai déjà un code débile en O(n²) et pourri par ailleurs parce que pour l'instant il réduit les faces test à des points (un rayon par face). Du coup, il "oublie" certaines faces cachées.
je peux essayer d'implémenter un raytracer. je suis d'accord, ce n'est pas si compliqué et d'ailleurs j'ai déjà l'essentiel du code pour la géométrie. Mais, il risque d'être lent, et j'aurais bien aimé bénéficier du GPU.

Un raytracer ça se parallélise très bien sur GPU, mais c'est un peu plus complexe !
Par contre c'est aussi en O(n²) un raytracer...
Du coup je vois pas vraiment ce qu'il y aurait de plus rapide comme algo.
Un zbuffer à la rigueur, effectivement.
Mais du coup pour openGL, je ne connais pas du tout et je ne sais pas comment faire, là tu es tout seul.

 
 
Si tu pars sur un Raytracer, ca peut avoir une utilité de mettre l'ensemble de tes triangles dans un octree effectivement. Pour chaque rayon que tu envoies en direction d'un triangle, tu pourrais donc demander l'ensemble des triangles qui sont dans des "feuilles" de ton octree sur ton chemin. Ca te permet de limiter le nombre de tests de collisions que tu dois faire et du coup, de tendre vers du O(N*log(N)) au lieu de ton O(N²)
 
Tu peux trouver des exemples d'octree online, si tu as un ensemble de données statiques, une approche de ce genre est tout à fait adaptée .
 
Accessoirement, pour ton problème de ray tracing qui manque de précision, tu peux toujours essayer de prendre plus de points par triangle pour valider sa visibilité, ou sinon, donc, tu prends une approche plus typique d'un raytracer : tu considères une résolution donnée pour ton raytracer et tu "marques" chaque triangle que tu rencontres à ta résolution fixe. Il se peut qu'il te manque des triangles, mais plus ta résolution sera haute, moins ce sera probable, et tu peux peut-être te permettre une certaine tolérance ?

Merci
bon du coup j'ai un algo qui me récupère les faces d'intersection potentielles. Maintenant je ne suis pas très sûr de la façon optimale de procéder. Je pourrai faire plusieurs tests d'intersection point triangle, plusieurs tests triangle-triangle après translations dans la bbox du triangle cible.
enfin pour l'instant ça n'a pas l'air de bien fonctionner, je risque de revenir vers vous Merci !

J'utiliserai openGL, sans shading et en assignant une couleur par triangle.
Ensuite tu parcours l'image rendue pour mesurer la surface visible de chaque triangle.

Pour moi c'est du O(n) et delestable en partie au GPU

 
On est d'accord

Ok, j'ai fait ça alors.
Simplement, la lecture de la frame est assez lente avec glReadPixels.
Y a-t-il une meilleure méthode ?
Par ailleurs : connaissant la "axis aligned bounding box" de mon objet, et la matrice de rotation (je la calcule moi-même), comment paramétrer glOrtho pour exploiter au mieux le viewport ?
 
Merci !

 
Tu n'as pas une méthode pour te retourner l'intégralité du FrameBuffer d'un coup ?

je croyais que c'est ce que faisait glReadPixels, peut être naïvement :

uchar *buf = new uchar[3*w*h];
glReadPixels(0, 0, w, h, GL_RGB, GL_UNSIGNED_BYTE, buf);

Du coup, j'ai du mal à imaginer que ce souci de performances là soit le plus gros problème pour ta situation.
Peut-être que tu ne nous a pas décrit l'intégralité de ta tâche ?

Edit : est-ce que ton frame buffer est vraiment en 24 bits ? S'il est plutôt en 32 bits, ca n'irait pas plus vite de faire le readPixels en RGBX ou RGBA plutôt ?

ah si, ça prend de l'ordre de 1 seconde pour effectuer ça
EDIT: ok j'ai aligné ça sur 32 bits, et fait une optimisation supplémentaire, c'est beaucoup plus rapide

Merci!

J'ai encore une question concernant glOrtho
mon objectif est d'utiliser au maximum mon viewport, pour que le nombre de pixels "vides" soit le plus bas possible.
Je ne sais pas trop comment faire. Voilà mon code :
 

void set_renderer()
{
    glViewport (0, 0, w, h) ;
    
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    
    //glOrtho(asteroid1.mdl->bbmin.x, asteroid1.mdl->bbmax.x, asteroid1.mdl->bbmin.y, asteroid1.mdl->bbmax.y, asteroid1.mdl->bbmin.z, asteroid1.mdl->bbmax.z);
    glOrtho(asteroid1.mdl->o.x-asteroid1.mdl->size, asteroid1.mdl->o.x+asteroid1.mdl->size, asteroid1.mdl->o.y-asteroid1.mdl->size, asteroid1.mdl->o.y+asteroid1.mdl->size, asteroid1.mdl->o.z-asteroid1.mdl->size, asteroid1.mdl->o.z+asteroid1.mdl->size);
 
    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();
    glTranslated(-asteroid1.centerofmass.x, -asteroid1.centerofmass.y, -asteroid1.centerofmass.z);
 
    vec dir = asteroid1.pos;
    dir.normalize(10);
 
    gluLookAt(-dir.x, -dir.y, -dir.z,
              0, 0, 0,
              asteroid1.plan.x, asteroid1.plan.y, asteroid1.plan.z);
 
    matrix m(4, 4);
    for(int i = 0; i < 4; ++i) for(int j = 0; j < 4; ++j)
    {
        if(i < 3 && j < 3) m[i][j] = asteroid1.rotmatrix[i][j];
        else if (i != j) m[i][j] = 0;
        else m[i][j] = 1;
    }
    double *arr = m.array();
    glMultMatrixd(arr);  
    delete[] arr;
}

 
remarquer les deux appels à glOrtho. Le premier, commenté, utilise une AABB de mon objet. Le second utilise une AABB cubique qui contient l'AABB précédente.
Si j'utilise la première, il y a des trous, à cause de la rotation de mon objet.
Si j'utilise la seconde, beaucoup d'espace est inutilisé.
Quelle est la meilleure façon de faire ? Dois-je calculer ceci à la main? donc appliquer la matrice de ma modelview aux coins de mon AABB ?
 
Merci !

Tu ne peux pas recalculer l'AABB de ton mesh directement en world-space ? Parce que vraisemblablement ici, ton souci vient du fait que tu transformes ton AABB d'object-space à world-space, ce qui, pour une AABB, n'est pas du tout idéal.

Tu veux dire comme ça ? j'ai fait ça plus tôt.
En gros, je récupère la matrice modelview et je l'applique au 8 sommets de mon AABB puis je récupère les coordonnées extrêmes pour glOrtho.
Ça devrait fonctionner, je pense, mais j'ai repéré quelques artefacts plus tôt, comme une partie de l'objet qui apparait en premier plan (c'était bizarre et assez court).
 

void set_renderer()
{
    static double viewmatrix[16];
 
    glViewport (0, 0, w, h);
 
    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();
    glTranslated(-asteroid1.centerofmass.x, -asteroid1.centerofmass.y, -asteroid1.centerofmass.z);
 
    vec dir = asteroid1.pos;
    dir.normalize(1);
 
    gluLookAt(-dir.x, -dir.y, -dir.z,
              0, 0, 0,
              asteroid1.plan.x, asteroid1.plan.y, asteroid1.plan.z);
 
    matrix m(4, 4);
    for(int i = 0; i < 4; ++i) for(int j = 0; j < 4; ++j)
    {
        if(i < 3 && j < 3) m[i][j] = asteroid1.rotmatrix[i][j];
        else if (i != j) m[i][j] = 0;
        else m[i][j] = 1;
    }
    double *arr = m.array();
    glMultMatrixd(arr);  
    delete[] arr;
 
    glGetDoublev(GL_MODELVIEW_MATRIX, viewmatrix);
    for(int i = 0; i < 4; ++i) for(int j = 0; j < 4; ++j)
    {
        m[i][j] = viewmatrix[i+4*j];
    }
 
    // recompute bounds for glOrtho
    vec bounds[8];
    for(int i = 0; i < 8; ++i)
    {
        bounds[i] = asteroid1.mdl->bounds[i];
        bounds[i].mul4d(m);
    }
 
    vec min, max;
    vector<double> coordinates[3];
    for(int i = 0; i < 8; ++i) for(int j = 0; j < 3; ++j)
    {
        coordinates[j].push_back(bounds[i].v[j]);
    }
 
    for(int j = 0; j < 3; ++j)
    {
        min.v[j] = *min_element(coordinates[j].begin(), coordinates[j].end());
        max.v[j] = *max_element(coordinates[j].begin(), coordinates[j].end());
    }
 
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
 
    glOrtho(min.x, max.x, min.y, max.y, min.z, max.z);  
}

non, je parlais de faire la transformation de tous les points/sommets de ton astéroide dans l'espace dans lequel tu transformes ton AABB et donc construire une nouvelle AABB à partir de ces points transformés.La transformation d'une AABB va te donner un résultat beaucoup plus gros que nécessaire (enfin, en fonction de la rotation, la déviation vis-à-vis de l'AABB désirée va varier).

Ok
pour le problème mentionné plus haut, c'est un faux problème, simplement l'absence de perspective donnait une impression bizarre, mais ça semble fonctionner
 
en effet ce n'est pas optimal : je pourrais donc faire comme tu dis, avec un bémol, le nombre d'opérations supplémentaires à réaliser (sur plusieurs milliers de points auxquels appliquer la transformation)
 
Merci !

"Plusieurs milliers de points", ca doit sans doit encore aisément se transformer en une ou deux millisecondes sur une machine récente  

 
ok

A titre de curiosité, comment sont organisées tes données ?
Tu as bien un index buffer + vertex buffer pour représenter ta géométrie ? Je vois des double dans ton code, tu ne travailles pas avec des float ?

Edit : Accessoirement, aussi, as-tu d'autres informations que tu associes à chaque sommet ? Parce que les performances de ta transformation vont surtout être limitée par la bande passante mémoire, en théorie, donc plus tes données sont compactes, plus ca ira vite.

non je n'utilise pas ces structures pour les stocker
en fait à la base, je n'utilisais opengl que pour avoir une visualisation de ce que je faisais : l'essentiel des calculs consiste en la résolution numérique d'une équation aux dérivées partielles à 2D pour chaque face de l'objet.