Project: 3D Craft -- Datastructures

One of the things I've discovered in writing and re-writing this library is that the way you structure the data has a huge effect on how easy or how hard it is to do things. I remember from college waaay back when this was told to me but somehow it didn't sink in. I would say that the most time spent so far on version 5 has been in crafting new data structures to work with.

Basic Types

The first seems pretty trivial but isn't, that is the p3dc_FLOAT type. It is typedef'd as a float which seems somewhat redundant however the idea is that by changing this you can change the library from single precision FP to double precision FP. Presumably you could even change it to fixed point but you would need compiler support in that case because I have not special cased the math functions (add, subtract, multiply, etc) In practice it isn't that simple to convert the library (I've done it as a test), but it is possible.

Next up in the basic types is structure that holds two co-ordinates. It is called a p3dc_PNT2 (point 2) and consists of two p3dc_FLOAT members named u and v. I chose u and v because this structure is most often associated with textures and textures are defined in terms of a uv space to keep from confusing them with the xy space of the screen. Here a page of things you can do with a p3dc_PNT2 type variable.

Two more types in the point family are p3dc_PNT3 and p3dc_PNT4. The former has members x, y, and z, and the latter adds the member w. The definitions are compatible so casting a point-4 to a point-3 and referring to y will change the member y in either definition. Point-3's represent points in 3-D space, whereas point-4's are used to represent points in a 4-D homogenous space. Because of this converting to and from is fairly straight forward. Here is a link to things you can do with p3dc_PNT3 and p3dc_PNT4 type variables.

The next structure is a transform and is named p3dc_XFRM. A transform has a 16 bit id tag associated with it and a four x four array of floats. Transforms are stored in column major order so that they are compatible with PHIGS transforms (I use the PHIGS code to test my results sometimes). The id member of this structure holds a monotonically increasing number that uniquely identifies a transform. In the code, when a vertex is transformed, the identifier of the transform used is stored in the vertex and later, when the vertex is transformed again, if the identifiers match then the previously computed result is used. This speeds things up when you have static vertices that are part of a scene and they are transformed every frame. There is, of course, a wide variety of things you can do with a p3dc_XFRM typed variable.

Perhaps the most versatile data type in the library are nodes, p3dc_NODE's to be exact. These are a very useful data structure and are used through out the library to hold pointers to allocated memory, pieces of models, etc. The members nxt, prv, and parent facilitate connecting nodes together as either singly, doubly, or heirarchically linked lists. When used hierarchically they are connected into a red/black tree (a form of binary tree) and they use the name member to identify nodes and the color member to help keep the tree balanced. The "payload" of the node consists of a type variable which is a defined enum of type p3dc_TYPE, and a void pointer that points to the payload itself (which can be another node of course). When I get into the discussion of memory management the versatility of nodes will become clear. In the mean time there are many things you can do with nodes.

The place where nodes are stored is called a p3dc_LIST. The list structure maintains house keeping values associated with a list of nodes, these include the first node on the list and the last node on the list. Further, if the list is being enumerated there is a current pointer that will keep track of the last node seen. Additionally, lists can be type exclusive which means they will reject having nodes added to them that don' t match a particular type. This is very useful for debugging purposes. You can read more about lists on the LIST page.

The last of the basic types is the p3dc_CLR definition. This type defines a color in P3DC and it is a union of both separate red, green, blue, and alpha values, and one "packed" 32 bit RGBA value. There are typedefs for big endian and little endian machines so the library should port easily to those architectures. I chose the packed format as it is simpler to move into and out of it, alternatives were a floating point format where each color component has a value between 0 and 1.0 but that can be too slow. The color APIs, such as they are, are described in their own document.

Compound Types

With these basic types, some compound types are created. Each of the compound types gets its own page for clarity.

The first compound type is the p3dc_VRTX type. This type defines what a vertex is in the library. Vertices are used as the lynch pins that hold together polygons, lines, and faces.