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;
}
void vtxLoadObj( char *filename )
{
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);
vtxAddVertex(x, y, z, w );
}
else if ( line[0] == 't' )
{
sscanf(line + 2, "%d %d %d", &v1, &v2, &v3 );
vtxAddTriangle(v1, v2, v3);
}
else if ( line[0] == 'q' )
{
sscanf(line + 2, "%d %d %d %d", &v1, &v2, &v3, &v4 );
vtxAddQuad(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 )
{
int already;
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 )
{
already = 0;
for ( int j = 0 ; j < nSpiraling ; j++ )
{
if ( Spiraling[j] == Edges[i].v2 )
{
already = 1;
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;
}
int AddSurface( int f )
{
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 already;
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 )
{
already = 0;
for ( int j = 0 ; j < nSpiraling ; j++ )
{
if ( Spiraling[j] == Edges[i].v2 )
{
already = 1;
break;
}
}
if ( already == 0 )
{
v0 = Edges[i].v2;
Spiraling[nSpiraling++] = v0;
AddSurface(Edges[i].f1);
AddSurface(Edges[i].f2);
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 )
{
vtxLoadObj( argv[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++] = vtxAddQuad( v[1], v[2], v[5], v[4] );
f[i++] = vtxAddQuad( v[2], v[3], v[6], v[5] );
f[i++] = vtxAddQuad( v[5], v[6], v[9], v[8] );
f[i++] = vtxAddQuad( v[4], v[5], v[8], v[7] );
// 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
Load the quads_2x2.obj file
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
Load the cube.obj file
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 )
