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

[John Gay]

I've been contemplating a project for quite a few years now and have been 
trying to teach myself C so that I can realise it. I've even enrolled in a 
programming course at DIT. I've also bought several books on C programming 
and recently got Interactive Computer Graphics for OpenGL info.

Unfortunately, my lack of proper data structure understanding has limited my 
ability to accomplish what I want. I've made some progress using a matrix 
tookit which I've recently converted to GPL with the original authors 
permission, of course. The fruits of this endevour can be found at:

homepage.eircom.net/~johngay

I've also been able to get even more limited use by incorporating OpenGL to 
get a graphical output.

I've been reading and re-reading the data structures chapters of C How To 
Program in an attempt to get the more general purpose data structures I need 
to achive the original goals of my project. I've been trying to incorporate 
this with the data structure info in the Computer Graphics book, but I keep 
running into the limitations of my lack of understanding C data structures.

I made a fresh start today but I'm not sure if I'm starting on the right foot 
or not. I was hoping that I could get some help in getting my ideas straight 
and my data structures right from the great programming talent that created 
this list in the first place.

Lets get the basis of my requirements laid out first:

I'm trying to create data structures that can contain a full description of 
an N-Dimensional object. The data structures need to be recursive and dynamic 
so that the objects can be combined into higher dimensional objects. To 
illustrate this, I'll start from the bottom-up.

N = an unknown number of dimensions.

Where N = 0, I.E. 0-Dimensional objects, we have the vertices, defined as an 
array of GLfloats. The size of the array depends, of course, on how many 
dimensions the final object is.

Where N = 1 we have Lines. A Line has two ends and points to the two vertices 
that define the Line.

Where N = 2 we have 2-D surfaces. A 2-D surface has to point to a random 
number of lines that outline the surface.  It would be simple if the lines 
arranged the vertices in a counter-clockwise order, but this is not possible 
unless we define each line twice to allow for either direction and that would 
result in not only excess data, but twice the processing as well.

Where N = 3 we have 3-D surfaces. A 3-D surface has to point to a random 
number of 2-D surfaces that outline the 3-D surface. You can see that as we 
go high in dimensions, this description becomes recursive.

As a (possibly false) start, using my references I tried to get an idea of 
how the definitions would go.

typedef GLfloat Vertice4[4];

struct line {
	Veritce4 *left;
	Vertice4 *right;
	};

typedef struct line Line;
typedef Line *LinePtr;

So, I typedef Vertice4 as an array of 4 GLfloats,
I create a structure, line that can point to two Vertice4's,
I typedef Line as a struct line and LinePtr as a pointer to a line struct.

This is the limit of my abilities, and is probably completely wrong. It seems 
to be heading in the wrong direction anyway.

I thought of trying to create a tree-type data structure but ran into more 
problems with that. I've created a graphical representaion of a 3-D cube 
showing how the data should be represented logically. The image is available 
on my web site. I won't post it to this list, because attachments are frowned 
upon.

Basically, a 3-D cube points to 6 2-D faces.
Each face points to 4 Lines.
Each Line points to two vertices.
Each vertice contains the GLfloat data.

The reason for these strict requirements is I want to be able to take an 
N-Dimensional object and slice it at the N = 0 plane. This requires being 
able to start at the Lines, find each line that crosses the N = 0 plane and 
convert this to a new N-1 vertice.
Then I go to the 2-D surfaces to find the new n-1 lines.
Than I can use the 3-D surfaces to find the new 2-D surfaces.
Again, this becomes recursive.

I've created a function that can take  two N Dimensional vertices that define 
a line and determine if it crosses the N = 0 plane and return the N-1 
dimensional vertice at the point of crossing. I can also manually find the 
rest of the information for the new Lines, 2-D surfaces, 3-D surfaces ect, 
but programming the function to accomplish this requires knowing exactly how 
the data is represented, so I need to define the data structures first.

I realise this is a complex task for someone who is just starting to fingure 
out how to program, but this project has been tossing around in my head for 
more than two decades now and I really need to get it out! Don't be 
intimidated by the Nth Dimension! The maths are the same if your are working 
with a 3-D object or a 23-D object! Everything from the 3rd Dimension up 
should be recersive anyway.

So, any ideas or help with defining this data structure would be greatly 
appreciated. I know there are many good programmers on this list, and I am 
writing this on my Linux machine using kdevelop. My biggest problem is trying 
to figure out how to keep from limiting myself to a fixed number of 
dimensions or even a fixed object!

Cheers,

	John Gay