Hierarchical View Frustum Culling doubts and difficulties

Hi there everyone! How are you doing? I hope you’re fine.

I’m studying and trying to implement Hierarchical View Frustum Culling by using Bounding Volume Hierarchy (BVH) and AABB as Bounding Volume (BV). My current implementation is not working and I’m here to ask your help to understand why it is not working, but also to understand more about the theories or ideas behind frustum culling.

Scene description
My scene is a simple one. It is static and there are cubes only (4500 cubes). The cubes have unit size (i.e., x, y and z of the vertices are between -0.5 and 0.5). They are disposed as somekind of 3d matrix. There are 5 lines (y-axis), 9 columns (x-axis) and 100 layers (z-axis). The current distance between the cubes is 1, so they form a big box .

The camera position is currently (0, 0, 0). My model matrix does not change, neither the projection one, but the view matrix can change since I allow the user to move the camera.

Building the BVH
I’m currently trying to calculate the AABB and the frustum planes in world space. So I think I should not use the MVP matrix, but “VP only” (projection * view). The structure of the BVH is a binary tree. The first thing I do is to calculate the model matrix for each cube and the respective AABB. I put this in a structure called NodeData. The BVH is then built by recursion. The steps being followed are (mixing C++ with pseudo-code to simplify):

BVHNode(vector<NodeData> objects)
    if (objects.size() < 2)
        data_ = objects[0]
        volume_ = data_.volume_;
        volume_ = AABB(objects)
        sortObjectsByLongestAxis(volume_, objects)
        leftObjects, rightObjects = splitObjects(objects)
        leftChild_ = BVHNode(leftObjects)
        rightChild_ = BVHNode(rightObjects)

Drawing the BVH
Code again in “C++ pseudo-code”:

BVHNode::Draw(const glm::mat4& view, const glm::mat4& projection)
    glm::mat4 vp = projection * view
    ViewFrustum frustum = BuildViewFrustum(vp)
    IntersectionResult intersectionResult = CheckFrustumAgainstVolume(frustum, volume_)
    if (intersectionResult != IntersectionResult::Outside)
        if (leftChild_)
            leftChild_->Draw(view, projection)
            rightChild_->Draw(view, projection)
            data_.drawable_->Draw(data_.model_, view, projection)

Now the code to build the view frustum and the check against method (now in pure C++):

enum class IntersectionResult { Outside, Inside, Intersecting };

	class ViewFrustum
		glm::vec4 planes_[6];

		ViewFrustum(const glm::mat4& m)
			planes_[0] = -(m[3] + m[0]);
			planes_[1] = -(m[3] - m[0]);
			planes_[2] = -(m[3] + m[1]);
			planes_[3] = -(m[3] - m[1]);
			planes_[4] = -(m[3] + m[2]);
			planes_[5] = -(m[3] - m[2]);

		IntersectionResult CheckAgainst(const AABB& box)
			bool intersecting(false);

			for (int k = 0; k < 6; ++k)
				glm::vec3 n(planes_[k].x, planes_[k].y, planes_[k].z);
				glm::vec3 vmin, vmax;

				for (int i = 0; i < 3; ++i)
					if (n[i] >= 0)
						vmin[i] = box.bmin_[i];
						vmax[i] = box.bmax_[i];
						vmin[i] = box.bmax_[i];
						vmax[i] = box.bmin_[i];

				float d(planes_[k].w);

				if (glm::dot(n, vmin) + d > 0.0f)
					return IntersectionResult::Outside;

				if (glm::dot(n, vmax) + d >= 0.0f)
					intersecting = true;

			return intersecting ? IntersectionResult::Intersecting : IntersectionResult::Inside;

[li]Should I really use BVH instead of octrees or something similar?
[/li][li]Am I building the BVH correctly? Am I doing it in a good way (sorting objects by longest axis of the AABB) and why? Which are the good ways?
[/li][li]My teacher originally asked me to calculate the AABB in the object space and to bring the frustum planes to the object space and to make the calculations there. But how am I supposed to build hierarchy of the BVH like that? The BV would be the same for all, right? That’s why I’m currently trying to calculate stuff in world space.
[/li][li]How can I get the frustum planes correctly? Should I multiply the planes by the transpose of the projection-view matrix?

My main reference is the book “Real-Time Rendering”, of Tomas Moller and Eric Haines, but I’m also using:




Thanks a lot!

Well, it seems to be working now… All I did was transposing the matrix glm::mat4 vp = projection * view and using it to build the ViewFrustum. I think the error was that the glm uses column-major order. So m[0], for example, doesn’t return the first row, but the first column. Is this right?

That is correct.

OpenGL prefers column-major order. Earlier versions only support column-major order, later versions provide a choice (in most cases) but use column-major by default.

[QUOTE=GClements;1287783]That is correct.

OpenGL prefers column-major order. Earlier versions only support column-major order, later versions provide a choice (in most cases) but use column-major by default.[/QUOTE]

Thanks for your reply, I really appreciate it! Could you comment something about my doubts?


I forgot to say that the sort uses the center of the AABB. I have 3 sorting functions, one that uses the x component, one the uses y and another one that uses z.

OpenGL prefers column-major order.