Salut!
Je suis en train de developper un éditeur de jeux 3D a la RPGMaker 2000 ( faites travailler votre imagination : )

Je pense que je risque d´avoir besoin a terme d´un frustum culling, mais la question est
"Serait il possible d´user le hardware pour ca ? "

Je m´explique : OpenGL offre un moyen via gluPickMatrix, GL_SELECT, glLoadName... d´identifier les meshs dessinés dans une zone de l´écran...Tout comme le frustum culling classique a part qu´on obtient la reponse dans un tableau d´entier...En plus, on obtient les coordonnées Z de ces boites, donc on peut eviter de rendre celle qui son rendues trop loin dans un brouillard...

Alors la solution tient en peu de ligne de code, accessible a l´allergique aux maths que je suis et cela pourrait peut etre accelerer ce traitement du frustum culling en transferant la charge de calcul a la carte graphique ( elle qui aime bien les matrices...)???!!!

Alors...Est ce reellement intéressant ?

tu peux répeter en français
SVP

LOL =|

Je ne connais pas trop ce système, mais dans ta question je peux lire "[...]d´identifier les meshs dessinés dans une zone de l´écran[...]", ce qui signifie que si le mesh est déja dessiné c´est trop tard, le clipping n´a plus aucun interet puisque le but du frustum culling est d´empecher ce mesh d´etre dessiner lorsqu´il est hors écran. Pareil pour la carte graphique, il n´est pas possible d´envoyer tout ses objets à la carte pour qu´elle "clippe", tu encombrerais le BUS et la charge GPU pour rien.

Je suis en train de faire également un editeur 3D style RPGMONKU pour mon moteur de jeu. J´ai fait un landscape avec une méthode de clipping "made in dino" qui semble etre efficace, si c´est ca que tu recherches, je peux t´aider.

Bon, avec juste un topic dur de t´aider

mais si tu as des problemes avec les matrices, ou des problemes d´adaptation a cause des maths, donne moi les prototypes des fonctions que tu veux utiliser ainsi que la structure de ta classe Matrix, et j´essaierai de te l´implémenter.
J´ai fait bcp de théorie sur la 3D, et de projets pour la fac, je m´en sors bien en produits scalaires, vectoriels et matrices
Mail moi.

Oulà...
Ce que tu parle, c´est le mode Select d´OpenGL, c´est effectué pour trouver quels polys ont étés dessinés selon un numéro que leur aurait préalablement attribués.

Je ne voit pas trop le rapport avec le frustrum culling, si c´est de la même chose que nous parlons. Le Fustrum Culling, pour moi, c´est le culling de polys dessinés hors du frustrum...
Et il me semble que OpenGL gère ça automatiquement...
Mais tu voudrais te le faire toi même, c´est ça?
Si tout ce que j´ai dit avant est vrai(je peut me tromper) alors:
PRIMO:
Il faudrait que tu le dessine 2 fois, une fois pour trouver tes polys a clipper, une 2ème fois pour renderer tes polys non clippés.
SECUNDO:
Tes polys auraient été déjà clippés lors de ton premier rendering =)

Résultat: Tu dessine toute la scène une fois, puis après tu la redessine une deuxième fois, mais sans les polys clippés...

Le seul intéret que je vois à ça: le drag-and-drop; C´est simple: tu dessine ta scène de base une fois, puis tu garde les numéros de polys qui aurant été non-clippés dans une banque de polys à renderer. Ensuite, tu te contente de renderer que les polys qui aurant été Sélect-és + :
-si le curseur est en train de faire autre chose, c´est tout.
-si le curseur est en train de drag-er un poly ou un set de polys, tu les render.
-si les polys viennent d´être drag-és, tu les rajoutes à ta liste de polys à renderer, et ça recommence...

C´est la seule solution viable à ton idée que j´entrevois, si je me suis pas gouré quelque part et/ou que je t´ai bien compris...

Kelios
---------

JeanYvesYves!!! MOI MOI ! !!

