Share
La possibilité de diviser de manière dynamique une forme convexe en deux formes distinctes est une compétence ou un outil très précieux à avoir dans votre arsenal de jeu. Cette division permet des types de simulation avancés, tels que des partitions d'espace binaire pour les graphiques ou la physique, des environnements destructifs de manière dynamique (rupture fragile!), La simulation d'océan ou d'eau, la résolution de collision pour les moteurs physiques, le partitionnement spatial binaire, etc. Un bon exemple est le jeu Fruit Ninja for Kinect.
Qu'est-ce que cela signifie exactement de scinder une forme convexe? En deux dimensions, nous nous référons à une forme en tant que polygone; en trois dimensions, nous nous référons à une forme en tant que polyèdre. (Polyèdres est le mot utilisé pour désigner plus d’un polyèdre.)
Pointe: En général, les polygones et les polyèdres convexes simplifient de nombreux aspects de la manipulation et de la gestion des volumes ou des maillages. En raison de cette simplification, l'article entier suppose des polygones convexes et des polyèdres convexes. Les formes concaves ne sont pas en dehors de toute discussion ici. En général, les formes concaves complexes sont simulées comme une collection de formes convexes jointes.
Afin de donner un sens aux idées présentées dans cet article, vous devez avoir une connaissance pratique de certains langages de programmation et une compréhension simple du produit scalaire..
Un excellent moyen de diviser des formes en deux et trois dimensions consiste à utiliser la routine de découpage de Sutherland-Hodgman. Cette routine est assez simple et très efficace, et peut également être légèrement étendue pour tenir compte de la robustesse numérique. Si vous ne connaissez pas l'algorithme, consultez mon article précédent sur le sujet..
Une compréhension des plans en deux ou trois dimensions est également indispensable. Il convient de noter qu’un plan bidimensionnel pourrait être considéré comme une projection d’un plan tridimensionnel en deux dimensions - ou, en d’autres termes, une ligne.
S'il vous plaît, comprenez qu'un avion peut aussi être considéré comme un demi-espace. Le calcul de la distance ou de l'intersection de points en demi-espaces est une condition préalable requise: reportez-vous à la dernière section de Création d'un moteur de physique 2D personnalisé: Le moteur principal pour plus d'informations à ce sujet..
Veuillez vous reporter à la source de démonstration (également sur Bitbucket) que j'ai créée lors de la lecture de ce didacticiel. J'ai utilisé cette démo pour créer toutes les images GIF de l'article. Le code source est en C ++ (et devrait être compatible avec toutes les plates-formes), mais il est écrit de manière à pouvoir être facilement porté dans n’importe quel langage de programmation..
Avant d'aborder le problème de la division d'un polygone entier, examinons le problème de la division d'un triangle par un plan de coupe. Cela constituera la base de la compréhension pour passer à une solution robuste et généralisée.
La bonne chose à propos du fractionnement de forme est que, souvent, les algorithmes en 2D peuvent être étendus sans trop de problèmes directement en 3D. Ici, je vais présenter un algorithme très simple de fractionnement de triangle pour les deux et trois dimensions.
Lorsqu'un triangle intersecte avec un plan de division, trois nouveaux triangles doivent être générés. Voici une image montrant un triangle avant et après le fractionnement suivant un plan:
Dans un plan de division, trois nouveaux triangles sont générés lors de l'opération de découpage. Jetons du code à l'air libre, en supposant que les trois sommets d'un triangle soient a, b, c dans le sens anti-horaire (CCW), et que nous savons que le bord un B (bord des sommets a à b) ont croisé le plan de division:
// Coupez un triangle contre un plan en sachant que // a à b croise le plan de coupe // Référence: Bouyancy exacte pour Polyhedra par // Erin Catto dans Game Programming Gems 6 void SliceTriangle // Premier point du triangle, ordre CCW const Vec2 & b, // Deuxième point du triangle, CCW ordre const. Vec2 & c, // Troisième point du triangle, ordre CCW f32 d1, // Distance du point a au plan de division f32 d2. , // Distance du point b au plan de division f32 d3 // Distance du point c au plan de division) // Calculez le point d'intersection de a à b Vec2 ab = a + (d1 / (d1 - d2)) * (b - a); Triangle Tri; si (d1 < 0.0f) // b to c crosses the clipping plane if(d3 < 0.0f) // Calculate intersection point from b to c Vec2 bc = b + (d2 / (d2 - d3)) * (c - b); tri.Set( b, bc, ab ); out.push_back( tri ); tri.Set( bc, c, a ); out.push_back( tri ); tri.Set( ab, bc, a ); out.push_back( tri ); // c to a crosses the clipping plane else // Calculate intersection point from a to c Vec2 ac = a + (d1 / (d1 - d3)) * (c - a); tri.Set( a, ab, ac ); out.push_back( tri ); tri.Set( ab, b, c ); out.push_back( tri ); tri.Set( ac, ab, c ); out.push_back( tri ); else // c to a crosses the clipping plane if(d3 < 0.0f) // Calculate intersection point from a to c Vec2 ac = a + (d1 / (d1 - d3)) * (c - a); tri.Set( a, ab, ac ); out.push_back( tri ); tri.Set( ac, ab, b ); out.push_back( tri ); tri.Set( b, c, ac ); out.push_back( tri ); // b to c crosses the clipping plane else // Calculate intersection point from b to c Vec2 bc = b + (d2 / (d2 - d3)) * (c - b); tri.Set( b, bc, ab ); out.push_back( tri ); tri.Set( a, ab, bc ); out.push_back( tri ); tri.Set( c, a, bc ); out.push_back( tri );
Espérons que le code ci-dessus vous effraie un peu. Mais n'ayez crainte. Tout ce que nous faisons ici consiste à calculer des points d'intersection afin de savoir comment générer trois nouveaux triangles. Si l’on avait examiné l’image précédente avec soin, les emplacements des points d’intersection pourraient être évidents: c’est là où la ligne pointillée rencontre le plan de séparation et où le bord un B coupe le plan de division. Voici un schéma pour plus de commodité:
À partir de ce diagramme, il est facile de voir que les triangles de sortie doivent contenir les sommets a, ac, ab, ac, c, b, et ab, ac, b. (Mais pas nécessairement dans ce format exact; par exemple, a, b, c serait le même triangle que c, b, a parce que les sommets étaient simplement décalés vers la droite.)
Afin de déterminer quels sommets contribuent à lequel des trois nouveaux triangles, nous devons déterminer si le sommet une et sommet c reposer au-dessus ou au-dessous de l'avion. Puisque nous supposons que le bord un B est connu pour se croiser, on peut déduire implicitement que b est du côté opposé du plan de coupe de une.
Si la convention d'une distance négative par rapport à un plan de division signifie pénétrant Dans le plan, nous pouvons formuler un prédicat pour déterminer si un point intersecte un demi-espace: #define HitHalfspace (distance) ((distance) < 0.0f). Ce prédicat est utilisé dans chaque si déclaration pour vérifier et voir si un point est dans le demi-espace du plan de découpage.
Il existe quatre cas de combinaisons de une et b frapper le demi-espace de l'avion de découpage:
a | T T F F ----------- b | T F T F
Puisque notre fonction exige que les deux une et b être sur les côtés opposés de l'avion, deux de ces cas sont abandonnés. Il ne reste plus qu'à voir de quel côté c pose. A partir de là, l'orientation des trois sommets est connue; les points d'intersection et les sommets de sortie peuvent être calculés directement.
Pour utiliser le SliceTriangle () fonction, nous devons trouver un bord intersectant d’un triangle. L'implémentation ci-dessous est efficace et peut être utilisée sur tous les triangles de la simulation pour être potentiellement divisée:
// Coupe tous les triangles en donnant un vecteur de triangles. // Une nouvelle liste de triangles de sortie est générée. L'ancienne // liste de triangles est supprimée. // n - La normale du plan de coupe // d - Distance du plan de coupe à l'origine // Référence: Bouyancy exacte pour Polyhedra par // Erin Catto dans Game Programming Gems 6 void SliceAllTriangles (const Vec2 & n, f32 d) std :: vector out; pour (uint32 i = 0; i < g_tris.size( ); ++i) // Grab a triangle from the global triangle list Triangle tri = g_tris[i]; // Compute distance of each triangle vertex to the clipping plane f32 d1 = Dot( tri.a, n ) - d; f32 d2 = Dot( tri.b, n ) - d; f32 d3 = Dot( tri.c, n ) - d; // a to b crosses the clipping plane if(d1 * d2 < 0.0f) SliceTriangle( out, tri.a, tri.b, tri.c, d1, d2, d3 ); // a to c crosses the clipping plane else if(d1 * d3 < 0.0f) SliceTriangle( out, tri.c, tri.a, tri.b, d3, d1, d2 ); // b to c crosses the clipping plane else if(d2 * d3 < 0.0f) SliceTriangle( out, tri.b, tri.c, tri.a, d2, d3, d1 ); // No clipping plane intersection; keep the whole triangle else out.push_back( tri ); g_tris = out;
Après avoir calculé la distance signée de chaque sommet de triangle par rapport au plan de division, vous pouvez utiliser la multiplication pour déterminer si deux points distincts se trouvent de part et d'autre d'un plan. Étant donné que les distances auront un flottant positif et négatif dans une paire, le produit des deux multiplié ensemble doit être négatif. Cela permet d'utiliser un prédicat simple pour voir si deux points se trouvent de part et d'autre d'un plan: #define OnOppositeSides (distanceA, distanceB) ((distanceA) * (distanceB) < 0.0f).
Une fois que tout On constate que l’arête intersecte le plan de division, les sommets des triangles sont renommés et décalés et immédiatement transmis à l'intérieur SliceTriangle une fonction. De cette manière, le premier bord d'intersection trouvé est renommé en un B.
Voici à quoi peut ressembler un produit fini de travail:
La division des triangles de cette manière tient compte de chaque triangle indépendamment, et l'algorithme présenté ici s'étend, sans création supplémentaire, de deux à trois dimensions. Cette forme d’écrêtage de triangles est idéale lorsque l’information sur la contiguïté des triangles n’est pas requise ou lorsque les triangles écrêtés ne sont stockés nulle part en mémoire. C’est souvent le cas lors du calcul des volumes d’intersections, comme en simulation de flottabilité..
Le seul problème avec la division de triangles de manière isolée est qu’il n’ya pas d’information sur les triangles adjacent à une autre. Si vous examinez attentivement le format GIF ci-dessus, vous constaterez que de nombreux triangles partagent des sommets colinéaires et que, par conséquent, ils peuvent être réduits en un seul triangle afin d'être rendus efficacement. La section suivante de cet article aborde ce problème avec un autre algorithme plus complexe (qui utilise toutes les tactiques présentées dans cette section)..
Passons maintenant au dernier sujet. En supposant une compréhension pratique de l’algorithme de Sutherland-Hodgman, il est assez facile d’étendre cette compréhension pour scinder une forme avec un plan et des sommets en sortie sur tous les deux côtés de l'avion. La robustesse numérique peut (et devrait) également être considérée.
Examinons brièvement les anciennes affaires de coupures de Sutherland-Hodgman:
// 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
Ces trois cas fonctionnent correctement, mais ne tiennent pas compte de l'épaisseur du plan de fractionnement. Par conséquent, une erreur numérique peut dériver lorsque des objets se déplacent, ce qui entraîne une faible cohérence temporelle des images. Ce type d'instabilité numérique peut entraîner le découpage d'un coin d'une image et non pas dans une autre, et ce type de scintillement peut être très laid visuellement ou inacceptable pour la simulation physique..
Un autre avantage de ce test de plan épais est que des points situés très près du plan peuvent en réalité être considérés comme étant sur le plan, ce qui rend la géométrie découpée légèrement plus utile. Il est tout à fait possible qu'un point d'intersection calculé soit situé numériquement du mauvais côté d'un plan! Les avions épais évitent de tels problèmes étranges.
En utilisant des plans épais pour les tests d'intersection, un nouveau type de cas peut être ajouté: une pose en point directement sur dans un avion.
Sutherland-Hodgman devrait être modifié comme suit (avec une virgule flottante EPSILON pour tenir compte des avions épais):
// InFront = plane.Distance (point)> EPSILON // Behind = plane.Distance (point) < -EPSILON // OnPlane = !InFront( dist ) && !Behind( dist ) 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 case any p1 and p2 OnPlane push p2
Cependant, cette forme de Sutherland-Hodgman n’émet que des sommets sur un côté du plan de fractionnement. Ces cinq cas peuvent facilement être étendus à un ensemble de neuf afin de générer des sommets de chaque côté d'un plan de division:
// InFront = plane.Distance (point)> EPSILON // Behind = plane.Distance (point) < -EPSILON // OnPlane = !InFront( dist ) && !Behind( dist ) Vec2 p1, p2; Poly front, back; ClipPlane plane; case p1 InFront and p2 InFront front.push( p2 ) case p1 OnPlane and p2 InFront front.push( p2 ) case p1 Behind and p2 InFront front.push( intersection ) front.push( p2 ) back.push( intersection ) case p1 InFront and p2 OnPlane front.push( p2 ) case p1 OnPlane and p2 OnPlane front.push( p2 ) case p1 Behind and p2 OnPlane front.push( p2 ) back.push( p2 ) case p1 InFront and p2 Behind front.push( intersection ) back.push( intersection ) back.push( p2 ) case p1 OnPlane and p2 Behind back.push( p1 ) back.push( p2 ) case p1 Behind and p2 Behind back.push( p2 )
Une implémentation de ces neuf cas pourrait ressembler à ceci (dérivée de la détection de collision en temps réel d'Ericson):
// divise un polygone en deux le long d'un plan de division en utilisant un algorithme de découpage // appelez découpage de Sutherland-Hodgman // ressource: Page 367 de Ericson (Détection de collision en temps réel) void SutherlandHodgman (const Vec2 & n, f32 d, const Poly * poly, std :: vector * out) Poly frontPoly; PolyPolyPoly; uint32 s = poly-> vertices.size (); Vec2 a = poly-> sommets [s - 1]; f32 da = point (n, a) - d; pour (uint32 i = 0; i < s; ++i) Vec2 b = poly->sommets [i]; f32 db = point (n, b) - d; if (InFront (b)) if (Derrière (a)) Vec2 i = Intersection (b, a, db, da); frontPoly.vertices.push_back (i); backPoly.vertices.push_back (i); frontPoly.vertices.push_back (b); else if (derrière (b)) if (InFront (a)) Vec2 i = intersection (a, b, da, db); frontPoly.vertices.push_back (i); backPoly.vertices.push_back (i); else if (On (a)) backPoly.vertices.push_back (a); backPoly.vertices.push_back (b); else frontPoly.vertices.push_back (b); if (On (a)) backPoly.vertices.push_back (b); a = b; da = db; if (frontPoly.vertices.size ()) out-> push_back (frontPoly); if (backPoly.vertices.size ()) out-> push_back (backPoly);
Voici un exemple de Sutherland-Hodgman en action:
Il est à noter que les polygones finaux peuvent être rendus sous forme de liste de vertex au format de fan de triangle..
Vous devez être conscient d'un problème: lors du calcul d'un point d'intersection de un B et un plan de fractionnement, ce point souffre de quantification numérique. Cela signifie que toute valeur d'intersection est une approximation de la valeur d'intersection réelle. Cela signifie également que le point d'intersection ba n'est pas numériquement identique; dérive numérique minuscule entraînera en fait deux valeurs différentes!
Exemple de fissure visible entre des triangles à la suite d'un découpage incohérent (image inspirée du livre de Eric Collaboration sur la détection de collision en temps réel). Une routine de découpage naïve peut faire une grosse erreur en calculant les points d'intersection à l'aveuglette, ce qui peut entraîner des jonctions en T ou d'autres lacunes dans la géométrie. Pour éviter un tel problème, une orientation d'intersection cohérente doit être utilisée. Par convention, les points doivent être coupés d'un côté à l'autre de l'avion. Cet ordre d'intersection strict garantit que le même point d'intersection est calculé et résoudra les écarts potentiels en géométrie (comme le montre l'image ci-dessus, le résultat de découpage est cohérent à droite)..
Pour pouvoir réellement rendre les textures sur des formes divisées (peut-être lors de la scission des sprites), vous devez comprendre les coordonnées UV. Une discussion complète sur les coordonnées UV et le mappage de texture va bien au-delà de la portée de cet article, mais si vous avez déjà compris cela, il devrait être facile de transformer les points d'intersection en espaces UV..
S'il vous plaît, comprenez qu'une transformation de l'espace mondial en espace UV nécessite un changement de transformation de base. Je laisse les transformations UV comme exercice pour le lecteur!
Dans ce tutoriel, nous avons étudié quelques techniques simples d’algèbre linéaire pour résoudre le problème de la division dynamique de formes génériques. J'ai également abordé quelques problèmes de robustesse numérique. Vous devriez maintenant pouvoir implémenter votre propre code de fractionnement de forme ou utiliser la source de démonstration pour obtenir de nombreux effets et fonctionnalités avancés et intéressants pour la programmation de jeux en général..
Accentsconagua