# New type of compact primitive

Hi,

I have begin to work about a new type of primitive that can regroup a numerous number of triangles and/or quads using only a really compact storage for their topology

This store the number of triangles/quads founded around a vertex and store them vertice by vertice along a spirale and this produce a very compact chunk of topology
(the storage of the topoly is really very very compact because 16 quads/ 25 vertices are contained using only consecutives 9 bytes for the last example for example)

Think you that this type of new primitive can to be added to OpenGL in the future ?

That’s unlikely.

I don’t really understand what your diagrams represent. You have some drawings and numbers, but it’s unclear what they mean.

If you want to implement this form of mesh compression (however it works), you’re free to do so. It may even be reasonably inexpensive; given what you’ve said about it, it seems very ameniable to using mesh shaders.

But hardware isn’t going to incorporate your compression technique. That’s just not the direction GPUs are going in; they prefer to give you the freedom to do whatever compression you like. Hence mesh shaders.

Thank, Alfonse

I take a look about mesh shaders that seem effectively to be a good way for to implement this
(because the entire topoly is contained at the vertices level, this can certainly “easily” to be stored into one specific vertex array for to be decompacted in a real time in a mesh shader)

Blues numbers are consécutives vertices indices

Green numbers specify for each associated facet if this is is a triangle or a quad
(quads are 4 in the draw and their associated binary value 1 in the binary storage)

Red numbers specify the numbers of frees/unvisited quads/triangles around the current vertex
(this is stored in the firsts “inverse” unary bits, cf. red bits, at the binary representation)

And the decompression scheme is relatively simple,work very well and is really speed, the “only” problem is at the compression level that as to be manually make for this instant

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int v0 = 1;
int v1 = 2;
int v2 = 3;

int surf = 0;
int Holes[10];
int nHoles = 0;

FILE *fin = stdin;
FILE *fout = stdout;
FILE *ferr = stderr;

bool bVerbose = false;

void DisplayNextTriangle( bool last = false )
{
bool notHole = true;

surf++;

if ( Holes[0] )
{
for ( int i = 1 ; i <= nHoles ; i++ )
{
if ( Holes[i] == surf )
{
notHole = false ;
}
}
}

if ( last == false )
{
if ( notHole )
{
fprintf( fout, "p %d %d %d \n", v0, v1, v2 );
}

v1++;
v2++;
}
else
{
if ( notHole )
{
fprintf( fout, "p %d %d %d \n", v0, v1, v0+1 );
}

v0++;
}
}

void DisplayNextQuad( bool last = false )
{
bool notHole = true;

surf++;

if ( Holes[0] )
{
for ( int i = 1 ; i <= nHoles ; i++ )
{
if ( Holes[i] == surf )
{
notHole = false ;
}
}
}

if ( last == false )
{
if ( notHole )
{
fprintf( fout, "p %d %d %d %d \n", v0, v1, v2, v2+1 );
}

v1 += 2;
v2 += 2;
}
else
{
if ( notHole )
{
fprintf( fout, "p %d %d %d %d \n", v0, v1, v2, v0+1 );
}

v0++;
v1++;
v2++;
}
}

int main( int argc, char **argv )
{
char buffer[80];
int  nLines = 0;

for ( int arg = 1 ; arg < argc ; arg++ )
{
if      ( strstr( argv[arg], "-verbose" ) != NULL ) { bVerbose = true; }
else if ( strstr( argv[arg], "-fin"     ) != NULL ) { fin  = fopen( argv[++arg], "r" ); }
else if ( strstr( argv[arg], "-fout"    ) != NULL ) { fout = fopen( argv[++arg], "w" ); }
else if ( strstr( argv[arg], "-ferr"    ) != NULL ) { ferr = fopen( argv[++arg], "w" ); }
else if ( strstr( argv[arg], "-v0"      ) != NULL ) { v0 = atoi( argv[++arg] ); v1 = v0 + 1 ; v2 = v0 + 2; }
else if ( strstr( argv[arg], "-v1"      ) != NULL ) { v1 = atoi( argv[++arg] ); v2 = v1 + 1; }
else if ( strstr( argv[arg], "-v2"      ) != NULL ) { v2 = atoi( argv[++arg] ); }
}

if ( bVerbose )
{
fprintf( ferr, "## Generated by obz2obj \n\n");
}

while ( fgets( buffer, 80, fin ) > 0 )
{
if ( bVerbose )
{
fprintf( fout, "#%s", buffer );
}

if ( buffer[0] == '0' )
{
v0++;
}
else if ( (buffer[0] > '0') && (buffer[0] <= '7') )
{
int nFacets = buffer[0] - '0';

unsigned char prefix = 1 << nFacets;

char *facets = buffer + 1;

for ( prefix >>= 1 ; prefix ; prefix >>= 1 )
{
if ( *facets++ == '4' )
{
}
else
{
DisplayNextTriangle( prefix == 0x01 );
}
}
}
else if ( buffer[0] == 'H' )
{
int hole;

sscanf(buffer + 2, "%d", &hole);
Holes[++nHoles] = hole;
Holes[0]++;
}

if ( bVerbose )
{
fprintf( fout, "## next(v0,v1,v2) = (%d,%d,%d) \n\n", v0, v1, v2 );
nLines++;
}
}

if ( bVerbose )
{
fprintf( fout, "\n## %d lines converted \n", nLines );
}

return 0;
}``````

For example, for to define the topology of 16 quads, this need only the use of a file with only 9 lines
(this use a text format for to be more simple to edit)

``````44444
244
244
14
244
14
244
14
14``````

and this generate this