Tu saurais faire des algos de colisions optimisés de type Sphere/Triangle et Rayon/Triangle ?

Parce que je les ai fait... mais il ne sont pas optimisés...

: (

Bon je la refais en détaillant alors :
( ou alors je confond avec une autre technique)

La technique consiste a découper l´espace en une multitude de cubes, et de n´afficher que les meshs des cubes qui sont dans le frustum, ce qui a pour effet de libérer le bus et la charge de la carte graphique puisqu on réduit le nombre de mesh que l´on envoie ( puisque pour une grande partie des meshs, ceux-ci étaient en dehors du champ de vision : maintenant, on ne le affiche plus).

Habituellement, cette technique decoupe l´espace est en x cubes eux meme sous découpés en plus petits cubes. Bien sur les polygones qui nous interessent ( votre bonhomme en 3D, le terrain, etc) appartiennent aux différents cubes suivant leurs positions dans l´espace.

La premiere étape consiste a utiliser GL_SELECT et rendre tous les cubes pour obtenir une liste des cubes qui "apparaissent" à l´écran ( en réalité, rien n´est affiché). Une fois la liste des cubes affichés obtenus, il suffit de rendre a l´écran tous les objets associés aux cubes précédement visibles pour obtenir notre scene épuré de ses excedents.

D´un coté, on décharge le processeur central et onsimplifie le code, d´un autre, on fait un rendu en 2 passes...Alors..a votre avis, on peut etre gagnant avec cette méthode ?

ps:Kelios, tu es sur la voie....

En faite tu veux faire une sorte d´octree. Il serait plus efficace de determiner les objets visibles par un petit algo executer par le CPU. Utiliser OpenGL pour ca... meme si tu desengages les lumieres, texture et autre tu y perdras surement en vitesse en faisant 2 passes.

J´y ai moi meme deja reflechi, et faire cette determination n´est pas tres difficile dans le principe.
Pour les grandes lignes :
http://www.gametutorials.com/Tutorials/OpenGL/Octree.htm

Pour le detail, une petite recherche sur google et c´est partit : )

Pour en revenir a ton dernier post arnaud81, tu parles de liberer le bus et la charge de la CG en envoyant moins d´objets...
Heuuuu, pourquoi ne charge tu pas une fois pour toutes tes objets en memoire de la carte ? En liste d´affichage par exemple.

I sea, I sea, comme la disait la Mer...

Au moment où je m´appretait à écrire ces lignes, je clique sur répondre, et hop, Kouic m´a devancé... [grrrrr]

Effectivement, ça fait plus penser à un octree qu´à autre chose.

Mais si je te suis Arnaud, ce rendu en 2 passes, ce n´est peut-être pas nécessairement mauvais, ça dépend des cas:
Si il y beaucoup de polys à culler, ça pourrait être intérressant.
Sinon, ça m´étonnerait que ça soit utile.

Exemple en chiffre de ce que je pense:
nombres fictifs[chiffres qui ne représentent qu´une unité de temps fictive que ça prendrait à renderer, juste là pour comparer]:
AVEC TA MÉTHODE:
1st Pass
Dessine cubes, imaginons, heu, disons 50.
2 Pass
Dessine polys, 5 par poly.

AVEC NORMAL
0.5 pour vérifier si à culler, 5 à renderer.

Vous voyez ce que j´en pense? Que ça ne doit être utile que dans une scène en high poly.
Je pense que le mieux reste encore de faire confiance à la carte graphique, et de lui laisser faire son boulot.

Désolé, c´est une bonne idée, mais je ne pense pas que l´on puisse s´en sortir bien avec ça...

À moins qu´il y ait bien sur une donnée imprévue qui surgisse dans le calcul, bien entendu =)

Kelios
---------

hs_dino, tu veux tester une collision avec une sphere ?

Déja, truc simple : si tu veux tester si un point A touche une sphere ( est dedans, dessus, ou dehors), tu consideres la distance au centre C :

