Discussion :

[yannoo95170]

Bonsoir,

Je suis en train de rechercher une méthode efficace de compression de maillages triangulaires/quadrilataires

L'algorithme utilisé consiste à compter pour chaque sommet le nombre de faces encore non trouvées qui y sont attachées et le degrée de chacune d'elles, les faces et les sommets étant pré-ordonnés par l'ordre horaire de leur énumération selon le sens anti-horaire
(on pourrait tout aussi parfaitement utiliser le sens horaire qu'anti-horaire, le seul truc étant de toujours utiliser la même convention de sens)

Par exemple, pour un maillage de 2x2 carrés (9 sommets) , en préssortant les sommets et les faces dans un ordre spilaré, cela peut se résumer à ceci pour la partie connectivité (topologique) du maillage

4 4 4 4 4

Soit 4 faces (le premier 4) , suivi des 4 degrées des 4 faces séquentiellement énumérées (les 4x 4 suivants)

Ces 5 entiers peuvent même être compactés de la sorte **EN UN SEUL OCTET** en utilisant ce compactage en mode binaire

* degree = 7 : 1 suivi de 7 bits indiquant si les 7 faces énumérées sont triangulaires (bit à 0) ou des quadrilatères ( bit à 1)
* degree = 6 !: 01 suivi de 6 bits indiquant si les 6 faces énumérées sont triangulaires (bit à 0) ou des quadrilatères ( bit à 1)
* degree = 5 : 001 suivi de 5 bits indiquant si les 5 faces énumérées sont triangulaires (bit à 0) ou des quadrilatères ( bit à 1)
* degree = 4 : 0001 suivi de 4 bits indiquant si les 4 faces énumérées sont triangulaires (bit à 0) ou des quadrilatères ( bit à 1)
* degree = 3 : 00001 suivi de 3 bits indiquant si les 3 faces énumérées sont triangulaires (bit à 0) ou des quadrilatères ( bit à 1)
* degree = 2 : 000001 suivi de 2 bits indiquant si les 2 faces énumérées sont triangulaires (bit à 0) ou des quadrilatères ( bit à 1)
* degree = 1 : 0000001 suivi de 1 bit indiquant si la face énumérée est triangulaires (bit à 0) ou un quadrilatère ( bit à 1)
* degree = 0 : 00000000 iindiquant que ce sommet ne contient aucune information sur la connectivité

Dans l'exemple basique du maillage de 2x2 carrés, ceci ne génère donc qu'une simple valeur binaire 0001(4 faces énumérées) 1111(chacune des 4 faces est un quadrilatère), **SOIT UN SEUL OCTET** pour coder la connectivité d'un maillage de 2x2 quadrilatères = 9 sommets !!!!!
(pour l'instant, cela nécessite 8 octets de plus = 0 à la suite pour coder la connectivité/degrées des 8 derniers sommets suivants mais ils pourraient très bien être automatiquement générés, donc non sauvegardés, lorsque l'on rencontre le signal EOF indiquant que l'on arrive en fin de fichier par exemple)

Je viens de commencer un embryon de programme permettant de décoder ce style d'énumérations en une suite ordonnée de triangles utilisant une suite ordonnée des sommets selon un ordre en spirale, et pense ensuite passer à la partie encodage par la suite, une fois la partie décodage sera totalement terminée

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 
#include <stdio.h>
#include <stdlib.h>
 
 
int v0 = 0;
int nV = 0;
 
 
void PrintTriangle( int v0, int v1, int v2 )
{
	printf("\tTriangle(v%d, v%d, v%d) \n", v0, v1, v2); 
}
 
void PrintByte( unsigned char byte )
{
	for( int i = 0 ; i < 8 ; i++ )
	{
		if ( byte & (0x80 >> i) )
		{
			printf("1");
		}
		else
		{
			printf("0");
		} 
	}
}
 
int AnalyseLine( char *line )
{
	int degrees, degree;
	unsigned char flag, flag1; 
 
	printf("%s",line);
 
	if( line[0] != '#' )
	{
		degrees = line[0] - '0';
 
		flag = (degrees ? 0x80 >> (7-degrees) : 0 );
		flag1 = flag >> 1;
 
		for ( int i = 1 ; i <= degrees ; i++, flag1 >>= 1 )
		{
			degree = line[i] - '0';
 
			if ( degree == 4 )
			{
				flag |= flag1;
			}
 
 
			degree -= 2;
 
 
			for ( int j = 1 ; j <= degree ; j++)
			{
				if ( (i != degrees) || (j != degree) )
				{ 				
					PrintTriangle( v0, nV+1, nV+2) ; 
					nV++;
				}
				else
				{
					PrintTriangle( v0, nV+1, v0+1);
				}
			}
 
			// printf("\n");
		}
 
		printf("\n\tDegrees[v%d] =  0b", v0);
		PrintByte(flag);
		printf("\n");
 
		v0++;
	}
}
 
 
int main( int argc, char **argv)
{
	char line[1024];
    	FILE *fp;
 
	if ( (fp = fopen( argv[1] ,"r")) == NULL )
	{
		// Cannot open the file :( 
        	return 1;
    	}
 
    	while ( !feof( fp ) )
	{ 
		if( fgets(line,1024,fp) )
		{
        		AnalyseLine(line);	
		}
    	}
 
	for ( int v = v0 + 1 ; v <= nV + 1 ; v++ )
	{
		printf("\tDegrees[v%d] =  0b", v);
		PrintByte(0);
		printf("\n");
	}
 
    	return 0;
}

Et qui me génère ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
yannoo@cyclone ~/Dev/Facets $ ./degrees 4quads.deg
#*this is a window of 4 quads
44444
	Triangle(v0, v1, v2) 
	Triangle(v0, v2, v3) 
	Triangle(v0, v3, v4) 
	Triangle(v0, v4, v5) 
	Triangle(v0, v5, v6) 
	Triangle(v0, v6, v7) 
	Triangle(v0, v7, v8) 
	Triangle(v0, v8, v1) 
 
	Degrees[v0] =  0b00011111
#*end
	Degrees[v2] =  0b00000000
	Degrees[v3] =  0b00000000
	Degrees[v4] =  0b00000000
	Degrees[v5] =  0b00000000
	Degrees[v6] =  0b00000000
	Degrees[v7] =  0b00000000
	Degrees[v8] =  0b00000000

Mais qui peut générer ceci pour une énumération un peu plus longue d'un maillage de 3x3 quads (16 sommets)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
yannoo@cyclone ~/Dev/Facets $ ./degrees 9quads.deg
# an array 3x3 quads
44444
	Triangle(v0, v1, v2) 
	Triangle(v0, v2, v3) 
	Triangle(v0, v3, v4) 
	Triangle(v0, v4, v5) 
	Triangle(v0, v5, v6) 
	Triangle(v0, v6, v7) 
	Triangle(v0, v7, v8) 
	Triangle(v0, v8, v1) 
 
	Degrees[v0] =  0b00011111
244
	Triangle(v1, v8, v9) 
	Triangle(v1, v9, v10) 
	Triangle(v1, v10, v11) 
	Triangle(v1, v11, v2) 
 
	Degrees[v1] =  0b00000111
244
	Triangle(v2, v11, v12) 
	Triangle(v2, v12, v13) 
	Triangle(v2, v13, v14) 
	Triangle(v2, v14, v3) 
 
	Degrees[v2] =  0b00000111
14
	Triangle(v3, v14, v15) 
	Triangle(v3, v15, v4) 
 
	Degrees[v3] =  0b00000011
# end
	Degrees[v5] =  0b00000000
	Degrees[v6] =  0b00000000
	Degrees[v7] =  0b00000000
	Degrees[v8] =  0b00000000
	Degrees[v9] =  0b00000000
	Degrees[v10] =  0b00000000
	Degrees[v11] =  0b00000000
	Degrees[v12] =  0b00000000
	Degrees[v13] =  0b00000000
	Degrees[v14] =  0b00000000
	Degrees[v15] =  0b00000000

Et on peut bien sûr y mélanger des triangles et des quadrilatères, un quandrillataire n'étant après tout que 2 triangles ayant leur hypothénuse commune

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
yannoo@cyclone ~/Dev/Facets $ ./degrees TriQuads.deg
43434
	Triangle(v0, v1, v2) 
	Triangle(v0, v2, v3) 
	Triangle(v0, v3, v4) 
	Triangle(v0, v4, v5) 
	Triangle(v0, v5, v6) 
	Triangle(v0, v6, v1) 
 
	Degrees[v0] =  0b00010101
43343
	Triangle(v1, v6, v7) 
	Triangle(v1, v7, v8) 
	Triangle(v1, v8, v9) 
	Triangle(v1, v9, v10) 
	Triangle(v1, v10, v2) 
 
	Degrees[v1] =  0b00010010
3433
	Triangle(v2, v10, v11) 
	Triangle(v2, v11, v12) 
	Triangle(v2, v12, v13) 
	Triangle(v2, v13, v3) 
 
	Degrees[v2] =  0b00001100
0
 
	Degrees[v3] =  0b00000000
13
	Triangle(v4, v13, v5) 
 
	Degrees[v4] =  0b00000010
0
 
	Degrees[v5] =  0b00000000
0
 
	Degrees[v6] =  0b00000000
0
 
	Degrees[v7] =  0b00000000
0
 
	Degrees[v8] =  0b00000000
13
	Triangle(v9, v13, v10) 
 
	Degrees[v9] =  0b00000010
0
 
	Degrees[v10] =  0b00000000
0
 
	Degrees[v11] =  0b00000000
0
 
	Degrees[v12] =  0b00000000
0
 
	Degrees[v13] =  0b00000000
0
 
	Degrees[v14] =  0b00000000
0
 
	Degrees[v15] =  0b00000000