Compression of triangles mesh

[The_Little_Body]

Hi,

I work actually about a triangle mesh compressor that give only a little more than 6 bits per triangle
(only the topologic part, not already the geometric part)

Think you than this style of triangle compression can efficicently to be used for to speed the input of larges triangles meshes
(this give very superiors results than BELR that use about 20+ bits per triangle and seem to approch the level of Zipper that uses about 5 bpt on average, at about 6 bpt with my scheme)

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <bitset>
#include <cstddef>

// Fonction pour lire un fichier .obj et extraire les faces
void readObjFile(const std::string &filename, std::vector<std::vector<int>> &faces) {
    std::ifstream file(filename);
    std::string line;

    while (std::getline(file, line)) {
        if (line.substr(0, 2) == "f ") {
            std::istringstream iss(line.substr(2));
            std::vector<int> face;
            int vertex;
            while (iss >> vertex) {
                face.push_back(vertex - 1); // Convertir en indice 0-based
            }
            faces.push_back(face);
        }
    }
}

// Fonction pour générer les tables L et R
void generateTables(const std::vector<std::vector<int>> &faces, std::vector<int> &L, std::vector<int> &R) {
    int num_corners = faces.size() * 3;
    L.resize(num_corners, -1);
    R.resize(num_corners, -1);

    std::map<std::pair<int, int>, std::pair<int, int>> edge_to_corners;

    // Initialiser edge_to_corners
    for (int i = 0; i < faces.size(); ++i) {
        for (int j = 0; j < 3; ++j) {
            int v1 = faces[i][j];
            int v2 = faces[i][(j + 1) % 3];
            edge_to_corners[{v1, v2}] = {i * 3 + j, i * 3 + ((j + 1) % 3)};
            edge_to_corners[{v2, v1}] = {i * 3 + ((j + 1) % 3), i * 3 + j};
        }
    }

    // Remplir la table R (cycle autour du sommet)
    for (int i = 0; i < faces.size(); ++i) {
        for (int j = 0; j < 3; ++j) {
            int corner_index = i * 3 + j;
            int next_corner_index = i * 3 + ((j + 1) % 3);
            R[corner_index] = next_corner_index;
        }
    }

    // Remplir la table L (corner opposé)
    for (int i = 0; i < faces.size(); ++i) {
        for (int j = 0; j < 3; ++j) {
            int v1 = faces[i][j];
            int v2 = faces[i][(j + 1) % 3];
            int corner_index = i * 3 + j;
            auto it = edge_to_corners.find({v2, v1});
            if (it != edge_to_corners.end() && it->second.first != corner_index) {
                L[corner_index] = it->second.first; // Corner opposé
            }
        }
    }
}

// Fonction pour compter les occurrences des incréments
std::map<int, int> countIncrementOccurrences(const std::vector<int> &L, const std::vector<int> &R) {
    std::map<int, int> totalCount;

    for (int i = 0; i < L.size(); ++i) {
        int incrementL = L[i] - i;
        totalCount[incrementL]++;

        int incrementR = R[i] - i;
        totalCount[incrementR]++;
    }

    return totalCount;
}

// Fonction pour créer un codage sur 2 bits pour les incréments fréquents
void create2BitEncoding(const std::map<int, int> &totalCount, std::map<int, std::string> &compactEncoding, std::vector<int> &frequentIncrements) {
    // Convertir les occurrences en un vecteur de paires pour le tri
    std::vector<std::pair<int, int>> sortedIncrements(totalCount.begin(), totalCount.end());
    std::sort(sortedIncrements.begin(), sortedIncrements.end(), [](const std::pair<int, int> &a, const std::pair<int, int> &b) { return a.second > b.second; });

    // Attribuer les codes sur 2 bits aux 3 incréments les plus fréquents
    compactEncoding[sortedIncrements[0].first] = "00";  // Le plus fréquent
    compactEncoding[sortedIncrements[1].first] = "01";  // Deuxième plus fréquent
    compactEncoding[sortedIncrements[2].first] = "10";  // Troisième plus fréquent
    frequentIncrements.push_back(sortedIncrements[0].first);
    frequentIncrements.push_back(sortedIncrements[1].first);
    frequentIncrements.push_back(sortedIncrements[2].first);
}

// Fonction pour encoder un tableau avec codage sur 2 bits
std::string encodeTable2Bit(const std::vector<int> &table, const std::map<int, std::string> &compactEncoding, std::vector<int> &exceptionIndices, std::vector<int> &exceptions) {
    std::string encoded;
    std::map<int, int> exceptionIndexMap;
    int currentExceptionIndex = 0;

    for (int i = 0; i < table.size(); ++i) {
        int increment = table[i] - i;
        if (compactEncoding.find(increment) != compactEncoding.end()) {
            encoded += compactEncoding.at(increment);
        } else {
            // Ajouter l'incrément à la liste des exceptions s'il n'y est pas déjà
            if (exceptionIndexMap.find(increment) == exceptionIndexMap.end()) {
                exceptionIndexMap[increment] = currentExceptionIndex++;
                exceptions.push_back(increment);
            }
            // Utiliser un code spécial pour indiquer une exception (par exemple, "11")
            encoded += "11";
            exceptionIndices.push_back(exceptionIndexMap[increment]);
        }
    }
    return encoded;
}

