Was ist Paging ?

Paging ist ein Verfahren, mit dessen Hilfe das Gelände in einzelne Bereiche zerlegt wird. Die Objekte im Gelände werden entsprechend ihrer Position den Pages zugeordnet. Während der Laufzeit werden dann nur noch die Objekte in Betracht gezogen, die in der aktuellen Page liegen, wodurch der Aufwand reduziert werden kann.

Im wesentlich kommt das Paging bei zwei Problemkreisen in Betracht, und zwar einmal, wenn es um die Sichtbarkeit geht, zum anderen bei Kollisionserkennungen. Gelegentlich muss der Sichtbarkeitsbereich eingeschränkt werden, um nicht zu viele Objekte zeichnen zu müssen. Die Größe des Bereichs hängt vor allem von der Nebeleinstellung ab. Bei Kollisionen ist es noch wichtiger, denn es sollen nur die Objekte einer Kollisionserkennung unterzogen werden, die aufgrund ihrer Lage überhaupt in Frage kommen, denn die Kollisionsberechnungen sind äußerst aufwendig.

Entscheidend ist, dass bereits im Vorfeld die Verteilung auf die Pages stattfindet, z.B. in dem die Objekt-Indices in einem geeigneten Array gespeichert werden. Da nicht bekannt ist, wieviel Objekte in den einzelnen Pages untergebracht werden, kann ein Zweipass-Verfahren angewandt werden. Im ersten Pass wird die Anzahl festgestellt, damit Speicher allokiert werden kann. Im zweiten Pass werden die Indices in die Pages eingelesen.

Paging lohnt sich nur dann, wenn sehr viele Objekte (mehrere tausend) vorhanden sind, und wenn die Zuordnung zu den Bereichen ein bestimmtes Maß an Aufwand erfordert. Eine einfache Abstandsbestimmung kann wohl besser zur Laufzeit mit der gesamten Objektmenge erfolgen. Wenn aber mit Hilfe einer aufwändigen Intersektionsroutine ein Bounding-Check durchgeführt werden soll, kann sich die Objektmenge sehr wohl auswirken; dann ist das Paging zumindest in Erwägung zu ziehen.

Wie aufteilen?

Zwei Faktoren sind zu berücksichtigen. Da ist erstens die Reichweite, z.B. die Sichtbarkeitsweite oder die Kollisionsweite. Zweitens haben wir die Pagegröße, die zwar unabhängig von der Reichweite ist, aber zweckmäßigerweise damit in Einklang gebracht wird.

Die Pages oben sind groß. Die Reichweite (rot) muss immer zu den beiden Pagegrenzen addiert werden, da ja nicht bekannt ist, wo in der Page die Position gerade ist. Bei diesen großen Pages sind drei davon abzufragen. Bei kleiner und mehr Pages (unten) müssen sogar insgesamt 7 Pages abgefragt werden, obwohl der Gesamtbereich kleiner ist, wie man sieht (blaue Klammern). Ein weniger an Aufwand wie bei den größeren Pages wird durch eine größere Zahl von Objekten erkauft. Die Lösung kann nur ein Kompromiss sein. Ein guter Kompromiss ist es, die Pages so groß wie die Reichweite zu machen, dann haben wir die minimale Objektzahl bei dem Minimum an Pages, nämlich 3.

Überlappende Pages

Leider lassen sich nur punktförmige Objekte eindeutig den Pages zuordnen. Flächige Objekte liegen oft auf den Grenzen und berühren zwei oder mehr Pages. Wenn nun einfach die benachbarten Pages bei der Abfrage hinzugenommen werden, tritt ein Objekt u.U. mehrfach in Erscheinung, was unbedingt vermieden werden sollte, denn das Objekt würde dann auch mehrfach gezeichnet oder in die Kollisionserkennung einbezogen. Das Vermeiden solcher Mehrdeutigkeiten kann nur zur Laufzeit erfolgen, was wiederum die Effektivität herabsetzt. Zwar ist die Zuordnung zu den Pages eindeutig, aber nicht die Auswertung.

Ein anderer Weg sind die überlappenden Pages:

Hierbei ist die Auswertung eindeutig, denn jeder Terrainbereich hat eine exakt zugeordnete Menge von Objekten. Zwar werden viele Objekte in mehreren Pages aufgeführt, aber dadurch erhöht sich nur der Speicherbedarf. Es ist zu erkennen, dass die Reichweite außerhalb des eigentlichen Page-Bereiches liegt, was zu konstanten Bedinungen über das gesamte Terrain führt.