YardenJ2R

07-09-2017, 11:11 AM

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_;

else

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)

else

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

{

public:

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];

}

else

{

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;

}

};

Doubts

Should I really use BVH instead of octrees or something similar?

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?

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.

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:

https://coocoscode.wordpress.com/2010/12/15/building-bounding-volume-hiearchies/

http://ruh.li/CameraViewFrustum.html

http://gamedevs.org/uploads/fast-extraction-viewing-frustum-planes-from-world-view-projection-matrix.pdf

Thanks a lot!

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_;

else

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)

else

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

{

public:

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];

}

else

{

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;

}

};

Doubts

Should I really use BVH instead of octrees or something similar?

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?

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.

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:

https://coocoscode.wordpress.com/2010/12/15/building-bounding-volume-hiearchies/

http://ruh.li/CameraViewFrustum.html

http://gamedevs.org/uploads/fast-extraction-viewing-frustum-planes-from-world-view-projection-matrix.pdf

Thanks a lot!