pour avoir la distance, tu fais
distance(a,c) = sqrt((xa-xc)²+(ya-yc)²+(za-zc)²)
et tu teste si elle est inférieure au rayon ( =dans la sphere), ou supérieur ( = dehors)
une asuce déja pour optimer ça, ne considere par la rayon, mais le rayon au carré, comme ça tu n´as pas a calculer la racine carrée, et tu gagnes énormément.

Ensuite je ne vois pas bien ce que tu veux dire pas "sphere/triangle", tu veux dire une sphere faite de triangles ?
ou alors tester si un triangle dans l´espace coupe la sphere ?
--> tres chaud ça : car meme si les 3 points du triangles sont hors de la sphere, une partie peut etre dedans.

Pareil tu veux tester l´intersection d´un rayon avec un triangle ?
( auquel cas il te faut l´équation du plan formé par le triangle, et la résoudre : c´est un systeme, ou alors une matrice dont tu dois calculer le KER)
Ou alors par dichotomie : tu considere la normale du triangle et le point que tu veux tester sur ton rayon : si le produit scalaire de la normale par un vecteur ( un sommet quelconque -> le point testé) est <0, alors tu est derriere le triangle, sinon, tu es devant.

En général, les collisions dans l´espace ne se font pas directement sur les triangles, mais sur les boites englobantes des objets, a l´intérieur desquelles on peut considérer des sous boites englobantes.

et si on a 0.2 images par seconde on peu traverser un objet avec ta methode, a revoir.

Merci JeanYvesYves d´avoir répondu.

Bon déja, le test du point et de la sphere ne va pas m´aider puisqu´il faut tester un triangle et non pas un point.

Ensuite pour l´histoire du Sphere/Triangle, c´est pas si chaud que çà en fait. Je teste si la sphere est suffisament proche du plan du triangle et ensuite je teste si la projection du point du centre du cercle sur le plan du triangle est dans le triangle. ( Ouf! Faut prendre sa respiration).

Voici donc le code que j´ai conçu pour faire ce test. Il semble bien marcher, mais j´aimerais l´optimiser. Avis aux matheux!!!

bool IntersectTriangle( KVector& center, float radius, KVector& v0, KVector& v1, KVector& v2, KVector* pPoint )
{
KVector edge1 = v1 - v0;
KVector edge2 = v2 - v0;
KVector edge3 = v1 - v2;

KVector Normal = KVector::CrossProduct( edge1, edge2 ) ;
Normal.Normalize();
KPlane Plane( Normal, KVector::DotProduct( Normal, v0 ) ) ;

float fDist = ( KVector::DotProduct( Plane.m_Vector, center ) - Plane.m_Distance);

// La sphere est suffisament loin du plan, pas de collision
if( fDist > radius )
return false;

if( fDist < 0.0f )
return false;

// La sphere touche le plan
*pPoint = center + Normal * -fDist;

// Edge 1
KVector ve1 = KVector::CrossProduct( Normal, v1 - v0 ) ;
ve1.Normalize();
KPlane Plane1( ve1, KVector::DotProduct( ve1, v0 ) ) ;
float d1 = KVector::DotProduct( Plane1.m_Vector, *pPoint ) - Plane1.m_Distance;
if( d1 < 0.0f )
return false;

// Edge 2
KVector ve2 = KVector::CrossProduct( Normal, v0 - v2 ) ;
ve2.Normalize();
KPlane Plane2( ve2, KVector::DotProduct( ve2, v0 ) ) ;
float d2 = KVector::DotProduct( Plane2.m_Vector, *pPoint ) - Plane2.m_Distance;
if( d2 < 0.0f )
return false;

// Edge 3
KVector ve3 = KVector::CrossProduct( Normal, v2 - v1 ) ;
ve3.Normalize();
KPlane Plane3( ve3, KVector::DotProduct( ve3, v1 ) ) ;
float d3 = KVector::DotProduct( Plane3.m_Vector, *pPoint ) - Plane3.m_Distance;
if( d3 < 0.0f )
return false;

return true;