2D / 3D Räume in Programmen

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Benutzeravatar
str1442
User
Beiträge: 520
Registriert: Samstag 31. Mai 2008, 21:13

Montag 22. September 2008, 01:05

Hallo,

Ich behaupte einfach mal, ziemlich viele Programme benötigen 2 oder 3D Räume / Koordinatensysteme.

Ich bekomme es allerdings nicht auf die Reihe, bei der Planung eines Projektes einen solchen Raum "richtig" einzuplanen.

Ganz allgemein könnte man natürlich Listen und/oder Tupel kreuzfidel verschachteln und die entsprechenden Indizes als Koordinatenpunkte verwenden. Oder auch ein Dict / Shelve Objekt mit Tupeln als Keys verwenden.

Aber mit sowas baut man sich quadratische / tertiäre (<- ist das der richtige Ausdruck?) Algorithmen und bei Dingen, die für alle Objekte innerhalb des Koordinatensystem gelten sollen, braucht man meist sowieso wieder andere Container, die zb alle Objekte der Sorte xy zusammenfassen.

Andererseits könnte man dann das Koordinatensystem auch gleich ganz weglassen und es nur imaginär behandeln. Sprich, ein Objekt hat eine festgelegte Position, wenn es die zb wechseln will, schnappt man sich einen beliebigen Algorithmus, rechnet alles wichtige aus und Ende. Dann wird aber die Interaktion von Objekten wiederrum komplizierter, vermute ich.

Das wird alles recht schnell ineffizient. Mit 20 ** 3 (8000) Punkten wird jawohl kein komplexes 3D Spiel auskommen und halbwegs Menschen/Autos/Schiffe/etc. darstellen können, die auch noch richtig nach der Physik Engine agieren? Wie funktioniert eigentlich die Mathematik hinter sowas? Wie kann man so ein komplexes Objekt eigentlich zb drehen, (hier vermute ich allerdings Trigonometrie), oder für jenes komplexe Kollisionsabfragen durchführen? (Anmerkung: Ich plane natürlich nicht ähnliches zu realisieren, aber allein solche Dinge erscheinen mir einfach so rechenlastig, so "fein" und komplex)

Wie sollte man Objekte mithilfe einer "Physik Engine" miteinander agieren lassen? Wie überhaupt Physik in ein Programm hereinbringen? Und vorallem wo sollte man sie einsetzen? Als ein eigenes, zentrales Objekt, das eventgesteuert alle Objektanfragen entgegenimmt? Und wie sollte man sowas anfangen?

Das klingt vermutlich etwas diffus, aber an diesem Punkt knacke ich jetzt schon ziemlich lange dran rum ohne irgendwie weiterzukommen. Google und co hab ich immer wieder versucht, kam aber nie hilfreiches bei raus - außer bei kleinen Dingen, wie 10 * 10 Felder für Tetris usw.

Danke fürs Lesen :)
BlackJack

Montag 22. September 2008, 06:20

Apropos diffus: Könntest Du die Frage vielleicht nochmal kurz und knackig auf den Punkt gebracht formulieren? :-)
Benutzeravatar
str1442
User
Beiträge: 520
Registriert: Samstag 31. Mai 2008, 21:13

Montag 22. September 2008, 06:43

Das wäre dann in etwa:

Wie verwalten Programme idR Koordinatensystem bzw Räume so, das man

A. Eine Physik halbwegs gut und zentral einbauen kann, und vorallem wo (Eigenes Objekt, ...) und wie
B. Es nicht zu speicher / rechenlastig wird bei schon kleinen Mengen an Koordinaten

C. Bin ich da ganz falsch gewickelt und um Objekte zb zu bewegen oder interagieren zu lassen braucht man gar kein "richtiges" Koordinatensystem?

( {(0, 0, 0) : ["Objekt bla"], ... } )

^_^
Benutzeravatar
veers
User
Beiträge: 1219
Registriert: Mittwoch 28. Februar 2007, 20:01
Wohnort: Zürich (CH)
Kontaktdaten:

