[ILUG] Data structures, typedefs, arrays and OpenGL?

[John Gay]

I was given this address by : Frank Duignan <fduignan at esatclear.ie> as a good 
place to ask my questions about data structures and such.

I am attempting to create a program that can take an N-Dimensional object, 
rotate it, take a 3-D cross-section and display it stereoscopically using 
OpenGL. Simple, really ;-)

At the moment, I've got a matrix toolkit that allows me to create arbitrary 
sized 2D matrixes and can perform the maths needed to rotate the resulting 
matrix. This is NOT the problem.

The problem is, at the moment, I've only got the vertex co-ords for the 
various objects. To allow me to get cross-sections, I need a way of 
describing the rest of the structure recursively so that I can traverse the 
dimensions and perform the 'slicing' of the object to create a new N-1 D 
object. Another problem is, I don't know a lot about C or data structures in 
general. After many googles and reading of a similar, but dead project called 
Peek, I think I've got the start of what I need.

I've created a graphic representation of a 3-D cube at:
homepage.eircom.net/~johngay/program/3Dcube.jpg

The intercrossings were preventing me from figuring out a tree-type data 
structure, but after reading some more about Peek, I think I've found a way 
around it.

For each dimension object, I create two nodes, an Object and a Virtual node.

/* Virtual Identifies the linked list dataset at each dimension.
*       There will be many Virtuals for each object, but they
*       will all point to the same object. In theory at least ;) */
typedef struct virtualNode {
        /*      pointer to the next virtualNode in this
                        list of objects */
        struct virtualNode *next;
        /*      pointer to the actual object represented
                        by this node */
        struct objectNode *down;
        } *Virtual;

/*      Object identifies the actual object and provides
*               a pointer down to the next lower dimension. */
typedef struct objectNode {
        int dim; /* Dimension for this object */
        /* pointer to the virtualNode for the next
                level down */
        struct virtualNode *down;
        } *Object;


Starting from the top-down, referencing the jpg above:
Virtual Cube->next pointed to NULL and a ->down pointing to Object Cube.

Object Cube->dim = 3 and ->down points to Virtual Face0 node.

Virtual Face0->next points to Virtual Face1 etc until Virtual Face5->next 
points to NULL
Virtual Face0->down points to Object Face0, as do the rest.

Object Face0->dim = 2 and ->down points to Virtual Line0 for this face.
Object Face1->down points to Virtual Line0 for this face, etc

For Face0, Virtual Line0->next points to Virtual Line1 for this face etc 
until Virtual Line 3->next points to NULL.
The same pattern is repeated for the other faces, I.E. Each face points to a 
linked-list of Line0 through Line3 unique to it's face, thus we have 6 * 4 = 
24 Virtual Lines.
The tricky part is, there are only 12 Object Lines. The Virtual Line0->down 
will point to the Object Line that it relates to. This is where I can get the 
cross-connections in the data structure, while still having simple 
linked-lists for each dimensional level.

The same pattern is repeated for the lines to the vertices, however, the 
Object Vertice0->down will point to the array countaining the co-ordinate 
info for that vertex.

In the end, this gives me as data structure that is basically a pointer to a 
set of pointers to a set of pointer etc until the vertices point to the 
arrays.

The typedef's I've given above seem to work and I've been able to create new 
nodes. Now I'm trying to figure out how I can actually create the nodes and 
assign them to point to the right places using some type of recursive 
function, or set of functions so I can create the data structure of objects 
of arbitrary complexity and arbitrary dimensions. The first objects I've 
created are platonic solids, which have the advantage that all the faces and 
surfaces are identical, but I hope to allow for non-platonic solids as well.

The other reason I need the recursive data structure is the slice routine 
I've worked out has to start from the bottom and work up each dimension 
building up a new N-1 dimensional object.

I hope that someone can help me figure out how to create the functions I 
need, or has a better way of defining the data I'm looking for.

Cheers,

	John Gay