``````yannoo@Thinkoo:~/Dev/Vertex\$ time cat quads_4x4.obz | ./obz2obj
p 1 2 3 4
p 1 4 5 6
p 1 6 7 8
p 1 8 9 2
p 2 9 10 11
p 2 11 12 3
p 3 12 13 14
p 3 14 15 4
p 4 15 16 5
p 5 16 17 18
p 5 18 19 6
p 6 19 20 7
p 7 20 21 22
p 7 22 23 8
p 8 23 24 9
p 9 24 25 10

real	0m0,009s
user	0m0,001s
sys	0m0,007s
``````

Ps : note the very high correlation between incrementals succesives indices (vertically and horizontally) and that this really reduce the size of indices data to transmit from 3 ou 4 integers per face to only one byte per vertex/groups of faces, so I think this that this have a sens to incorporate this into a new primitive for to very greatly reduce the size of data used for to transmit indices from the CPU to the GPU …
(but I like your idea about passing via a mesh shader because this regroup the advantages of a very small memory footprint input AND a speed generation of triangles/quads without the need of any hardware change)

Ark, I see this at Introduction to Mesh Shaders (OpenGL and Vulkan) | Geeks3D

“Currently, mesh shaders are only supported by NVIDIA Turing GPUs (GeForce RTX 20 Series, GeForce GTX 16 Series). According to some news, AMD RDNA2 GPUs will support mesh shaders too.”

=> I see if the mesh shader stage can to handled and/or simulated on MESA for 99.99% of “olds” graphics cards that of course doesn’t handle it …

Though that’s a 3.5 year old link, today the the OpenGL Mesh Shader support still appears to be NVIDIA-only.

Ark, OpenGL mesh/geometry shaders seem to be restricted to ONLY very lastest AND high ends / very expensives cards
(it’s simple, OpenGL mesh/geometry shaders are no supported on ALLS commons plateforms where I have tested it presence via “glxinfo | grep shader” …)

So, I have write a very basic converter from my .obz human readable text format to a more concise binary version for to see the potential interest of this new type of primitive

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

FILE *fin = stdin;
FILE *fout = stdout;
FILE *ferr = stderr;

bool bVerbose = false;

void BinarizeLine( char *line )
{
unsigned char code, flag;
int degrees;

if ( line[0] == '#' ) return;

degrees = line[0] - '0';

code = 0x01 << (degrees);
flag = code >> 1;

for ( int i = 1 ; i <= degrees ; i++, flag >>= 1 )
{
if ( line[i] == '4' )
{
code |= flag;
}
}

fwrite( &code, 1, 1, fout );
}

int main( int argc, char **argv )
{
char buffer[80];
int  nLines = 0;

for ( int arg = 1 ; arg < argc ; arg++ )
{
if      ( strstr( argv[arg], "-verbose" ) != NULL ) { bVerbose = true; }
else if ( strstr( argv[arg], "-fin"     ) != NULL ) { fin  = fopen( argv[++arg], "r" ); }
else if ( strstr( argv[arg], "-fout"    ) != NULL ) { fout = fopen( argv[++arg], "w" ); }
else if ( strstr( argv[arg], "-ferr"    ) != NULL ) { ferr = fopen( argv[++arg], "w" ); }
else if ( strstr( argv[arg], "-help"	) != NULL ) { fprintf(stderr, "obz2bin [-fin \$in] [-fout \$out] [-ferr \$err]  [-verbose] [-help] \n"); }
}

if ( bVerbose )
{
fprintf( ferr, "## Generated by obz2bin \n\n");
}

while ( fgets( buffer, 80, fin ) != NULL )
{
nLines++;

//if ( bVerbose )
{
fprintf( ferr, "%s", buffer );
}

BinarizeLine( buffer );

}

// if ( bVerbose )
{
fprintf( ferr, "\n## %d lines converted \n", nLines );
}

return 0;
}``````

For exemple, a manual conversion of a 8x8 grid of quads (9x9 vertices) generate logically a .obj file of 924 bytes / 64 lines (cf. 8x8 quads = 64 quads = 64 x “p v1 v2 v3 v4” lines), where the .obz is contained using only 163 bytes / 50 lines and the binary representation is compacted to only 50 bytes / 1 lines, so a gain of about 95% of the data to transfer from a regular indexed format to a compacted degrees based scheme as used by the binarized .obz format

``````yannoo@cyclone ~/Dev/Vertex \$ ls -lrt quads_9x9*
-rw-rw-r-- 1 yannoo yannoo 163 nov.  20 13:16 quads_9x9.obz
-rw-rw-r-- 1 yannoo yannoo 924 nov.  20 13:21 quads_9x9.obj
-rw-rw-r-- 1 yannoo yannoo  50 nov.  20 13:23 quads_9x9.bin
yannoo@cyclone ~/Dev/Vertex \$ wc -l quads_9x9*
114 total
p 1 2 3 4
p 1 4 5 6
p 1 6 7 8
p 1 8 9 2
p 2 9 10 11
p 2 11 12 3
p 3 12 13 14
p 3 14 15 4
p 4 15 16 5
p 5 16 17 18
44444
244
244
14
244
14
244
14
14
244
yannoo@cyclone ~/Dev/Vertex \$ hexdump -C quads_9x9.bin
00000000  1f 07 07 03 07 03 07 03  03 07 03 03 07 03 03 03  |................|
00000010  07 03 03 03 07 03 03 03  03 07 03 03 03 03 07 03  |................|
00000020  03 03 03 03 07 03 03 03  03 03 07 03 03 03 03 03  |................|
00000030  03 00                                             |..|
00000032``````

