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