|
Building a 3D Portal Engine - Issue 04 - Data Structures For 3D Graphics by (22 January 1999) |
Return to The Archives |
Introduction
 |
|
Welcome back to the world famous series of articles on 3D graphics in general and Portal engines in particular by the Phantom :) This week: Some thoughts on 3D data structures, and why it is important to think about them at an early stage of the engine development. As some of you might know, I'm working on Focus, a light-weight 3D engine experiment that I merely use to try out little things like bilinear interpolation, shadows and fast software rendering in general. The engine and it's sources can be found at the following URL: http://www.flipcode.com/focus/ This little engine is of course not my first engine, and that's why I want to talk a little about 3D data structures. I've discovered that the main reason for dropping an engine and starting over from scratch is 'bad design'. Rewriting is no problem of course: Starting from scratch often improves code, since you can rewrite stuff that you painfully wrote in an earlier engine rather quickly, and usually with far less ugly and more efficient code. Earlier engines often had limitations that I could only get rid of by making heavy changes, or rewriting. Most of these limitations merely consisted of limitations in the data structures. Some examples: One of my first 3D engines (the E3Dengine) was coded completely in Pascal. Polygons where internally stored as four-sided convex polygons, since my world only consisted of squares, so that seemed fine at first. After some months of coding, I had an indoor rendering engine, with 6DOF (that was before the release of Quake, by the way) and I encountered my first major problem: Clipping against the Z=0 plane. This is neccessary for an indoor engine, since polygons often are partially behind you (as opposed to object rendering engines, where the entire object is usually in front of you). Vertices behind the camera do weird things when you apply perspective to them: Remember the perspective formulas from the previous article, where the rotated x and y coords where divided by their depth. The x and y coords are negated by this formula as soon as they pass z=0, and ON z=0, the formula causes a 'divide by zero'. The problem with clipping something off a polygon is that the polygon gets extra or less vertices. My structures could cope with 3 vertices, but not with 5... In this case, I could have increased the space in all the arrays to 5 vertices for each polygon, but that messed up my assembly routines, since they expected certain data to be at fixed positions in memory. Learned lessons: More recent engines had other limitations: Object records couldn't cope with a hierarchical system of objects, polygon records couldn't be easily expanded to hold bump data, and so on. So I guess you might learn something from my scars... A modern 3D engine needs quite some data, at different levels. Here's what I think you need (top-down): In the ideal case, all this should be as generic as possible, to avoid too much rewriting resulting in possible demotivation and leaving of the 3D scene of a talented new coder. :) That's a bad thing. OK, on with the details. On the top level (world structure) you should think about how you would organize a world, if you would ever build an engine that needs something like that. I mean, if you are a beginner, you will probably begin with an object renderer, just like I did. So it might be tempting to regard this object as a 'world', since there is no other data to process anyway. You might just declare an array of vertices, rotate them, and dump them to the screen. Fine. But think about this: If your array of vertices would have been stored in a larger structure, called an 'object', you would be tempted (probably) to try to get your engine to work with TWO or even more objects. Here are some things that you should take into account when you are figuring out a good world structure for you: Here's how I would implement the top level:
And here's what a sector looks like:
Most engines work like this: Even a BSP engine. This way, objects are linked directly to the world, as long as they are stored in the right sector every time they move. So the problem of object visibility is now directly linked to the world visibility problem. The next level you should think about (or the first level, if you're only doing an object engine) is the object data structure. Here's a sample structure:
There are some interesting things in this structure. First, I always put a pointer to a list of objects in this structure. There's a good reason for this: Many objects are linked in some way. If they are, their matrices are usually determined in an incremental way: An arm for example rotates relative to a torso, and thus it needs both it's own matrix, and the matrix of it's parent (the torso). The torso itself is probably rotated relative to the world: Therefore I also put a matrix in the Object class. OK, one more level down, the polygon level. Here's a basic polygon class:
And the vertex class:
Finally, the coordinate class:
This is interesting stuff, since even beginning coders will encounter this. Let's start with the polygon class: In this case I have used a VertexList class to hold my vertices. This makes it possible to have an arbitrary number of vertices in a polygon, but there's a drawback: Each list entry also has a 'next' pointer (assuming that it is a linked list). Thus, each vertex takes 4 more bytes than you would expect. If that's not a big problem, consider this: The alternative is an array. An array is stored sequentially, and is usually better for the cache. But an array is fixed size... In Focus, I finally choosed the array approach. Therefore, you MUST specify the number of vertices when instantiating the polygon. My polygon class looks like this:
So, there is a single pointer to a block of memory that holds pointers to vertices. Note that I still use extra memory: An integer for the number of vertices (since there's no NULL pointer at the end of a list anymore), and a pointer to the block of pointers. Another thing to note in the polygon class is the sector pointer. This is used for portal polygons: Since a portal links two sectors, this is the place where you should store this information. Finally, there is a plane structure. You could also make this a plane pointer, if you want to re-use the plane (for example, if you have a lot of polygons in the same plane). In case you don't know what to do with planes: I'll talk more about that in a later article. Recycling is also the reason for storing a coordinate pointer in the Vertex class. A cube has eight vertices, but the six sides all have 4 vertices, making a total of 24 vertices. In the cube case, it is obvious that the 3D position of only eight vertices are unique. The texture coordinates however need not be shared by two polygon vertices at the same position. Therefore, a vertex class should contain U/V information (the texture coordinates), and a pointer to a 3D position. This saves space and processing time, since a rotated vertex doesn't have to be rotated again. This brings me to the coordinate class: In the coordinate class there's maybe a bit more than you would expect. First, there's both an original vector and a rotated vector. You need to keep the original to ensure maximal accuracy: Even high precision floating point arithmetic will introduce numerical instability quickly when you rotate coordinates again and again. The other interesting thing is the 'processed' field: It indicates whether a vertex has been rotated for the current frame or not. This eliminates duplicate rotations. Here's a small tip for more advanced coders: Instead of a boolean you could also use an integer. If you store the current 'frame ID' in this integer (just increase it each frame) you don't have to reset the 'processed' flag for all rotated vertices each frame. This is particularly handy when it's not so easy to determine which vertices of a huge set where rotated at the end of the drawing process. OK, that's what I wanted to say about 3D data structures. My intention is to get you thinking about this at an early stage: The way you setup your data is probably the most important decision you make in the design of your engine. Actual tips in short are: Use pointers and lists, and as few arrays as possible. Arrays look simple at first, but they soon make your engine more complicated and force you to do ugly things that C++ was not designed for. I touched a lot of subjects that I want to elaborate on, like the plane equations, cache optimizing and so on, but I promise you I'll get back to you on those... |