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

[tbc92]

Je n'ai pas vu de question, mais peu importe. Juste une remarque sur cette portion de phrase : lorsque l'on rencontre le signal EOF indiquant que l'on arrive en fin de fichier par exemple
Attention, le signal EOF n'est qu'une séquence de 0 et de 1 parmi d'autres. Tu peux très bien avoir une séquence de 0 et de 1 qui soient dans ton fichier, et qui coïncide exactement avec ce EOF. Si mes lointains souvenirs sont bons, Pour un fichier ouvert en mode texte, on lit jusqu'à avoir cet EOF, et pour un fichier ouvert en mode binaire, on lit tant que Read renvoie quelque chose. Le système d'exploitation stocke quelque part dans la FAT la taille du fichier ... et c'est sur cette taille qu'il s'appuie pour stopper la lecture, pas sur le caractère EOF.

Si ton fichier contient des caractères '''non-affichables''', ce qui est ton cas, il n'est pas question d'ouvrir le fichier en mode texte.
Je me souviens de ce programme qui buggait de façon plus ou moins aléatoire, parce que le développeur ouvrait en mode texte un fichier contenant des caractères comme les tiens ... et donc dans certains cas, le programme ne lisait qu'une partie du fichier. Tout simplement parce qu'il y avait dans les données cette séquence de 0 et de 1 qui coïncidait avec ce caractère EOF. Quel soulagement ça avait été quand j'avais fini par débugger ça !

[yannoo95170]

Pas de problème, le fichier d'entrée est bien un simple fichier texte

Par exemple, pour le cas basique de 4 carrés accollés, il ne contient que 2 lignes de commentaires (1ère et dernière ligne ) et la ligne (celle du milieu) énumérant les 4 faces

Code :

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

1
2
3
4
 yannoo@cyclone ~/Dev/Facets $ cat 4quads.deg
#this is a window of 4 quads
44444
#end

=> effectivement, il faudra que je fasse attention avec ce qui est généré en sortie, qui n'est pour l'instant du texte généré sur la sortie standard via des printf() mais qu'il va falloir que je complète par des sorties dans des fichiers binaires pour l'énumération des degrés sous forme compactée, cf. les "Degrees[v] = 0bxxxxxxxx"
(ces listes seront encapsulées dans des structures de plus haut niveau qui contiendront la taille des listes incluses => ça ne devrait donc pas être un problème)

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
 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

Concernant la question, ce serait pour trouver l'algorithme de compression associé, cf. celui qui passerait d'une liste de triangles non ordonnés au "4444" dans cet exemple (ou au code binaire "0b00011111", éventuellement suivi d'une suite de 8 octets = 0 qui peut très facilement être oubliée si tableau des Degrees[] est initialisé à 0 en amont), algorithme qui est pour l'instant 100% effectué mentalement/manuellement, maintenant que l'algorithme de décompression m'est connu et me semble relativement efficace