Note the very regulars occurences of 0x07 and 0x03 values into the binary stream, corresponding to the “244” and “14” lines into the .obz human readable format, so this can to be compressed in realtime via gzip or something similar if we want to reduce even more the size of data to transfer

I think to implement a thin lightweight wrapper for to can directly use something like a glDrawArraysEXT(GLenum mode, GLint first, GLsize count) and/or glDrawElementsEXT( GLenum mode, GLsizei count, GLenum type, const void * indices) with a new primitive mode GL_DEGREES for to complete the standards GL_POINTS, GL_LINES, GL_TRIANGLES, GL_QUADS and others GL_[TRIANGLES, QUADS]_STRIP or GL_ADJACENCY currently handled primitives on OpenGL

Hi,

I have too write this code one week ago for the compression side and after the reading of a lot of documents about HalfEdges, WingedEdges, QuadEdges and others G-maps / combinatorials maps , I find that the algorithm I have used seem surprisingly similar at what I read at the wikipédia page Combinatorial map - Wikipedia about the signication of the map, cf.

"A combinatorial map is a triplet M = (D, σ, α) such that:

• D is a finite set of darts;
• σ is a permutation on D;
• α is an involution on D with no fixed point."
(Note that the french version at Carte combinatoire — Wikipédia is more complete because it contain in more the example of a permutation table => cocorico a new time )

=> I think that perhaps the reindexation make in my code is what they call the permutation and perhaps ever that what they call the involution the correspondance’s arrays Spiraling and InvSpiraling

Here my first attempt for to automatically found the (first) best vertex to use and the spiraling order that give with
(this seem to generate more or less the same re-ordering than the one that I maked manually before => this is the style of things that encourage me in this way )

Here the code that I use

``````#include "vertex.h"
#include <math.h>

#define MAX_ARRAY_SIZE  16384

int         nVertices = 0;
vertex_t    *Vertices;

int         nEdges   = 0;
edge_t      *Edges;

int         nFacets = 0;

int Spiraling[MAX_ARRAY_SIZE];
int InvSpiraling[MAX_ARRAY_SIZE];
int nSpiraling = 0;

int Surfaces[MAX_ARRAY_SIZE];
int nSurfaces = 0;

edge_t *EdgesOrder[MAX_ARRAY_SIZE];

vertex_t *vtxAllocVertices( int numVertices )
{
Vertices = (vertex_t *) malloc( (numVertices+1) * sizeof(vertex_t) );

return Vertices;
}

edge_t *vtxAllocEdges( int numEdges )
{
Edges = (edge_t *) malloc( (numEdges+1) * sizeof(edge_t) );

return Edges;
}

void vtxAlloc()
{
(void) vtxAllocVertices(MAX_ARRAY_SIZE);
(void) vtxAllocEdges(MAX_ARRAY_SIZE);
}

int vtxGetNumVertices()
{
return nVertices;
}

int vtxGetNumEdges()
{
return nEdges;
}

int vtxGetVertexValence( int v )
{
int count = 0;

for ( int i = 1 ; i<= nEdges ; i++ )
{
if ( Edges[i].v1 == v ) count++;
if ( Edges[i].v2 == v ) count++;
}

return count;
}

int vtxGetVertexDegree( int v )
{
int count = 0;

for ( int i = 1 ; i<= nEdges ; i++ )
{
if ( Edges[i].v1 == v )
{
if ( Edges[i].f1 != 0 ) count++;
}

if ( Edges[i].v2 == v )
{
if ( Edges[i].f2 != 0)  count++;
}
}

return count;
}

int vtxGetFaceDegree( int f )
{
int count = 0;

for ( int i = 1 ; i<= nEdges ; i++ )
{
if ( Edges[i].f1 == f ) count++;
if ( Edges[i].f2 == f ) count++;
}

return count;
}

int vtxGetVertexScore( int v )
{
return Vertices[v].valence * Vertices[v].degree;
}

int vtxGetEdgeScore( int e )
{
return Vertices[ Edges[e].v1 ].degree * Vertices[ Edges[e].v2 ].valence;
}

int vtxGetFaceScore( int f )
{
int count = 0;

for ( int i = 1 ; i<= nEdges ; i++ )
{
if ( Edges[i].f1 == f ) count++;
if ( Edges[i].f2 == f ) count++;
}

return count;
}

int vtxAddVertex(  float x , float y , float z , float w )
{
++nVertices;

Vertices[nVertices].x = x;
Vertices[nVertices].y = y;
Vertices[nVertices].z = z;
Vertices[nVertices].w = w;

Vertices[nVertices].valence = 0;
Vertices[nVertices].degree = 0;

return nVertices;
}

int vtxAddEdge( int v1, int v2, int f1 , int f2 )
{
// skip if one vertice is missed
if ( v1 == 0 ) return 0;
if ( v2 == 0 ) return 0;

// return the index of the edge if already exist (negative index if the inverse edge)
for ( int i = 1 ; i <= nEdges ; i++ )
{
if ( Edges[i].v1 == v1 )
{
if ( Edges[i].v2 == v2 )
{
if ( Edges[i].f1 == 0 )
{
Edges[i].f1 = f1;
}

if ( Edges[i].f2 == 0 )
{
Edges[i].f2 = f2;
}
return i;
}
}
if ( Edges[i].v2 == v1 )
{
if ( Edges[i].v1 == v2 )
{
if ( Edges[i].f1 == 0 )
{
Edges[i].f1 = f2;
}

if ( Edges[i].f2 == 0 )
{
Edges[i].f2 = f1;
}
return -i;
}
}
}

// Create a new edge if not already finded
nEdges++;
Edges[nEdges].v1 = v1;
Edges[nEdges].v2 = v2;
Edges[nEdges].f1 = f1;
Edges[nEdges].f2 = f2;

return nEdges;
}