Montag 22. September 2008, 07:33

Hängt ganz davon ab was du damit machen willst ;)

Für die Physikerausbildungen in interaktiven Anwendungen verwendet man oft Vereinfachungen wie Bounding Boxes. Welche dann in einem Octree o.ä. abgelegt werden. Wenn du es genau wissen willst lies den Source einer Physik Engine wie ODE oder Bullet.

Ein Raytracer hingegen verwendet oft andere Datenstrukturen wie kd-trees ;)

Grundsätzlich:
Überlasse A und B eine Physik Engine, und was C angeht, wie beschreibst du die Position eines Punktes im Raums sonst ;)
[url=http://29a.ch/]My Website - 29a.ch[/url]
"If privacy is outlawed, only outlaws will have privacy." - Phil Zimmermann
sea-live
User
Beiträge: 440
Registriert: Montag 18. Februar 2008, 12:24
Wohnort: RP

Montag 22. September 2008, 08:17

Also für 2D objekt bewegung empfehle ich PYGAME.org

und in 3D bietet sich dann Python BLENDER.org an

bei beiden gibt es tolle integrierte bewegungs befehle
und der user weis immer per get befehl wo sich die objekte gerade befinden
die sich bei jedem programmcyclus selbstständig weiterbewegen !
Benutzeravatar
Rebecca
User
Beiträge: 1662
Registriert: Freitag 3. Februar 2006, 12:28
Wohnort: DN, Heimat: HB
Kontaktdaten:

Montag 22. September 2008, 09:32

Wenn du das wirklich wissen willst, solltest du mal bei Amazon nach den Stichworten 3D Math Programming Physics suchen, da findet man dann so Buecher wie dieses hier. Aber das ist ein sehr komplexes Feld, am sinnvollsten ist es, du suchst dir eine existierende Physics-Engine (z.B. ODE mit Python-Bindings pyODE).

Ansonsten funktioniert es etwa so: Du speicherst zu jedem Objekt die Koordinate seines Schwerpunkts. Ausserdem brauchst du noch eine Moeglichkeit, den Raum, den ein Objekt einnimmt, zu speichern. Wenn du nicht allein mit Primitives (durch mathematische Formeln beschriebene Objekte wie Kugeln, Quader, Zylinder, ...) auskommst, ist der gaengige Weg, die Oberflaeche dur ein Polygon zu beschreiben. Dann musst du zu jedem Objekt die Eckpunkte des Polynoms speichern (relativ zum Objektursprung) und wo zwischen diesen Punkten Flaechen und Kanten bestehen. Verschieben des Objektes mit seinem Schwerpunkt ist dann nur eine Vektoraddition mit dem Vektor, der den Koordinatenursprung angibt.

Transformationen (Roatation, Verschiebung, Skalierung, Spiegelung) sind nichts weiter als Lineare Abbildungen von R^3 -> R^3, also Matrix-Multikplikation und Vektor-Addition mit geeigneten 3x3-Matrizen und 3d-Vektoren (bzw. nur Vektor-Multiplikation mit 4x4-homogenen Matrizen). Grundkenntnisse Lineare Algebra sind hier von Vorteil. :wink:

Kollisionsdetektion laeuft darauf hinaus, dass du berechnest, ob sich zwei Objekte mathematisch gesehen schneiden. Das ist einfach fuer Primitives, fuer beliebige Objekte verwendet man zur Kollisionsdetektion dann vereinfachte Formen als diejenigen, die zur Darstellung verwendet werden. Also ganz einfach z.B. Quader, die das Objekt umfassen, komplizierter mit sogenannten Einhuellenden (konvexe Polygone, die das Objekt umschliessen). Die Objekte, die fuer Kollisionsdetektion verwendet werden, muessen im Objekt natuerlich auch gespeichert werden.

Physik bleibt solange einfach, solange du nur Effekte betrachtest, zu denen du allein den Schwerpunkt des Objekts und evtl. Kollisionen betrachtest (Fall, Wurf, Abprallen ohne Reibungseffekte oder Rotation). Alles andere wird sehr schnell sehr aufwaendig. Verformungen von Objeten erst recht.

Insgesamt legst du dir also eine Klasse an mit den oben genannten Attributen, und in deinem Spiel hast du einfach eine Liste aller Objekte. Was genau meinst du mit vollstaendigem Koordinatensystem? Alle moeglichen Punkte werden einfach gegeben durch den Wertebereich der Floats, das speicherst du dir nicht nochmal extra ab.
Offizielles Python-Tutorial (Deutsche Version)

Urheberrecht, Datenschutz, Informationsfreiheit: Piratenpartei
Benutzeravatar
wuf
User
Beiträge: 1497
Registriert: Sonntag 8. Juni 2003, 09:50

Montag 22. September 2008, 16:22

Hallo str1442

Unser Forum-Mitglied 'Sugar Princes' hat vor langer Zeit ein Animations-Programm mit einem Würfel der sich dreht geschrieben. Lohn sich vielleicht einmal anzuschauen.

http://www.python-forum.de/topic-3058.html

Gruss wuf :wink:
Take it easy Mates!
Benutzeravatar
str1442
User
Beiträge: 520
Registriert: Samstag 31. Mai 2008, 21:13

Montag 22. September 2008, 17:38

Vielen Dank für die Antworten, insbesondere Danke für die ausführliche Beschreibung an Rebecca! Das hat mir viele Dinge klarer gemacht.

ODE / PyODE werde ich mir mal anschauen. Und den drehenden Würfel auch :D
Insgesamt legst du dir also eine Klasse an mit den oben genannten Attributen, und in deinem Spiel hast du einfach eine Liste aller Objekte. Was genau meinst du mit vollstaendigem Koordinatensystem? Alle moeglichen Punkte werden einfach gegeben durch den Wertebereich der Floats, das speicherst du dir nicht nochmal extra ab.
Mit vollständig meinte ich "richtig da"... Eben dargestellt durch eine Datenstruktur, wie zb eine Liste mit 10 Sublisten mit jeweils 10 Elementen (also ein 10^2 Feld) - Also nicht schlicht durch Speichern der Zahl eines Rechenweges.

Wird aber nicht das Zusammenspiel zwischen anderen Komponenten denn der Physics Engine und eben den Koordinaten etwas kompliziert? Wenn ein Objekt nun grafisch dargestellt werden soll, müsste man doch das Koordinatensystem wieder grafisch abbilden - Dann müsste man die Koordinaten (als reine Zahlen und dahinter stehenden mathematischen Polygon Strukturen) wieder in eine Relation miteinander stellen. Dieses "in Relation miteinander stellen" - Wenn ich 3 Koordinaten in einer Matrix darstelle und sie mit anderen vergleiche, stellt das sicher kein allzugroßes Problem dar. Aber wie bildet man das dann ab? Das will mir noch nicht so recht einleuchten.
BlackJack

Montag 22. September 2008, 18:09

Was heisst abbilden hier? 3D-Koordinaten in eine 2D-Grafik? Dazu sind unter anderem die vorgeschlagenen Bücher interessant.

Oder wenn Du's lieber praktischer magst, arbeite dich ein wenig in OpenGL ein. Zu den "Nehe Tutorials" gibt's auch Python-Code: http://nehe.gamedev.net/
Benutzeravatar
str1442
User
Beiträge: 520
Registriert: Samstag 31. Mai 2008, 21:13

Montag 22. September 2008, 20:03

Naja, beispielsweise - Wenn ich alle Objekte als etwas mathematisch komplett beschreibares ansehe, sind die (jedes für sich) erstmal abgeschlossen. Die Interaktion kann dann mithilfe von zb einer Physics Engine stattfinden, nur der Raum an sich ist ja erstmal nur Zahl ohne irgendwas drumrum. Mit Zahlen kann ich mit obigen Dingen wunderbar arbeiten, nur beim Darstellen (und eventuell bei anderen Dingen) muss man ja festlegen: Wie wird dargestellt? In welcher "Entfernung" sind die Einzelnen Koordinaten zueinander (wobei hier natürlich floats die Lücke füllen), wie bilde ich zb 3D Koordinaten auf eine OpenGL 3D Ebene ab? Deswegen mein Gedanke, das der Raum eigentlich nicht "einfach" nur ein Sammelsurium von Koordinatenangaben der einzelnen Objekte sei.

Das macht OpenGL aller Wahrscheinlichkeit nach automatisch, wenn richtig verwendet.

Insofern müsste ich nur zb PyODE und OpenGL möglichst nett miteinander kombinieren. Ich habe mich schon durch einige Beispielskripte bezüglich PyODE durchgewühlt und auch prompt eins mit OpenGL gefunden, was mich dann schon recht beeindruckt hat ( http://pyode.sourceforge.net/tutorials/tutorial3.html ), für das bisschen Code...

Danke auch für die Nehe OpenGL Seite - sieht sehr interessant aus.
Benutzeravatar
Rebecca
User
Beiträge: 1662
Registriert: Freitag 3. Februar 2006, 12:28
Wohnort: DN, Heimat: HB
Kontaktdaten:

Montag 22. September 2008, 21:19

str1442 hat geschrieben:nur der Raum an sich ist ja erstmal nur Zahl ohne irgendwas drumrum.
:?:
Mit Zahlen kann ich mit obigen Dingen wunderbar arbeiten, nur beim Darstellen (und eventuell bei anderen Dingen) muss man ja festlegen: Wie wird dargestellt?
Wenn du deine Objekte nachher in einem zweidimensionalen Bild darstellen willst, musst du sie "rendern". In diesem Prozess wird von einer Kamera, die in einem Punkt verankert ist, aus berechnet, was diese Kamera bei gegebeen Lichtverhaeltnissen etc alles sehen kann, welche Objekte von anderen verdeckt werden, welche Flaechen im Schatten liegen etc. Schau dir z.B. mal PovRay an. Hat zwar nichts mit Python zu tun, aber hier siehst du genau, wie aus mathematschen Beschreibungen richtige Bilder werden.
In welcher "Entfernung" sind die Einzelnen Koordinaten zueinander (wobei hier natürlich floats die Lücke füllen), wie bilde ich zb 3D Koordinaten auf eine OpenGL 3D Ebene ab?
In welcher raeumlichen Beziehung die Objekte untereinande stehen, sagt dir ja gerade die Mathematik. Betrachten wir zwei Punkte x und y (jeweils als 3D-Vektor). Ihr Abstand betraegt sqrt((x-y|x-y)). Das erste Objekt ist genau ueber dem anderen wenn x_1 = y_1, x_2 = y_2 und x_3 > y_3. Etc pp.
Deswegen mein Gedanke, das der Raum eigentlich nicht "einfach" nur ein Sammelsurium von Koordinatenangaben der einzelnen Objekte sei.
Nein, der Raum ist im Computerprogramm: Menge aller Floats X Menge aller Floats X Menge aller Floats, das sind ziemlich viele Punkte. In "echt" (in der Mathematik) ist der dreidimensionale Raum R x R x R, hat also sogar (ueberabzaehlbar) unendlich viele Punkte. Aber du merkst dir halt nur diejenigen Punkte, die interessant sind. Alle andere ist einfach unmoeglich.

3D-Graphik ist halt ein sehr weites, nicht sehr einfaches und sehr mathematiklastiges Feld. Ich wuerde dir wirklich zu einem der oben genannten Buecher raten, wenn du mehr zu den Innereien wissen moechtest.
Offizielles Python-Tutorial (Deutsche Version)

Urheberrecht, Datenschutz, Informationsfreiheit: Piratenpartei
Benutzeravatar
str1442
User
Beiträge: 520
Registriert: Samstag 31. Mai 2008, 21:13

Dienstag 23. September 2008, 06:43

Ich versuchs mal so:

Ich dachte, da der Raum als ein Objekt gebraucht wird, müsste man ihn *zuerst* mit einer Datenstruktur darstellen. zb so:

Code: Alles auswählen

import operator as op

a = {}
[op.setattr(a, (x, y, z), []) for x in xrange(40) for y in xrange(40) for z in xrange(40)]
Jetzt hat man die Koordinaten nochmal verschachtelt und ein 40^3 Feld erschaffen.

Man kann mit den (Integer) Koordinaten weiterhin rechnen, sofern man sie intelligent extrahiert, aber das ganze ist jetzt umgeben von einer "richtigen" Datenstruktur.

Solche Konstrukte sind bei *kleineren* Dingen auch sicherlich hilfreich, zumindest hilfreicher als mit den ganz großen Kanonen aufzufahren.

Deswegen finde ich Raum / Koordinaten als bloße Zahl etwas abstrakt. Ein Objekt mit Polygonen / Primitives ist mathmematisch beschrieben, in der Physics Engine wird mathematisch alles abgeregelt, der Raum aber ist einfach nur Zahl. Man müsste mit einer Klasse diese Zahlenberechnung zentrieren, um nicht ein Chaos zu verursachen, und nur wenn nötig die Koordinaten nutzen.

Ich hoffe ich habe hier niemanden zu sehr verwirrt.

Danke für die Erklärung des Begriffes Rendern, wußte ich auch noch nicht.
BlackJack

Dienstag 23. September 2008, 07:41

Du hast komische Vorstellung von "Raum". Was bedeutet "der Raum aber ist einfach nur Zahl"?

Der Raum wird nicht als Objekt gebraucht. Falls doch ist er durch die enthaltenen Objekte definiert. Ganz bestimmt braucht man nicht alle im Raum möglichen Koordinaten als Objekte. Wozu? Es reicht sich auf die zu beschränken, die auch verwendet werden.

Die Datenstruktur die Dir vielleicht vorschwebt braucht man für Volumengrafik, aber die wird nicht zum Modellieren von Spielen eingesetzt.

Dein Quelltextschnippsel ist übrigens sehr komisch. `setattr()` ist nicht in `operator` definiert, hier auch die falsche Wahl, denn ich denke du meintest `operator.setitem()`. Aber selbst das wäre hier unnötig, weil man auch einfach die Zuweisung ganz normal machen könnte. Aber am direktesten wäre wohl das hier gewesen:

Code: Alles auswählen

a = dict(((x, y, z), list())
         for x in xrange(40) for y in xrange(40) for z in xrange(40))
Oder speicherplatzsparender:

Code: Alles auswählen

from collections import defaultdict
a = defaultdict(list)
Und man sollte keine "list comprehension" für Funktionsaufrufe verwenden, bei denen man nur an den Seiteneffekten des Aufrufs interessiert ist.
Benutzeravatar
str1442
User
Beiträge: 520
Registriert: Samstag 31. Mai 2008, 21:13

Dienstag 23. September 2008, 18:52

Du hast komische Vorstellung von "Raum". Was bedeutet "der Raum aber ist einfach nur Zahl"?

Der Raum wird nicht als Objekt gebraucht. Falls doch ist er durch die enthaltenen Objekte definiert. Ganz bestimmt braucht man nicht alle im Raum möglichen Koordinaten als Objekte. Wozu? Es reicht sich auf die zu beschränken, die auch verwendet werden.
Mit "nur Zahl" meinte ich eher "nicht greifbar".

Genauer gesagt, ich wusste nie, wo ich mit der Planung anfangen sollte bei Dingen, die Raum und Raum Koordinaten erfordern. Ich konnte zwar Planungen über Objekte darlegen, aber immer, wenn ich dazu kam, das irgendwie in Interaktion in einem eigenem Raum zu setzen, kam ich gedanklich nicht weiter - Ich hätte ein Objekt anlegen können, das schlicht zb einen Tupel von Objekten entgegen nimmt und dann eine bestimmte Aktion ausführt. Das wär dann sowas ähnliches wie eine Physics Engine, zumindest sehr primitiv, da es ja um Interaktion geht. Aber bei der Darstellung hakte das wieder, denn: Eine Raumstruktur sollte ja möglichst günstig mit seiner Darstellung zusammenarbeiten. Das existierende Physics Engines mit zb OpenGL auf sehr einfache Art und Weise sowas von Haus aus mitbringen, wußte ich nicht. Genauer gesagt, wußte ich auch da nie, wo man anfangen sollte. Deswegen nochmals Danke für die Links zu OpenGL und PyODE. Genauso erschienen mir *nur* Zahlen als Koordinaten etwas abgehoben, denn: Damit kann man alles machen.

Eher dachte ich da an Sequenzen, wie also zb Listen. Und an Flächeninhalte: A = a*b, für einfache Rechtecke. Zahlen dienen, sofern es Ganzzahlen sind, nur zur Indizierung jedes Feldes von a*b. Solche Strukturen funktionieren für einfache Dinge ja auch recht gut.

Außerdem hätte ich nicht den Deut einer Vorstellung, wie man mit schlichter (:D) Mathematik komplexe Objekte irgendwie darstellen sollte. Insofern war mein Gedankengang: "Sofern das keine Primitives sind, müssen sie eine bestimmte Koordinate haben um dann als Ganzes behandelt zu werden. Man müsste um Objekte zu drehen, praktisch den Raum drehen *oder* den Koordinaten selbst eine gewisse *räumliche* Ausdehnung geben und den Rest als Eigenschaft des Objektes (zb self.rotation = 1,5 (Bogenmaß)) da die Objekte per se nicht drehbar sind." Dieser "gebe einer Koordinate, die zweifelsfrei ein *Integer* ist, eine räumliche Ausdehnung, und rechne für die Darstellung den Schmonz wieder in *3D Floats* um." Gedankengang war zb einer meiner Hauptpunkte. Und genauso wird es bei *einfachen* Dingen ja auch gemacht, zb bei diversen Tetris Varianten. Da ist ein Block ja auch per se ein Objekt, dessen räumliche Einnehmung durch ein zweidimensionales Array / Liste dargestellt werden kann, da es sich auch nur abrupt bewegen muss. Alle anderen Eigenschaften sind Sache des Objektes.

Das war falsch, denn scheinbar sind alle Objekte aus Polygonen aufgebaut oder eben Primitives. Sieht nur selten so aus, wenn man sich von zb komplexen 3D Anwendungen deren Objekte in einem ModelViewer anschaut, rein zur Informationen drüber.

Eigentlich fehlte mir also nur mathematisches Hintergrundwissen. Deswegen hat's auch ziemlich *klick* gemacht, als ich das in meinen letztem Post erwähnte PyODE / OpenGL Beispiel sah.

Ich hoffe, ich habe es jetzt etwas besser erläutern können.

@Quellcode:

Ja, ich meinte operator.setitem. Attr und Item schmeiß ich abundzu durcheinander. Das man dict() auch einfach einen Tupel aus 2er Tupeln übergeben kann, und daraus automatisch Key/Schlüssel Paare werden, wußte ich noch nicht - wieder was gelernt :)

Zur LC:

Ich hab das als LC geschrieben, da ich das für Foren als besser lesbar empfinde. In Produktiv Code würde ich sowas auch nicht benutzen, eben, da ich die Struktur wegen ihres Seiteneffektes quasi missbrauche. op.setitem kam dann nur mitrein, da ich unter Zeitdruck stand und das noch fertig bringen wollte.
Antworten