求助：Sutherland-Hodgman算法实现异常问题排查

我完全理解你在本科论文物理引擎中遇到这个问题的挫败感——碰撞检测的细节很容易出错，尤其是Sutherland-Hodgman这种依赖精确几何判断的算法。结合你的代码和示例输入输出，我梳理出几个核心问题，以及对应的修复方案：

1. InsideEdge函数的方向一致性问题 #

你的InsideEdge函数通过叉乘判断点是否在裁剪边内侧，但叉乘的符号完全取决于裁剪多边形的顶点顺序（顺时针/逆时针）。如果你的裁剪多边形是顺时针定义的（比如示例中的正方形[(2.0,2.0),(2.0,-2.0),(-2.0,-2.0),(-2.0,2.0)]），当前的返回条件(one - two) < 0可能刚好把内侧判断反了。

修复方法：先确认裁剪多边形的顶点顺序，然后调整叉乘的符号判断。比如用一个已知在内部的点（如示例中的(0,0)）测试，确保返回true时表示点在裁剪区域内侧。

修复后的InsideEdge函数：

bool SAT::InsideEdge(double px, double py, double edgeMaxX, double edgeMaxY, double edgeMinX, double edgeMinY) {
    // 计算向量 edgeMin->edgeMax 和 edgeMin->p 的叉乘
    // 叉乘结果的符号表示点相对于边的位置
    double crossProduct = (edgeMaxX - edgeMinX) * (py - edgeMinY) - (edgeMaxY - edgeMinY) * (px - edgeMinX);
    // 调整符号确保返回true时为内侧，用已知内部点验证后再确定最终符号
    return crossProduct > 0; 
}

2. Sutherland-Hodgman算法的数组复用错误 #

你的代码在处理单个裁剪边时，复用了同一个newPoints数组，这会导致后续顶点处理时访问到已经被覆盖的新顶点，而不是上一轮裁剪后的完整顶点列表。比如当处理第v个顶点时，前面的newPoints[0..newSize-1]已经被修改，v+1可能指向这些新点，而非原始输入的顶点。

修复方法：使用两个独立的数组——一个保存当前输入的顶点，另一个保存裁剪后的输出顶点，避免覆盖。同时用局部变量跟踪每一轮的顶点数，不要依赖类成员变量（避免多次调用时的状态污染）。

修复后的SutherlandHodgman函数核心部分：

void SAT::SutherlandHodgman(std::vector<Vector3>& _clipped, const Vector3& normal, const Vector3* polyVertices, unsigned int polyVertexCount, const Vector3* clippingVertices, unsigned int clipVertexCount) {
    const unsigned maxPoints = 16;
    Vector3 inputPoints[maxPoints];
    Vector3 outputPoints[maxPoints];
    unsigned int currentVertexCount = polyVertexCount;

    // 初始化输入点为原始多边形顶点
    for (unsigned i = 0; i < currentVertexCount; i++) {
        inputPoints[i] = polyVertices[i];
    }

    for (unsigned edge = 0; edge < clipVertexCount; edge++) { // 遍历每个裁剪边
        unsigned int outputSize = 0;
        Vector3 edgeMin = clippingVertices[edge];
        Vector3 edgeMax = clippingVertices[(edge + 1) % clipVertexCount];

        for (unsigned v = 0; v < currentVertexCount; v++) { // 遍历当前输入的每个顶点
            Vector3 v1 = inputPoints[v];
            Vector3 v2 = inputPoints[(v + 1) % currentVertexCount];

            bool insideEdge1 = InsideEdge(v1[axes[0]], v1[axes[1]], edgeMax[axes[0]], edgeMax[axes[1]], edgeMin[axes[0]], edgeMin[axes[1]]);
            bool insideEdge2 = InsideEdge(v2[axes[0]], v2[axes[1]], edgeMax[axes[0]], edgeMax[axes[1]], edgeMin[axes[0]], edgeMin[axes[1]]);

            if (insideEdge1 && insideEdge2) {
                // 两个点都在内部，保留v2
                outputPoints[outputSize++] = v2;
            } else if (!insideEdge1 && insideEdge2) {
                // v1在外，v2在内，添加交点和v2
                outputPoints[outputSize++] = CalculateIntersection(v1, v2, axes, edgeMin, edgeMax);
                outputPoints[outputSize++] = v2;
            } else if (insideEdge1 && !insideEdge2) {
                // v1在内，v2在外，添加交点
                outputPoints[outputSize++] = CalculateIntersection(v1, v2, axes, edgeMin, edgeMax);
            }
            // 两个点都在外，不添加任何点
        }

        // 更新输入点为当前裁剪结果，准备下一轮裁剪
        currentVertexCount = outputSize;
        if (currentVertexCount == 0) break; // 多边形完全被裁剪，提前退出
        for (unsigned i = 0; i < currentVertexCount; i++) {
            inputPoints[i] = outputPoints[i];
        }
    }

    // 去重后添加到结果列表
    for (unsigned i = 0; i < currentVertexCount; i++) {
        VerifyVertex(_clipped, inputPoints[i]);
    }
}

3. 交点计算中t值的错误计算 #

你的交点计算代码中，percAcrossLine的逻辑完全错误——(x1 + X)/x2没有任何几何意义，这会导致第三个轴的分量计算错误，甚至可能影响交点的正确性。正确的做法是计算交点在v1-v2线段上的比例t，然后用t插值第三个轴的分量。

修复后的CalculateIntersection函数：

Vector3 SAT::CalculateIntersection(const Vector3& v1, const Vector3& v2, const unsigned int axes[2], const Vector3& edgeMin, const Vector3& edgeMax) {
    double x1 = v1[axes[0]], y1 = v1[axes[1]];
    double x2 = v2[axes[0]], y2 = v2[axes[1]];
    double x3 = edgeMin[axes[0]], y3 = edgeMin[axes[1]];
    double x4 = edgeMax[axes[0]], y4 = edgeMax[axes[1]];

    // 计算两条线段的交点（二维）
    double num = (x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4);
    double den = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
    if (fabs(den) < 1e-9) {
        // 线段平行，返回v1（或根据需求处理）
        return v1;
    }
    double X = num / den;
    double Y = ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)) / den;

    Vector3 intersection;
    intersection[axes[0]] = X;
    intersection[axes[1]] = Y;

    // 计算交点在v1-v2线段上的比例t
    double dx = x2 - x1;
    double dy = y2 - y1;
    double t;
    if (fabs(dx) > fabs(dy)) {
        t = (X - x1) / dx;
    } else {
        t = (Y - y1) / dy;
    }
    t = std::clamp(t, 0.0, 1.0); // 确保t在0-1之间，避免超出线段范围

    // 插值第三个轴的分量
    unsigned int thirdAxis = 3 - axes[0] - axes[1]; // 假设axes是0,1,2中的两个
    intersection[thirdAxis] = v1[thirdAxis] + t * (v2[thirdAxis] - v1[thirdAxis]);

    return intersection;
}

额外建议 #

• 给InsideEdge函数添加测试用例：用已知在裁剪区域内部和外部的点验证返回值，快速定位方向判断错误。
• 避免使用类成员变量numVertices和numEdges传递临时状态，改用函数参数，减少状态污染风险。
• 在交点计算中添加浮点数精度判断，避免除以零的情况。

按照这些修复方案，你的示例输入应该能得到正确的裁剪结果：[(2.0,1.0), (0.5,1.0), (0.5,2.0), (2.0,2.0)]。

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