void vtxCorrectValences()
{
for ( int i = 1; i <= nVertices ; i++ )
{
Vertices[i].valence = vtxGetVertexValence(i);
}
}

void vtxCorrectDegrees()
{
for ( int i = 1; i <= nVertices ; i++ )
{
Vertices[i].degree = vtxGetVertexDegree(i);
}
}

void vtxPrintVertices()
{
for ( int i = 1; i <= nVertices; i++ )
{
printf("\tv%d = { %f %f %f } (valence = %d , degree = %d)  \n", i,
Vertices[i].x,
Vertices[i].y,
Vertices[i].z,
Vertices[i].valence,
Vertices[i].degree
);
}

printf("\n");
}

void vtxPrintEdges()
{
for ( int i = 1 ; i <= nEdges;  i++ )
{
printf("\te%d = { v%d -> v%d , f%d / f%d } \n",
i,
Edges[i].v1,
Edges[i].v2,
Edges[i].f1,
Edges[i].f2
);
}

printf("\n");
}

int vtxAddTriangle( int v1 , int v2 , int v3 )
{
++nFacets;

(void) vtxAddEdge( v1, v2, nFacets, 0);
(void) vtxAddEdge( v2, v3, nFacets, 0);
(void) vtxAddEdge( v3, v1, nFacets, 0);

Vertices[v1].degree++;
Vertices[v2].degree++;
Vertices[v3].degree++;

return nFacets;
}

int vtxAddQuad( int v1 , int v2 , int v3, int v4 )
{
++nFacets;

(void) vtxAddEdge( v1, v2, nFacets, 0);
(void) vtxAddEdge( v2, v3, nFacets, 0);
(void) vtxAddEdge( v3, v4, nFacets, 0);
(void) vtxAddEdge( v4, v1, nFacets, 0);

Vertices[v1].degree++;
Vertices[v2].degree++;
Vertices[v3].degree++;
Vertices[v4].degree++;

return nFacets;
}

{
FILE *file;
char line[120];
float x, y, z, w;
int v1, v2, v3, v4;

printf("Load the %s file \n\n", filename);
file = fopen( filename, "r" );

while ( fgets( line, 120, file) )
{
printf("%s", line);

if ( line[0] == 'v' )
{
sscanf(line + 2, "%f %f %f %f", &x, &y, &z, &w);
}
else if ( line[0] == 't' )
{
sscanf(line + 2, "%d %d %d", &v1, &v2, &v3 );
}
else if ( line[0] == 'q' )
{
sscanf(line + 2, "%d %d %d %d", &v1, &v2, &v3, &v4 );
}
}
fclose(file);

printf("\n\n");
}

int vtxFindBestVertex0()
{
int bestVertex = 0;
int score, scoreMax = 0;

for ( int i = 1; i <= nVertices ; i++ )
{
score = Vertices[i].valence * Vertices[i].degree;

if ( score > scoreMax )
{
bestVertex = i;
scoreMax = score;
}
}

return bestVertex;
}

int vtxFindBestVertex()
{
// return vtxFindBestVertex0();
// return (0.5f) * (float)(nVertices + 1);
return  sqrt(nVertices) * 2 - 1;
}

int ComputeSpirale( int v0 )
{

nSpiraling = 0;
Spiraling[nSpiraling++] = v0;

printf("Spiraling from v%d : v%d ", v0, v0);

for ( int i = 1 ; i <= nEdges ; i++)
{
if ( Edges[i].v1 == v0 )
{

for ( int j = 0 ; j < nSpiraling ; j++ )
{
if ( Spiraling[j] == Edges[i].v2 )
{
break;
}
}

if ( already == 0 )
{
v0 = Edges[i].v2;
Spiraling[nSpiraling++] = v0;
printf("v%d ", v0);
i = 0;
}
}
}

printf(" (length = %d/%d = %.1f%% of vertices)  \n", nSpiraling, nVertices, ((double)(nSpiraling) /  (double)(nVertices))*100.0f );

return nSpiraling;
}

{
if ( f == 0 ) return 0;

for ( int i = 0 ; i < nSurfaces ; i++ )
{
if ( Surfaces[i] == f ) return i;
}

Surfaces[nSurfaces++] = f;

return nSurfaces;
}

void PrintReindexedVertices()
{
int idx;

for ( int i = 1; i <= nVertices; i++ )
{
idx = Spiraling[ i - 1 ];

if ( idx == 0 ){ idx = i; };

printf("\tv%d (original v%d)  = { %f %f %f } (valence = %d , degree = %d)  \n", i, idx,
Vertices[idx].x,
Vertices[idx].y,
Vertices[idx].z,
Vertices[idx].valence,
Vertices[idx].degree
);
}

printf("\n");
}

void ReindexEdges()
{
for ( int i = 1 ; i <= nEdges ; i++)
{
Edges[i].v1 = InvSpiraling[ Edges[i].v1 ];
Edges[i].v2 = InvSpiraling[ Edges[i].v2 ];
}

PrintReindexedVertices();
// vtxPrintEdges();
}

