math - 截锥体剔除，实现

Question

我目前正在尝试（再次）为我的世界实施平截头体剔除。我的世界由大小为 16x256x16 (x, y, z) 的块组成：

Frustum frustum = Frustum(engine.proj * engine.view);

foreach(chunkc, chunk; chunks) {
    vec3i w_chunkc = vec3i(chunkc.x*16, chunkc.y*256, chunkc.z*16);

    AABB aabb = AABB(vec3(w_chunkc), vec3(w_chunkc.x+16, w_chunkc.y+256, w_chunkc.z+16));
    if(aabb in frustum) {
        bind(engine, chunk);

        glDrawArrays(GL_TRIANGLES, 0, cast(uint)chunk.vbo_vcount);
    }
}

chunkc保存整个chunk例如的坐标[0, 0, -2]。因此，要获得块边界框，我必须将这些坐标乘以每个块的大小以获得 AABB 的最小位置，并将大小添加到每个组件以获得最大值。AABB 的位置。然后我对照截锥体检查这个 AABB。

截锥实现：

struct Frustum {
    enum {
        LEFT, /// Used to access the planes array.
        RIGHT, /// ditto
        BOTTOM, /// ditto
        TOP, /// ditto
        NEAR, /// ditto
        FAR /// ditto
    }

    Plane[6] planes; /// Holds all 6 planes of the frustum.

    @safe pure nothrow:

    @property ref Plane left() { return planes[LEFT]; }
    @property ref Plane right() { return planes[RIGHT]; }
    @property ref Plane bottom() { return planes[BOTTOM]; }
    @property ref Plane top() { return planes[TOP]; }
    @property ref Plane near() { return planes[NEAR]; }
    @property ref Plane far() { return planes[FAR]; }

    /// Constructs the frustum from a model-view-projection matrix.
    /// Params:
    /// mvp = a model-view-projection matrix
    this(mat4 mvp) {
        planes = [
            // left
            Plane(mvp[0][3] + mvp[0][0], // note: matrices are row-major
                mvp[1][3] + mvp[1][0],
                mvp[2][3] + mvp[2][0],
                mvp[3][3] + mvp[3][0]),

            // right
            Plane(mvp[0][3] - mvp[0][0],
                mvp[1][3] - mvp[1][0],
                mvp[2][3] - mvp[2][0],
                mvp[3][3] - mvp[3][0]),

            // bottom
            Plane(mvp[0][3] + mvp[0][1],
                mvp[1][3] + mvp[1][1],
                mvp[2][3] + mvp[2][1],
                mvp[3][3] + mvp[3][1]),
            // top
            Plane(mvp[0][3] - mvp[0][1],
                mvp[1][3] - mvp[1][1],
                mvp[2][3] - mvp[2][1],
                mvp[3][3] - mvp[3][1]),
            // near
            Plane(mvp[0][3] + mvp[0][2],
                mvp[1][3] + mvp[1][2],
                mvp[2][3] + mvp[2][2],
                mvp[3][3] + mvp[3][2]),
            // far
            Plane(mvp[0][3] - mvp[0][2],
                mvp[1][3] - mvp[1][2],
                mvp[2][3] - mvp[2][2],
                mvp[3][3] - mvp[3][2])
        ];

        normalize();
    }

    /// Constructs the frustum from 6 planes.
    /// Params:
    /// planes = the 6 frustum planes in the order: left, right, bottom, top, near, far.
    this(Plane[6] planes) {
        this.planes = planes;
        normalize();
    }

    private void normalize() {
        foreach(ref e; planes) {
            e.normalize();
        }
    }

    /// Checks if the $(I aabb) intersects with the frustum.
    /// Returns OUTSIDE (= 0), INSIDE (= 1) or INTERSECT (= 2).
    int intersects(AABB aabb) {
        vec3 hextent = aabb.half_extent;
        vec3 center = aabb.center;

        int result = INSIDE;
        foreach(plane; planes) {
            float d = dot(center, plane.normal);
            float r = dot(hextent, abs(plane.normal));

            if(d + r < -plane.d) {
                // outside
                return OUTSIDE;
            }
            if(d - r < -plane.d) {
            result = INTERSECT;
            }
        }

        return result;
    }

    /// Returns true if the $(I aabb) intersects with the frustum or is inside it.
    bool opBinaryRight(string s : "in")(AABB aabb) {
        return intersects(aabb) > 0;
    }
}

和 AABB 实施：

struct AABBT(type) {
        alias type at; /// Holds the internal type of the AABB.
        alias Vector!(at, 3) vec3; /// Convenience alias to the corresponding vector type.

        vec3 min = vec3(0.0f, 0.0f, 0.0f); /// The minimum of the AABB (e.g. vec3(0, 0, 0)).
        vec3 max = vec3(0.0f, 0.0f, 0.0f); /// The maximum of the AABB (e.g. vec3(1, 1, 1)).

        @safe pure nothrow:

        /// Constructs the AABB.
        /// Params:
        /// min = minimum of the AABB
        /// max = maximum of the AABB
        this(vec3 min, vec3 max) {
            this.min = min;
            this.max = max;
        }

        /// Constructs the AABB around N points (all points will be part of the AABB).
        static AABBT from_points(vec3[] points) {
            AABBT res;

            foreach(v; points) {
                res.expand(v);
            }

            return res;
        }

