2D-Querschnitt Polygon aus 3D-Mesh generieren

Ich schreibe ein Spiel, das 3D-Modelle verwendet, um eine Szene zu zeichnen (Top-Down-orthographische Projektion), aber eine 2D-Physik-Engine, um die Reaktion auf Kollisionen usw. zu berechnen einige 3D-Assets, für die ich automatisch eine Hitbox erstellen möchte, indem ich das 3D-Mesh mit der XY-Ebene "schneide" und aus den resultierenden Kanten ein Polygon erstelle.2D-Querschnitt Polygon aus 3D-Mesh generieren

Google versagt mich auf diesem (und nicht viel hilfreiches Material auf SO entweder). Vorschläge?

Die Netze, mit denen ich es zu tun habe, werden vereinfachte Versionen der angezeigten Modelle sein, die verbunden sind, geschlossen, nicht-konvex und haben Null-Klasse.

Quelle

2010-05-09 nornagon

Ist es unter Berücksichtigung Ihrer Beschreibung auch möglich, das 3D-Netz auf eine 2D-Ebene zu projizieren? Der Projektionsteil ist einfach und reduziert die Frage auf "Erstellen eines Polygons aus einem Bündel überlappender Dreiecke", was leichter zu lösen sein kann, besonders wenn Ihre Projektion konvex ist. – Thomas

Vielleicht können Sie uns mehr über Ihr Mesh erzählen. Ist es konvex? Ist es verbunden? Ist es geschlossen? Hat es null Gattung? Wie ist es in der Erinnerung dargestellt? – Thomas

Die Netze sind nicht konvex, aber sie werden verbunden und geschlossen und haben Null-Klasse. – nornagon

Da Ihre Netze nicht konvex sind, kann der resultierende Querschnitt getrennt sein, sodass sie tatsächlich aus mehreren Polygonen bestehen. Dies bedeutet, dass jedes Dreieck überprüft werden muss, so dass Sie mindestens 0 (n) Operationen für n Dreiecke benötigen.

Hier ist eine Möglichkeit, es zu tun:

T <- the set of all triangles 
P <- {} 
while T is not empty: 
    t <- some element from T 
    remove t from T 
    if t intersects the plane: 
    l <- the line segment that is the intersection between t and the plane 
    p <- [l] 
    s <- l.start 
    while l.end is not s: 
     t <- the triangle neighbouring t on the edge that generated l.end 
     remove t from T 
     l <- the line segment that is the intersection between t and the plane 
     append l to p 
    add p to P

Die in O läuft (n) Zeit für n Dreiecken, vorausgesetzt, dass Ihre Dreiecke Zeiger auf ihre drei Nachbarn haben, und dass T unterstützt konstante Zeit Umzüge (zB ein Hash-Set).

Wie bei allen geometrischen Algorithmen steckt der Teufel im Detail. Denken Sie sorgfältig über Fälle nach, in denen der Scheitelpunkt eines Dreiecks beispielsweise genau in der Ebene liegt.

Quelle

2010-05-09 11:46:09 Thomas

Danke, jetzt muss ich nur ein wenig darüber nachdenken, wie zu bestimmen, welches Dreieck ist, welches andere Dreieck an welcher Kante ... – nornagon

Deshalb fragte ich, wie Ihr Netz im Speicher dargestellt wird. Sie könnten das Mesh vorverarbeiten, indem Sie Kanten verbinden, wenn sie sich zwei Ecken teilen. – Thomas

Sie können auch zuerst alle Dreiecke durchlaufen, die Liniensegmente generieren und die Zeiger auf die ursprünglichen Dreiecke zurückführen. Schleifen Sie dann alle Liniensegmente und verknüpfen Sie sie miteinander. Das wird Ihnen die Vorverarbeitungsphase ersparen, kann aber langsamer sein, wenn Sie es viele Male tun. – Thomas

Sie können dies mit einem Abit der Geometrie tun, indem Sie alle Polygone finden, die sich mit der Ebene schneiden und dann das exakte Segment des Schnittpunktes finden. Diese Segmente sind die Linien des 2D Polygons, nach denen Sie suchen.

Quelle

2010-05-09 11:40:24 shoosh

Wie bestelle ich die Segmente? – nornagon

Segmente, die benachbart sind, stammen von zwei Dreiecken, die sich dieselbe Kante teilen. – shoosh

2D-Querschnitt Polygon aus 3D-Mesh generieren

Antwort

Verwandte Themen