// Fonction pour décoder une chaîne binaire avec codage sur 2 bits
std::vector<int> decodeTable2Bit(const std::string &encoded, const std::map<std::string, int> &compactDecoding, const std::vector<int> &exceptionIndices, const std::vector<int> &exceptions) {
    std::vector<int> decoded;
    int currentIndex = 0;
    int exceptionPos = 0;

    for (size_t pos = 0; pos < encoded.size(); pos += 2) {
        if (pos + 2 > encoded.size()) {
            break; // Éviter de dépasser la taille de la chaîne
        }
        std::string code = encoded.substr(pos, 2);
        if (code == "11") {
            // Cas exceptionnel : utiliser l'index de l'exception
            if (exceptionPos < exceptionIndices.size() && exceptionIndices[exceptionPos] < exceptions.size()) {
                int increment = exceptions[exceptionIndices[exceptionPos]];
                decoded.push_back(currentIndex + increment);
                exceptionPos++;
            } else {
                std::cerr << "Erreur: Index d'exception hors limites" << std::endl;
            }
        } else {
            // Cas normal : utiliser le dictionnaire de décodage
            if (compactDecoding.find(code) != compactDecoding.end()) {
                int increment = compactDecoding.at(code);
                decoded.push_back(currentIndex + increment);
            } else {
                std::cerr << "Erreur: Code non reconnu: " << code << std::endl;
            }
        }
        currentIndex++;
    }
    return decoded;
}

// Fonction pour afficher les détails du codage
void printEncodingDetails(const std::vector<int> &table, const std::map<int, std::string> &compactEncoding, const std::vector<int> &exceptionIndices, const std::vector<int> &exceptions, const std::string &tableName) {
    std::cout << "\nDétails du codage sur 2 bits pour " << tableName << " : " << std::endl;
    int exceptionPos = 0;
    for (int i = 0; i < table.size(); ++i) {
        int increment = table[i] - i;
        if (compactEncoding.find(increment) != compactEncoding.end()) {
            std::cout << "Indice " << i << " : c" << table[i] << " (c" << (increment >= 0 ? "+" : "") << increment << ") -> "
                      << compactEncoding.at(increment) << std::endl;
        } else {
            if (exceptionPos < exceptionIndices.size()) {
                std::cout << "Indice " << i << " : c" << table[i] << " (c" << (increment >= 0 ? "+" : "") << increment << ") -> "
                          << "11 (exception index: " << exceptionIndices[exceptionPos] << ")" << std::endl;
                exceptionPos++;
            } else {
                std::cerr << "Erreur: Pas assez d'indices d'exceptions" << std::endl;
            }
        }
    }
}

// Fonction pour afficher les statistiques de compression
void printCompressionStats(const std::string &encoded, const std::vector<int> &table, const std::string &tableName) {
    int originalSizeBits = table.size() * 32; // Chaque int occupe 32 bits
    float compressionRate = (float)encoded.size() / originalSizeBits * 100;

    std::cout << "\nChaîne binaire encodée pour " << tableName << " : " << encoded << std::endl;
    std::cout << "Longueur de la chaîne binaire : " << encoded.size() << " bits (au lieu de " << originalSizeBits << " bits)" << std::endl;
    std::cout << "Taux de compression par rapport aux indices non compressés : " << compressionRate << "%" << std::endl;
}

// Fonction pour afficher la table des exceptions
void printExceptionTable(const std::vector<int> &exceptions) {
    std::cout << "\nTable des exceptions : " << std::endl;
    for (size_t i = 0; i < exceptions.size(); ++i) {
        std::cout << "Index " << i << " : c" << (exceptions[i] >= 0 ? "+" : "") << exceptions[i] << std::endl;
    }
}

int main(int argc, char* argv[]) {
    if (argc != 2) {
        std::cerr << "Usage: " << argv[0] << " <fichier.obj>" << std::endl;
        return 1;
    }

    std::string filename = argv[1];
    std::vector<std::vector<int>> faces;
    readObjFile(filename, faces);

    std::vector<int> L, R;
    generateTables(faces, L, R);

    // Compter les occurrences des incréments
    std::map<int, int> totalCount = countIncrementOccurrences(L, R);

    // Afficher les occurrences des incréments
    std::cout << "Occurrences des incréments (trié par fréquence) :" << std::endl;
    std::vector<std::pair<int, int>> sortedIncrements(totalCount.begin(), totalCount.end());
    std::sort(sortedIncrements.begin(), sortedIncrements.end(), [](const std::pair<int, int> &a, const std::pair<int, int> &b) { return a.second > b.second; });
    for (const auto &entry : sortedIncrements) {
        std::cout << "c" << (entry.first >= 0 ? "+" : "") << entry.first << " : " << entry.second << " fois" << std::endl;
    }

    // Créer un codage sur 2 bits pour les incréments fréquents
    std::map<int, std::string> compactEncoding;
    std::vector<int> frequentIncrements;
    create2BitEncoding(totalCount, compactEncoding, frequentIncrements);

    // Affichage du dictionnaire de codage sur 2 bits
    std::cout << "\nDictionnaire de codage sur 2 bits : " << std::endl;
    for (const auto &entry : compactEncoding) {
        std::cout << "c" << (entry.first >= 0 ? "+" : "") << entry.first << " -> " << entry.second << std::endl;
    }

    // Encodage et affichage des détails pour L[]
    std::vector<int> exceptionIndicesL, exceptionsL;
    std::string encodedL = encodeTable2Bit(L, compactEncoding, exceptionIndicesL, exceptionsL);
    printEncodingDetails(L, compactEncoding, exceptionIndicesL, exceptionsL, "L[]");
    printCompressionStats(encodedL, L, "L[]");

    // Encodage et affichage des détails pour R[]
    std::vector<int> exceptionIndicesR, exceptionsR;
    std::string encodedR = encodeTable2Bit(R, compactEncoding, exceptionIndicesR, exceptionsR);
    printEncodingDetails(R, compactEncoding, exceptionIndicesR, exceptionsR, "R[]");
    printCompressionStats(encodedR, R, "R[]");

    // Fusionner les exceptions de L[] et R[]
    std::vector<int> allExceptions = exceptionsL;
    for (int exception : exceptionsR) {
        if (std::find(allExceptions.begin(), allExceptions.end(), exception) == allExceptions.end()) {
            allExceptions.push_back(exception);
        }
    }

    // Afficher la table des exceptions unifiée
    printExceptionTable(allExceptions);

    // Taux de compression global
    int totalEncodedBits = encodedL.size() + encodedR.size();
    int totalOriginalBits = L.size() * 32 + R.size() * 32; // 32 bits par int
    float globalCompressionRate = (float)totalEncodedBits / totalOriginalBits * 100;

    std::cout << "\nCompression globale : " << totalEncodedBits << " bits (au lieu de " << totalOriginalBits << " bits)" << std::endl;
    std::cout << "Taux de compression global par rapport aux indices non compressés : " << globalCompressionRate << "%" << std::endl;

    // Comparaison avec une représentation naïve (3 ints × nombre de triangles)
    int naiveSizeBits = (L.size() / 3) * 96; // 3 ints × 32 bits × nombre de triangles
    float naiveCompressionRate = (float)totalEncodedBits / naiveSizeBits * 100;

    std::cout << "\nComparaison avec une représentation naïve (3 ints × nombre de triangles) : " << std::endl;
    std::cout << "Taille naïve : " << naiveSizeBits << " bits" << std::endl;
    std::cout << "Taux de compression par rapport à la représentation naïve : " << naiveCompressionRate << "%" << std::endl;

    // Créer les dictionnaires de décodage
    std::map<std::string, int> compactDecoding;
    for (const auto &entry : compactEncoding) {
        compactDecoding[entry.second] = entry.first;
    }

    // Décodage pour vérifier la cohérence
    std::vector<int> decodedL = decodeTable2Bit(encodedL, compactDecoding, exceptionIndicesL, allExceptions);
    std::vector<int> decodedR = decodeTable2Bit(encodedR, compactDecoding, exceptionIndicesR, allExceptions);

    // Vérification que les tableaux décodés correspondent aux originaux
    bool correctL = (L == decodedL);
    bool correctR = (R == decodedR);
    std::cout << "\nVérification du décodage : " << (correctL && correctR ? "Succès ✅" : "Échec ❌") << std::endl;

    return 0;
}