int CompareEdges( const void *p1, const void *p2 )
{
edge_t *e1 = *(edge_t **)(p1);
edge_t *e2 = *(edge_t **)(p2);

// if ( e1->f1 < e2->f1 )  return -1;
// if ( e1->f1 > e2->f1 )  return +1;

// printf("Compare edge(%p) and edge(%p) \n", e1, e2 );

if ( e1->v1 < e2->v1 )
{
// printf("permute edge(%d,%d) <-> edge(%d,%d) \n", e1->v1, e1->v2, e2->v1, e2->v2 );
return -1;
}
if ( e1->v1 > e2->v1 )
{
// printf("permute edge(%d,%d) <-> edge(%d,%d) \n", e1->v1, e1->v2, e2->v1, e2->v2 );
return +1;
}

return 0;

}

void SortEdges()
{
// printf("Sort Edges : EdgesOrder[] = %p \n\n", EdgesOrder);
for ( int i = 0 ; i <= nEdges ; i++ )
{
EdgesOrder[i] = &Edges[i];

// printf("EdgesOrder[%d] = %p \n", i, EdgesOrder[i] );
}

// printf("qsort(%p, %d, %d, CompareEdges ) \n", &EdgesOrder[1], nEdges, (int)sizeof(edge_t *) );
qsort(&EdgesOrder[1], nEdges, sizeof(edge_t *), CompareEdges );
}

void PrintSortedEdges()
{
for ( int i = 1 ; i <= nEdges;  i++ )
{
printf("\te%d = { v%d -> v%d , f%d / f%d } \n",
i,
EdgesOrder[i]->v1,
EdgesOrder[i]->v2,
EdgesOrder[i]->f1,
EdgesOrder[i]->f2
);
}

printf("\n");
}

int DisplaySpirale( int v0 )
{
int reindexed;

nSpiraling = 0;
Spiraling[nSpiraling++] = v0;

printf("Spiraling from v%d : \n\n", v0);

for ( int i = 1 ; i <= nEdges ; i++)
{
if ( Edges[i].v1 == v0 )
{

for ( int j = 0 ; j < nSpiraling ; j++ )
{
if ( Spiraling[j] == Edges[i].v2 )
{
break;
}
}

if ( already == 0 )
{
v0 = Edges[i].v2;
Spiraling[nSpiraling++] = v0;

printf("\te%d \t = { v%d -> v%d , f%d / f%d } \n",
i, Edges[i].v1, Edges[i].v2, Edges[i].f1, Edges[i].f2
);

i = 0;
}
}
}
printf("\n\n");
printf("%d/%d vertices extracted (%.1f%%) \n",  nSpiraling,    nVertices,  ((double)(nSpiraling)   / (double)(nVertices)) * 100.0f );
printf("%d/%d faces extracted  (%.1f%%) \n",    nSurfaces,     nFacets,    ((double)(nSurfaces)      / (double)(nFacets)) * 100.0f );
printf("%d/%d edges spiraled (%1.f%%) \n",          nSpiraling-1,  nEdges,     ((double)(nSpiraling-1) / (double)(nEdges)) * 100.0f );

printf("\n\ngenerate vertex order : ");

int maxreindex = 0;
for ( int i = 0 ; i <= nVertices ; i++ )
{
InvSpiraling[i] = -1;
}
for ( int i = 0 ; i < nSpiraling ; i++ )
{
reindexed = Spiraling[i];
printf("v%d ", reindexed );
InvSpiraling[reindexed] = i + 1 ;
}
printf("\n");

printf("\n\nreindexation : \n\n");
// Step 1 : find the maximal index that is contained into the spirale
int maxindex = 0;
for ( int i = 1 ; i <= nVertices ; i++ )
{
reindexed = InvSpiraling[i];

if ( reindexed > maxindex )
{
maxindex = reindexed;
}
}
// step 2 : set incremental order of unvisited vertices and print the finals vertices reindexation
for ( int i = 1 ; i <= nVertices ; i++ )
{
if ( (reindexed = InvSpiraling[i]) == -1 )
{
reindexed = ++maxindex;
InvSpiraling[i] = reindexed;
}
printf("\tv%d -> v%d \n", i, reindexed );
}

printf("\n");

return nSpiraling;
}

int main( int argc, char **argv )
{
int i, bestVertex, test, result, bestResult;

printf("Vertex v0.2 by Cyclone \n\n");

vtxAlloc();

if ( argc > 1 )
{
}
else
{
int v[256];
int f[256];

int i = 1;

v[1] = vtxAddVertex(0, 0, 0, 0 );
v[2] = vtxAddVertex(1, 0, 0, 0 );
v[3] = vtxAddVertex(2, 0, 0, 0 );

v[4] = vtxAddVertex(0, 1, 0, 0 );
v[5] = vtxAddVertex(1, 1, 0, 0 );
v[6] = vtxAddVertex(2, 1, 0, 0 );

v[7] = vtxAddVertex(0, 2, 0, 0 );
v[8] = vtxAddVertex(1, 2, 0, 0 );
v[9] = vtxAddVertex(2, 2, 0, 0 );

// f[i++] = vtxAddPolygon( 6, v + 1 );

// f[i++] = vtxAddFan( v[1], 6, v + 2 );
}

// printf("Correct valences \n");
vtxCorrectValences();

printf("\nExtract vertices \n\n");
vtxPrintVertices();

printf("\nExtract edges \n\n");
vtxPrintEdges();

// Select the best first pivot vertex
// bestVertex = vtxFindBestVertex();
for ( test = 1 , bestVertex = 1, bestResult = 0 ; test <= nVertices ; test++ )
{
result = ComputeSpirale( test );

if ( result > bestResult )
{
bestResult = result;
bestVertex = test;

// TODO : early exit when the first best finded vertex hit 100% of vertices and faces ?
// TODO : and / or select the spirale that have the biggest size with the more incremental form ?
if ( result == nVertices ) break;
}
}

printf("\nThe first best vertex for to begin the spirale is v%d \n\n", bestVertex);

DisplaySpirale( bestVertex );

ReindexEdges();

SortEdges();

PrintSortedEdges();

return 0;
}``````

