Pixels et objets - Page 1

Comment font des logiciels tel qu'AutoCAD, Cabri-Géomètre et autres pour savoir à quel(s) objet(s) appartient un pixel sur l'écran?

Il peut y avoir plusieurs techniques envisageables, ça dépend comment tu stockes tes objets...
Si tes objets sont contenus dans une liste, en vrac, sans partitionnement ni autre critère permettant de simplifier la recherche, alors tu devras parcourir bêtement tes objets pour tester s'il y en a un qui est positionné là où l'utilisateur aura cliqué...

Sachant que tu peux avoir la position 3D du point cliqué (genre, sous OpenGL, glunproject)
Bien entendu, combiner cela avec une partition (octree etc.) permettra d'accélérer considérablement ta recherche de l'objet (si tu as bcp d'objets à l'écran)

Sasume :
Il peut y avoir plusieurs techniques envisageables, ça dépend comment tu stockes tes objets...
Si tes objets sont contenus dans une liste, en vrac, sans partitionnement ni autre critère permettant de simplifier la recherche, alors tu devras parcourir bêtement tes objets pour tester s'il y en a un qui est positionné là où l'utilisateur aura cliqué...

Rien n'est fait pour le moment.
Si je comprends bien il faut d'abord organiser correctement les objets ; mais quels sont les méthodes pour les organiser au mieux sachent que le but principal est d'obtenir tous les objets se trouvant sur un pixel donné.
Ensuite faire une recherche objet par objet. Ca ne devrait pas poser de problèmes puisque qu'il s'agit d'objets simples comme des lignes, cercles, ... ou des objets composés eux aussi d'objets simples (rectangles, triangles, ou les blocs comme sous AutoCAD).

nEUrOO :
Sachant que tu peux avoir la position 3D du point cliqué (genre, sous OpenGL, glunproject)
Bien entendu, combiner cela avec une partition (octree etc.) permettra d'accélérer considérablement ta recherche de l'objet (si tu as bcp d'objets à l'écran)

Je ne travaille qu'en 2D pour le moment.
J'ai fait une recherche sur octree mais je n'ai pas bien compris sont utilité vis à vis de mon problème?

le principe du quadtree (octree en 2d) c'est d'éviter d'avoir à tester tous les objets.
au début tu as 4 cellules (subdivisions du quadtree) et tu peux facilement savoir dans laquelle tu as cliqué. donc tu n'as pas besoin de tester les objets qui sont des les 3 autres cellules ainsi que dans leurs sous-cellules. (puisque toutes les sous cellules sont inclues dans les cellules parent)

donc tu teste les objet qui sont la cellule ou tu as cliqué, puis tu recommences la même chose avec les 4 sous-cellules de celle que tu viens de tester récursivement...

et ce qu'il faut bien comprendre c'est que quand un objet est dans une cellule, on ne considère pas qu'il est dans ses sous-cellules
donc quand tu parcours ton quadtree tu n'as que très peu de test d'intersections (entre le point ou tu as cliqué et les objets) à faire

Bien sur il faut que tu ais placé tous tes objets dans l'arbre avant de lancer la recherche

Qu'est-ce que tu veux faire comme programme ?
Quels sont les objets que tu manipules ?

Tiens en passant, quelqu'un sait s'il y a un impact en terme de performances (temps et mémoire) à utiliser un octree plutôt qu'une séparation binaire et inversement ?
Instinctivement, le comportement asymptotique devrait être le même, mais on a rarement une inifnité d'objets dans un monde.

Sasume :
Qu'est-ce que tu veux faire comme programme ?
Quels sont les objets que tu manipules ?

Les objets utilisés sont des objets simples (points, lignes, cercles, ...) ou des objets composés d'objets simples (triangles, rectangles, ...).
Le programme est un peu compliqué, c'est pour gérer/déplacer/modifier des éléments dans des zones de confinement à partir de plans de locaux (c'est pour ma boite).

Nue :
et ce qu'il faut bien comprendre c'est que quand un objet est dans une cellule, on ne considère pas qu'il est dans ses sous-cellules
donc quand tu parcours ton quadtree tu n'as que très peu de test d'intersections (entre le point ou tu as cliqué et les objets) à faire

J'ai fait un peu le tour du web au sujet de octree et quadtree. Je ai compris le principe mais je ne vois pas où se situe les objets dedans?
Un objet peu être contenu dans plusieurs sous-cellules en même temps. Comment faire dans ce cas précis?

un octree est une facon de partitionner un espace (c'est simplement ca)
tu as une scene avec des objets et tout ton espace est partitionné (suivant un octree)

Un objet peu être contenu dans plusieurs sous-cellules en même temps. Comment faire dans ce cas précis?

1) c'est un objet statique => alors il ne peut pas être dans plusieurs cellules en même temps (tu le découpes à l'initialisation)
2) c'est un objet mobile => tu considères qu'il est des deux côtés (tu le prends en compte dès lors qu'il a au moins un morceau qui dépasse quoi)

Ce sont des objets statiques.
Finalement j'ai opté pour le plus simple, je n'ai pas énormément d'objets et la recherche est plutôt rapide.
J'ai créé une structure contenant un pointeur vers une fonction qui retourne vrai ou faux si le point choisit appartient à l'objet.
Cette fonction fait une simple résolution d'équation (y=ax+b pour les lignes, (x − a)² + (y − b)² = r² pour un cercle, ...).