This give this for a basic cube for example

annoo@yannoo-ThinkCentre-M710q:~/Dev/LR2$ ./lr2 cube.obj
Occurrences des incréments (trié par fréquence) :
c+1 : 45 fois
c-2 : 15 fois
c+10 : 4 fois
c+18 : 2 fois
c+13 : 1 fois
c+14 : 1 fois
c+15 : 1 fois
c+21 : 1 fois
c+23 : 1 fois
c+26 : 1 fois

Dictionnaire de codage sur 2 bits : 
c-2 -> 01
c+1 -> 00
c+10 -> 10

Détails du codage sur 2 bits pour L[] : 
Indice 0 : c13 (c+13) -> 11 (exception index: 0)
Indice 1 : c19 (c+18) -> 11 (exception index: 1)
Indice 2 : c3 (c+1) -> 00
Indice 3 : c4 (c+1) -> 00
Indice 4 : c25 (c+21) -> 11 (exception index: 2)
Indice 5 : c31 (c+26) -> 11 (exception index: 3)
Indice 6 : c16 (c+10) -> 10
Indice 7 : c22 (c+15) -> 11 (exception index: 4)
Indice 8 : c9 (c+1) -> 00
Indice 9 : c10 (c+1) -> 00
Indice 10 : c28 (c+18) -> 11 (exception index: 1)
Indice 11 : c34 (c+23) -> 11 (exception index: 5)
Indice 12 : c13 (c+1) -> 00
Indice 13 : c23 (c+10) -> 10
Indice 14 : c15 (c+1) -> 00
Indice 15 : c16 (c+1) -> 00
Indice 16 : c17 (c+1) -> 00
Indice 17 : c31 (c+14) -> 11 (exception index: 6)
Indice 18 : c19 (c+1) -> 00
Indice 19 : c29 (c+10) -> 10
Indice 20 : c21 (c+1) -> 00
Indice 21 : c22 (c+1) -> 00
Indice 22 : c23 (c+1) -> 00
Indice 23 : c21 (c-2) -> 01
Indice 24 : c25 (c+1) -> 00
Indice 25 : c35 (c+10) -> 10
Indice 26 : c27 (c+1) -> 00
Indice 27 : c28 (c+1) -> 00
Indice 28 : c29 (c+1) -> 00
Indice 29 : c27 (c-2) -> 01
Indice 30 : c31 (c+1) -> 00
Indice 31 : c32 (c+1) -> 00
Indice 32 : c33 (c+1) -> 00
Indice 33 : c34 (c+1) -> 00
Indice 34 : c35 (c+1) -> 00
Indice 35 : c33 (c-2) -> 01

Chaîne binaire encodée pour L[] : 111100001111101100001111001000000011001000000001001000000001000000000001
Longueur de la chaîne binaire : 72 bits (au lieu de 1152 bits)
Taux de compression par rapport aux indices non compressés : 6.25%

Détails du codage sur 2 bits pour R[] : 
Indice 0 : c1 (c+1) -> 00
Indice 1 : c2 (c+1) -> 00
Indice 2 : c0 (c-2) -> 01
Indice 3 : c4 (c+1) -> 00
Indice 4 : c5 (c+1) -> 00
Indice 5 : c3 (c-2) -> 01
Indice 6 : c7 (c+1) -> 00
Indice 7 : c8 (c+1) -> 00
Indice 8 : c6 (c-2) -> 01
Indice 9 : c10 (c+1) -> 00
Indice 10 : c11 (c+1) -> 00
Indice 11 : c9 (c-2) -> 01
Indice 12 : c13 (c+1) -> 00
Indice 13 : c14 (c+1) -> 00
Indice 14 : c12 (c-2) -> 01
Indice 15 : c16 (c+1) -> 00
Indice 16 : c17 (c+1) -> 00
Indice 17 : c15 (c-2) -> 01
Indice 18 : c19 (c+1) -> 00
Indice 19 : c20 (c+1) -> 00
Indice 20 : c18 (c-2) -> 01
Indice 21 : c22 (c+1) -> 00
Indice 22 : c23 (c+1) -> 00
Indice 23 : c21 (c-2) -> 01
Indice 24 : c25 (c+1) -> 00
Indice 25 : c26 (c+1) -> 00
Indice 26 : c24 (c-2) -> 01
Indice 27 : c28 (c+1) -> 00
Indice 28 : c29 (c+1) -> 00
Indice 29 : c27 (c-2) -> 01
Indice 30 : c31 (c+1) -> 00
Indice 31 : c32 (c+1) -> 00
Indice 32 : c30 (c-2) -> 01
Indice 33 : c34 (c+1) -> 00
Indice 34 : c35 (c+1) -> 00
Indice 35 : c33 (c-2) -> 01

