SOL3D data structure

By Jose Parrot
Structure definition document

Version 1.2, October, 20, 2008 – minor corrections and improved explanation

Version 1.1, October, 13, 2008
Project at sourceforge.net
More information at main page

Downloads at http://sourceforge.net/projects/sol3d

Introduction

General hierarchy

Most intuitive data structures of geometric entities are hierarchically arranged, in the following general format:

 
Number N of polyhedra
        Number NF of faces of polyhedron P1
               Number of vertices of Face F1 of P1
                       Number NE of edges of face F1
                               Set of vertices (x,y,z) coordinates
               Number of vertices of Face F2 of P1
                       Number NE of edges of face F2
                               Set of vertices (x,y,z) coordinates
               :
               :
               Number of vertices of Face NF of P1
                       Number NE of edges of face F1
                               Set of vertices (x,y,z) coordinates
        :
        :
 
        Number NF of faces of polyhedron PN
               Number of vertices of Face F1 of PN
                       Number NE of edges of face F1
                               Set of vertices (x,y,z) coordinates
               Number of vertices of Face F2 of PN
                       Number NE of edges of face F1
                               Set of vertices (x,y,z) coordinates
 
                               :
                               :
               Number of vertices of Face NF of PN
                       Number NE of edges of face F1
                               Set of vertices (x,y,z) coordinates

 

General structure

This structure determines the creation of the following variables and arrays:

 
MAXP           // maximum number of Polyhedra
MAXF           // maximum number of faces of each Polyhedron
MAXE           // maximum number of edges of a face
Struct vertex
{
        float x,y,z
}
int N
int NF[MAXP]
int NE[MAXP][MAXF]
vertex V[MAX][MAXF][MAXE]

 
Such data structure has the disadvantage of wasting of space, because each array is dimensioned for the larger object. For example, if there are 900 objects with 4 faces of 4 edges each and just one with 12 faces, and 6 edges, then MAXF = 12 and MAXE = 6 would apply to the entire arrays, which result very large.

 

Sol3d structure

To avoid that wasting of space, SOL adopts the following structure:
 
MAXP           // maximum number of Polyhedra
MAXV           // maximum total number of vertices
MAXL           // maximum total number of lines
MAXF           // maximum total number of faces
MAXE           // maximum total number of edges
struct vertex
{
        float x,y,z
}
struct line
{
        int L1, L2;    // index of points of the line
}
int N          // number of Polyhedra
int qp[MAXP]   // number of points (vertices)of each polyhedron
int ql[MAXP]   // number of lines of each polyhedron
int qf[MAXP]   // number of faces of each polyhedron
int qa[MAXF]   // number of vertices of each face
int na[MAXE]   // indexes of vertices of each face
vertex xyz[MAXV]       // coordinates of the points
line L1L2[MAXL] // indexes of pairs of points

 

In such way, there is just one array for each Points, Lines, Faces and Edges of faces.

The arrays for “number of” (points, lines, etc.) qp, ql, etc. have pointers to the points, lines arrays. To obtain the indexes of a given polyhedron, we need the previous one to know where it starts. Example: calculate the indexes of sol (polyhedron) 3.
1. Calculate the index of first elements of sol 3
iPoint = qp[sol-1]; // index of first point of sol
iPoint = qp[ 2 ];   // index of first point of sol=3
first point of sol 3 = xyz[iPoint]
iLine  = ql[sol-1]; // index of first line of sol
iLine  = ql[ 2 ];   // index of first line of sol=3
first line of sol 3 = L1L2[iLine]
… and so on.

2. Calculate the index of last element of sol 3, with 8 points and 10 lines
// index of last point of sol, being Qt_Points the number of points
iPoint = qp[sol-1 + Qt_Points] - 1; // index of last point of sol
iPoint = qp[ 3 -1 + 8 ] - 1;  
iPoint = qp[ 10 ] - 1;              // index of last point of sol=3
last point of sol 3 = xyz[iPoint]
// index of last line of sol, being Qt_Lines the number of lines
iLine  = ql[sol-1 + Qt_Lines]-1;    // index of last line of sol
iLine  = ql[ 12 ] - 1;              // index of last line of sol=3
last line of sol 3 = L1L2[iLine]
… and so on.

At the 8088 and DOS era, this approach allowed a large number of polyhedra in a scene. Today, even with large amounts of memory available around, it is useful for huge number of objects. The implementation of the described structure is the varsol.h include file, as below.

varsol.h

#define    qtmax_solidos    255       // maximum number of Polyhedra
#define    qtmax_pontos    1900       // maximum total number of vertices
#define    qtmax_linhas    2900       // maximum total number of lines
#define    qtmax_faces     1250       // maximum total number of faces
#define    qtmax_arestas   4850       // maximum total number of edges
 
int     Qt_Solidos,            // number of Polyhedra
        Qt_Pontos,                    // number of points (vertices)
        Qt_Linhas,                    // number of lines
        Qt_Faces,                     // number of faces
        Qt_Arestas,            // number of edges
        Num_das_arestas;              // índex of the edge
 
int     qp   [ qtmax_solidos],        // number of points (vertices)
        ql   [ qtmax_solidos],        // number of lines
        qf   [ qtmax_solidos],        // number of faces
        qa   [  qtmax_faces ],        // number of vertices of each face
        na   [ qtmax_arestas],        // indexes of vertices of each face
        xyz  [ qtmax_pontos ]  [3],   // points coordinates
        pxpy [ qtmax_pontos ]  [2],   // perspective coordinates
        L1L2 [ qtmax_linhas ]  [2];   // indexes of pairs of points