如何在C++中识别3D多边形中完全冗余的共面三角形？

针对3D场景中跨多个共面三角形的冗余面问题，核心思路是将3D共面问题转化为2D区域覆盖分析，以下是分步可行方案：

1. 共面三角形分组 #

首先将所有三角形按平面分组，解决浮点误差下的共面判断：

• 对每个三角形计算归一化平面方程 ax + by + cz + d = 0：通过三角形两条边叉乘得到法向量，归一化后代入任意顶点得到d值；
• 定义全局浮点容差（如const double EPS = 1e-6），比较两个平面的a、b、c、d值，若差值均在容差范围内则判定为共面；
• 可选：若场景为单面渲染，需额外校验法向量方向一致性，避免将正反平面误判为共面。

2. 共面组的2D投影 #

将3D共面三角形投影到2D平面简化计算：

• 选择平面法向量中绝对值最大的分量，确定投影轴：例如法向量x分量最大时，投影到y-z平面（丢弃x坐标），避免投影拉伸导致的数值误差；
• 将每个三角形的3D顶点转换为对应2D坐标，保留原三角形的索引关联。

3. 构建共面区域的合并面域 #

将零散共面三角形合并为连续的2D面域（含外边界与内洞）：

• 三角网合并法：遍历共面组内的三角形，合并共享边的相邻三角形，逐步形成更大的多边形；
• 扫描线法：将所有三角形的边按投影坐标排序，扫描过程中记录区域的边界变化，构建完整面域；
• 所有边重合判断需加入浮点容差，例如两点距离小于EPS则视为重合。

4. 冗余三角形的判定 #

对目标三角形（如引发Z-fighting的红色三角形），通过2D分析判断是否被完全包含：

• 点-in-多边形测试：取三角形的三个顶点，用射线法判断是否均在合并面域内部（含边界，容差校验），同时确认三角形所有边均在面域内部或边界上；
• 面积交比法：计算三角形面积，再计算其与合并面域的交集面积，若交集面积与原三角形面积的差值在容差范围内，则判定为完全被包含；
• 特殊处理：若存在互相覆盖的三角形，需根据原始多边形的归属（如并集结果的源多边形）保留有效面，避免误删。

5. C++实现关键代码片段 #

平面定义与共面判断 #

#include <vector>
#include <cmath>
#include <unordered_map>

const double EPS = 1e-6;

struct Vec3 {
    double x, y, z;
    Vec3 operator-(const Vec3& other) const {
        return {x - other.x, y - other.y, z - other.z};
    }
    double length() const {
        return sqrt(x*x + y*y + z*z);
    }
};

Vec3 cross(const Vec3& v1, const Vec3& v2) {
    return {
        v1.y*v2.z - v1.z*v2.y,
        v1.z*v2.x - v1.x*v2.z,
        v1.x*v2.y - v1.y*v2.x
    };
}

struct Triangle {
    Vec3 p0, p1, p2;
    bool isRedundant = false; // 标记是否为冗余面
};

struct Plane {
    double a, b, c, d;
    Plane(const Triangle& tri) {
        Vec3 v1 = tri.p1 - tri.p0;
        Vec3 v2 = tri.p2 - tri.p0;
        Vec3 normal = cross(v1, v2);
        double len = normal.length();
        if (len < EPS) { // 跳过退化三角形
            a = b = c = d = 0;
            return;
        }
        a = normal.x / len;
        b = normal.y / len;
        c = normal.z / len;
        d = -(a * tri.p0.x + b * tri.p0.y + c * tri.p0.z);
        // 统一法向量方向（可选）
        if (d < 0) {
            a = -a; b = -b; c = -c; d = -d;
        }
    }
    bool isCoplanar(const Plane& other) const {
        return fabs(a - other.a) < EPS &&
               fabs(b - other.b) < EPS &&
               fabs(c - other.c) < EPS &&
               fabs(d - other.d) < EPS;
    }
};

// 共面三角形分组
std::unordered_map<size_t, std::vector<Triangle*>> groupCoplanarTriangles(std::vector<Triangle>& triangles) {
    std::unordered_map<size_t, std::vector<Triangle*>> groups;
    std::vector<Plane> planes;
    for (auto& tri : triangles) {
        Plane p(tri);
        bool found = false;
        for (size_t i = 0; i < planes.size(); ++i) {
            if (p.isCoplanar(planes[i])) {
                groups[i].push_back(&tri);
                found = true;
                break;
            }
        }
        if (!found) {
            planes.push_back(p);
            groups[planes.size()-1].push_back(&tri);
        }
    }
    return groups;
}

内容的提问来源于stack exchange，提问作者KiraHoneybee