Chaîne binaire encodée pour R[] : 000001000001000001000001000001000001000001000001000001000001000001000001
Longueur de la chaîne binaire : 72 bits (au lieu de 1152 bits)
Taux de compression par rapport aux indices non compressés : 6.25%

Table des exceptions : 
Index 0 : c+13
Index 1 : c+18
Index 2 : c+21
Index 3 : c+26
Index 4 : c+15
Index 5 : c+23
Index 6 : c+14

Compression globale : 144 bits (au lieu de 2304 bits)
Taux de compression global par rapport aux indices non compressés : 6.25%

Comparaison avec une représentation naïve (3 ints × nombre de triangles) : 
Taille naïve : 1152 bits
Taux de compression par rapport à la représentation naïve : 12.5%

Vérification du décodage : Succès ✅

Here, the file Cube.obj used

v -1.0 -1.0 -1.0
v  1.0 -1.0 -1.0
v  1.0  1.0 -1.0
v -1.0  1.0 -1.0
v -1.0 -1.0  1.0
v  1.0 -1.0  1.0
v  1.0  1.0  1.0
v -1.0  1.0  1.0

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

[The_Little_Body]

This give this for a more simple tetrahedron

yannoo@yannoo-ThinkCentre-M710q:~/Dev/LR2$ more tetra.obj
# Sommets
v 1.0 1.0 1.0
v -1.0 -1.0 1.0
v -1.0 1.0 -1.0
v 1.0 -1.0 -1.0

# Faces
f 1 2 3
f 2 1 4
f 1 3 4
f 2 4 3

yannoo@yannoo-ThinkCentre-M710q:~/Dev/LR2$ ./lr2 tetra.obj
Occurrences des incréments (trié par fréquence) :
c+1 : 12 fois
c-2 : 6 fois
c+4 : 3 fois
c+3 : 2 fois
c+10 : 1 fois

Dictionnaire de codage sur 2 bits : 
c-2 -> 01
c+1 -> 00
c+4 -> 10

Détails du codage sur 2 bits pour L[] : 
Indice 0 : c3 (c+3) -> 11 (exception index: 0)
Indice 1 : c11 (c+10) -> 11 (exception index: 1)
Indice 2 : c6 (c+4) -> 10
Indice 3 : c4 (c+1) -> 00
Indice 4 : c8 (c+4) -> 10
Indice 5 : c9 (c+4) -> 10
Indice 6 : c7 (c+1) -> 00
Indice 7 : c10 (c+3) -> 11 (exception index: 0)
Indice 8 : c6 (c-2) -> 01
Indice 9 : c10 (c+1) -> 00
Indice 10 : c11 (c+1) -> 00
Indice 11 : c9 (c-2) -> 01

Chaîne binaire encodée pour L[] : 111110001010001101000001
Longueur de la chaîne binaire : 24 bits (au lieu de 384 bits)
Taux de compression par rapport aux indices non compressés : 6.25%

Détails du codage sur 2 bits pour R[] : 
Indice 0 : c1 (c+1) -> 00
Indice 1 : c2 (c+1) -> 00
Indice 2 : c0 (c-2) -> 01
Indice 3 : c4 (c+1) -> 00
Indice 4 : c5 (c+1) -> 00
Indice 5 : c3 (c-2) -> 01
Indice 6 : c7 (c+1) -> 00
Indice 7 : c8 (c+1) -> 00
Indice 8 : c6 (c-2) -> 01
Indice 9 : c10 (c+1) -> 00
Indice 10 : c11 (c+1) -> 00
Indice 11 : c9 (c-2) -> 01

Chaîne binaire encodée pour R[] : 000001000001000001000001
Longueur de la chaîne binaire : 24 bits (au lieu de 384 bits)
Taux de compression par rapport aux indices non compressés : 6.25%

Table des exceptions : 
Index 0 : c+3
Index 1 : c+10

Compression globale : 48 bits (au lieu de 768 bits)
Taux de compression global par rapport aux indices non compressés : 6.25%

Comparaison avec une représentation naïve (3 ints × nombre de triangles) : 
Taille naïve : 384 bits
Taux de compression par rapport à la représentation naïve : 12.5%

Vérification du décodage : Succès ✅

[The_Little_Body]

I have a little reworked the code for to make it a little more lisible
(it use now tables Opposite and Next instead L and R)

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <bitset>
#include <cstddef>

// Fonction pour afficher la liste complète des corners
void printAllCorners(const std::vector<int> &Opposite, const std::vector<int> &Next) {
    std::cout << "Liste complète des corners : " << std::endl;
    for (int i = 0; i < Opposite.size(); ++i) {
        std::cout << "Corner " << i << " : Opposite = c" << Opposite[i] << ", Next = c" << Next[i] << std::endl;
    }
}

// Fonction pour lire un fichier .obj et extraire les faces
void readObjFile(const std::string &filename, std::vector<std::vector<int>> &faces) {
    std::ifstream file(filename);
    std::string line;

    while (std::getline(file, line)) {
        if (line.substr(0, 2) == "f ") {
            std::istringstream iss(line.substr(2));
            std::vector<int> face;
            int vertex;
            while (iss >> vertex) {
                face.push_back(vertex - 1); // Convertir en indice 0-based
            }
            faces.push_back(face);
        }
    }
}