And the header file that come with

``````#ifndef _VERTEX_H_
#define _VERTEX_H_

#include <stdlib.h>
#include <stdio.h>

typedef struct
{
float x , y , z , w;
float u , v , s , t;
float i , j , k , l;
float r , g , b , a;

int valence;
int degree;

// edge_t *edge;

} vertex_t;

typedef struct
{
int v1;
int v2;

int f1;
int f2;

} edge_t;

extern int         nVertices;
extern vertex_t    *Vertices;

extern int         nEdges;
extern edge_t      *Edges;

extern int vtxAddVertex(  float x , float y , float z , float w );

extern int vtxAddTriangle( int v1 , int v2 , int v3 );
extern int vtxAddQuad( int v1 , int v2 , int v3 , int v4 );
extern int vtxAddPolygon( int n, int *Vertices );
extern int vtxAddFan( int v0, int n, int *Fans );

#endif /* _VERTEX_H_ */``````

This generate this for the simple case of a grid of 4 quads

``````yannoo@cyclone ~/Dev/Spiraling \$ ./vertex quads_2x2.obj
Vertex v0.2 by Cyclone

v 0 0
v 1 0
v 2 0

v 0 1
v 1 1
v 2 1

v 0 2
v 1 2
v 2 2

q 1 2 5 4
q 2 3 6 5
q 5 6 9 8
q 4 5 8 7

Extract vertices

v1 = { 0.000000 0.000000 0.000000 } (valence = 2 , degree = 1)
v2 = { 1.000000 0.000000 0.000000 } (valence = 3 , degree = 2)
v3 = { 2.000000 0.000000 0.000000 } (valence = 2 , degree = 1)
v4 = { 0.000000 1.000000 0.000000 } (valence = 3 , degree = 2)
v5 = { 1.000000 1.000000 0.000000 } (valence = 4 , degree = 4)
v6 = { 2.000000 1.000000 0.000000 } (valence = 3 , degree = 2)
v7 = { 0.000000 2.000000 0.000000 } (valence = 2 , degree = 1)
v8 = { 1.000000 2.000000 0.000000 } (valence = 3 , degree = 2)
v9 = { 2.000000 2.000000 0.000000 } (valence = 2 , degree = 1)

Extract edges

e1 = { v1 -> v2 , f1 / f0 }
e2 = { v2 -> v5 , f1 / f2 }
e3 = { v5 -> v4 , f1 / f4 }
e4 = { v4 -> v1 , f1 / f0 }
e5 = { v2 -> v3 , f2 / f0 }
e6 = { v3 -> v6 , f2 / f0 }
e7 = { v6 -> v5 , f2 / f3 }
e8 = { v6 -> v9 , f3 / f0 }
e9 = { v9 -> v8 , f3 / f0 }
e10 = { v8 -> v5 , f3 / f4 }
e11 = { v8 -> v7 , f4 / f0 }
e12 = { v7 -> v4 , f4 / f0 }

Spiraling from v1 : v1 v2 v5 v4  (length = 4/9 = 44.4% of vertices)
Spiraling from v2 : v2 v5 v4 v1  (length = 4/9 = 44.4% of vertices)
Spiraling from v3 : v3 v6 v5 v4 v1 v2  (length = 6/9 = 66.7% of vertices)
Spiraling from v4 : v4 v1 v2 v5  (length = 4/9 = 44.4% of vertices)
Spiraling from v5 : v5 v4 v1 v2 v3 v6 v9 v8 v7  (length = 9/9 = 100.0% of vertices)

The first best vertex for to begin the spirale is v5

Spiraling from v5 :

e3 	 = { v5 -> v4 , f1 / f4 }
e4 	 = { v4 -> v1 , f1 / f0 }
e1 	 = { v1 -> v2 , f1 / f0 }
e5 	 = { v2 -> v3 , f2 / f0 }
e6 	 = { v3 -> v6 , f2 / f0 }
e8 	 = { v6 -> v9 , f3 / f0 }
e9 	 = { v9 -> v8 , f3 / f0 }
e11 	 = { v8 -> v7 , f4 / f0 }

9/9 vertices extracted (100.0%)
4/4 faces extracted  (100.0%)
8/12 edges spiraled (67%)

generate vertex order : v5 v4 v1 v2 v3 v6 v9 v8 v7

reindexation :

v1 -> v3
v2 -> v4
v3 -> v5
v4 -> v2
v5 -> v1
v6 -> v6
v7 -> v9
v8 -> v8
v9 -> v7

v1 (original v5)  = { 1.000000 1.000000 0.000000 } (valence = 4 , degree = 4)
v2 (original v4)  = { 0.000000 1.000000 0.000000 } (valence = 3 , degree = 2)
v3 (original v1)  = { 0.000000 0.000000 0.000000 } (valence = 2 , degree = 1)
v4 (original v2)  = { 1.000000 0.000000 0.000000 } (valence = 3 , degree = 2)
v5 (original v3)  = { 2.000000 0.000000 0.000000 } (valence = 2 , degree = 1)
v6 (original v6)  = { 2.000000 1.000000 0.000000 } (valence = 3 , degree = 2)
v7 (original v9)  = { 2.000000 2.000000 0.000000 } (valence = 2 , degree = 1)
v8 (original v8)  = { 1.000000 2.000000 0.000000 } (valence = 3 , degree = 2)
v9 (original v7)  = { 0.000000 2.000000 0.000000 } (valence = 2 , degree = 1)

