Surface de lotissement

Dans le domaine de l'infographie 3D , une surface de subdivision (généralement abrégée en surface SubD ou Subsurf ) est une surface courbe représentée par la spécification d'un maillage polygonal plus grossier et produite par une méthode algorithmique récursive . La surface courbe, le maillage interne sous-jacent , peut être calculée à partir du maillage grossier, connu sous le nom de cage de contrôle ou maillage externe , comme limite fonctionnelle d'un processus itératif de subdivision de chaque face polygonale en faces plus petites qui se rapprochent mieux de la surface courbe sous-jacente finale. Moins fréquemment, un algorithme simple est utilisé pour ajouter de la géométrie à un maillage en subdivisant les faces en faces plus petites sans modifier la forme ou le volume global.

Le contraire est la réduction des polygones ou leur dés-subdivision.

Un algorithme de subdivision de surface est de nature récursive . Le processus commence par un maillage polygonal de niveau de base. Un schéma de raffinement est ensuite appliqué à ce maillage. Ce processus prend ce maillage et le subdivise, créant de nouveaux sommets et de nouvelles faces. Les positions des nouveaux sommets dans le maillage sont calculées en fonction des positions des anciens sommets, arêtes et/ou faces proches. Dans de nombreux schémas de raffinement, les positions des anciens sommets sont également modifiées (éventuellement en fonction des positions des nouveaux sommets).

Ce processus produit un maillage plus dense que l'original, contenant plus de faces polygonales (souvent d'un facteur 4). Ce maillage résultant peut être soumis au même schéma de raffinement encore et encore pour produire des maillages de plus en plus raffinés. Chaque itération est souvent appelée un niveau de subdivision , commençant à zéro (avant tout raffinement).

La surface de subdivision limite est la surface produite par ce processus appliqué de manière itérative un nombre infini de fois. Cependant, dans la pratique, cet algorithme n'est appliqué qu'un nombre limité et relativement faible ( ) de fois.

Mathématiquement, le voisinage d'un sommet extraordinaire (nœud non 4- valent pour les maillages raffinés quadruples) d'une surface de subdivision est une spline avec un point paramétriquement singulier .

Les schémas de raffinement de surface de subdivision peuvent être largement classés en deux catégories : interpolation et approximation .

• Des schémas d'interpolation sont nécessaires pour correspondre à la position d'origine des sommets dans le maillage d'origine.
• Les schémas approximatifs ne le sont pas ; ils peuvent et vont ajuster ces positions selon les besoins.

En général, les schémas d'approximation ont une meilleure régularité, mais l'utilisateur a moins de contrôle global sur le résultat. Cela est analogue aux surfaces et courbes splines , où les courbes de Bézier sont nécessaires pour interpoler certains points de contrôle, alors que les B-Splines ne le sont pas (et sont plus approximatives).

Les schémas de surface de subdivision peuvent également être classés par type de polygone sur lequel ils fonctionnent : certains fonctionnent mieux pour les quadrilatères (quads), tandis que d'autres fonctionnent principalement sur les triangles (tris).

L'approximation signifie que les surfaces limites se rapprochent des maillages initiaux et qu'après la subdivision, les points de contrôle nouvellement générés ne se trouvent pas dans les surfaces limites. Il existe cinq schémas de subdivision approximatifs :

• Catmull et Clark (1978), Quads – généralise l'insertion de nœuds B-splines uniformes bicubiques . Pour des maillages initiaux arbitraires, ce schéma génère des surfaces limites qui sont C ² continues partout sauf aux sommets extraordinaires où elles sont C ¹ continues (Peters et Reif 1998).
• Doo-Sabin (1978), Quads – Le deuxième schéma de subdivision a été développé par Doo et Sabin, qui ont étendu avec succès la méthode de découpage des coins de Chaikin (George Chaikin, 1974 ) pour les courbes aux surfaces. Ils ont utilisé l'expression analytique de la surface B-spline uniforme biquadratique pour générer leur procédure de subdivision afin de produire des surfaces limites C ¹ avec une topologie arbitraire pour des maillages initiaux arbitraires. Un point auxiliaire peut améliorer la forme de la subdivision Doo-Sabin. Après une subdivision, tous les sommets ont une valence 4.
• Loop (1987), Triangles – Loop a proposé son schéma de subdivision basé sur une boîte-spline quartique de six vecteurs de direction pour fournir une règle permettant de générer des surfaces limites continues C ² partout sauf aux sommets extraordinaires où elles sont continues C ¹ (Zorin 1997).
• Schéma de subdivision des bords intermédiaires (1997-1999) – Le schéma de subdivision des bords intermédiaires a été proposé indépendamment par Peters-Reif (1997) et Habib-Warren (1999). Le premier a utilisé le point médian de chaque bord pour construire le nouveau maillage. Le second a utilisé une spline à quatre directions pour construire le schéma. Ce schéma génère des surfaces limites continues C ¹ sur des maillages initiaux avec une topologie arbitraire. (La subdivision des bords intermédiaires, qui pourrait être appelée « subdivision √2 » puisque deux étapes divisent par deux les distances, pourrait être considérée comme la plus lente.)
• Schéma de subdivision √3 (2000), Triangles – Ce schéma a été développé par Kobbelt et offre plusieurs fonctionnalités intéressantes : il gère des maillages triangulaires arbitraires, il est C ² continu partout sauf aux sommets extraordinaires où il est C ¹ continu et il offre un raffinement adaptatif naturel lorsque cela est nécessaire. Il présente au moins deux spécificités : il s'agit d'un schéma Dual pour les maillages triangulaires et il a un taux de raffinement plus lent que les maillages primaires.

Après la subdivision, les points de contrôle du maillage d'origine et les points de contrôle nouvellement générés sont interpolés sur la surface limite. Le premier travail fut le soi-disant « schéma papillon » de Dyn, Levin et Gregory (1990), qui ont étendu le schéma de subdivision interpolatoire à quatre points pour les courbes à un schéma de subdivision pour les surfaces. Zorin, Schröder et Sweldens (1996) ont remarqué que le schéma papillon ne peut pas générer de surfaces lisses pour les maillages triangulaires irréguliers et ont donc modifié ce schéma. Kobbelt (1996) a généralisé le schéma de subdivision interpolatoire à quatre points pour les courbes au schéma de subdivision du produit tensoriel pour les surfaces. En 1991, Nasri a proposé un schéma d'interpolation de Doo-Sabin ; tandis qu'en 1993 Halstead, Kass et DeRose en ont proposé un pour Catmull-Clark.

• Papillon (1990), Triangles – nommé d'après la forme du schéma
• Papillon modifié (1996), Quads – conçu pour surmonter les artefacts générés par une topologie irrégulière
• Kobbelt (1996), Quads – une méthode de subdivision variationnelle qui tente de surmonter les inconvénients de la subdivision uniforme

• 1978 : Les surfaces de subdivision ont été décrites par Edwin Catmull et Jim Clark (voir Surface de subdivision Catmull-Clark ) et par Daniel Doo et Malcom Sabin (voir Surfaces de subdivision Doo-Sabin ).
• 1995 : Ulrich Reif a résolu le comportement des surfaces de subdivision à proximité de sommets extraordinaires.
• 1998 : Jos Stam a contribué à une méthode d'évaluation exacte pour les surfaces de subdivision Catmull-Clark sous des valeurs de paramètres arbitraires.