// Fonction pour générer les tableaux Opposite et Next
void generateTables(const std::vector<std::vector<int>> &faces, std::vector<int> &Opposite, std::vector<int> &Next) {
    int num_corners = faces.size() * 3;
    Opposite.resize(num_corners, -1);
    Next.resize(num_corners, -1);

    std::map<std::pair<int, int>, std::pair<int, int>> edge_to_corners;

    // Initialiser edge_to_corners
    for (int i = 0; i < faces.size(); ++i) {
        for (int j = 0; j < 3; ++j) {
            int v1 = faces[i][j];
            int v2 = faces[i][(j + 1) % 3];
            edge_to_corners[{v1, v2}] = {i * 3 + j, i * 3 + ((j + 1) % 3)};
            edge_to_corners[{v2, v1}] = {i * 3 + ((j + 1) % 3), i * 3 + j};
        }
    }

    // Remplir le tableau Next (cycle autour du sommet)
    for (int i = 0; i < faces.size(); ++i) {
        for (int j = 0; j < 3; ++j) {
            int corner_index = i * 3 + j;
            int next_corner_index = i * 3 + ((j + 1) % 3);
            Next[corner_index] = next_corner_index;
        }
    }

    // Remplir le tableau Opposite (corner opposé)
    for (int i = 0; i < faces.size(); ++i) {
        for (int j = 0; j < 3; ++j) {
            int v1 = faces[i][j];
            int v2 = faces[i][(j + 1) % 3];
            int corner_index = i * 3 + j;
            auto it = edge_to_corners.find({v2, v1});
            if (it != edge_to_corners.end() && it->second.first != corner_index) {
                Opposite[corner_index] = it->second.first; // Corner opposé
            }
        }
    }
}

// Fonction pour compter les occurrences des incréments
std::map<int, int> countIncrementOccurrences(const std::vector<int> &Opposite, const std::vector<int> &Next) {
    std::map<int, int> totalCount;

    for (int i = 0; i < Opposite.size(); ++i) {
        int incrementOpposite = Opposite[i] - i;
        totalCount[incrementOpposite]++;

        int incrementNext = Next[i] - i;
        totalCount[incrementNext]++;
    }

    return totalCount;
}

// Fonction pour créer un codage sur 2 bits pour les incréments fréquents
void create2BitEncoding(const std::map<int, int> &totalCount, std::map<int, std::string> &compactEncoding, std::vector<int> &frequentIncrements) {
    // Convertir les occurrences en un vecteur de paires pour le tri
    std::vector<std::pair<int, int>> sortedIncrements(totalCount.begin(), totalCount.end());
    std::sort(sortedIncrements.begin(), sortedIncrements.end(), [](const std::pair<int, int> &a, const std::pair<int, int> &b) { return a.second > b.second; });

    // Attribuer les codes sur 2 bits aux 3 incréments les plus fréquents
    compactEncoding[sortedIncrements[0].first] = "00";  // Le plus fréquent
    compactEncoding[sortedIncrements[1].first] = "01";  // Deuxième plus fréquent
    compactEncoding[sortedIncrements[2].first] = "10";  // Troisième plus fréquent
    frequentIncrements.push_back(sortedIncrements[0].first);
    frequentIncrements.push_back(sortedIncrements[1].first);
    frequentIncrements.push_back(sortedIncrements[2].first);
}

// Fonction pour encoder un tableau avec codage sur 2 bits
std::string encodeTable2Bit(const std::vector<int> &table, const std::map<int, std::string> &compactEncoding, std::vector<int> &exceptionIndices, std::vector<int> &exceptions) {
    std::string encoded;
    std::map<int, int> exceptionIndexMap;
    int currentExceptionIndex = 0;

    for (int i = 0; i < table.size(); ++i) {
        int increment = table[i] - i;
        if (compactEncoding.find(increment) != compactEncoding.end()) {
            encoded += compactEncoding.at(increment);
        } else {
            // Ajouter l'incrément à la liste des exceptions s'il n'y est pas déjà
            if (exceptionIndexMap.find(increment) == exceptionIndexMap.end()) {
                exceptionIndexMap[increment] = currentExceptionIndex++;
                exceptions.push_back(increment);
            }
            // Utiliser un code spécial pour indiquer une exception (par exemple, "11")
            encoded += "11";
            exceptionIndices.push_back(exceptionIndexMap[increment]);
        }
    }
    return encoded;
}

// Fonction pour décoder une chaîne binaire avec codage sur 2 bits
std::vector<int> decodeTable2Bit(const std::string &encoded, const std::map<std::string, int> &compactDecoding, const std::vector<int> &exceptionIndices, const std::vector<int> &exceptions) {
    std::vector<int> decoded;
    int currentIndex = 0;
    int exceptionPos = 0;

    for (size_t pos = 0; pos < encoded.size(); pos += 2) {
        if (pos + 2 > encoded.size()) {
            break; // Éviter de dépasser la taille de la chaîne
        }
        std::string code = encoded.substr(pos, 2);
        if (code == "11") {
            // Cas exceptionnel : utiliser l'index de l'exception
            if (exceptionPos < exceptionIndices.size() && exceptionIndices[exceptionPos] < exceptions.size()) {
                int increment = exceptions[exceptionIndices[exceptionPos]];
                decoded.push_back(currentIndex + increment);
                exceptionPos++;
            } else {
                std::cerr << "Erreur: Index d'exception hors limites" << std::endl;
            }
        } else {
            // Cas normal : utiliser le dictionnaire de décodage
            if (compactDecoding.find(code) != compactDecoding.end()) {
                int increment = compactDecoding.at(code);
                decoded.push_back(currentIndex + increment);
            } else {
                std::cerr << "Erreur: Code non reconnu: " << code << std::endl;
            }
        }
        currentIndex++;
    }
    return decoded;
}

