Files |  Tutorials |  Articles |  Links |  Home |  Team |  Forum |  Wiki |  Impressum

Aktuelle Zeit: Do Mär 28, 2024 17:56

Foren-Übersicht » Programmierung » Allgemein
Unbeantwortete Themen | Aktive Themen



Ein neues Thema erstellen Auf das Thema antworten  [ 3 Beiträge ] 
Autor Nachricht
BeitragVerfasst: Do Feb 22, 2018 16:13 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Apr 25, 2005 17:51
Beiträge: 464
Hiho,

um meine Kollisionstests zu beschleunigen, die bisher nur Bounding Volumes nutzen, möchte ich gerne einen hierarchien Ansatz nutzen. Bevor ich nun selber anfange, was schon etliche male vorher implementiert worden ist, wollte ich fragen, ob da jemand eine gute Lib für Delphi kennt. Mir reicht wirklich die reine Kollisionskontrolle, ich brauche keine Physik-Engine (wie zB Newton Physics)


VG

Pellaeon

_________________
__________
"C++ is the best language for garbage collection principally because it creates less garbage." Bjarne Stroustrup


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Do Feb 22, 2018 17:33 
Offline
DGL Member
Benutzeravatar

Registriert: Di Mai 18, 2004 16:45
Beiträge: 2621
Wohnort: Berlin
Programmiersprache: Go, C/C++
Schau doch mal nach Sweep and Prun, z.B. hier.
Der Algorithmus nutzt aus, dass die Überlappung der Bounding Volumes, auf den einzelnen Achsen das raus werfen von unmöglichen kollissionen einfach raus filtert.
Es bleiben nur noch Potenzielle Paare über, die werden genauer geprüft.
Du kannst dann noch die Sache bei Caches erweitern, ein Paar, was sich zum vorigen Frame nicht verändert hat, brauch nicht mehr geprüft werden, wenn der Cache sagt es war ein Treffer.

Hierarchische Systeme sind Tricky, zu stark zerlegt und es ist Speicherhungrig, zu flach und du hast zuviele Berechnungen.
Ein dynamischer Octree ist langsam, weil er umgebaut werden muss, ein Statischer ressourcenverschwenderig.

Multithreading ist ein sehr einfaches optimierungstool, da man in der Regel sehr viele Objekte hat und die liegen in fortlaufenden Listen.
N-Threads, jeder verarbeitet ein Bereich der Liste, z.B. 0-24 Thread 0, 25-49 Thread 1, 50-74 Thread 2 und 75-99 Thread 3 bei 100 Elementen.
Lesen können die Threads ja auf allen 100 Elementen, solange niemand schreibt und dass sollte eigentlich nicht passieren.
Jeder Thread bekommt die Liste, STart, Amount und eine ResultList, wo der Thread rein schreibt.
Dann warten bis alle fertig sind, die ResultList von jeden Thread auswerten und zur nächsten Phase.
Nicht das beste aber skaliert schon mal wesentlich besser mit der Hardware, die meisten eh brach liegt.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Fr Feb 23, 2018 08:16 
Offline
DGL Member
Benutzeravatar

Registriert: Mo Apr 25, 2005 17:51
Beiträge: 464
TAK2004 hat geschrieben:
Hierarchische Systeme sind Tricky, zu stark zerlegt und es ist Speicherhungrig, zu flach und du hast zuviele Berechnungen.
Ein dynamischer Octree ist langsam, weil er umgebaut werden muss, ein Statischer ressourcenverschwenderig.


Ein hierarchisches Prinzip hat eine logaritschmische Komplexität (oft n log n) während die Brute-Force-variante bei liegt. Von daher würde ich deiner Aussage jetzt so nicht zustimmen wollen. Natürlich hängt es stark von der Anzahl der Objekte und von der Verteilung in der Szene ab, wie gut oder schlecht ein Algo im konkreten arbeitet. Multithreading beschleunigt Brute Force natürlich auch, ändert aber nix am quadratischen Sachverhalt.

Das Sweep and Prune sagt mir vom Namen etwas, ich habe es aber noch nicht konkret angeschaut. So wie du es beschreibst, klingt es, als wenn das auf dem Separation Axis Theorem aufbaut.

Aber an sich ging es mir nicht um eine Diskussion, welche Verfahrensweise am besten ist :D Das ist eh immer stark abhängig von der Szene und der konkreten Impementierung. Ich suche eine Delphi-Bibliothek, welche KOllisionskontrolle beherrscht und das nicht nur Brute Force macht, sondern auf irgendeine Art räumliche EInteilung zurückgreift (Trees, BVH, Sweep and Prune, ...), Bei meiner Anwendung ist es an sich egal, was ich da nehme. Der Performance-Schub würde mir in jedem Fall genügen. Meine Szene ist groß genug, das Brute Force mit Bounding Boxes ruckelt, aber klein genug, dass es egal ist, welche der intelligenteren Strukturen ich nutze.
In C++ kenne ich genug Libs, wo ich sofort drauf zugreifen könnte. Ich dachte, in Delphi gibt es da evtl. auch was, sodass man sich nicht selber die Arbeit machen.


VG

Pellaeon

_________________
__________
"C++ is the best language for garbage collection principally because it creates less garbage." Bjarne Stroustrup


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 3 Beiträge ] 
Foren-Übersicht » Programmierung » Allgemein


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 25 Gäste


Du darfst keine neuen Themen in diesem Forum erstellen.
Du darfst keine Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
cron
  Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de
[ Time : 0.051s | 17 Queries | GZIP : On ]