e1 = { v1 -> v2 , f1 / f4 }
e2 = { v2 -> v3 , f1 / f0 }
e3 = { v3 -> v4 , f1 / f0 }
e4 = { v4 -> v1 , f1 / f2 }
e5 = { v4 -> v5 , f2 / f0 }
e6 = { v5 -> v6 , f2 / f0 }
e7 = { v6 -> v1 , f2 / f3 }
e8 = { v6 -> v7 , f3 / f0 }
e9 = { v7 -> v8 , f3 / f0 }
e10 = { v8 -> v1 , f3 / f4 }
e11 = { v8 -> v9 , f4 / f0 }
e12 = { v9 -> v2 , f4 / f0 } ``````

and this work too with the classical cube where alls faces share alls their edges with anothers faces, so no “border faces”, cf. f0 faces, such as in a 2D grid

``````yannoo@cyclone ~/Dev/Spiraling \$ ./vertex cube.obj
Vertex v0.2 by Cyclone

v 0 0 0
v 1 0 0
v 1 1 0
v 0 1 0
v 0 0 1
v 1 0 1
v 1 1 1
v 0 1 1

q 1 2 3 4
q 2 1 5 6
q 3 2 6 7
q 4 8 5 1
q 5 8 7 6
q 7 8 4 3

Extract vertices

v1 = { 0.000000 0.000000 0.000000 } (valence = 3 , degree = 3)
v2 = { 1.000000 0.000000 0.000000 } (valence = 3 , degree = 3)
v3 = { 1.000000 1.000000 0.000000 } (valence = 3 , degree = 3)
v4 = { 0.000000 1.000000 0.000000 } (valence = 3 , degree = 3)
v5 = { 0.000000 0.000000 1.000000 } (valence = 3 , degree = 3)
v6 = { 1.000000 0.000000 1.000000 } (valence = 3 , degree = 3)
v7 = { 1.000000 1.000000 1.000000 } (valence = 3 , degree = 3)
v8 = { 0.000000 1.000000 1.000000 } (valence = 3 , degree = 3)

Extract edges

e1 = { v1 -> v2 , f1 / f2 }
e2 = { v2 -> v3 , f1 / f3 }
e3 = { v3 -> v4 , f1 / f6 }
e4 = { v4 -> v1 , f1 / f4 }
e5 = { v1 -> v5 , f2 / f4 }
e6 = { v5 -> v6 , f2 / f5 }
e7 = { v6 -> v2 , f2 / f3 }
e8 = { v6 -> v7 , f3 / f5 }
e9 = { v7 -> v3 , f3 / f6 }
e10 = { v4 -> v8 , f4 / f6 }
e11 = { v8 -> v5 , f4 / f5 }
e12 = { v8 -> v7 , f5 / f6 }

Spiraling from v1 : v1 v2 v3 v4 v8 v5 v6 v7  (length = 8/8 = 100.0% of vertices)

The first best vertex for to begin the spirale is v1

Spiraling from v1 :

e1 	 = { v1 -> v2 , f1 / f2 }
e2 	 = { v2 -> v3 , f1 / f3 }
e3 	 = { v3 -> v4 , f1 / f6 }
e10 	 = { v4 -> v8 , f4 / f6 }
e11 	 = { v8 -> v5 , f4 / f5 }
e6 	 = { v5 -> v6 , f2 / f5 }
e8 	 = { v6 -> v7 , f3 / f5 }

8/8 vertices extracted (100.0%)
6/6 faces extracted  (100.0%)
7/12 edges spiraled (58%)

generate vertex order : v1 v2 v3 v4 v8 v5 v6 v7

reindexation :

v1 -> v1
v2 -> v2
v3 -> v3
v4 -> v4
v5 -> v6
v6 -> v7
v7 -> v8
v8 -> v5

v1 (original v1)  = { 0.000000 0.000000 0.000000 } (valence = 3 , degree = 3)
v2 (original v2)  = { 1.000000 0.000000 0.000000 } (valence = 3 , degree = 3)
v3 (original v3)  = { 1.000000 1.000000 0.000000 } (valence = 3 , degree = 3)
v4 (original v4)  = { 0.000000 1.000000 0.000000 } (valence = 3 , degree = 3)
v5 (original v8)  = { 0.000000 1.000000 1.000000 } (valence = 3 , degree = 3)
v6 (original v5)  = { 0.000000 0.000000 1.000000 } (valence = 3 , degree = 3)
v7 (original v6)  = { 1.000000 0.000000 1.000000 } (valence = 3 , degree = 3)
v8 (original v7)  = { 1.000000 1.000000 1.000000 } (valence = 3 , degree = 3)

e1 = { v1 -> v2 , f1 / f2 }
e2 = { v1 -> v6 , f2 / f4 }
e3 = { v2 -> v3 , f1 / f3 }
e4 = { v3 -> v4 , f1 / f6 }
e5 = { v4 -> v1 , f1 / f4 }
e6 = { v4 -> v5 , f4 / f6 }
e7 = { v5 -> v6 , f4 / f5 }
e8 = { v5 -> v8 , f5 / f6 }
e9 = { v6 -> v7 , f2 / f5 }
e10 = { v7 -> v2 , f2 / f3 }
e11 = { v7 -> v8 , f3 / f5 }
e12 = { v8 -> v3 , f3 / f6 }   ``````