// Fonction pour afficher les détails du codage
void printEncodingDetails(const std::vector<int> &table, const std::map<int, std::string> &compactEncoding, const std::vector<int> &exceptionIndices, const std::vector<int> &exceptions, const std::string &tableName) {
    std::cout << "\nDétails du codage sur 2 bits pour " << tableName << " : " << std::endl;
    int exceptionPos = 0;
    for (int i = 0; i < table.size(); ++i) {
        int increment = table[i] - i;
        if (compactEncoding.find(increment) != compactEncoding.end()) {
            std::cout << "Indice " << i << " : c" << table[i] << " (c" << (increment >= 0 ? "+" : "") << increment << ") -> "
                      << compactEncoding.at(increment) << std::endl;
        } else {
            if (exceptionPos < exceptionIndices.size()) {
                std::cout << "Indice " << i << " : c" << table[i] << " (c" << (increment >= 0 ? "+" : "") << increment << ") -> "
                          << "11 (exception index: " << exceptionIndices[exceptionPos] << ")" << std::endl;
                exceptionPos++;
            } else {
                std::cerr << "Erreur: Pas assez d'indices d'exceptions" << std::endl;
            }
        }
    }
}

// Fonction pour afficher les statistiques de compression
void printCompressionStats(const std::string &encoded, const std::vector<int> &table, const std::string &tableName) {
    int originalSizeBits = table.size() * 32; // Chaque int occupe 32 bits
    float compressionRate = (float)encoded.size() / originalSizeBits * 100;

    std::cout << "\nChaîne binaire encodée pour " << tableName << " : " << encoded << std::endl;
    std::cout << "Longueur de la chaîne binaire : " << encoded.size() << " bits (au lieu de " << originalSizeBits << " bits)" << std::endl;
    std::cout << "Taux de compression par rapport aux indices non compressés : " << compressionRate << "%" << std::endl;
}

// Fonction pour afficher la table des exceptions
void printExceptionTable(const std::vector<int> &exceptions) {
    std::cout << "\nTable des exceptions : " << std::endl;
    for (size_t i = 0; i < exceptions.size(); ++i) {
        std::cout << "Index " << i << " : c" << (exceptions[i] >= 0 ? "+" : "") << exceptions[i] << std::endl;
    }
}

int main(int argc, char* argv[]) {
    if (argc != 2) {
        std::cerr << "Usage: " << argv[0] << " <fichier.obj>" << std::endl;
        return 1;
    }

    std::string filename = argv[1];
    std::vector<std::vector<int>> faces;
    readObjFile(filename, faces);

    std::vector<int> Opposite, Next;
    generateTables(faces, Opposite, Next);

    // Afficher la liste complète des corners
    printAllCorners(Opposite, Next);

    // Compter les occurrences des incréments
    std::map<int, int> totalCount = countIncrementOccurrences(Opposite, Next);

    // Afficher les occurrences des incréments
    std::cout << "\nOccurrences des incréments (trié par fréquence) :" << std::endl;
    std::vector<std::pair<int, int>> sortedIncrements(totalCount.begin(), totalCount.end());
    std::sort(sortedIncrements.begin(), sortedIncrements.end(), [](const std::pair<int, int> &a, const std::pair<int, int> &b) { return a.second > b.second; });
    for (const auto &entry : sortedIncrements) {
        std::cout << "c" << (entry.first >= 0 ? "+" : "") << entry.first << " : " << entry.second << " fois" << std::endl;
    }

    // Créer un codage sur 2 bits pour les incréments fréquents
    std::map<int, std::string> compactEncoding;
    std::vector<int> frequentIncrements;
    create2BitEncoding(totalCount, compactEncoding, frequentIncrements);

    // Affichage du dictionnaire de codage sur 2 bits
    std::cout << "\nDictionnaire de codage sur 2 bits : " << std::endl;
    for (const auto &entry : compactEncoding) {
        std::cout << "c" << (entry.first >= 0 ? "+" : "") << entry.first << " -> " << entry.second << std::endl;
    }

    // Encodage et affichage des détails pour Opposite[]
    std::vector<int> exceptionIndicesOpposite, exceptionsOpposite;
    std::string encodedOpposite = encodeTable2Bit(Opposite, compactEncoding, exceptionIndicesOpposite, exceptionsOpposite);
    printEncodingDetails(Opposite, compactEncoding, exceptionIndicesOpposite, exceptionsOpposite, "Opposite[]");
    printCompressionStats(encodedOpposite, Opposite, "Opposite[]");

    // Encodage et affichage des détails pour Next[]
    std::vector<int> exceptionIndicesNext, exceptionsNext;
    std::string encodedNext = encodeTable2Bit(Next, compactEncoding, exceptionIndicesNext, exceptionsNext);
    printEncodingDetails(Next, compactEncoding, exceptionIndicesNext, exceptionsNext, "Next[]");
    printCompressionStats(encodedNext, Next, "Next[]");

    // Fusionner les exceptions de Opposite[] et Next[]
    std::vector<int> allExceptions = exceptionsOpposite;
    for (int exception : exceptionsNext) {
        if (std::find(allExceptions.begin(), allExceptions.end(), exception) == allExceptions.end()) {
            allExceptions.push_back(exception);
        }
    }

    // Afficher la table des exceptions unifiée
    printExceptionTable(allExceptions);

    // Taux de compression global
    int totalEncodedBits = encodedOpposite.size() + encodedNext.size();
    int totalOriginalBits = Opposite.size() * 32 + Next.size() * 32; // 32 bits par int
    float globalCompressionRate = (float)totalEncodedBits / totalOriginalBits * 100;

    std::cout << "\nCompression globale : " << totalEncodedBits << " bits (au lieu de " << totalOriginalBits << " bits)" << std::endl;
    std::cout << "Taux de compression global par rapport aux indices non compressés : " << globalCompressionRate << "%" << std::endl;

    // Comparaison avec une représentation naïve (3 ints × nombre de triangles)
    int naiveSizeBits = (Opposite.size() / 3) * 96; // 3 ints × 32 bits × nombre de triangles
    float naiveCompressionRate = (float)totalEncodedBits / naiveSizeBits * 100;

    std::cout << "\nComparaison avec une représentation naïve (3 ints × nombre de triangles) : " << std::endl;
    std::cout << "Taille naïve : " << naiveSizeBits << " bits" << std::endl;
    std::cout << "Taux de compression par rapport à la représentation naïve : " << naiveCompressionRate << "%" << std::endl;

    // Créer les dictionnaires de décodage
    std::map<std::string, int> compactDecoding;
    for (const auto &entry : compactEncoding) {
        compactDecoding[entry.second] = entry.first;
    }

    // Décodage pour vérifier la cohérence
    std::vector<int> decodedOpposite = decodeTable2Bit(encodedOpposite, compactDecoding, exceptionIndicesOpposite, allExceptions);
    std::vector<int> decodedNext = decodeTable2Bit(encodedNext, compactDecoding, exceptionIndicesNext, allExceptions);

    // Vérification que les tableaux décodés correspondent aux originaux
    bool correctOpposite = (Opposite == decodedOpposite);
    bool correctNext = (Next == decodedNext);
    std::cout << "\nVérification du décodage : " << (correctOpposite && correctNext ? "Succès ✅" : "Échec ❌") << std::endl;

    return 0;
}

