Zusammenfassen von Polygonen
-
Ich würd's mal mit www.flipcode.com unter "Ask Midnight" versuchen.
-
Sgt. Nukem schrieb:
...wenn er NICHT NUR Pseudocode will?!?
dann würde ich schnell die seiten wechseln, weil es zwei dinge gibt, bei denen jede hilfsbereitschaft flöten geht.
a) ich will dieses und jenes, postet mir mal jemand fertigen code, den ich dann am besten bloß noch mit copy/paste einfügen muß?
b) ich knall mal schnell 5 bildschirmseiten code hin. so, und das "funzt" nicht, wo ist der fehler?
aber bei der frage nach dem algo. bin ich stillschweigend davon ausgegangen, daß er wirklich nur eine clevere methode und keinen fertigen code sucht.
ist ein polygon überhaupt noch ein polygon, wenn es nicht planar ist? und kann man in dem fall in der praxis wirklich noch soviel einsparen? *grübel* naja, in ein paar jahren kein thema mehr, wenn selbst os-oberflächen nur noch in "3d" gemacht werden und "altmodische" 2d grafik endgültig ausgestorben ist *fg*
-
ChrisBorgolte schrieb:
Welche Sprache? Vielleicht war ich ein wenig voreilig mit dem Posten, aber ich dachte, wenn die URL schon c-plusplus.net heißt, dann läge die Sprache auf der Hand.
Dann guck' Dir die Foren hier mal genauer an...
Trienco schrieb:
*grübel* naja, in ein paar jahren kein thema mehr, wenn selbst os-oberflächen nur noch in "3d" gemacht werden und "altmodische" 2d grafik endgültig ausgestorben ist *fg*
Soweit wird's zum Glück niemals kommen!!
Jetzt können zunächst auch Mainstream-Handys alle 3D wie FarCry.
Dann gibt's mehr und mehr Waschmaschinen und Kühlschränke, die mit kleinen Computern und zunächst nur billigen LC-Displays ausgerüstet werden. Dort erleben dann die alten C64-Spiele wieder eine Renaissance...
-
Sgt. Nukem schrieb:
Dann gibt's mehr und mehr Waschmaschinen und Kühlschränke, die mit kleinen Computern und zunächst nur billigen LC-Displays ausgerüstet werden. Dort erleben dann die alten C64-Spiele wieder eine Renaissance...
perfekt. dann wird wäsche waschen dank m.u.l.e. zum partyspaß und wer den highscore in tetris knackt bekommt seine cola extra kalt ,-)
-
Sgt. Nukem schrieb:
Dort erleben dann die alten C64-Spiele wieder eine Renaissance...
Da fällt mir ein, ich wollte doch ein paar solche hochladen...
Bye, TGGC (Der Held bei Dir!)
-
ChrisBorgolte schrieb:
Leider muss ich sehr viele Polygone auch gemeinsame Kanten testen und da reicht Dein Ansatz wirklich nicht aus.
Das ist so nicht ganz richtig. Der Ansatz ist weder ineffizient noch sonstwas. Es steht nirgends, daß die Suche ungeschickt erfolgen muß oder sowas. Auf jeden Fall könntest Du es mal so implementieren. Das geht in ca. 20 Minuten, dann läuft es korrekt würde ich mal schätzen.
Von da an hast Du mal ne funktionierende Referenz. Das heißt, Du kannst wenn Du den Algorithmus verbesserst immer noch die funktionierende kahme Version mitlaufen lassen um so automatisch das Ergebnis zu verifizieren.
Dann nimmste mal ne vernünftig große Szenerie und haust die durch. Profiler verrät Dir dann die Bottle-Necks und Du kannst an's optimieren gehen.
Vielleicht nützt es was, wenn Du die Polygone vorher in eine Art BSP-Tree einsortierst etc. oder Dir beim durchlaufen zumindest merkst, wie weit Du schon verglichen hattest und nur das wieder vergleichst, was sich auch geändert haben kann. Aber das ist dann ne andere Frage.
Und zunächst einfach mal ne funktionierende Referenzimplementierung zu haben ist sicher was feines, wenn man nen ordentlichen Algorithmus bauen will.MfG Jester
-
Jester schrieb:
Das geht in ca. 20 Minuten, dann läuft es korrekt würde ich mal schätzen.
Das ist der Irrglaube, dem man als Programmierer leider immer wieder erlegen ist. Dann fängst Du an zu hacken, debuggen und wenn es dann endlich klappt, mit dem Profiler nochmal die möglichen Bottlenecks rauszufiltern.
Anschließend probiert man es dann mal in einem realitätsnahen Einsatz von vielleicht 500.000 Polygonen aus und stellt dann fest, dass
1.man mal wieder irgendeinen Sonderfall übersehen hat
2.es viel zu langsam ist
3.der Speicher nicht ausreicht
4....Dann sitzt man da, zerbricht sich den Kopf über mögliche Sortierverfahren, eine alternative Datenhaltung und weitere mögliche Sonderfälle, die man vielleicht noch nicht berücksichtigt hat, oder doch einen ganz anderen Ansatz, dieses Problem zu lösen. Schliesslich hat man ja noch nicht einmal das grösste bekannte Modell ausprobiert, sondern nur ein grosses.
Das dauert dann nicht mehr schlappe 20 Minuten.Irgendwann, wenn man wirklich viel Zeit investiert hat, dann stolpert man zufällig im Internet über einen interessanten Beitrag: Da hat doch irgend so ein schlauer Mensch genau über Dein Problem eine Abhandlung verfasst und am besten gleich noch eine Bibliothek oder die Quellen zum Download bereit gestellt, und das Ganze läuft dann sogar schon seit einigen Jahren und ist von tausenden von Leuten getestet worden.
Dann fällt dir die Grundregel wieder ein, die Du mal in jedem Buch, das mit Softwareentwicklung zu tun hat, gelesen hast: „Versuche nicht das Rad neu zu erfinden“.Wie bereits erwähnt, hatte mit meinem Posting erhofft, jemand könnte mir mitteilen, dass es tatsächlich bereits eine Lösung für mein Problem gäbe. Es gibt schliesslich in diesem Bereich einige vorhandene Algorithmen, bzw. mathematische Disziplinen, ob es nun Triangulation oder Mesh Simplification oder sonst noch was ist.
Darum hatte ich auf so eine Antwort gehofft, wie:
„Klar, so was gibt's schon. Schau doch mal bei „...“ unter der Rubrik „...“ nach.“
(Leider habe ich trotz der grandiosen Hilfe von noebef den entsprechenden Artikel unter "Ask Midnight" nicht gefunden, vielleicht kannst Du mir da nochmal weiterhelfen, rapso.)Ich wollte weder Pseudo-, noch realen Code, den irgendwer mal nach zwei Minuten nachdenken niedergeschrieben hat. Mir ist schon bewusst, dass es sich dabei nicht um Raketenphysik handelt (auch wenn ich Deinen Algorithmus schon als äußerst nahe daran bezeichnen möchte, TGGC), aber hier liegt der Teufel tatsächlich im Detail, bzw. in der Performance und im Speichermanagement.
mfG
chris
-
in dem fall würde mir höchstens eine google suche zwecks progressive meshes oder allgemein dynamic lod einfallen. ist zwar nicht ganz das gleiche, aber das grundlegende problem möglichst schnell (bevorzugt echtzeit) das modell zu vereinfachen bzw. die nötigen infos dafür dürften ähnlich ausfallen.
-
@ChrisBorgolte:
Du erliegst gerade dem Irrglauben, einfach so mal schnell irgendwoher ne bessere Lösung herzukriegen...
Ich sagte nicht, Du sollst die lahme Version bauen und die dann optimieren, ich sagte Du sollst schaun, wo Du sie danach (algorithmisch) verbessern kannst und Du sollst die lahme Version zum Testen verwenden. Das ist eine Standardvorgehensweise um komplexe Algorithmen zu entwerfen.
Außerdem könnte es ja sein, daß eine relativ einfach Lösung schon genügt. Aber da ist man als Programmierer ja auch ständig im Irrglauben... man braucht da auch nicht messen oder so, es muß schon das Schnellste sein und so, alles andere kann ja garnicht gehen.MfG Jester
-
Ich halte dieses Problem nicht für so komplex, als das man hier libs o.ä. benutzen müsste. Ich werde mich mal bei gelegenheit dransetzen und ausprobieren, ob mein Vorschlag so klappt, aber ich glaube ein eigener Algorithmus für diesen Zweck ist weder sehr groß noch besonders zeitaufwändig.
