Modélisation solide

  • Published on
    07-Jan-2016

  • View
    14

  • Download
    0

Embed Size (px)

DESCRIPTION

Modlisation solide. Tir de Olivier Drion, Amapi 7 Ateliers graphiques. Eyrolles, 2003, p. 141. Reprsentation et construction dobjets. OBJECTIFS. numrer les principaux modes de reprsentation dobjets gomtriques. - PowerPoint PPT Presentation

Transcript

<ul><li><p>Modlisation solideTir de Olivier Drion, Amapi 7 Ateliers graphiques. Eyrolles, 2003, p. 141.</p></li><li><p>Reprsentation et construction dobjetsOBJECTIFSnumrer les principaux modes de reprsentation dobjets gomtriques.Montrer leur potentiel de modlisation.PLAN DU CHAPITREIntroductionFamilles dobjets paramtrissModles de dcompositionModles de compositionDescription de lenveloppe de lobjetDcrire les principales proprits de ces modes de reprsentation dobjetsModle en fil de ferReprsentation partir de surfacesfrontiresModles bass sur la notion de demi-espacesModles C.S.G.numration spatialeQUADTREE, OCTREE</p></li><li><p>INTRODUCTIONUn modle dun objet est une reprsentation idalise ou simplifie dun objetpermettant de lobserver plus facilement.La construction dun modle pour reprsenter la structure gomtrique dun objetest intressante plusieurs points de vue:certaines caractristiques du modle peuvent tre tudies plus facilement quecelles de lobjet lui-mme;lobjet peut ne pas exister;lobjet ne peut tre observ directement;lobjet ne peut tre observ sans engendrer des cots draisonnables ou sanscontrle de lexprience.</p></li><li><p>PROBLMES RENCONTRS DANS LE PROCESSUS DE MODLISATIONBesoin dun modle complet :un modle qui offre une description complte de la gomtrie dun objet,permettant de rpondre aux diffrentes questions gomtriques pertinentes.</p><p>Construction dun modle correct :nous devons tre capable de dtecter et de corriger des anomalies lors de laconstruction du modle dun objet.</p><p>Ex. :Un modle dobjet bas sur des facettes polygonales convexes.</p><p>Nous devons nous assurer que cette restriction est toujourssatisfaite aprs une opration quelconque.</p><p>Complexit de lobjet modliser :La reprsentation sous forme polydrique dune main est trs difficile.</p><p>Laugmentation du potentiel de modlisation afin de reprsenter des formesdavantage complexes entrane des problmes lors des calculs gomtriques.</p></li><li><p>Objectifs atteindre pour reprsenter un objetprcision de limage;possibilit de visualiser, danalyser ou de manipuler lobjet selon nimporte quelledirection dobservation;capacit de recueillir toutes les informations pertinentes dcrivant lobjet ncessaires chaque application;reprsentation non ambigu de lobjet;rduction du nombre de paramtres dcrivant lobjet;simplification de calcul de certaines mesures;approche systmatique de construction dobjets partir de formes connues.Les objectifs prcdents ne sont pas tous atteints travers les modlesque nous verrons; des choix doivent tre faits.</p></li><li><p>Modles frontires(connus aussi sous le nom de b-reps)Il sagit dun mode de reprsentation indirect dun solide en dcrivantlenveloppe du solide laide de ses frontires : sommets, artes etfacettes.Modles simplifis : les modles en fil de ferLes objets sont reprsents partirdun ensemble de segments de droiterelis ventuellement par leursextrmits.Ils permettent de reprsenteruniquement le contour des objets.Les extrmits des segments de droiteet les liens existant entre eux sontstocks.</p></li><li><p>Modles en fil de fer+Ce modle est simple : facilite les transformations de base et devisualisation.Permet peu de frais davoir une reprsentation gomtriqueglobale de lobjet.Capacit de modlisation trs limite : faible degr de ralisme.-Le calcul de certaines mesures de lobjet peut tre difficile ouimpossible par manque dinformations sur lobjet. La quantit imposante de donnes ncessaires pour dcrirelobjet. </p></li><li><p>Modles en fil de fer-Il peut y avoir ambigut</p><p>- dans linterprtation de la reprsentation ou- donner lieu un modle impossible.Ces ambiguts dans linterprtationde la reprsentation rendent difficiles larsolution du problme dliminationdes lignes caches.</p><p>Ces </p><p>Modle impossible</p><p>Plusieurs interprtations dun mme objet.</p></li><li><p>Les modles dfinis partir de surfaces frontiresModles frontiresIl sagit de dcrire lenveloppe de lobjet partir de la description deses surfaces frontires : surfaces courbes, frontires planes,polygonales, polygonales convexes, triangulaires.La plupart du temps, chaque surface frontire courbe est divise enfacettesEx. : des facettes polygonaleset chaque facette est reprsente par lensemble des artes et dessommets qui la dlimitent.Tir de O. Drion, Amapi 7 Ateliers graphiques. Eyrolles, 2003, p. 80.</p></li><li><p>Modles dfinis partir de surfaces frontires-+ Le modle ne fournit pas dinformation quant lintrieur de lobjet. Lvaluation dune mesure de lobjet peut tre difficile faire. Le modle permet de rsoudre le problme dlimination des parties caches. Il permet dappliquer un modle dillumination et/ou de gnration de texture.Conditions respecter : Lensemble des facettes forme une figure ferme. Les facettes ne sinterceptent pas sauf des artes ou sommets communs. Les surfaces frontires ne sinterceptent pas elles-mmes. Ils ne sont pas ambigs comme cela pouvait tre le cas prcdemment. Les conditions prcdentes sont difficiles vrifier. Le nombre de facettes peut tre lev (approximation polygonale).</p></li><li><p>Famille dobjets paramtrissIl sagit de dcrire la famille laquelle cet objet appartient et de dfinirles paramtres permettant didentifier de faon unique un objet de cettefamille.Ex. :Pour gnrer une ellipse, il suffit de fixer les valeurs desparamtres dcrivant la classe des coniques.Les paramtres dun objet sont en gnral des caractristiques gom-triques : le volume, laire, laxe principal, la hauteur, la largeur, etc.Un objet paramtris peut tre aussi bien une forme connue (cube,sphre, etc.) quune forme spcialise selon le besoin de lapplication.Forme paramtrise par l, h, r et m</p></li><li><p>Famille dobjets paramtrissPices mcaniquesM. E. Mortenson, Geometric Modeling.Wiley, 1997, p. 262.</p></li><li><p>Cest un modle spcialis facilitant la description de pices souventutilises mais trop limit cause de la faible flexibilit des objetsparamtriss.Lapparition dun nouvel objet ncessite la gnration dune nouvelleclasse, ce qui peut savrer difficile, voire impossible raliser.Dfinir des paramtres simples en nombre limit pour caractriser unobjet complexe nest pas une mince tche.Famille dobjets paramtriss2 alternatives :restreindre notre potentiel de modlisationouaugmenter substantiellement le nombre de formes paramtrises.Exemple :Modlisation dun visage humain.Donne lieu des algorithmes efficaces en synthse dimages.Il sagit dun mode de reprsentation secondaire dans les modeleurslesquels sappuient sur dautres reprsentations.</p></li><li><p>Modles de compositionConsidrent les solides comme des ensembles de points 3D.Dbutent avec des ensembles simples qui peuvent tre reprsentsdirectement laide de primitives (quadriques, polydres, etc.).Des objets plus complexes sont obtenus en combinant des ensemblessimples entre eux laide doprations ensemblistes.1er cas : Modles bass sur la notion de demi-espacesNous pouvons dfinir une fonction caractristique dun ensemble A depoints 3D:gA(x, y, z): (x, y, z) {0, 1}qui nous indique si un point (x, y, z) appartient ou non A.</p><p>Si gA(X) = 1, alors (x, y, z) A; si gA(X) = 0 alors (x, y, z) A.</p></li><li><p>Modles bass sur la notion de demi-espacesPour des ensembles de points 3D, la reprsentation de gA est aussidifficile que celle de A.Par contre, il existe des classes dobjets qui peuvent tre reprsentes partir dun ensemble de points 3D dcrit par une fonction f(x, y, z)(demi-espace).Lobjet est dcrit comme tant lensemble des points (x, y, z) tels quef(x, y, z) 0,le complment de cet objet comme tant les points (x, y, z) tels quef(x, y, z) &lt; 0.Un solide est reprsent partir dune expression ensembliste dedemi-espaces:Objet = i j Dijo Dij = un demi-espace.Toutes les surfaces dintrt ne sont pas des demi-espaces:surfaces bicubiques.</p></li><li><p>Modles bass sur la notion de demi-espacesExempleC = D1 D2 D3oD1 x2 + y2 r2 0D2 z 0D3 z h 0.Trs souvent, on opte pour des demi-espaces linaires :a x + b y + c z + d 0ou quadratiques (demi-espaces sphriques, cylindriques, ).La capacit de modlisation dpend des familles de demi-espaces dis-ponibles et des techniques nous permettant de les combiner ensemble.Les demi-espaces sont rarement des ensembles finis. Ainsi, uneexpression ensembliste de demi-espaces nest pas ncessairement unereprsentation valide de solide.Aucune dfinition ambigu :chaque combinaison valide de solides donne un solide mais sareprsentation nest pas ncessairement unique.</p></li><li><p>Modles bass sur la notion de demi-espacesComment valuer les expressions ensemblistes de demi-espaces ?Il sagit dadapter lalgorithme de tracs de rayons (ray tracing) ensynthse dimages.Pour gnrer une image, dfinissons pour chaque pixel de lcran unedemi-droite issue de lobservateur et passant par ce pixel.Le calcul principal consiste valuer lintersection dune demi-droiteavec chaque solide de la scne, puis, retenir le point le plus prs delobservateur.Lintersection dune demi-droite avec un solide de la scne se ramne valuer larbre binaire reprsentant lexpression ensembliste dedemi-espaces.Contrainte :Lintersection dune demi-droite avec un demi-espacedoit tre relativement simple.Problme unidimensionnel</p></li><li><p>Modles de composition2ime cas : Modles CSG (constructive solid geometry)Contrairement aux modles avec demi-espaces, il sagit de manipulerdes objets lmentaires borns : polydre, cylindre, sphre, etc. := | | ::= union | intersection | diffrence ::= translation | rotation | changement dchelle.On met la disposition de lusager un nombre fini de primitives simplesdont la grandeur, la forme, la position et lorientation sont dfinies parlusager.Pour ce qui est des primitives non lmentaires, lusager doit spcifieruniquement le systme de rfrence de lobjet.</p></li><li><p>Modles CSGTir de Martti Mntyl, An Introduction to Solid Modeling. Computer Science Press, 1988, p. 82.Approche base sur lusage de blocs de construction</p></li><li><p>Modles CSG-Ce modle est incomplet car il ncessite des algorithmes pour valuerlarbre de construction.Lorsque larbre CSG est mal balanc, les algorithmes proposs sontinefficaces.Il est difficile de construire un modle CSG pour dcrire des objetscomplexes nintgrant aucune proprit gomtrique.Ex. : la reprsentation dun visage humain.+Lopration de modlisation est simplifie; lanimateur doit spcifierseulement larbre de construction.Lvaluation de larbre de construction peut exiger des temps decalculs importants.Aucune ambigut dans le modle; cela donne lieu des objets valides.</p></li><li><p>valuation des arbres de constructiondes modles CSGLalgorithme de tracs de rayons sapplique aussi aux modles CSG enautant que le calcul dintersection entre un rayon et chaque primitivedu modle soit relativement simple.Au lieu dopter pour une approche approximative lors de lvaluationde larbre de construction, on peut valuer de manire exacte chaquecomposante de larbre de construction.Exemple : Chaque feuille de larbre est un polydre convexe.Chaque sommet intermdiaire de larbre est un ensemble depolydres convexes disjoints.Pour valuer chaque sommet intermdiaire de larbre, on peutadapter un algorithme de dcoupage 3D.Ex. de primitives : polydres, formes implicites : f(x, y, z)= 0, ...</p></li><li><p>Modle de dcompositionLes objets sont reprsents comme un ensemble dobjets ou celluleslmentaires.Un mode de reprsentation de solides par partitionnement spatial ochaque solide est dcompos en un ensemble de solides adjacents, sansintersection, qui sont plus primitifs que le solide original, bien quencessairement du mme type.1er cas : numration exhaustive des cellules lmentairesConsidrer lensemble infini de tous les points faisant partie dunsolide.numration impossibleLespace est dcompos en cellules identiques, souvent appeles voxels,arranges en une grille fixe et rgulire faisant partie ou non du solide.Subdivision rgulire de lespace.</p></li><li><p>numration spatialeCes cubes ne se recouvrent pas; ils ont mme dimension et mmeorientation.Le type de cellule le plus courant est le cube.Chaque cube peut tre dfini uniquement partir dun de ses sommets.En associant chaque objet une rgion rgulire dont lobjet fait partie,lobjet est reprsent partir dun tableau binaire 3D.un lment du tableau 1 le cube associ reprsente une sous-rgion du solide 0 le cube ne fait pas partie du solide.</p></li><li><p>numration spatiale+Permet de construire facilement et efficacement de nouveaux objets laide doprations ensemblistes en se basant sur ces tableaux binaires.Permet dvaluer efficacement diffrentes mesures de lobjet.Ce modle est une reprsentation approximative de lobjet moins quecelui-ci ne concide exactement avec la grille ce qui est rarement le cas.-On peut rduire la taille des voxels afin daugmenter la prcision de lareprsentation du solide.Cela exige une quantit despace mmoire imposante.Cette approche ne peut tre exploite directement : pour construire unobjet, on ne peut exiger lnumration de lensemble de ces cellules.</p></li><li><p>numration spatiale-Une faon plus pratique de procder consiste passer dune autrereprsentation celle par numration des cellules lmentaires.Modle frontire, modle de composition, modle de familles paramtrises, etc.A)Il faut dabord dfinir une rgion (paralllpipde) renfermant lesobjets de la scne.B)Il faut ensuite construire la grille binaire qui correspond chaqueobjet de la scne du modle frontire ou de familles paramtrises.C)Dans le cas dun modle de composition, il faut appliquer ltapeB) avec les feuilles de larbre, puis, valuer larbre de construction laide des grilles binaires de ces feuilles.</p></li><li><p>numration spatiale2 ime cas : subdivision irrgulire dune rgion dont lobjet modliser fait partiePour remdier cet inconvnient, nous nous basons sur le principe suivant:Les techniques dnumration spatiale sont simples, gnrales etpermettent de dvelopper une grande varit dalgorithmes. Mais elles exigent une grande quantit despaces mmoires et unereprsentation trs approximative des solides. Les cubes lmentaires voisins dun cube faisant partie de lobjetont de bonnes chances den faire partie aussi.Le # de cubes ncessaires pour reprsenter un objet devraitdpendre de la surface de lobjet et non du volume de lobjet.Il existe plusieurs mthodes bases sur ce principe:notamment les OCTREE et les QUADTREE.</p></li><li><p>Reprsentation QUADTREE en 2D</p><p>1</p><p>2</p><p>3</p><p>4</p><p>(a)</p><p>(b)</p><p>= Noeud plein</p><p>= Noeud vide</p><p>= Noeud avec descendants</p></li><li><p>Reprsentation QUADTREERacine :lespace initial englobant lobjet (un carr renfermantles objets de la scne).Feuilles :des blocs (carrs) qui sont- compltement remplis (faisant partie de lobjet) ou- compltement vides (ne faisant pas partie de lobjet).Subdivision rcursive de lespace contenant lobjet 2D en 4 rgionscarres, chaque carr en 4 rgions carres, etc.Le processus prend fin dans lun des 3 cas suivants:Nous aboutissons une cellule vide ne contenant aucunepartie de lobjet.Nous aboutissons une cellule entirement remplie.Le niveau de rsolution est atteint.La structure de donnes correspondante ce modle est un arbre o lessommets ont 0 ou 4 descendants (QUADTREE).</p></li><li><p>Reprsentation QUADTREEconst niveau_maximum_de_recursivite = 10; enum etat { homogene, heterogene };struct Information_QUADTREE{enum etat Statut;union{int Couleur;// sommet homognestruct Information_QUADTREE * Quatre_Enfants;// sommet htrogne};};struct objet{float vx; float vy; float longueur;// dfinition dun carr renfermant lobjet. struct Information_QUADTREE * racine;};</p></li><li><p>Reprsentation QUADTREENote :Dans chaque sommet du QUAD...</p></li></ul>