This give this for a tetrahedon

yannoo@yannoo-ThinkCentre-M710q:~/Dev/LR2$ ./lr2 tetra.obj
Liste complète des corners : 
Corner 0 : Opposite = c3, Next = c1
Corner 1 : Opposite = c11, Next = c2
Corner 2 : Opposite = c6, Next = c0
Corner 3 : Opposite = c4, Next = c4
Corner 4 : Opposite = c8, Next = c5
Corner 5 : Opposite = c9, Next = c3
Corner 6 : Opposite = c7, Next = c7
Corner 7 : Opposite = c10, Next = c8
Corner 8 : Opposite = c6, Next = c6
Corner 9 : Opposite = c10, Next = c10
Corner 10 : Opposite = c11, Next = c11
Corner 11 : Opposite = c9, Next = c9

Occurrences des incréments (trié par fréquence) :
c+1 : 12 fois
c-2 : 6 fois
c+4 : 3 fois
c+3 : 2 fois
c+10 : 1 fois

Dictionnaire de codage sur 2 bits : 
c-2 -> 01
c+1 -> 00
c+4 -> 10

Détails du codage sur 2 bits pour Opposite[] : 
Indice 0 : c3 (c+3) -> 11 (exception index: 0)
Indice 1 : c11 (c+10) -> 11 (exception index: 1)
Indice 2 : c6 (c+4) -> 10
Indice 3 : c4 (c+1) -> 00
Indice 4 : c8 (c+4) -> 10
Indice 5 : c9 (c+4) -> 10
Indice 6 : c7 (c+1) -> 00
Indice 7 : c10 (c+3) -> 11 (exception index: 0)
Indice 8 : c6 (c-2) -> 01
Indice 9 : c10 (c+1) -> 00
Indice 10 : c11 (c+1) -> 00
Indice 11 : c9 (c-2) -> 01

Chaîne binaire encodée pour Opposite[] : 111110001010001101000001
Longueur de la chaîne binaire : 24 bits (au lieu de 384 bits)
Taux de compression par rapport aux indices non compressés : 6.25%

Détails du codage sur 2 bits pour Next[] : 
Indice 0 : c1 (c+1) -> 00
Indice 1 : c2 (c+1) -> 00
Indice 2 : c0 (c-2) -> 01
Indice 3 : c4 (c+1) -> 00
Indice 4 : c5 (c+1) -> 00
Indice 5 : c3 (c-2) -> 01
Indice 6 : c7 (c+1) -> 00
Indice 7 : c8 (c+1) -> 00
Indice 8 : c6 (c-2) -> 01
Indice 9 : c10 (c+1) -> 00
Indice 10 : c11 (c+1) -> 00
Indice 11 : c9 (c-2) -> 01

Chaîne binaire encodée pour Next[] : 000001000001000001000001
Longueur de la chaîne binaire : 24 bits (au lieu de 384 bits)
Taux de compression par rapport aux indices non compressés : 6.25%

Table des exceptions : 
Index 0 : c+3
Index 1 : c+10

Compression globale : 48 bits (au lieu de 768 bits)
Taux de compression global par rapport aux indices non compressés : 6.25%

Comparaison avec une représentation naïve (3 ints × nombre de triangles) : 
Taille naïve : 384 bits
Taux de compression par rapport à la représentation naïve : 12.5%

Vérification du décodage : Succès ✅

And this for a cube

yannoo@yannoo-ThinkCentre-M710q:~/Dev/LR2$ ./lr2 cube.obj
Liste complète des corners : 
Corner 0 : Opposite = c13, Next = c1
Corner 1 : Opposite = c19, Next = c2
Corner 2 : Opposite = c3, Next = c0
Corner 3 : Opposite = c4, Next = c4
Corner 4 : Opposite = c25, Next = c5
Corner 5 : Opposite = c31, Next = c3
Corner 6 : Opposite = c16, Next = c7
Corner 7 : Opposite = c22, Next = c8
Corner 8 : Opposite = c9, Next = c6
Corner 9 : Opposite = c10, Next = c10
Corner 10 : Opposite = c28, Next = c11
Corner 11 : Opposite = c34, Next = c9
Corner 12 : Opposite = c13, Next = c13
Corner 13 : Opposite = c23, Next = c14
Corner 14 : Opposite = c15, Next = c12
Corner 15 : Opposite = c16, Next = c16
Corner 16 : Opposite = c17, Next = c17
Corner 17 : Opposite = c31, Next = c15
Corner 18 : Opposite = c19, Next = c19
Corner 19 : Opposite = c29, Next = c20
Corner 20 : Opposite = c21, Next = c18
Corner 21 : Opposite = c22, Next = c22
Corner 22 : Opposite = c23, Next = c23
Corner 23 : Opposite = c21, Next = c21
Corner 24 : Opposite = c25, Next = c25
Corner 25 : Opposite = c35, Next = c26
Corner 26 : Opposite = c27, Next = c24
Corner 27 : Opposite = c28, Next = c28
Corner 28 : Opposite = c29, Next = c29
Corner 29 : Opposite = c27, Next = c27
Corner 30 : Opposite = c31, Next = c31
Corner 31 : Opposite = c32, Next = c32
Corner 32 : Opposite = c33, Next = c30
Corner 33 : Opposite = c34, Next = c34
Corner 34 : Opposite = c35, Next = c35
Corner 35 : Opposite = c33, Next = c33

