From: John Gay (johngay at domain eircom.net)
Date: Mon 03 Jun 2002 - 01:54:05 IST
After more thoughts and re-visiting the only site I've found that comes close
to doing what I want to do, I think I've found a possibility, but it requires
two levels of nodes for each dimension :-(
If I use VirtualNode's to provide a traditional tree-type linked list with a
next pointer pointing to other VirtualNode's on the current dimension and a
down pointer pointing to an ObjectNode for the current dimension.
The ObjectNode's will just have down pointer pointing to the VirtualNodes for
the next lower dimension. This way, the VirtualNodes will link the objects in
a traditional fashion with all the duplication that intails, and the
ObjectNode's can be the single reference point for each object. The down side
is this will take upto 3 times as many structures as I want, but the data
itself will not be duplicated. Any time you reference an object, reguardless
from where, it still points to the one object. I'll try to give you an idea
of what I mean.
Imagine a triangle.
We have an ObjectNode that points down to the first of three VirtualNodes for
the lines.
Each VirtualNode->next points to the next VirtualNode until the last one,
which points to NULL.
Each VirtualNode->down points to the ObjectNode for that line.
The ObjectNode for each line points down to the first of two VirtualNodes for
the vertices at each end of the line.
Each VirtualNode->next points to the other VirtualNode for hte other end of
the line.
Each VirtualNode->down points to the ObjectNode for that vertice.
The ObjectNode for each vertice will point to the array of GLfloat data that
describes that vertice in the N-space.
So, we have:
ObjectNode triangle
|
VirtualNode -> VirtualNode -> VirtualNode -> NULL
Line 0 Line1 Line2
| | |
ObjectNode ObjectNode ObjectNode
Line0 Line1 Line2
| | |
| | VirtualNode -> VirtualNode -> NULL
| | vertex2 vertex0
| VirtualNode -> VirtualNode -> NULL |
| vertex1 vertex2 |
VirtualNode -> VirtualNode -> NULL | |
vertex0 vertex1 | /
| | | /
ObjectNode ObjectNode ObjectNode /
vertex0 vertex1 vertex2 /
|______________________________________/
The diagram might not come out, depending on your font settings, and it's
still a bit confusing, but the important thing in this example is each
ObjectNode Line points to a seperate linked-list of VirtualNode vertex for a
total of 6 vertex VirtualNodes. But all the VirtualNodes for, say vertex0
point to the same ObjectNode for vertex0. I.E. there are only 3 ObjectNodes
for the vertices even though each line has it's own list of two vertices.
This also has the advantage that each object can identify it's sub-objects in
counter-clockwise order to simplify the rendering in OpenGL. The advantages
become even more appearent when you go to higher dimensions.
A cube ObjectNode will point to the first of 6 face VirtualNodes.
Each face VirtualNode will point it it's face Object Node.
Each face Object Node will point to the first of four line Virtual nodes,
I.E. 6 * 4 = 24 line VirtualNodes but there will only be 12 line ObjectNodes.
Faces that share a line will both point to the same ObjectNode for that line.
The line ObjectNodes will point to the first of two vertex VirtualNodes, I.E.
12 * 2 = 24 vertex VirtualNodes but there are only 8 vertex ObjectNodes.
The vertex Object nodes will point to the arrays that hold the GLfloat data
for that vertex.
This type of structure should be able to grow recursively to as many
dimensions as I want. Now I just need to figure out just how to declare these
structures and how to assign the pointers properly. Right now the only thing
confusing me is which comes first, the ObjectNode or the VirtualNode, since
each refers to the other. Is it possible to declare them like this:
And my attempt at a tree structure
/*--------------------------------------------------------------------------
* ObjectNode identifies 'physical' objects. The only info contained
* is the dimension level and a pointer 'down' to the next level of
* VirtualNode's
*---------------------------------------------------------------------------
*/
typedef struct objectNode {
int dim;
struct virtualNode *down;
}ObjectNode;
/*--------------------------------------------------------------------------
* VirtualNode identifies 'virtual' objects. These make up a common
* tree structure of pointers. next points to the next virtual
* object in a linked list, down points to the Object node for this
* dimension. A diagram would simplify things greatly.
*---------------------------------------------------------------------------
*/
typedef struct virtualNode {
struct virtualNode *next;
struct objectNode *down;
}VirtualNode;
So we have two complimentary structures ObjectNode and VirtualNode.
The VirtualNodes provide tree-type pointers;
next points to the next VirtualNode in the linked list.
Down points to the ObjectNodes for this dimension.
The ObjectNodes just point to the next dimension down, until we reach the
vertices. These will point directly to the arrays created with the matrixt
oolkit. Still not sure how I can rectify the different pointer types unless I
use unions or maybe I can originally assign the pointers to *NULL until the
links are created. This might be a better idea.
Of course if anyone has a better plan, I'm all ears ;-)
Cheers,
John Gay
This archive was generated by hypermail 2.1.6 : Thu 06 Feb 2003 - 13:17:04 GMT