Ich arbeite mit einer Spiel-Engine und meine Aufgabe ist es, Code zum Simulieren des Bruchs starrer Netze hinzuzufügen.
Im Moment arbeite ich nur daran, einen Würfel zu zerbrechen.
Ich verwende den Voronoi-Algorithmus, um einen (realistischen) gebrochenen Splitter herzustellen, und ich verwende die Halbebenenmethode, um eine Voronoi-Zelle zu erzeugen.
Jetzt mache ich das für jeden Startpunkt. Ich erstelle Ebenen, die senkrechte Winkelhalbierende sind (die geraden schwarzen Linien im Bild), mit den restlichen Startpunkten und berechne die Schnittpunkte all dieser Ebenen, um mir unterschiedliche Punkte zu geben ( alle orangefarbenen Punkte).
Ich bin so weit gekommen.
Von all diesen berechneten Schnittpunkten benötige ich nur diejenigen, die am nächsten liegen und den Startpunkt einschließen (die rot eingekreisten Punkte), und ich muss den Rest verwerfen.
Informationen, die ich habe:
1) Ebenengleichungen aller Ebenen (definiert durch normalisierte Normalenvektoren und deren Abstand vom Ursprung)
2) Schnittpunkte (die ich berechnet habe)
Kann mir jemand helfen, herauszufinden, wie ich die rot eingekreisten Punkte finden kann?
quelle
Antworten:
Nach der Halbebenenmethode haben Sie die Liniensegmente zu jedem anderen Punkt und die senkrechten Winkelhalbierenden von jedem dieser Punkte gefunden
die Sie dann geschnitten haben, um mögliche Eckpunkte der Voronoi-Zelle zu finden.
Nun möchten Sie diejenigen ausschließen, die eine der von den Winkelhalbierenden gebildeten "entfernten" Halbebenen schneiden.
Ich habe die "entfernten" Halbebenen zur Klarheit durchscheinend blau gefärbt.
Hier bestehen die beiden eingekreisten roten Punkte den Test: Sie befinden sich nicht in einer Halbebene. Der nicht eingekreiste rote Punkt geht nicht durch, da er sich innerhalb der Halbebene befindet, die zum Punkt oben rechts hin gebildet ist.
Dies bedeutet effektiv zu testen, ob sich jeder Punkt auf der anderen Seite jeder Halbierungslinie befindet (relativ zur Voronoi-Stelle) und diejenigen zu verwerfen, die sich befinden. (Vorsicht vor Rundungsfehlern.)
quelle
Sie können einfach über Kanten iterieren und alle Scheitelpunkte herausfiltern, die sich nicht in derselben Halbebene mit dem interessierenden Punkt befinden.
Iterieren Sie zur Optimierung von den nächsten bis zu den am weitesten entfernten Kanten. Ich denke, Sie können sogar Scheitelpunkte filtern, während Sie Slices generieren.
Es ist, als würde man mit einem endlosen Messer Kuchen schneiden, bis nur noch ein kleines Stück Kirsche übrig ist. Wenn Sie Analogien mögen. Schneiden Sie einfach und sehen Sie, welches Teil genommen und welches weggeworfen wird.
quelle