        /// Expands the AABB by another AABB.
        void expand(AABBT b) {
            if (min.x > b.min.x) min.x = b.min.x;
            if (min.y > b.min.y) min.y = b.min.y;
            if (min.z > b.min.z) min.z = b.min.z;
            if (max.x < b.max.x) max.x = b.max.x;
            if (max.y < b.max.y) max.y = b.max.y;
            if (max.z < b.max.z) max.z = b.max.z;
        }

        /// Expands the AABB, so that $(I v) is part of the AABB.
        void expand(vec3 v) {
            if (v.x > max.x) max.x = v.x;
            if (v.y > max.y) max.y = v.y;
            if (v.z > max.z) max.z = v.z;
            if (v.x < min.x) min.x = v.x;
            if (v.y < min.y) min.y = v.y;
            if (v.z < min.z) min.z = v.z;
        }


        /// Returns true if the AABBs intersect.
        /// This also returns true if one AABB lies inside another.
        bool intersects(AABBT box) const {
            return (min.x < box.max.x && max.x > box.min.x) &&
                (min.y < box.max.y && max.y > box.min.y) &&
                (min.z < box.max.z && max.z > box.min.z);
        }

        /// Returns the extent of the AABB (also sometimes called size).
        @property vec3 extent() const {
            return max - min;
        }

        /// Returns the half extent.
        @property vec3 half_extent() const {
            return 0.5 * (max - min);
        }

        /// Returns the area of the AABB.
        @property at area() const {
            vec3 e = extent;
            return 2.0 * (e.x * e.y + e.x * e.z + e.y * e.z);
        }

        /// Returns the center of the AABB.
        @property vec3 center() const {
            return 0.5 * (max + min);
        }

        /// Returns all vertices of the AABB, basically one vec3 per corner.
        @property vec3[] vertices() const {
            return [
                vec3(min.x, min.y, min.z),
                vec3(min.x, min.y, max.z),
                vec3(min.x, max.y, min.z),
                vec3(min.x, max.y, max.z),
                vec3(max.x, min.y, min.z),
                vec3(max.x, min.y, max.z),
                vec3(max.x, max.y, min.z),
                vec3(max.x, max.y, max.z),
            ];
        }

        bool opEquals(AABBT other) const {
            return other.min == min && other.max == max;
        }
    }

    alias AABBT!(float) AABB;

到目前为止，在理论上，不幸的是我得到了完全错误的结果，在某些方向（z-和x+）整个世界消失了，在所有其他方向上什么都没有被剔除。

我希望你们中的任何人都知道为什么这不起作用。

编辑（检查 AABB 和 Frustum 的不同方法）：

bool intersects2(AABB aabb) {
    foreach(plane; planes) {
        if(plane.a * aabb.min.x + plane.b * aabb.min.y + plane.c * aabb.min.z + plane.d > 0 )
            continue;
        if(plane.a * aabb.max.x + plane.b * aabb.min.y + plane.c * aabb.min.z + plane.d > 0 )
            continue;
        if(plane.a * aabb.min.x + plane.b * aabb.max.y + plane.c * aabb.min.z + plane.d > 0 )
            continue;
        if(plane.a * aabb.max.x + plane.b * aabb.max.y + plane.c * aabb.min.z + plane.d > 0 )
            continue;
        if(plane.a * aabb.min.x + plane.b * aabb.min.y + plane.c * aabb.max.z + plane.d > 0 )
            continue;
        if(plane.a * aabb.max.x + plane.b * aabb.min.y + plane.c * aabb.max.z + plane.d > 0 )
            continue;
        if(plane.a * aabb.min.x + plane.b * aabb.max.y + plane.c * aabb.max.z + plane.d > 0 )
            continue;
        if(plane.a * aabb.max.x + plane.b * aabb.max.y + plane.c * aabb.max.z + plane.d > 0 )
            continue;
        return false;
    }
    return true;
}

编辑 2（示例输入）：

这是一个MVP：

[[1.18424,0,0.31849,-331.577], [0.111198,1.51016,-0.413468,-88.5585], [0.251117,-0.274135,-0.933724,214.897], [0.249864,-0.272768,-0.929067,215.82]]

还有一个可能失败的AABB： min: (14*16, 0, 13*16) max: (14*16+16, 256, 13*16+16)

score 3 · Accepted Answer

好的，我现在有答案了……我没有想到，这是一件非常愚蠢的事情。

我做了“彼得亚历山大”的建议并尝试调试一切......我最终发现平截头体平面完全错误（左右平面法线指向同一方向）所以我弄乱了我的代码和其他示例代码并发现，矩阵没有转置（我将其存储为 row-major，opengl 存储为 column.major），所以很简单：mvp.transpose()在 Frustum-Ctor 中修复了我的 frustum。

谢谢你的帮助。

score 1 · Accepted Answer

您的点积方法确实有效（制作了一个小jsfiddle来测试它），但在我看来，您的截锥体设置不正确：

Frustum(engine.proj * engine.view)

代替：

Frustum(engine.model * engine.view * engine.proj)

注意顺序（矩阵是反交换的！）和模型矩阵的附加乘法，以便您创建 MVP 矩阵。

score 0 · Accepted Answer

我发现您初始化AABB课程的方式存在问题。我不知道这是否是导致您的问题的原因，但无论如何都值得修复（以防止有时意外使用损坏的初始化程序）。

对于默认值AABB（这似乎是您在制作一个时开始使用的from_points()），两个角都设置为(0,0,0)-- 因此，当以这种方式构造时，每个 AABB 都必须包含原点。

如果必须AABB像这样设置默认值，则需要设置默认值min=(infinity,infinity,infinity)和max=(-infinity,-infinity,-infinity).

math - 截锥体剔除，实现

3 回答 3

Related

Reference