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

[David Neary]

John Gay wrote:

[snip 50 lines or so]

> Lets get the basis of my requirements laid out first:

That's some definition of 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.

OK - it's a fairly complicated idea but I see where you're going.

> 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.

You can have a k-dimensional object in N dimensional space where
k<N (say, a plane in 3-D space, or a line in 4-D space) - so it
depends more on how many dimensions the space is. But that's
neither here nor there :)

For something of variable size, an array is a bad idea (imho). OK
variable length arrays are defined in the newest C standard, but
they're not in common use. The normal way to do this would be to
either dynamically allocate the space, or use a list.

> 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.

A 2d plane is defined by 3 p[oints, as long as they're not
colinear. But if you also want shapes, then you're into more
complicated stuff. Scary, in fact :) Easier if it's a list of
vertices where the last vertex points at the first - in that way,
you're extending the idea of a line, and keeping wor down for
yourself. For example, the unit square on the plane would be just
(0,0)->(1,0)->(1,1)->(0,1)->(0,0) (or just ->NULL to show you're
finished).

Ah. Just realised that when you're talking about lines, you're
really talking about line segments. Right.

> 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.

Extending the "list of vertices" we can go into N dimensions -
all we need to do is have a path around the object which visits
every vertex, and crosses every edge. (OK, when I say "all we
need to do", I'm simplifying). I have trouble seeing how your
scheme can describe any 3-d object. How would you d4escribe the
unit cube in 3d space, for example?

> 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;

I would advise against this one strongly - the pointer
indirection is useful in the declaration of a variable. There's
no problem with declaring something as 
Line *myline;
instead of 
LinePtr myline;
in fact, doing so saves typing, and is clearer (to my mind). No
need to pollute the namespace.

> 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.

How about something along the lines of the following - 

struct vertex {
int dim;
GLFloat *coord;
};

typedef struct vertex Vertex; /* If you really wanted to */

which would have an init function something like this...

Vertex *vertex_new(int dim, ...)
{
  Vertex *vertex;
  int i;
  va_list varargs;

  va_start(varargs, dim);

  vertex = malloc(sizeof (Vertex));
  vertex->dim = dim;
  vertex->coords = malloc(dim*sizeof(GLFloat)

  for( i=0; i<dim; i++)
  {
    vertex->coords[i] = va_arg(varags, GLFloat);
  }

  return vertex;
}

which you'd use pretty much as you'd expect - 

Vertex *v;
v = vertex_new(3, 1.0, 1.0, 1.0); /* For point (1,1,1) in 3d
                                   * space */

and moves nicely up to the next dimension, as you say - 

struct line {
  Vertex *vertices; /* Array of vertices */
};

and surfaces
struct surface {
  Vertex *vertices; /* Bounding vertices */
};

But I see that you want to go the iterative route - a line
defined by 2 points, a shape defined by a number of lines, a
space defined by a number of surfaces, and so on... I think
something like this might work. I haven't thought about it at
all, though. And to be this generic you have to be horribly hard
to program :)

struct object {
  int dim; /* Current dimension of object - 1 for line, 2 for
  surface, etc */
  union {
    struct object *subobjects; /* list of n-1 dim objects for n>=1 */
    Vertex *vertices; /* vertices for n=0 */
  } data;
};

This is a horrible thing to manage though. I can't see how you'd
allocate space for them, never mind manipulate them. Being honest
I didn't really follow your requirements, and this has been kind
of stream-of-consciousness stuff, but worse than Joyce. I hope
there's something useful in it, at least.

Cheers,
Dave.

-- 
       David Neary,
    Marseille, France
  E-Mail: bolsh at gimp.org