简介

参考链接 https://gamedev.stackexchange.com/questions/26974/repairing-back-facing-triangles-without-user-input
缺陷, 对于非流形的网格会失败

code

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
struct triangle{
    int pv1;
    int pv2;
    int pv3;
    triangle(int pv1_, int pv2_, int pv3_):pv1(pv1_), pv2(pv2_), pv3(pv3_){};
    bool operator == (const triangle &rhs){
        return pv1 == rhs.pv1 && pv2 == rhs.pv2 && pv3 == rhs.pv3;
    }
    bool operator < (const triangle &rhs) {
        return (pv1 + pv2 + pv3) < (rhs.pv1 + rhs.pv2 + rhs.pv3);
    }
        bool operator < (const triangle &rhs) const {
        return (pv1 + pv2 + pv3) < (rhs.pv1 + rhs.pv2 + rhs.pv3);
    }
};
int pointNum;
int faceNum;
std::queue<int> triQ;
std::vector<bool> check;
std::vector<triangle> allTriangle;
std::map<int, std::vector<int> > mm;
// 检查a和b的公共边是否序列相等
bool isFlip(triangle b, int a1, int a2){
    if(b.pv1 == a1 && b.pv2 == a2){
        return true;
    }
    if(b.pv2 == a1 && b.pv3 == a2){
        return true;
    }
    if(b.pv3 == a1 && b.pv1 == a2){
        return true;
    }
    return false;
}
void fixFlip(triangle &a){
    int a1 = a.pv1;
    int a2 = a.pv2;
    int a3 = a.pv3;
    a.pv1 = a3;
    a.pv3 = a1;
}

/**
 * @description: 
 * @param {set<int> &s1, std::set<int>} &s2
 * @param {int} a1
 * @param {int} a2
 * @return 是否修复了, 或者除了一种情况两个三角形都是true的情况
 */
bool refine(std::set<int> &s1, std::set<int> &s2, int a1, int a2, int &falseTri){
    std::set<int> c;
    std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(c, c.begin()));
    if(c.size() != 2) { // 对于封闭的曲面而言是对的
        std::cout << "[ERROR] c size not equal 2 " << c.size() << "\n";
        return false;
    }
    std::vector<int> cv;
    for(auto it:c){
        cv.push_back(it);
    }
    int trueTri = -1;
    falseTri = -1;
    if(check[cv[0]] == true && check[cv[1]] == false){
        trueTri = cv[0];
        falseTri = cv[1];
    }
    else if(check[cv[0]] == false && check[cv[1]] == true) {
        trueTri = cv[1];
        falseTri = cv[0];
    }else{
        std::cout << "[DEBUG] maybe this two triangle is true??\n";
        return false;
    }
    if(falseTri != -1) {
        if(isFlip(allTriangle[falseTri], a1, a2)){
            fixFlip(allTriangle[falseTri]);
        }
    }
    return true;
}
void BFS(int i){
    check[i] = true;
    triQ.push(i);
    while(!triQ.empty()){
        int front = triQ.front();
        triQ.pop();
        triangle t = allTriangle[front];
        std::set<int> s1;
        std::set<int> s2;
        std::set<int> s3;
        std::set<int> c;
        for(auto it : mm[t.pv1]) {
            s1.insert(it);
        }
        for(auto it : mm[t.pv2]) {
            s2.insert(it);
        }
        for(auto it : mm[t.pv3]) {
            s3.insert(it);
        }
        int falseTri;
        if(refine(s1, s2, t.pv1, t.pv2, falseTri)){
            triQ.push(falseTri);
            check[falseTri] = true;
        }
        if(refine(s2, s3, t.pv2, t.pv3, falseTri)){
            triQ.push(falseTri);
            check[falseTri] = true;
        }
        if(refine(s3, s1, t.pv3, t.pv1, falseTri)){
            triQ.push(falseTri);
            check[falseTri] = true;
        }
    }
}
void BFSTraverse(){
    // 访问数组初始化
    for(int i=0; i<faceNum; i++){
        if(!check[i]){
            BFS(i);
        }
    }
}
int main() {
    std::string filename;
    filename = "test.off";
    std::string filenameOut;
    filenameOut = "testOut.off";
    std::ifstream iff = std::ifstream(filename.c_str(), std::ios::in);
    std::ofstream off = std::ofstream(filenameOut.c_str(), std::ios::out);
    // Write header
    off << "OFF" << std::endl;
    if (!off.good()) {
        std::cout << "[Error] Could not open file " << filenameOut << " for writing!" << std::endl;
        off.close();
        return false;
    }
    if(!iff.good()) {
        std::cout << "[ERROR] could not open file " << filename << " for reading!" << std::endl;
        iff.close();
        return false;
    }
    std::string line;
    getline(iff, line);
    if(line != "OFF") {
        std::cout << "[ERROR] format not supported" << std::endl;
        return false;
    }
    getline(iff, line);
    stringstream sstr;
    sstr.str(line);
    
    sstr >> pointNum;
    sstr >> faceNum;
    sstr.clear();

    off << line << "\n";
    for(int i=0; i<pointNum; i++){
        getline(iff, line);
        off << line << "\n";
    }
    
    
    std::map<triangle, int> mi;
    int tmp;
    int pv1;
    int pv2;
    int pv3;
    for(int i=0; i<faceNum; i++){
        getline(iff, line);
        sstr.str(line);
        sstr >> tmp;
        if(tmp != 3) {
            std::cout << "[ERROR] format not supported_" << std::endl;
            return false;
        }
        sstr >> pv1;
        sstr >> pv2;
        sstr >> pv3;
        triangle t(pv1, pv2, pv3);
        sstr.clear();
        mm[pv1].push_back(i);
        mm[pv2].push_back(i);
        mm[pv3].push_back(i);
        allTriangle.push_back(t);
        mi[t] = i;
    }
    check.resize(allTriangle.size(), false);
    BFSTraverse();
    for(auto it : allTriangle){
        off << "3 " << it.pv1 << " " << it.pv2 << " " << it.pv3 << "\n";
    }
    off.close();
    iff.close();
    return 0;
}