1. Traitements
1.1. Méthodes de subdivision
1.1.1. Problématique : comment augmenter le nombre de points de contrôle d'une surface paramétrique sans la modifier. Trouver la surface/courbe limite revient à affiner indéfiniment.
1.1.2. Définition
1.1.2.1. En entrée : Maillage + règles de subdivisions
1.1.2.2. En sortie : Maillage subdivisé
1.1.2.3. Utilisation d'un ensemble de règles de subdivisions (schéma) : associe à chaque cas possible une action
1.1.3. Vocabulaire
1.1.3.1. Sommet pair : sommet présent avant la subdivision
1.1.3.2. Sommet dual : sommet créé par la subdivision
1.1.3.3. Sommet régulier : sommet à valence idéale
1.1.3.4. Sommet extraordinaire : sommet dont la valence est différente de la valence idéale
1.1.3.5. Schéma d'approximation : La surface/courbe limite NE passe PAS par les points initiaux
1.1.3.6. Schéma d'interpolation : La surface/courbe limite passe par les points initiaux
1.1.3.7. Schéma primal : subdivision de faces
1.1.3.8. Schéma dual : subdivision de sommets
1.1.4. Méthodes sur maillages triangulaires
1.1.4.1. Loop
1.1.4.1.1. Schéma primal d'approximation
1.1.4.1.2. Description méthode
1.1.4.2. Butterfly
1.1.4.2.1. Schéma primal d'interpolation
1.1.5. Méthode sur maillages quadrangulaires
1.1.5.1. Catmull-Clark (C2)
1.1.5.2. Kobbelt (C1)
1.2. Partitionnement
1.2.1. Structures de subdivision (Spatiales) hiérarchiques
1.2.2. QuadTree / Octree
1.2.2.1. Parcours : O(log(n)) = parcours profondeur arbre, au lieu de O(n^3)
1.2.2.2. Applications
1.2.2.2.1. LOD : On se déplace à un certain niveau de l'arbre
1.2.2.2.2. Ray Tracing : On ne lance pas de rayon la ou il n'y a rien
1.2.2.3. On part du milieu de l'image, elle n'est pas forcément centrée
1.2.2.4. Subdivision de l'image en 4 quads / 8 cubes
1.2.2.5. On arête subdivision quand il n'y a plus rien à afficher
1.2.3. kD-Tree
1.2.3.1. Partitionnement par plans
1.2.3.2. Plans orthogonaux
1.2.3.3. On découpe données en deux parts égales à chaque itération
1.2.4. BSPtree
1.2.4.1. Binary split plans
1.2.4.2. Plans pas forcément orthogonaux
1.2.4.3. Wolf 3D, Doom ...
1.2.5. BVH
1.2.5.1. Bounding box (BB)
1.2.5.2. Oriented Bounding box (OBB) (Suivant les axes
1.2.5.3. Polyhèdres (PBB) (Convex hull, Enveloppe connexe)
1.3. Simplification de surfaces
1.3.1. Objectifs
1.3.1.1. Moins de polygones
1.3.1.2. Pas de rupture topologique
1.3.1.3. Représentation correcte de la surface
1.3.2. Caractéristiques
1.3.2.1. Efficacité : tps réel / précalculé, mémoire
1.3.2.2. Qualité : Préservation géométrie / topologie
1.3.3. Classification
1.3.3.1. Partitionnement
1.3.3.1.1. Algorithme général
1.3.3.1.2. OOCS (Out Of Core Simplification)
1.3.3.1.3. VSA (Variationnal Shape Approximation)
1.3.3.2. Décimation
1.3.3.2.1. Algorithme général
1.3.3.2.2. Progressive Meshes
1.3.3.2.3. Quadratic Error Function : permet de calculer une distance (un sommet important est un sommer proche) =1/n * sum(i : 0..n) {||pi - centreGravité||²}
1.3.4. Algorithme polygonal
1.3.4.1. Entrée : Maillage
1.3.4.2. Sortie : Maillage
1.3.4.3. QEF
1.3.5. Algorithme Nuage de point
1.3.5.1. Prendre un représentant des points pour chaque cellule spatiale (barycentre, ...)
1.3.5.2. Conserver uniquement le représentant
1.3.5.3. Très simple
1.3.5.4. Limité aux nuages de points (pas d'information topologique)
2. Représentations
2.1. Nuages de points
2.1.1. Maillage polygonal - faces - arêtes
2.1.2. Perte voisinage
2.1.3. Perte topologie
2.1.4. Obtention
2.1.4.1. Modeleur
2.1.4.2. Microscribe
2.1.4.3. Scanner
2.1.5. Représentation
2.1.5.1. Ensemble non ordonné de points représentés par leurs coordonnées
2.1.5.2. Plusieurs centaines de points possibles par pixels : on peut parfois les afficher directement
2.1.6. Vocabulaire
2.1.6.1. Print : Echantillon (Surfel : Surface element)
2.1.6.2. Nuage de points = nuage de surfels
2.1.6.3. 2,5 D
2.1.6.3.1. Acquisition en 2D
2.1.6.3.2. Information de profondeur
2.1.7. Echantillonnage d'un modèle
2.1.7.1. Entrée
2.1.7.1.1. Surface paramétrée (Nurbs)
2.1.7.2. Sortie
2.1.7.2.1. N.P.
2.1.7.2.2. Anisotropie
2.1.7.2.3. Courbure
2.1.7.2.4. Bruit
2.1.7.2.5. Matériaux
2.1.8. Visualisation
2.1.8.1. Splatting
2.1.8.2. Ray Tracing
2.1.8.3. Affichage direct (Si tres grand nombre de points)
2.2. Surfaces implicites
2.2.1. Représentation d'une partition de l'espace
2.2.2. Composition
2.2.2.1. Surfaces à squelette
2.2.2.1.1. Dilatation à partir de points
2.2.2.1.2. Blobs / Metaballs
2.2.2.2. Construct Solid Geometry (CSG)
2.2.2.2.1. Primitives (Cubes, Sphères ...)
2.2.2.2.2. Intersection,
2.2.2.2.3. Union
2.2.2.2.4. Différence
2.2.2.2.5. Soustraction
2.2.3. Visualisation
2.2.3.1. Ray Tracing
2.2.3.1.1. Le plus simple
2.2.3.1.2. Lent
2.2.3.2. Visualisation Temps réel
2.2.3.2.1. Extraction (Calcul) de points
2.2.3.2.2. Surface polygonale
2.2.3.2.3. Aucune idée type maillage
2.2.3.2.4. Aboutit à un échantillonnage non régulier de la surface
2.2.3.3. Marching cubes
2.2.3.3.1. Visu surfaces implicites
2.2.3.3.2. Visu voxels
2.2.3.3.3. Quadrillage + shéma pour tracer contours
2.2.3.3.4. Grosses différences / Objet réel
2.2.3.3.5. Parfois apparition de trous, Version corrigeant cela existe
2.2.4. Applications
2.2.4.1. CAO
2.2.4.2. Metaballs
2.2.4.3. Fluides
2.2.4.4. Formes molles (Muscles ...)
2.2.4.5. Réparation d'un maillage
2.2.5. Surfaces implicites variationnelles
2.2.5.1. Ajout bruit, modif etc ...
2.2.5.2. Ex: rides dans l'eau
2.3. Maillages polygonaux
2.3.1. Soupe de polygones
2.3.1.1. Simple
2.3.1.2. Directement affichable
2.3.1.3. Redondant : Bien pour parralélisme mais mauvais pour Déplacement point
2.3.1.4. Pas de surface lisse
2.3.2. Maillage indexé (VEF)
2.3.2.1. Sommets (V)
2.3.2.1.1. Position
2.3.2.1.2. Normale (Moyenne des normales aux faces)
2.3.2.1.3. Couleur, matériau
2.3.2.1.4. Paramètres (Simulation, RV)
2.3.2.2. Arrêtes (E)
2.3.2.2.1. Plis vifs (Gradients)
2.3.2.3. Faces (F)
2.3.2.3.1. Couleur, matériau
2.3.2.3.2. Normale : Produit vectoriel de 2 arretes de la face
2.3.2.4. Modèle de référence pour la plupart des modeleurs
2.3.2.5. Information géométrique (Points)
2.3.2.6. Information topologique (faces, arrêtes) : Info sur le voisinage
2.3.2.7. Implémentation efficace : Table de hachage (Pour visualisation)
2.3.3. Caractéristiques
2.3.3.1. Coordonnées paramétriques : Origine + unité
2.3.3.2. Propriétés topologiques
2.3.3.2.1. 2-Variété : Surface ou en chaque point, il existe un disque sur la surface (Pas de trou)
2.3.3.2.2. 3-Variété : Boule ou portion de boule
2.3.3.2.3. 2-Variété avec bord : Demi disque
2.3.3.2.4. Genre : Nombre de trous au sens d'Euler (Nombre de coupes que je peux faire sur un objet sans le déconnecter
2.3.3.3. Isotropie / Anisotropie
2.3.3.3.1. Homogène
2.3.3.3.2. Isotrope
2.3.3.3.3. Anisotrope
2.4. Surfaces paramétriques
2.4.1. Enjeux
2.4.1.1. Surface "Lisse" (continuité de la dérivée Ck)
2.4.1.2. Nécessité d'une représentation adaptée
2.4.1.3. Manipulation (Création / Modification) Intuitive
2.4.2. Spline : Objet mathématique définissant une variété (Plan que l'on déforme) != fermé . Notion a associer à la notion de point de contrôle
2.4.3. Courbes de Bézier (somme des polynômes de Bernstein)
2.4.4. Patch : Ensemble de courbes de bézier
2.4.5. Non-Uniform Rational Basis Splines (Nurbs)
2.4.5.1. Splines de Bézier Uniformes
2.4.5.2. Forces sur le réseau de points de contrôle (Ex : Gravité)