3D Coding TAT - The "Planet" Method
For want of a better description I will use the title "Planet Method" to describe what is possibly the most obvious way to define a 3d environment. When first learning to program 3d stuff every programmer starts off by drawing a polygon and then building an object from a number of polygons. Now he/she wants to take the next step and build a 3d world with more than one thing in it. The inky black background of space is normally chosen and suddenly lots of space ships are zooming about. And maybe a few circles are drawn here and there as planets. So now we have built a game universe from these movable objects and each of them are made up from polygons. We have placed 3d object models randomly in the world.
This is what I mean by the "Planet method".
If we want to draw a more Earth bound scene then instead of space ships we could draw houses or trees. All we need is the world coordinates of each object together with a 3d shape and we could quickly make a dense forest by drawing the same polygon tree again and again in different places.
This method does have advantages over a huge-list-of-polygons approach where each and every polygon is just defined in a very, very, very big list. For a start the same object can be reused any number of times (as in the above example of a forest). And secondly it is a form of hierarchy which allows rapid rejection or acception of objects from our view-point. If the world position of an object is not within our view-point's range and direction then we don't need to bother checking all the object's polygons. On the other hand if an object's world position is visible from our view-point then we can draw each polygon. So in affect we can reject many polygons and vertices simply by processing the object's world position. You can think of the world position as being the parent and the vertices and polygons as the children.
It is possible to take this hierarchical method a stage further and describe sub-objects as children from a main object. For example a huge mile long space-ship could be built from say, 10 large objects (the engines, the wings, the hull, the cockpit). Now if the you were able to fly very close upto an engine then most of the rest of the ship will be clipped off the screen. We could now draw the sub-objects (the fine detail polygons/lines) on the engine object. And the player says, "Wow, look at all the details on these ships, think about all those polygons this engine is drawing...." and the programmer sits back and grins widely thinking "I've only drawn a few sub-objects... this player is a right clown." We have quickly rejected large groups of polygons simply by rejecting large objects (e.g. the ship's wing, tail and so on.) Only when an object is visible do we consider drawing its finer detail on its surfaces.
This 'planet' technique is sometimes used for drawing the scenary (trees, houses etc.) It was used years ago on slow computers, but is often used these days for monsters and movable objects within the 3d world.
The problem with this free placement of objects in the 3d universe is that the objects often need to be sorted in decreasing order of relative distance from our view-point so that the most distant objects can be drawn before closer ones.
1: More of the same..
With this placement of the same object again and again (like trees) it is possible to do some cheats. Instead of rotating, projecting and drawing each 3d tree from its 3d model for every single tree in the forest why try one of these tricks:
1. Rotate and project the 3d tree once then simply scale it up or down for trees at different distances. (This reduces the rotation, hidden surface and projection calculations to a minimum amount.)
2. Store pre-rotated and pre-projected polygon lists for boring objects like trees, stones or asteroids.
3. Scan the tree into an off-screen bitmap buffer, then scale this bitmap as a sprite onto the screen.
4. Simply use a 2d bitmap sprite and scale it onto the screen. (This was used in DOOM, Wolfenstein and System-Shock for objects and creatures.)
Method 1: This allows recolouring (or re-texturing) of each object, which is important to make trees look similar but NOT indentical to each other. The good thing about this technique is that a tree 3d object can be drawn correctly from any angle once and then repeatedly drawn onto the view screen. But ALL the trees face in the same direction.
Method 2: This is good for non-descript items which just help to flesh out the 3d environment but are not really important. In the case of an asteroid field or a forest a reasonable amount of speed can be obtained. The downside is that memory is eaten up unless you only have a few pre-calculated polygon lists. For spherical shaped object or highly symmetric ones this is reasonable.
Method 3: The bitmap buffer must be cleared, built up and finally scaled on the screen which takes time to do, also the bitmap can not be recoloured unless a pixel-by-pixel method is used which is far slower than using a polygon list and changing the colour of each polygon.
Method 4: This is a much faster way than building up the bitmap in realtime, but it suffers from having to store all the pre-drawn images in memory and again a pixel-by-pixel method must be used to recolour or shade images.
2: Grid based Planets
Rather than a vast list of every 'planet' object in the world, we can employ a simple, but effective technique to localise these moveable 3d models. The problem of maintaining a single list of everything it that is can take a large amount of processing time, most of which is unnecessary. What we really want is only handle those items within a certain range from our view-point. This means that things on the opposite side of the world are ignored so that much closer ones can be given more attention. There are various ways to do this from processing a sorted list of objects to one of the simplest, the grid based method which follows...
Using a grid based map (either a 2d or 3d array) it is very easy to start at a certain place and immediately find the surrounding neighbours in any direction. To visit all the neighbours at a range of 3 cells we can either scan a 7x7 square with our starting point at the middle or we can scan a circluar area with a radius of 4. The scanning can be done extremely quickly by using a list of displacements from a starting point. This doesn't have to be done in real time so can be pre-calculated before hand. A circluar area with a radius of 4 could look something like this:
---Å---Å---Å---Å---Å---Å---Å---Å---Å---Å---
³ ³ ³ ³ 3 ³ 4 ³ 5 ³ ³ ³ ³
---Å---Å---Å---Å---Å---Å---Å---Å---Å---Å---
³ ³ ³ 2 ³ 18³ 19³ 20³ 6 ³ ³ ³
---Å---Å---Å---Å---Å---Å---Å---Å---Å---Å---
³ ³ 1 ³ 17³ 31³ 32³ 33³ 21³ 7 ³ ³
---Å---Å---Å---Å---Å---Å---Å---Å---Å---Å---
³ ³ 0 ³ 16³ 30³ X ³ 34³ 22³ 8 ³ ³
---Å---Å---Å---Å---Å---Å---Å---Å---Å---Å---
³ ³ 15³ 27³ 37³ 36³ 35³ 23³ 9 ³ ³
---Å---Å---Å---Å---Å---Å---Å---Å---Å---Å---
³ ³ ³ 14³ 26³ 25³ 24³ 10³ ³ ³
---Å---Å---Å---Å---Å---Å---Å---Å---Å---Å---
³ ³ ³ ³ 13³ 12³ 11³ ³ ³ ³
---Å---Å---Å---Å---Å---Å---Å---Å---Å---Å---
The 'X' marks the origin (our start point) and the numbers represent the order in which these neighbouring cells could be visiting for rendering or processing NMEs etc. Please note how these cells are numbered, this is the order in which they should appear in our "visiting" list. Basically the furthest cells are defined first followed by the next closest and finally the adjacent cells. This way it is very easy to draw the more distant objects first and then to overdraw them with closer ones.
If you want to work outwards from the origin then number these cells in the opposite order, starting at the surrounding cells, then their surrounding cells and finally the outer ones. This outwards method does have a few advantages that the inwards one doesn't. 1. It is possible to clip distant objects behind closer ones using an "S-BUFFER" (span buffer) technique (only drawing in the background gaps left by the closer objects). 2. We can choose where we stop in the list more easily. This can be useful for moving the horizon cut-off point for low-detail on slower PCs.
Another method could be to define the radiating cells as a number of lists each one representing a certain radius. Because each list defines 360 degrees you could reject 50% or more of the cells based on viewing angle (this won't work if you can change your X-axis angle by looking up/down).
It is also possible that you wish to scan outwards in straight lines rather than an expanding spiral. This would allow you to direct the map scanning and so ignoring any map cells behind your view point. I believe this is a basic form of "Ray Casting", traceing lines or 'rays' across a map until either an obstruction is hit or the horizon cut-off distance has been passed.
"Okay", you might say, "but where are the planets then?" Well, we can define a link from each map cell to a list of objects ("planets") which are positioned in the cell. This means given just the cell we can use its link and find what objects it contains. This is not only useful for rendering the environment and any furniture it contains but it can help speed up collision detection and movement algorithms. If you use a linked-list approach to describe the items within a map cell then it means you can nuke an entire cell simply by zapping the link from the cell, so by breaking the chain of linked-list items.
But if maps are big and/or are 3-dimensional then this can begin to take up vast amounts of memory. For example, imagine a 50x50x50 grid which uses a double-word for each contents link. This would take up 500,000 bytes and that's ONLY the links, add on top of this the terrain/texture data for each cell and it soon become apparent the memory cost. In the most optimistic scheme the texture details could take 6 bytes each (1 byte for each face of a cell cube) that brings to total to 1,250,000 (over 1 meg) and remember this is just a 50x50x50 map which is small compared to the size of many recent games.
3: 3d-Linked Lists & Dynamic Neighbours
You might have worked out that most of the previous 50x50x50 map array is probably going to waste because a great deal of all those 125,000 cells are only being used as walls, floors or ceilings. The problem is that a cell can have a variable number of data components which need to be described (the textures, surface type, lighting, damage, contents list for the planted objects and so on). The very minimum amount of data that a map cell would require could be as low as a single byte and the maximum could run into 100's of bytes. We can't allow dynamic sizes of cells within the grid because it would not then be an array and we would have no quick way to navigate a path from cell-to-cell which is THE main reason why we are using an array.
One solution could be to create neighbour links of either a 2d linked-list or a 3d linked-list. This would certainly help navigation through the array but has two large problems.
1. Linked-lists are SERIAL data structures, we can NOT randomly access the N'th item without following N-1 links.
2. Memory requirements would sky-rocket. For example the 50x50x50 array would require 3,000,000 bytes JUST for the links (3d = 6 faces = 6 links * 4 bytes * 50x50x50), which is over 2.8 Megs!!
This neighbour-link method is similar to the "INLET" method described elsewhere in this document (see that for more info).
4: Tokenized Grids & Shared Items
But as we already know a lot of the 50x50x50 array is going to waste just by being used for walls or the padding between unused areas and rooms. There is a good, more memory friendly solution to the navigation and dynamic cell size problem that doesn't need the neighbour links. It's SO simple it hurts.
We can define the map as being a 50x50x50 array of single element links and use just one link to point to the variable sized contents/cell data list. The navigation is once again a matter of stepping through the array using a constant step size. And so the pre-calculated "visting" spiral list technique can be applied to the map again. The map array has returned to being a random-access data structure and so the Nth element is simply N*step bytes away (in this case 4 bytes per cell).
The dynamic storage can be quickly used, modified and most useful of all, can be RECYCLED (within reason). Because our 50x50x50 map array is built from links (or should that be pointers?) and the dynamic cell data structure can be anywhere in memory, we can re-use the same cell data just by using the cell's address more than once.
In the below greatly simplified diagram we have a 9x7 map array. Within the array we have a single link to a description elsewhere in memory which lists it's "contents" (the inhabitants, lighting, environmental structures and possibly background sound effects) which are present in a cell.
Array of Pointers (single Links) Cell Description
---Å---Å---Å---Å---Å---Å---Å---Å---Å---Å--- ---- -----------
³ 0 ³ 0 ³ 0 ³ 0 ³ 0 ³ 0 ³ 0 ³ 0 ³ 0 ³ 0 Solid Wall, rock
---Å---Å---Å---Å---Å---Å---Å---Å---Å---Å--- 1 floor
³ 0 ³ 2 ³ 2 ³ 2 ³ 2 ³ 0 ³ 0 ³ 0 ³ 0 ³ 2 ledge
---Å---Å---Å---Å---Å---Å---Å---Å---Å---Å--- 3 lift
³ 0 ³ 2 ³ 4 ³ 4 ³ 2 ³ 6 ³ 0 ³ 0 ³ 0 ³ 4 lava
---Å---Å---Å---Å---Å---Å---Å---Å---Å---Å--- 5 floor + rock
³ 0 ³ 0 ³ 4 ³ 3 ³ 2 ³ 0 ³ 0 ³ 0 ³ 0 ³ 6 Wall + switch
---Å---Å---Å---Å---Å---Å---Å---Å---Å---Å---
³ 0 ³ 0 ³ 4 ³ 1 ³ 1 ³ 1 ³ 0 ³ 0 ³ 0 ³
---Å---Å---Å---Å---Å---Å---Å---Å---Å---Å---
³ 0 ³ 0 ³ 4 ³ 1 ³ 5 ³ 1 ³ 0 ³ 0 ³ 0 ³
---Å---Å---Å---Å---Å---Å---Å---Å---Å---Å---
³ 0 ³ 0 ³ 0 ³ 0 ³ 0 ³ 0 ³ 0 ³ 0 ³ 0 ³
---Å---Å---Å---Å---Å---Å---Å---Å---Å---Å---
Doing it this way means a very large area can be filled with the same cell description link over and over again without the need to have multiple copies of indentical floor, wall, ceiling textures and other more interesting stuff. Objects and creatures could be defined within the cell description as well.
5: Movable Items & Monsters
There is a problem with the recycling method and it is due to the fact that one cell's contents can be shared by any number of other cells which use the same token or link address. What happens when you want to move an item? If you delete it from the description then it disappears from every other occurance of it on the map as well. Sometimes this is desirable (changing a lake of water to lava, a dark square to a light one or a large step into a small, climbable one) but on occasions it is not. If we placed one monster in the floor (1) description above then we would end up with five monsters instead of just one. It seems that the advantage of tokenizing has prevented us from placing individual items on the map. One solution could be to define two links for every map square, one for the environmental details (wall, floors, lighting etc.) and one for the creature in the map cell. But this would double the amount of storage needed for the map and what happens when we want two or three monsters on the same cell?
One answer could be to define a link in the cell description and use that to point to the first monster and give the monster a link to the second monster and so on...
Ú----------------¿
Ú------------³Cell Description³
---Å---Å-Á-Å---Å ³ ³
³ 0 ³ 5 ³ 2 ³ ³ Roof: Rock ³
---Å---Å---Å---Å ³ Floor: water ³
³ Light: 40% ³
Ã----------------´ Ú-----------¿
³ Inhabitant ³-----³ Monster 1 ³
À----------------- À-----Â------
³
³
Ú-----------¿
³ Monster 2 ³
À------------
This way we could add monsters to a cell description just by adding it to the end (or inserting at the beginning) of the linked-list.
But the ABOVE METHOD IS STILL WRONG !!!!!!!
It may allow an unlimited number of monsters to share the same map cell but it suffers from the same problem as before, namely when you modify one cell description ALL the other instances of it are modified too. You could fudge it and whenever you use the "inhabitant" link for the list of monsters you check to see if the true map location of cell (the array square address) matches the monster's map address and use it, otherwise the cell has been recycled and used elsewhere. This would mean keeping the array address of the square which the monster is standing on together with the monster's data structure and an extra compare when rendering a cell, but it would keep the map array down to a single link per cell size.
0 1 2 3 4 5 map location
---Å---Å---Å---Å---Å---Å---Å-
³ A ³ B ³ C ³ C ³ B ³ E ³ map array tokens/links
---Å---Å---Å---Å---Å---Å---Å-
³ ³
v v item location
Ú----<----<--Á---- Ú-----------¿-------¿
Ú-------Á--------¿ Ú--->---->³ Monster 1 ³ 2 ³
³Cell Description³ ³ À-----Â--------------
³ ³ ³ Ú-----------¿-------¿
³ Roof: Sky ³ ³ ³ Monster 1 ³ 3 ³
³ Floor: Gravel ³ ³ À-----Â--------------
³ Light: 80% ³ ³ Ú-----------¿-------¿
Ã----------------´ ³ ³ Gold Key ³ 2 ³
³ Inhabitant ³----->------ À--------------------
À-----------------
In the above diagram we have two cells sharing exactly the same cell description. This means that BOTH share the same "Inhabitant" link and list as well. So the two monsters and the gold key seem to appear twice on the map, this is where the 'location' field comes into play in the item's data structure. We compare each one against the actual address on map array and only allow those which have the correct location. In the above example the cell description is used by map cells 2 and 3 where cell 2 has Monster 1 and the Gold key and cell 3 has Monster 2 in it. We can get to the cell description from two different paths and so it is possible for the "Inhabitant" link to fork off into two path also. The location field is used to determine which.
6: Background Tails
There is another way to solve this junction problem where two map array links can lead to the same destination. If we have a spare bit in our map token/link then we can use it to indicate a vacant or occupied cell and then use just the item links to chain co-habiting items/creatures together. Now at the end of this inhabitance linked-list chain we point back to the cell description (the background). Doing it this way means we don't have to worry about splitting from the cell description for the different map locations which share the same cell description, we just point the tail of our item/creature list to the same end.
0 1 2 3 4 5 map location
---Å---Å---Å---Å---Å---Å---Å-
³ A ³ B ³ C ³ C ³ B ³ C ³ map array tokens/links
---Å---Å---Å---Å---Å---Å---Å-
³ ³ À------>-------¿
Ú--------<------ À----->------¿ ³
Ú-----Á-----¿ Ú-----Á-----¿ ³
³ Monster 1 ³ ³ Monster 1 ³ v
À------------ À------------ ³
Ú-----Á-----¿ ³ ³
³ Gold Key ³ ³ ³
À------------ ³ ³
À----->------>----Â-------<------ ³
Ã------------<-----------
Ú-------Á--------¿
³Cell Description³
³ ³
³ Roof: Sky ³
³ Floor: Gravel ³
³ Light: 80% ³
À-----------------
In the above diagram we have the same items but this time we use the tail of the inhabitants to point to the same cell description ending. You may have noticed that map cell location 5 using the same 'C' cell description but this time no items or creatures are in the chain so it points directly to the cell description. To simplify the cell description structure (because there can be hundreds or thousands of them) I used a single flag bit to indicate an inhabitance link OR a pure cell description link. This means we can quickly check to see if a cell is empty or not. It does create an extra test in the rendering algorithm but this is offset by the saving made by not having to compare the 'location' fields.
Depending on how your renderer works this background-last order might be good or bad. If you draw from front-to-back then this is good because the background is the last item in the chain. If you draw in the opposite order then you may need to place these items on a stack and then pop them to obtain the correct background-first order.
7: Coarse Area Nets
This is another useful (and very similar) method for localizing 'planet' objects on a large and/or highly memory intensive map. Going back to the 50x50x50 array with its 125,000 cells it is obvious that the maximum number of items (creatures, objects) we would want to place within it will be far lower than 125,000. In the case of creatures only 1/100th or less could be our limit. It seems wasteful to have such a high resolution array for such a relatively few number of items, so why not define a 25x25x25 array or just a 5x5x5 array instead?
The basic idea is to place a far lower resolution array over the memory-guzzling one and use for example 1 of these coarse net sections to represent 2x2 or 4x4 of the underlying map cells. Each net section is very similar to the map cell except the spacing between each corner is far bigger and it only describes movable or static items such as creatures or collectable objects and the like, NOT scenary graphics.
There is no real problem from only using a 2d CAN ("Coarse Area Net") array to partition a 3d map array apart from the extra work involved checking that items are on the same layer. E.g. if your 3d map used (X,Y,Z) coordinates but your 2d CAN used (X,Z) then you would need to check the (Y) coordinate of the occupied net section to make sure items are not above or below your map position.
This grid based method can also be applied to non-grid based maps where the environmental structures do not stick to the rigid cell boundaries of a map. Where the vertices of walls, floors, ceilings and so on can be placed on at any arbitary coordinate value these vertices can too be chopped up into groups using the "Coarse Area Net" method. This could be one possible way to prevent having to rotate the entire level's vertices, we only need to rotate the few that are contained with the nearest local net sections.
8: Occupied Sub-Nets
The old tree syndrome seems to have infecting every 3d programming idea including this one. The problem of using a low resolution grid is that it divides space very poorly with any number of items forced to share the same cell. But using a high resolution grid means wasting memory. Using a 16-bit number for the coordinates means 65536 different values can be defined. Using this for a 2d grid would mean 65536*65536 grid (4,294,967,296 cells!!). As I have mentioned before only a small fraction of all these cells will actually be used for items.
The idea of this method is take the best of both low and high resolution grids without incurring the huge memory waste. First use a very coarse grid. This will be the root grid. Find where in this grid items are and then create a sub-grid for each occupied cell. This means that only the coarse cells which are used will have a finer high resolution sub grid and all those empty root cells won't have any siblings, so saving a large amount of memory.