Occurrences des incréments (trié par fréquence) :
c+1 : 45 fois
c-2 : 15 fois
c+10 : 4 fois
c+18 : 2 fois
c+13 : 1 fois
c+14 : 1 fois
c+15 : 1 fois
c+21 : 1 fois
c+23 : 1 fois
c+26 : 1 fois

Dictionnaire de codage sur 2 bits : 
c-2 -> 01
c+1 -> 00
c+10 -> 10

Détails du codage sur 2 bits pour Opposite[] : 
Indice 0 : c13 (c+13) -> 11 (exception index: 0)
Indice 1 : c19 (c+18) -> 11 (exception index: 1)
Indice 2 : c3 (c+1) -> 00
Indice 3 : c4 (c+1) -> 00
Indice 4 : c25 (c+21) -> 11 (exception index: 2)
Indice 5 : c31 (c+26) -> 11 (exception index: 3)
Indice 6 : c16 (c+10) -> 10
Indice 7 : c22 (c+15) -> 11 (exception index: 4)
Indice 8 : c9 (c+1) -> 00
Indice 9 : c10 (c+1) -> 00
Indice 10 : c28 (c+18) -> 11 (exception index: 1)
Indice 11 : c34 (c+23) -> 11 (exception index: 5)
Indice 12 : c13 (c+1) -> 00
Indice 13 : c23 (c+10) -> 10
Indice 14 : c15 (c+1) -> 00
Indice 15 : c16 (c+1) -> 00
Indice 16 : c17 (c+1) -> 00
Indice 17 : c31 (c+14) -> 11 (exception index: 6)
Indice 18 : c19 (c+1) -> 00
Indice 19 : c29 (c+10) -> 10
Indice 20 : c21 (c+1) -> 00
Indice 21 : c22 (c+1) -> 00
Indice 22 : c23 (c+1) -> 00
Indice 23 : c21 (c-2) -> 01
Indice 24 : c25 (c+1) -> 00
Indice 25 : c35 (c+10) -> 10
Indice 26 : c27 (c+1) -> 00
Indice 27 : c28 (c+1) -> 00
Indice 28 : c29 (c+1) -> 00
Indice 29 : c27 (c-2) -> 01
Indice 30 : c31 (c+1) -> 00
Indice 31 : c32 (c+1) -> 00
Indice 32 : c33 (c+1) -> 00
Indice 33 : c34 (c+1) -> 00
Indice 34 : c35 (c+1) -> 00
Indice 35 : c33 (c-2) -> 01

Chaîne binaire encodée pour Opposite[] : 111100001111101100001111001000000011001000000001001000000001000000000001
Longueur de la chaîne binaire : 72 bits (au lieu de 1152 bits)
Taux de compression par rapport aux indices non compressés : 6.25%

Détails du codage sur 2 bits pour Next[] : 
Indice 0 : c1 (c+1) -> 00
Indice 1 : c2 (c+1) -> 00
Indice 2 : c0 (c-2) -> 01
Indice 3 : c4 (c+1) -> 00
Indice 4 : c5 (c+1) -> 00
Indice 5 : c3 (c-2) -> 01
Indice 6 : c7 (c+1) -> 00
Indice 7 : c8 (c+1) -> 00
Indice 8 : c6 (c-2) -> 01
Indice 9 : c10 (c+1) -> 00
Indice 10 : c11 (c+1) -> 00
Indice 11 : c9 (c-2) -> 01
Indice 12 : c13 (c+1) -> 00
Indice 13 : c14 (c+1) -> 00
Indice 14 : c12 (c-2) -> 01
Indice 15 : c16 (c+1) -> 00
Indice 16 : c17 (c+1) -> 00
Indice 17 : c15 (c-2) -> 01
Indice 18 : c19 (c+1) -> 00
Indice 19 : c20 (c+1) -> 00
Indice 20 : c18 (c-2) -> 01
Indice 21 : c22 (c+1) -> 00
Indice 22 : c23 (c+1) -> 00
Indice 23 : c21 (c-2) -> 01
Indice 24 : c25 (c+1) -> 00
Indice 25 : c26 (c+1) -> 00
Indice 26 : c24 (c-2) -> 01
Indice 27 : c28 (c+1) -> 00
Indice 28 : c29 (c+1) -> 00
Indice 29 : c27 (c-2) -> 01
Indice 30 : c31 (c+1) -> 00
Indice 31 : c32 (c+1) -> 00
Indice 32 : c30 (c-2) -> 01
Indice 33 : c34 (c+1) -> 00
Indice 34 : c35 (c+1) -> 00
Indice 35 : c33 (c-2) -> 01

Chaîne binaire encodée pour Next[] : 000001000001000001000001000001000001000001000001000001000001000001000001
Longueur de la chaîne binaire : 72 bits (au lieu de 1152 bits)
Taux de compression par rapport aux indices non compressés : 6.25%

Table des exceptions : 
Index 0 : c+13
Index 1 : c+18
Index 2 : c+21
Index 3 : c+26
Index 4 : c+15
Index 5 : c+23
Index 6 : c+14

Compression globale : 144 bits (au lieu de 2304 bits)
Taux de compression global par rapport aux indices non compressés : 6.25%

Comparaison avec une représentation naïve (3 ints × nombre de triangles) : 
Taille naïve : 1152 bits
Taux de compression par rapport à la représentation naïve : 12.5%

Vérification du décodage : Succès ✅

Note than the compression is only 12 bpt, not 6 bpt as say before
(48 / 4 = 144 / 12 = 12 bpt)

In fact, this seem only to be one form of compression/transformation of the O and V corners tables used in input by EdgeBreaker …