Loading
Notes d'étude
Study Reminders
Support
Text Version

Méthodes de représentation de l'espace

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Bonjour et bienvenue à la conférence numéro 9 dans le cours Computer Graphics. Nous discutons des étapes du pipeline graphique. Comme vous pouvez le rappeler, il y a 5 grandes étapes, la première étape est la représentation de l'objet, et nous discutons actuellement de la technique de représentation des objets.
Donc, ce sera le sujet de notre discussion aujourd'hui, les méthodes de partitionnement de l'espace.
Maintenant, quand on parle de partition de l'espace, de quoi on fait référence? Comme son nom l'indique, le partitionnement de l'espace fait référence à la représentation d'un objet en termes de l'espace 3D qu'il occupe. L'espace est défini par ses limites et nous représentons l'espace ou le volume qui est entouré par les limites plutôt que les limites, que nous avons vues lors des conférences précédentes.
Maintenant, il y a un concept important dans les techniques de partitionnement de l'espace, c'est ce qu'on appelle les voxels. Vous avez entendu parler de pixels, nous avons mentionné ce terme plus tôt. C'est la plus petite unité d'affichage. Et sur un écran d'affichage, on suppose qu'il y a une grille de pixels. De même, voxel est essentiellement la contrepartie 3D du concept de pixel. Voxel est la plus petite unité de représentation dans un espace 3D. Tout espace 3D peut être supposé avoir une grille de voxel.
Comme une grille de pixels, nous pouvons créer ou supposer qu'une grille de voxel existe pour représenter un espace 3D. Donc, la grille de pixels est pour l'espace 2D, la grille de voxel est pour l'espace 3D. Et voxel, comme peut-être évident, est la façon la plus simple de représenter des objets 3D.
Maintenant, quand on parle de voyxels, on fait essentiellement référence à des cubes ou des parallélépipèdes généralement de taille uniforme. Donc, essentiellement, une grille de cubes de taille uniforme ou des parallélépipeds qui sont notre grille de voxel. Désormais, dans chaque grille, chaque élément de voxel de la grille contient généralement diverses informations. Quelles sont ces informations? L'intensité dans cette région 3D particulière, la température de cette région et ainsi de suite. Et cette information aide en fait à décrire de manière unique la scène 3D. Ainsi, essentiellement les voxels ont des attributs qui sont des informations caractéristiques pour l'objet particulier sur la scène.
En utilisant les voxels, nous pouvons appliquer différentes techniques pour représenter des objets. L'une de ces techniques est la méthode Octree. Quelle est cette méthode? Comme son nom l'indique, c'est une sorte de représentation des arbres, maintenant essayons de comprendre ce qui est cet arbre. Donc, il se réfère essentiellement à une méthode pour créer une grille voxel, mais sous la forme d'un arbre.
Ainsi, dans cette méthode, l'entrée est une région 3D. Maintenant, nous divisons cet espace d'entrée en 8 sous-régions, puis chaque sous-région à son tour est à nouveau divisée en 8 sous-régions. Donc, il s'agit essentiellement d'une étape récursive et cette récursivité se poursuit jusqu'à ce que nous arri­sions à une taille uniforme prédéfinie des sous-régions. Maintenant, cette taille peut être définie par l'utilisateur, par exemple, un cube d'unité. Donc, quand on voit que notre division mène à des régions de taille de cube d'unité, alors on s'arrête là, un exemple est montré dans cette figure de droite.
Donc, c'est notre première région 3D. Maintenant, comme vous pouvez le voir, nous avons créé 8 sous-régions d'ici, c'est 1, 2, 3, 4, 5, 6, 7 et 8, puis chacune de ces sous-régions est encore divisée en 8 sous-régions comme ici que vous pouvez voir dans cette division, encore une fois il ya 8 sous-régions 1, 2, 3, 4, 5, 6, 7, 8. De même, ici aussi, nous avons divisé et toutes les autres sous-régions aussi nous pouvons diviser.
Maintenant, quel est le résultat de cette récursivité? Il crée un arbre. Donc, nous avons un noeud racine. Pour chaque noeud racine, nous avons créé 8 noeuds enfants d'ici. Pour chaque noeud enfant, nous créons à nouveau 8 noeuds enfant et ce processus se poursuit. Donc, essentiellement ça mène à un arbre. Comme chaque noeud a 8 enfants, nous l'appelons octree et les noeuds terminaux de cet arbre représentent l'espace 3D. Ainsi, tous les noeuds intermédiaires sont des représentations intermédiaires, ils ne représentent pas l'objet final, au niveau de la feuille, l'objet final est représenté. N'oubliez pas ici que, avec l'espace, les attributs ou les informations caractéristiques sont également stockés au niveau du noeud terminal.
Donc, pour représenter différents objets, nous pouvons associer des propriétés uniques à ces noeuds terminaux ou voxels, les propriétés telles que la couleur, la densité, la température et ainsi de suite, c'est l'idée de base. Donc, on nous donne de l'espace 3D, l'espace que nous avons divisé en 8 régions et nous continuons cette division, chaque sous-région est divisée en 8 sous-régions et ainsi de suite. Nous continuons cette division de manière récursive jusqu'à atteindre le niveau de voxel ou les cubes de taille uniforme. Et ce processus crée un arbre ; chaque noeud de cet arbre a 8 enfants, donc l'arbre est appelé octree.
Le niveau de feuille contient les voxels sont la représentation de l'objet 3D et les informations caractéristiques telles que la couleur, la densité, la température et ainsi de suite sont associées à chaque voxel dans cette arborescence pour identifier de manière unique les objets. Octree est l'une des diverses méthodes où l'espace est utilisé pour représenter les objets. Une autre méthode populaire est appelée BSP ou la méthode BSP.
Maintenant, BSP signifie partitionnement d'espace binaire et la méthode est une méthode de partitionnement d'espace binaire. Alors, qu'est-ce que c'est? Dans l'octree, nous avons fait un certain partitionnement récursif de l'espace. Dans l'arbre BSP, nous suivons une récursivité similaire, c'est-à-dire qu'on nous donne un espace, on le divise en sous-espace, puis on divise le sous-espace et on continue jusqu'à ce que certaines conditions soient remplies.
Cependant, au lieu de diviser un espace en 8 sous-espaces comme nous l'avons fait dans le cas d'octree, ici ce que nous faisons nous le divisons en 2 espaces ou sous-espaces à chaque étape récursive. Ainsi, en cas d'octree nous divisons la région en 8 sous-régions, dans le cas de l'arbre BSP, nous divisons la région en 2 sous-régions, c'est pourquoi il s'appelle le partitionnement de l'espace binaire. Maintenant, comment nous divisons? Nous utilisons des avions. Nous avons donc une région où nous supposons que des avions sont disponibles pour diviser la région en sous-régions. Mais ces avions ne doivent pas être parallèles aux plans formés par les axes XY, YZ ou ZX. Il peut s'agir d'avions de n'importe quelle orientation. Bien sûr, si nous avons parallèle aux plans formés par l'axe principal, alors il est plus facile à mettre en œuvre, sinon nous devons faire des calculs supplémentaires.
Voyons un exemple. Supposons qu'on nous donne cette région 3D et que nous allons le représenter sous la forme d'un arbre BSP. Donc, notre noeud racine est l'objet entier, puis nous avons utilisé un plan celui-ci pour le diviser en deux régions, la région de gauche D et la région droite C. La gauche par rapport au plan et à droite par rapport à l'avion, la sous-région de gauche et la sous-région de droite. Ensuite, nous avons utilisé un autre avion pour diviser le B en deux sous-régions D et E. Donc, finalement, ce que nous avons obtenu? L'objet est représenté en trois sous-régions D, E et C.
Ces trois éléments au niveau de la feuille représentent donc l'objet. Et comme dans le cas d'octree, nous pouvons associer des propriétés uniques à chacune de ces sous-régions pour identifier de manière unique l'objet. Maintenant, nous avons utilisé deux avions qui sont orthogonaux entre eux, ce sont des avions orthogonaux, mais c'est, comme nous l'avons déjà vu précédemment, ce n'est pas une exigence stricte. Les plans d'orientation peuvent être utilisés pour diviser les régions en deux sous-régions.
Donc, ici au lieu de ces plans orthogonaux, nous aurions pu utiliser n'importe quel plan de n'importe quelle orientation pour le diviser en deux régions, deux sous-régions qui sont la formulation la plus générale pour la création de l'arbre BSP. Mais, comme je l'ai dit, si nous utilisons des avions qui ne sont pas parallèles aux plans formés par l'axe principal, des calculs supplémentaires peuvent être nécessaires pour traiter la représentation. Voyons un autre exemple pour la création d'arbres BSP, comment nous pouvons créer, comment nous pouvons écrire un algorithme pour la création d'une représentation.
Considérez cette figure, ici nous voulons représenter ce cercle, c'est bien sûr une figure à deux dimensions, ce n'est pas un objet 3D, mais cet objet 2D que nous voulons représenter ce cercle qui a le centre à Pm et le rayon r. Donc, nous voulons le représenter à l'aide de l'arbre BSP.
Comment pouvons-nous faire? Ainsi, il prend comme entrée la région environnante R qui est le carré représenté par les quatre sommets ou les points d'angle P 1, P 2, P 3 et P 4 et le cercle se trouve dans cette région. Ainsi, lorsque nous représentons le cercle, nous représentons essentiellement cette région avec certaines régions qui font partie du cercle ayant des caractéristiques uniques du cercle. Comment pouvons-nous faire?
Nous allons donc diviser la région en quatre sous-régions. Donc, d'abord nous divisons en deux sous-régions, puis chacune de ces 2 sous-régions nous divisons en deux sous-régions et ainsi de suite. Par souci de simplicité, nous combinons ici ces étapes et nous les divisons en quatre sous-régions. Et nous utilisons ici des lignes parallèles aux axes.
À l'aide de cette idée, que pouvons-nous faire? Nous pouvons écrire un algorithme pour une fonction créée à BSP où R est la région d'entrée. Maintenant, nous allons utiliser R pour créer un nœud, puis de R va créer 4 régions en rejoignant les points milieu des côtés de la place, ceci est la même que l'application des techniques de partitionnement binaire espacées en plusieurs étapes. Comme dans ce cas, nous avons d'abord créé 2, puis pour chacun de ces deux en créer deux, et nous combinons ces étapes ici dans cette ligne.
Maintenant, pour chacune de ces sous-régions ici à ce nœud de la feuille de cette figure, si la taille de cette sous-région, supposons que cette région soit divisée en 4 sous-régions, donc nous y réfléchissons. Maintenant, si la taille de la sous-région est une place d'unité, où nous supposons qu'un pixel est représenté comme un carré d'unité. Ensuite, nous allons à l'étape suivante qui est si la distance entre les centres de la région d'origine R et la sous-région que nous étudions actuellement est inférieure ou égale au rayon du cercle, puis cette sous-région fait partie du cercle.
Donc, nous l'ajoutons comme un noeud de feuille à l'arbre BSP et le marquer comme "intérieur". Sinon, nous la marquons comme "à l'extérieur", bien que l'ajouter comme partie de l'arbre BSP. Maintenant, si la taille n'est pas une place d'unité, c'est-à-dire que nous n'avons pas atteint la condition de fin de récursivité. Donc, pour chaque noeud, nous réalisons à nouveau la fonction, c'est-à-dire que nous appelons la fonction de nouveau de manière récursive mentionnée dans ces 2 étapes. Donc, à la fin, nous obtenons un arbre, où les noeuds foliaires représentent la région d'origine, la région d'origine divisée en sous-régions.
Maintenant, certaines de ces sous-régions sont marquées comme à l'intérieur de cet objet particulier, à l'intérieur de la place. Alors que d'autres sont marqués comme extérieurs. Donc, de cet arbre, on obtient une représentation de la place. Jusqu'ici, si bien. Maintenant, quel est le problème? Y a-t-il un problème avec cette approche de partitionnement de l'espace?
Un problème peut être très évident pour vous maintenant, c'est-à-dire que nous avons besoin d'une grande mémoire pour stocker ces informations de grille de voxel. Donc, nous créons des arbres où les noeuds terminaux représentent la grille et si nous partitionnons uniformément, alors il y aura un grand nombre de voxels et nous avons besoin d'espace mémoire important pour stocker les informations voxel. Le problème vient du fait que nous divisons l'espace en voxels de taille uniforme, quelles que soient les propriétés de l'espace.
Comme nous l'avons vu dans l'exemple précédent, la région R est une grande région, à l'intérieur de ce cercle, occupe une petite zone, mais nous divisons la région en sous-régions de taille uniforme et de nombreuses sous-régions peuvent être en dehors du cercle. Donc, si vous voulez représenter le cercle, il n'est pas nécessaire de représenter les régions qui se trouvent à l'extérieur du cercle qui gaspprésentent en fait un espace de mémoire. Donc, si nous avons une méthode pour éviter ces gaspillages, alors bien sûr cela serait utile.
Alors, qu'est-ce que nous voulons? Si une certaine région de l'espace a les mêmes propriétés partout, idéalement, nous ne devrions pas la diviser davantage. Parce que même si nous divisons ce que nous obtenons, nous aurons la même propriété. Au lieu de cela, ce que nous faisons, nous la divisons toujours en voxels, bien que chaque voxel contienne les mêmes attributs, parce que la région plus large ou la région plus large dans l'espace a la même propriété partout.
Donc, on peut vraiment économiser, c'est qu'il y a une typo ici, c'est sûr, on peut économiser de la mémoire en utilisant cette idée de partitionnement non uniforme. Donc, nous parlons plus tôt de diviser une région en voxels de taille uniforme. Nous parlons maintenant de cloisonnement de l'espace non uniforme. Qu'est-ce que c'est? C'est-à-dire, au lieu d'utiliser beaucoup de voxels pour représenter une région homogène qui est une région où la propriété est la même partout où nous utilisons une seule unité. Ainsi, nous ne divisons pas davantage cette région, mais l'ensemble de la région est représentée comme une seule unité.
Comment pouvons-nous faire? Une façon est de modifier la méthode de l'octree. Maintenant, plus tôt, nous avons fixé 8 enfants pour chaque noeud parce que nous divisons la région en 8 sous-régions, quelle que soit la propriété de la région. Maintenant, que pouvons-nous faire? Soit nous divisons, soit nous ne divisons pas. Donc, si une sous-région a la même propriété partout, alors nous ne le divisons pas. Ainsi, ce noeud n'aura pas d'enfants ou 0 enfants. Mais si ce n'est pas le cas, nous le divisons en 8 sous-régions ou 8 enfants.
Donc maintenant, dans la méthode de l'octree révisé, ce que nous aurons soit 0 ou 8 enfants pour chaque noeud, ce qui n'était pas le cas plus tôt. Donc, plus tôt nous avons eu 8 enfants pour chaque noeud, noeud intermédiaire, maintenant nous aurons 0 ou 8 enfants pour chaque noeud intermédiaire en fonction de la propriété de cet espace représenté par le nœud.
La procédure de récursivité, bien sûr, restera, la procédure de récursivité restera la même. Mais à chaque étape de la récursivité, nous allons vérifier si les attributs d'un espace sont identiques partout. Si tel est le cas, nous ne le divisons pas davantage. Donc, on ne va pas à nouveau pour une division récursive pour cette région particulière.
La représentation du BSP souffre également du même problème si nous allons pour un partitionnement uniforme.
Et pour éviter cela, nous pouvons aller pour une méthode révisée ou une méthode affinée où nous pouvons soit diviser la région en 2 sous-régions si les sous-régions ont des propriétés différentes à différents endroits ou nous ne divisons pas. Ainsi, les noeuds intermédiaires auront 0 ou 2 enfants semblables à la méthode de l'octree révisée. Donc, ce que nous avons appris, c'est que l'unité de base de la représentation sera voxel. Maintenant, en utilisant voxel nous pouvons diviser un espace 3D donné pour représenter l'objet contenu dans cet espace de deux façons, l'une est une division uniforme.
Maintenant, quand nous allons pour une division uniforme, nous aurons un type particulier d'arbre si nous suivons la méthode octree ou un type particulier d'arbre si nous suivons la méthode BSP. Dans la méthode de l'octree, si nous allons pour une division uniforme, nous aurons 8 enfants pour chaque noeud. Dans la méthode BSP, nous aurons deux enfants pour chaque noeud. Maintenant, si la région que nous divisons a le même attribut ou les mêmes propriétés partout, ce sera le gaspillage de mémoire pour diviser cette région en sous-régions et stocker l'information.
Au lieu de cela, nous ne devons pas la diviser davantage. Ainsi, dans le cas de la méthode octree, nous la modifions pour un partitionnement non uniforme en imposant le fait qu'un nœud peut avoir 0 ou 8 enfants. De même, dans une méthode BSP révisée, nous pouvons modifier en imposant le fait que chaque noeud intermédiaire peut avoir 0 ou 2 enfants.
Il existe une autre méthode de partitionnement de l'espace appelée CSG. Qu'est-ce que cela signifie?
Il s'agit de Constructive Solid Geometry. Il s'agit donc d'une autre méthode pour la représentation spatiale des objets. Maintenant, en cas d'octree ou de BSP, ce que nous avons vu? Nous avons vu que ces représentations sont basées sur la division de l'espace. On nous donne un espace et on le divise en sous-espaces. Par rapport à cela, en cas de CSG ce que nous avons? Il est en fait basé sur l'assemblage des espaces, juste le contraire de ce que nous faisons dans les méthodes BSP ou octree. Ainsi, dans le cas de CSG, nous comptons sur l'assemblage d'espaces pour représenter des objets. Essayons de le comprendre par rapport à un exemple.
Considérez cet objet, cela semble assez complexe. Cependant, lorsque nous utilisons la méthode CSG ou une méthode de géométrie solide constructive, nous pouvons la représenter comme une union de certaines autres formes. Donc, on commence ici à ce niveau, ici on a cette forme, cette forme, cette forme et cette forme, donc 4 formes sont là. Maintenant, nous combinons ces 2 formes pour obtenir une forme et nous combinons ces 2 formes ici pour obtenir cette forme. Maintenant, ces 2 formes sont ensuite combinées pour obtenir cette forme globale.
Donc, ici nous commençons avec un ensemble de formes primitives ou de formes de base, puis nous appliquons un ensemble d'opérateurs booléens, à savoir l'union, l'intersection, la différence, etc. qui sont définis sur cet ensemble de formes primitives pour obtenir des formes plus récentes. Comme ici sur ces 2 formes, nous avons appliqué un opérateur booléen pour obtenir une nouvelle forme et ce processus se poursuit jusqu'à obtenir la forme désirée ici. Ainsi, les opérateurs peuvent être appliqués de manière hiérarchique. Donc, de ce niveau, nous atteindrons ce niveau, de ce niveau que nous atteindrons à ce niveau, à chaque niveau, nous appliquons les opérateurs booléens.
Il s'agit donc d'une application hiérarchique des opérateurs. Donc, en d'autres termes, nous avons un ensemble de formes primitives définies et un ensemble d'opérateurs booléens sur ces formes aussi définies. Maintenant, nous appliquons ces opérateurs sur les formes pour obtenir de nouvelles formes et nous appliquons ces opérateurs hiérarchiquement jusqu'à ce que nous obtiens la forme voulue, jusqu'à ce que nous puissions représenter la forme désirée. Alors, quelle est la représentation? La représentation est essentiellement les formes primitives et les opérateurs booléens appliqués de manière hiérarchique, donc c'est la représentation.
Donc, c'est en résumé, ce que cette géométrie solide constructive est à propos. Maintenant, résumons ce que nous avons appris jusqu'à présent.
Aujourd'hui et lors de quelques conférences précédentes, nous avons appris diverses techniques de représentation, qui constituent la première étape du pipeline. Présentation de la frontière, y compris les splines, la représentation de l'espace et aussi une vue d'ensemble des autres représentations. Maintenant, il y a beaucoup de techniques que nous avons vues jusqu'à présent. Une question est la technique à utiliser et quand? C'est une question qui confronte toujours un développeur de système graphique. Quelle technique doit être utilisée et dans quelle situation? Qu'est-ce qui guide le processus décisionnel?
Maintenant, nous souhaiterions peut-être avoir une représentation la plus réaliste. Il est clair que des techniques de pointe seraient utiles, mais des techniques de pointe comme les systèmes de particules peuvent ne pas toujours être possibles parce qu'elles nécessitent beaucoup de ressources informatiques qui ne sont pas disponibles dans tous les systèmes graphiques. Donc, chaque technique vient avec un coût et il y a un compromis, la technique à utiliser dans laquelle la situation.
Maintenant, ce coût peut être une exigence de calcul ou de stockage ou les deux, et selon la ressource disponible, nous devons prendre la décision. Si nous avons moins de ressources, alors nous ne pouvons pas penser à des techniques de modélisation avancées, alors nous pourrions avoir à perdre un peu de réalisme et à s'installer pour des scènes ou des images moins réalistes.
Par exemple, supposons que nous voulons représenter les côtes dans une scène. Alors, qu'est-ce qui est souhaitable? Les côtes sont généralement des structures auto-répétées et la représentation fractale est très bonne pour de telles formes. Nous devrions donc idéalement utiliser la représentation fractale pour avoir un littoral réaliste. Mais il se peut que cela ne soit pas possible si nous envisageons une plate-forme mobile avec un processeur de stockage et une batterie limités car la représentation fractale a un coût de calcul supplémentaire qui peut ne pas être supporté dans les appareils mobiles bas de gamme.
Donc, dans ce cas, il se peut que nous ayons à utiliser une méthode plus simple. Donc, nous perdons ici quelque chose, l'effet réaliste, mais nous gagnons quelque chose qui est une approximation de travail. Donc, de tels compromis font partie intégrante du processus de prise de décision, en équilibrtant ces compromis.
Une autre considération peut être la manipulation. Donc, lorsque nous créons l'animation, cette considération est utile et elle devient importante. Maintenant, comme nous l'avons dit, chaque représentation a ses propres méthodes, ses propres algorithmes, son propre processus. Les étapes subséquentes du pipeline doivent traiter ces représentations pour effectuer les opérations qui font partie des étapes subséquentes. Il faut donc manipuler les représentations.
Maintenant, si cela nécessite beaucoup de temps pour manipuler, par exemple, faire pivoter un objet, déplacer 10 objets horizontalement ou verticalement, monter ou descendre un objet ou un clip, projeter ou faire mieux dans l'enlèvement de la surface, etc., ces objets font partie des autres étapes du pipeline. Nous discuterons plus tard des étapes dans les détails. Maintenant, si beaucoup de temps est nécessaire pour effectuer ces opérations, pour les objets qui sont représentés d'une façon particulière, la qualité de l'animation peut être réduite. Donc, dans de tels cas, nous devrions rechercher des types plus simples.
Donc, c'est une autre considération qu'il faut garder à l'esprit tout en choisissant un modèle particulier de représentation qui est facile à manipuler. Donc, si nous avons des dispositifs bas de gamme, des systèmes graphiques bas de gamme, alors il n'est pas conseillé d'aller pour des techniques de représentation avancées qui nécessitent beaucoup de manipulations plus tard, en particulier dans le contexte de l'animation.
La troisième considération est la facilité d'acquisition de données. Par exemple, la représentation de la liste de sommet d'une surface incurvée à l'aide d'un maillage nécessite un grand nombre de sommets à spécifier. Maintenant, nous considérons la représentation de la spline. Dans ce cas, nous avons besoin de moins de points de contrôle pour représenter la même courbe. Donc, clairement ici, représenter une courbe à l'aide d'un maillage implique davantage d'efforts pour l'acquisition de données, alors que la représentation de la même courbe avec une spline implique moins d'effort pour acquérir des données. Par conséquent, cette facilité d'acquisition de données peut parfois être un facteur décisif. Selon le concepteur du système graphique, une méthode particulière peut être de choisir l'endroit où les données peuvent être acquises facilement.
Donc, il y a plusieurs compromis que nous devons équilibrer et nous devons décider quels sont les compromis disponibles, la nature des interactions, les ressources en termes de plate-forme informatique, la nature de l'interaction en termes de notre niveau de confort avec la fourniture d'une grande quantité de données et aussi d'effet, que nous voulions un effet très réaliste ou que nous cherchions une approximation en considérant le manque de ressources.
Donc, en fonction de ces 3 considérations générales, nous devons choisir une technique de modélisation particulière. Donc, avec ça, nous sommes arrivés à la fin de notre discussion sur la première étape du pipeline graphique qui est la représentation des objets.