基于Bresenham算法的3D三角形内部采样点生成方法问询

看起来你已经搞定了3D三角形边界点的采样，但内部点的生成确实是个需要额外处理的环节。针对你的需求，我整理了两种实用的方法——一种是针对你例子里这种**平面三角形（所有点z值相同）**的高效扫描线算法，另一种是适用于任意3D三角形的通用重心坐标法，你可以根据场景选择。

方法1：扫描线填充算法（适合平面3D三角形） #

你的示例三角形属于XY平面上的三角形（z=0），用扫描线算法会非常高效，核心思路是逐行（固定y值）计算当前行在三角形内的左右x边界，然后在边界之间生成采样点。

实现步骤： #

• 排序顶点：把三个顶点按y坐标从小到大排序，得到V_bottom（y最小）、V_mid（y中间）、V_top（y最大）
• 计算边的斜率：分别计算V_bottom到V_top、V_bottom到V_mid、V_mid到V_top三条边的x随y变化的增量（步长用你的resSize）
• 逐行扫描：从V_bottom.y到V_top.y，每次步进resSize，对每一行y：
  • 计算当前y对应的左右x边界值
  • 在左右x之间，按resSize步进生成采样点，z值固定为三角形的z值

示例代码（C#风格）： #

void ScanlineFillTriangle(float x1, float y1, float z1, float x2, float y2, float z2, float x3, float y3, float z3, float resSize)
{
    // 按y坐标排序顶点
    var vertices = new List<(float x, float y, float z)> { (x1,y1,z1), (x2,y2,z2), (x3,y3,z3) };
    vertices.Sort((a, b) => a.y.CompareTo(b.y));
    var (vBotX, vBotY, vBotZ) = vertices[0];
    var (vMidX, vMidY, vMidZ) = vertices[1];
    var (vTopX, vTopY, vTopZ) = vertices[2];

    // 计算边的x增量（每步resSize的y变化对应的x变化）
    float GetXStep(float xStart, float yStart, float xEnd, float yEnd)
    {
        float dy = yEnd - yStart;
        if (Math.Abs(dy) < 1e-6) return 0; // 水平边，x无变化
        return (xEnd - xStart) * resSize / dy;
    }

    var stepLeft = GetXStep(vBotX, vBotY, vTopX, vTopY);
    var stepRight1 = GetXStep(vBotX, vBotY, vMidX, vMidY);
    var stepRight2 = GetXStep(vMidX, vMidY, vTopX, vTopY);

    float currentLeftX = vBotX;
    float currentRightX = vBotX;

    // 扫描下半部分（从vBot到vMid）
    for (float y = vBotY; y <= vMidY; y += resSize)
    {
        // 生成当前行的所有采样点
        for (float x = currentLeftX; x <= currentRightX; x += resSize)
        {
            Console.WriteLine($"{x}, {y}, {vBotZ}"); // 输出内部点
        }
        currentLeftX += stepLeft;
        currentRightX += stepRight1;
    }

    // 扫描上半部分（从vMid到vTop）
    currentRightX = vMidX;
    for (float y = vMidY + resSize; y <= vTopY; y += resSize)
    {
        for (float x = currentLeftX; x <= currentRightX; x += resSize)
        {
            Console.WriteLine($"{x}, {y}, {vBotZ}");
        }
        currentLeftX += stepLeft;
        currentRightX += stepRight2;
    }
}

方法2：重心坐标法（通用任意3D三角形） #

如果你的3D三角形处于任意平面（三个点必然共面，所以该方法适用于所有3D三角形），或者需要更通用的实现，重心坐标法是首选。核心逻辑是：三角形内的任意点都可以用三个顶点的加权和表示，权重（重心坐标）均非负且和为1。

实现步骤： #

• 计算三角形的包围盒：找到x、y、z的最小和最大值，确定采样范围
• 遍历包围盒内的候选点：按resSize步长遍历每个(x,y,z)候选点
• 计算重心坐标：通过向量运算计算候选点的重心坐标(u, v, w)
• 判断是否在内部：如果u≥0、v≥0、w≥0（允许微小误差，避免浮点精度问题），则该点是三角形内部点

示例代码（C#风格）： #

// 辅助函数：判断点是否在3D三角形内部
bool IsPointInTriangle(float px, float py, float pz,
                       float v1x, float v1y, float v1z,
                       float v2x, float v2y, float v2z,
                       float v3x, float v3y, float v3z)
{
    // 用Vector3简化向量运算，也可以手动实现
    Vector3 v1 = new Vector3(v1x, v1y, v1z);
    Vector3 v2 = new Vector3(v2x, v2y, v2z);
    Vector3 v3 = new Vector3(v3x, v3y, v3z);
    Vector3 p = new Vector3(px, py, pz);

    Vector3 v2v1 = v2 - v1;
    Vector3 v3v1 = v3 - v1;
    Vector3 pv1 = p - v1;

    // 计算重心坐标的分母（三角形面积的2倍）
    float dot00 = Vector3.Dot(v3v1, v3v1);
    float dot01 = Vector3.Dot(v3v1, v2v1);
    float dot02 = Vector3.Dot(v3v1, pv1);
    float dot11 = Vector3.Dot(v2v1, v2v1);
    float dot12 = Vector3.Dot(v2v1, pv1);

    float denom = dot00 * dot11 - dot01 * dot01;
    if (Math.Abs(denom) < 1e-6) return false; // 退化三角形（三点共线）

    // 计算重心坐标u和v，w = 1 - u - v
    float u = (dot11 * dot02 - dot01 * dot12) / denom;
    float v = (dot00 * dot12 - dot01 * dot02) / denom;
    float w = 1 - u - v;

    // 允许微小负数值，处理浮点精度误差
    const float epsilon = 1e-6;
    return u >= -epsilon && v >= -epsilon && w >= -epsilon;
}

// 生成3D三角形内部采样点
void Fill3DTriangleWithBarycentric(float v1x, float v1y, float v1z,
                                  float v2x, float v2y, float v2z,
                                  float v3x, float v3y, float v3z,
                                  float resSize)
{
    // 计算三角形的包围盒，缩小采样范围
    float minX = Math.Min(Math.Min(v1x, v2x), v3x);
    float maxX = Math.Max(Math.Max(v1x, v2x), v3x);
    float minY = Math.Min(Math.Min(v1y, v2y), v3y);
    float maxY = Math.Max(Math.Max(v1y, v2y), v3y);
    float minZ = Math.Min(Math.Min(v1z, v2z), v3z);
    float maxZ = Math.Max(Math.Max(v1z, v2z), v3z);

    // 遍历包围盒内所有候选点
    for (float x = minX; x <= maxX; x += resSize)
    {
        for (float y = minY; y <= maxY; y += resSize)
        {
            for (float z = minZ; z <= maxZ; z += resSize)
            {
                if (IsPointInTriangle(x, y, z, v1x, v1y, v1z, v2x, v2y, v2z, v3x, v3y, v3z))
                {
                    Console.WriteLine($"{x}, {y}, {z}"); // 输出内部采样点
                }
            }
        }
    }
}

注意事项： #

• 浮点精度问题：判断点是否在内部时，一定要加入epsilon（比如1e-6），避免因为计算误差把边缘点误判为外部点
• 性能差异：扫描线算法只针对平面三角形，性能更优；重心坐标法需要遍历包围盒内所有点，通用性强但对于大包围盒可能稍慢

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