Share
Coupure est le processus permettant de déterminer quelle région de l’espace se trouve dans une autre région de l’espace. Ceci est particulièrement important dans des domaines d'étude tels que l'infographie et la simulation physique. Par exemple, lors du rendu d'un monde à l'écran, il est préférable de savoir ce qu'il y aura à l'écran avant de traiter des données. Cela permet d'ignorer de nombreuses données superflues, tout en traitant et en présentant ce que l'utilisateur verra..
Dans la simulation physique, on découvre souvent des corps rigides s'interpénétrant - c'est-à-dire que deux objets distincts se chevauchent. C'est mauvais. L'interpénétration est quelque chose qui ne se produit jamais dans le monde réel, mais c'est un problème qui doit être traité lors de la détection de collision. Souvent, une forme est coupée contre une autre afin de déterminer les caractéristiques qui se touchent. De là, une réponse de collision peut être initiée.
Les fonctionnalités avancées des moteurs de jeu peuvent être implémentées avec une forme de coupure; simulation de flottabilité, plans de vue de la caméra; rupture fragile, génération de contacts avec le test d'axe de séparation; toutes ces choses (et bien plus encore) peuvent être réalisées avec des algorithmes de découpage. En fait, une telle coupure était nécessaire dans mon précédent tutoriel sur la construction d'un moteur physique pour corps rigide.
Cet article nécessite que vous ayez une compréhension décente de:
Les domaines d'étude ci-dessus peuvent être appris d'une grande variété de ressources sur Internet (telles que le guide de Wolfire sur l'algèbre linéaire ou la Khan Academy - et elles ne sont pas trop difficiles à apprendre).!
De nombreuses routines de découpage complexes impliquent l'utilisation d'un seul type d'opération: diviser une forme avec un seul plan. Fractionner une forme par un plan implique de prendre une forme et de la couper en deux à travers un plan solide.
Il est important de réaliser que scinder une forme avec un plan est un outil fondamental dans cette routine de découpage..
Voir les excellentes animations de Davide Cervone pour une démonstration claire de ceci:
Sutherland Hodgman Clipping est ma routine de découpage préférée, car elle fonctionne pour couper les boucles de ligne contre des avions. Avec cet algorithme, à partir d’une liste de sommets d’entrée et d’une liste de plans, une sortie de nouveaux sommets existant uniquement dans l’ensemble des plans peut être calculée..
Le terme plan peut être utilisé pour désigner à la fois un plan en 3D et en 2D. Un plan 2D peut aussi être appelé un ligne.Nous pouvons imaginer la liste des sommets comme un seul polygone. Nous pouvons imaginer (pour l'instant) la liste des avions comme une seule ligne. Visualiser ceci en deux dimensions pourrait ressembler à l'image suivante:
Avec l'écrêtage de Sutherland Hodgman, le polygone à droite correspond à la forme souhaitée, tandis que le polygone rouge à gauche correspond à la forme en entrée et n'a pas encore été découpé. La ligne bleue représente un plan de division en deux dimensions. Vous pouvez utiliser n'importe quel nombre de plans de fractionnement. dans l'exemple ci-dessus, un seul plan de fractionnement est utilisé. Si de nombreux plans de scission sont utilisés, le découpage se produirait alors, plan par plan, supprimant de plus en plus une forme originale pour en produire un nouveau:
Pour plus de simplicité, travaillons dans deux dimensions strictes. Lorsque vous divisez un polygone contre un plan, il est important de savoir de quel côté se trouve un point donné..
Ci-dessus, le moyen le plus utilisé pour trouver la distance entre un point et un plan. Notez que le symbole de point dans l’équation ci-dessus représente le produit scalaire..
La distance n'a pas besoin d'être calculée explicitement; le vecteur normal n n’a pas besoin d’être normalisé (c’est-à-dire qu’il n’a pas besoin d’avoir une longueur de exactement une unité). Tout ce qui doit être vérifié est le signe du résultat de la distance ré. Si n n'est pas normalisé alors ré sera en unités de la longueur de n. Si n est normalisé, alors ré seront en unités équivalentes aux unités spatiales mondiales. Ceci est important à réaliser car cela permet de faire le calcul afin de voir si ré est positif ou négatif. Positif ré dénote que le point p est à l'avant de l'avion. Négatif signifie que c'est à l'arrière.
Maintenant, qu'entendons-nous exactement par les côtés "avant" et "arrière" d'un avion? Cela dépend vraiment de ce que vous définissez comme avant et arrière. Habituellement, "avant" signifie que c'est du même côté de l'avion que la normale.
Permet de plonger directement dans l'algorithme. Effectuez un balayage rapide du pseudocode:
Polygon SutherlandHodgman (const Polygon startPolygon, Plane [] clippingPlanes) Sortie polygone = départPolygone pour chaque plan clippingPlane dans clippingPlanes face de clippingPlane out.push (endPoint) else si startingPoint devant et finPoint derrière clippingPlane out.push (Intersection (clippingPlane, startingPoint, endPoint)) sinon si startedPoint et endPoint derrière clippingPlane out.push (Intersection (clippingPlane, départPoint, extrémité)) ) out.push (endPoint) endPoint = point de retour de la sortie
L'algorithme prend un polygone d'entrée et certains plans de découpage, puis génère un nouveau polygone. L'idée est de couper chaque segment du polygone en entrée avec un plan de découpe à la fois. Cette image de Wikimedia Commons le montre bien:
Chaque opération de découpage n'a que quelques cas différents dans lesquels des sommets en sortie, et peut être décrite comme suit:
// InFront = plane.Distance (point)> 0.0f // Behind = plane.Distance (point) < 0.0f Vec2 p1, p2; ClipPlane plane; case p1 InFront and p2 InFront push p2 case p1 InFront and p2 Behind push intersection case p1 Behind and p2 InFront push intersection push p2
La meilleure façon de comprendre cet algorithme consiste à dessiner une forme 2D sur un morceau de papier et à tracer une ligne droite à travers la forme. Parcourez ensuite les sommets du polygone et appliquez l’algorithme de Sutherland-Hodgman et dessinez les résultats. Cela construira une intuition sur la façon dont l’algorithme fonctionne en séquence sur chaque ligne, en veillant à conserver tous les sommets derrière le plan..
Après votre propre travail sur papier et crayon, essayez cette superbe page Web. Il y a quelques visuels impressionnants et une applet Java (en haut de la page) qui permet à l'utilisateur de voir des parties de l'algorithme en cours d'exécution!
Calculer l'intersection d'un plan à deux points est très simple. L'idée est d'utiliser le calcul de distance pour trouver la distance de chaque point à un avion. Étant donné ces distances, une intersection peut ensuite être calculée en utilisant une interpolation linéaire..
Pointe: L'interpolation linéaire est un concept extrêmement utile à comprendre, ayant une application prolifique dans tous les logiciels graphiques et dans les logiciels de simulation physique. L’interpolation linéaire peut être appelée familièrement lerp. Tout peut être interpolé linéairement d’une position de départ à la position de fin, tant que le équation du mouvement est linéaire.En général, la formule pour interpoler linéairement à partir de début à fin avec intersection alpha est:
Lerp (début, fin, alpha) retourne début * (1 - alpha) + fin * alphaPointe: Dans l'exemple ci-dessus,
Accentsconagua
alpha est ce qu'on appelle un interpolant. Les interpolants sont utilisés dans les calculs d'interpolation linéaire pour calculer les positions entre les points de départ et d'arrivée. Sachant cela, les distances entre le plan et chaque point peuvent être utilisées comme valeurs permettant de calculer un alpha interpolant. Les variables t1 et t2 peut représenter les distances au plan de p1 et p2 respectivement.
À cet égard, le point d'intersection est simplement un Lerp du point de départ au point final, en fonction du temps d'intersection.
Cet algorithme peut facilement être étendu dans un espace tridimensionnel et y être exécuté. (Cet algorithme peut être exécuté dans n’importe quelle dimension supérieure, quoi que cela signifie.) Toutefois, dans les applications pratiques, cet algorithme n’est généralement jamais utilisé. réellement réalisée en 3D. En utilisant des transformations inverses intelligentes, le problème de découpage d'un polyèdre 3D contre un plan peut (dans certains scénarios) être simplifié en une routine de découpage de polygone 2D en découpage de polygone. Cela permet une optimisation informatique significative.
De même, si l'on étudie le code source de Bullet Physics, on s'aperçoit que l'écrêtage est en réalité effectué dans un espace à une dimension, même si l'écrêtage 3D complet est en cours. Cela est dû à la possibilité de calculer un interpolant valide à partir d’une seule dimension de l’espace du problème..
Par exemple, si l’on connait le temps d’intersection de la X valeurs d'un problème simple, ce temps d'intersection peut être utilisé comme interpolant pour effectuer une Lerp sur un point en trois dimensions.
Examinons cela plus en détail. Regardez le schéma suivant:
Supposons que la ligne jaune représente le sol à une position y de 0. Supposons maintenant que la position y de départ est à dix, et la position y finale est à -1. Calculons une position d'interpolation et d'intersection valide le long de la coordonnée y:
// alpha = 0.9 / 10.0f float alpha = 0.9f // finalY = 0.0f float finalY = Lerp (y1, y2, alpha);
Ce qui précède peut être lu comme "90% du chemin de 10 à -1", ce qui serait zéro. Cet interpolant peut être appliqué à des types de données arbitraires, y compris un vecteur à deux dimensions:
// alpha = 9.0f / 10.0f float alpha = 0.9f Vec2 finalPosition = Lerp (p1, p2, alpha);
Le code ci-dessus calculerait réellement la coordonnée x correcte pour le moment de l'impact, sans même effectuer d'opérations avec la coordonnée x afin de déterminer l'interpolant. Cette idée de calculer les interpolants et de les appliquer à des dimensions supérieures à celles à partir desquelles ils ont été calculés est un excellent moyen d'optimiser le code..
Certains problèmes peuvent persister lors de l'exécution d'une implémentation naïve de cette routine de découpage. Lors du calcul du point d'intersection, une erreur numérique s'introduit dans le calcul. Cela pose un problème majeur lors de la scission d’un polygone avec un plan tout en générant une sortie sur des deux côtés de l'avion. Afin de générer une sortie pour les deux côtés d'un plan de division, l'algorithme de Sutherland-Hodgman d'origine doit être légèrement modifié, et c'est là que des problèmes se poseront..
Chaque fois qu'un point d'intersection est calculé, une erreur numérique s'introduit. C'est un problème car le point d'intersection est calculé à partir du point UNE pointer B sera légèrement différent du calcul du point B pointer UNE. Afin d'éviter de tels problèmes, l'intersection doit être calculée de manière cohérente. Cela évite une terrible Jonction en T problème. C'est bien s'il y a une erreur numérique tant que l'erreur est cohérente.
T-Junction issue: Un espace entre deux mailles qui permet à la pixellisation des triangles de laisser un espace visible entre trois triangles. Généralement causé par une mauvaise manipulation de la machine epsilon lors du calcul en virgule flottante. Solutions possibles: transformations de sommet cohérentes; soudage post-traitement post-traitement.
Un autre problème est de déterminer si un point est situé d'un côté ou de l'autre d'un avion. Pour toute une série de raisons, des vérifications sur des avions épais doivent être effectuées. L'idée est de traiter un avion comme un avion épais, plutôt que comme un avion d'une largeur infiniment petite. Cela permet de créer un cas supplémentaire dans la routine de Sutherland-Hodgman: la dans l'avion Cas.
float D = plane.Distance (point); // EPSILON est un nombre numériquement significatif et visuellement insignifiant. Peut-être 0.00001f. bool OnPlane (float D) retour D> -EPSILON et D < EPSILON;
Si un point quelconque se trouve sur le plan de coupe, appuyez simplement sur le point final. Cela portera le nombre de cas 3 à 4 au total. Pour plus d'informations sur EPSILON, vois ici.
La meilleure référence pour cet algorithme de découpage réside dans le livre de détection de collision en temps réel de Christer Ericson (alias le livre orange). Vous pouvez trouver ce livre dans presque tous les studios de jeu existants.
En plus de dépenser beaucoup d'argent pour un livre, il existe quelques ressources gratuites:
Le découpage Sutherland-Hodgman est un excellent moyen de réaliser un découpage dans les espaces 2D et 3D. Ce type de routine peut être utilisé pour résoudre de nombreux problèmes, dont certains s’appliquent dans des domaines d’étude assez avancés. Comme toujours, n'hésitez pas à poser des questions dans la section commentaires ci-dessous!