=> bon OK, it’s far to be the end of the story but my project seem now more realistic than it have never to be
(and this seem too a good start for to begin about a more raytracing approach instead the classical triangle/quad filling method because edges have explicites links to vertices and associated faces, so this can help for to automatically detect the visibilty/culling/grouping of faces/vertices and/or an automatic generation of a BSP for examples )

How to fastly retrieve the complete and ordonned list of vertices that make each face, and this indepently for each face ?
(cf. this can to be make in // for alls wanted faces for exemple)

I use the first very basic case of a grid of 2x2 quad for don’t to be speedly loose by the number/size of the egdes array to analyse here BUT exactely the same méthod can to be used for alls others case

This is the result of the vertices, edges and faces extraction / réordering

``````e1 = { v1 -> v2 , f1 / f4 }
e2 = { v2 -> v3 , f1 / f0 }
e3 = { v3 -> v4 , f1 / f0 }
e4 = { v4 -> v1 , f1 / f2 }
e5 = { v4 -> v5 , f2 / f0 }
e6 = { v5 -> v6 , f2 / f0 }
e7 = { v6 -> v1 , f2 / f3 }
e8 = { v6 -> v7 , f3 / f0 }
e9 = { v7 -> v8 , f3 / f0 }
e10 = { v8 -> v1 , f3 / f4 }
e11 = { v8 -> v9 , f4 / f0 }
e12 = { v9 -> v2 , f4 / f0 }
``````

See each edge as the form of a structure { vertice_origin → vertice_destination, face_inside / face_outside }

1. for the face f1

the ideal case, loop from the beginning of the array and select only entries with f1 on the inside side

`````` e1 = { v1 -> v2 , f1 / f4 }
e2 = { v2 -> v3 , f1 / f0 }
e3 = { v3 -> v4 , f1 / f0 }
e4 = { v4 -> v1 , f1 / f2 }
``````

=> v1 → v2 → v3 → v4 and the loop can finish because we have find a cycle on v1
(cf. 4 > 1, so the strictly increment ordering is stopped = cycle detected)

==> the face f1 contain 4 vertices, cf. the number of entries founded

2. for the face f2

a little more difficult, because f2 is only listed 3x on the inside side of edges

`````` e5 = { v4 -> v5 , f2 / f0 }
e6 = { v5 -> v6 , f2 / f0 }
e7 = { v6 -> v1 , f2 / f3 }
``````

=> reloop now from the begining of the array and select only entries wqith f2 on the OUTSIDE side of the array

`````` e4 = { v4 -> v1 , f1 / f2 }

what can be see as { v1 -> v4 , f2 / f1 }, cf. flip origin/destination vertices and inside/outside faces
``````

==> this give now the vertice order v4 → v5 → v6 → v1 and alls edeges with f2 on the inside or outside sides has been extracted

====> the face contain here too 4 vertices, cf. the number of entries founded from inside parts + entries founded for the ouside parts

3. for the face f3, it’s exactly the same thing

from inside parts

`````` e8 = { v6 -> v7 , f3 / f0 }
e9 = { v7 -> v8 , f3 / f0 }
e10 = { v8 -> v1 , f3 / f4 }
``````

from outside parts

`````` e7 = { v6 -> v1 , f2 / f3 }
``````

=> e8 + e9 + e10 - e7 = v6 → v7 → v8 → v1 and we know that the cycle is finish because 1 is < 6

4. for the face f4

extraction of entries with f4 on the inside parts

`````` e11 = { v8 -> v9 , f4 / f0 }
e12 = { v9 -> v2 , f4 / f0 }
``````

extraction of entries with f4 on the outside parts

`````` e1 = { v1 -> v2 , f1 / f4 }
e10 = { v8 -> v1 , f3 / f4 }
``````

=> e11 + e12 - e1 - e10 = v8 → v9 → v2 → v1 and cycle detected on e10 because the index of the origin is > to the index of the destination

We have now extracted alls faces/edges/vertices with the good ordering of vertices for each …

``````f1 =  e1 + e2 + e3 + e4 = v1 -> v2 -> v3 -> v4  (-> v1 for the local cycling)

f2 =  e5 + e6 + e7 -  e4  = v4 -> v5 -> v6 -> v1  (-> v4 for the  local cycling)

f3 =  e8 +  e9 + e10 - e7 = v6 -> v7 -> v8 -> v1  (-> v6 for the  local  cycling)

f4 =  e11 + e12 - e1 - e10  = v8 -> v9 -> v2 -> v1  (-> v8 for the local cycling)
``````

I think than we can detect too v1 as the pivot because it is the last vertice of alls faces contained it EXCEPT for one face (the first) where it is the first vertice extracted …
(this is only an intuition, not a certitude but I think that it’s a good intuition)

Note the auto-incremental ordering v1 → v2 → v3 → v4 → v5 → v6 → v7 → v8 → v9 given by the spirale reordering … that concord miraculously with my initial idea about compacting the incrementals indexations of vertices that I have implemented on the decompression side

Note too that firsts edgesa and vertices can to be deleted after the last use of them and that this can to be used for to handle a streaming with the use of a little glissant buffering of them for example … but this is another story to write on the future

PS : note that the total size of edges structs is not specially smaller than the total size of alls { v1, v2, v3, v4, v5, …] } vertices references on faces BUT this is only explicitly used/constructed at the compression side, not at the decompression side where they are automatically/implicitly extracted from the vertex code, cf. never stored …
(this is here than a stream buffering sheme can to help for a very limited RAM memory use in the compression side, such as in the decompression side after a little reflexion …)