I'm trying to add frustum culling to my voxel engine.   The way the program is currently set up, when it builds a scene for a given LOD, it organizes terrain meshes into kind of a loose octree with bounding spheres.   Everything is in world coordinates and my camera has front, up and right vectors, also in world coordinates

I can think of a couple of different ways to do the culling but I'm not sure which one would be fastest.  First I can calculate the frustum planes for the current camera position and direction and then just calculate the side of each plane that the spheres are on and eliminate them based on that.

Alternatively I can calculate the top/bottom and left/right angles of the frustum planes to the camera front vector.  The nice thing about this is that they don't change as the camera moves around unlike the frustum plane equations.  I would then calculate angles of the bounding spheres from the camera facing vector (taking sphere radius into account).  Then I can just eliminate spheres if the sphere angle is greater than pre-calculated frustum plane angles.  One variant of this is just to use one angle instead of width and height angles, which would be the corner edge angle of the frustum.   It would be kind of like drawing a big circle around the display. This would be less calculation but It would also be less accurate and I would included some meshes I didn't need to.

Also if there is some other third way, I'd be happy to hear about it.  Any opinions?

Not an expert and just self teaching me game programming. I had a similar question a few weeks ago, and following this i implemented that what you called alternative. They call it "Radar Approach".

In principle, you can frustum cull in view or in clip space, this is view space. Dragging planes around for complex tested didn't sound very effective to me, but i may be wrong.

From the above tutorial, here's the frustum method (OpenGL) to call when fov changes (angle, near/far plane). It intakes angle in y and calculate the x value via the ratio.

void ViewFrustum::setFOV( const float angle, const float ratio, const float nearD, const float farD ) {
	m_ratio = ratio;
	m_nearD = nearD;
	m_farD = farD;
	m_angle = glm::radians( angle );
	// compute width and height of the near plane for point intersection test
	m_tangensAngle = tanf( m_angle * 0.5f );
	m_height = m_nearD * m_tangensAngle;
	m_width = m_height * m_ratio;
	// compute sphere factors for sphere intersection test
	m_sphereFactorY = 1.0f / cosf( m_angle );
	float anglex{ atanf( m_tangensAngle * ratio ) };
	m_sphereFactorX = 1.0f / cosf( anglex );
}

The method to call on cam movement (every frame, that is).

void ViewFrustum::setCameraVectors( const glm::vec3 &pos, const glm::vec3 &front, const glm::vec3 &up ) {
	m_cameraPosition = pos;
	m_z = glm::normalize( front - pos );
	m_x = glm::normalize( glm::cross( m_z, up ) );
	m_y = glm::cross( m_x, m_z );
}

Intersection tests are in the tutorial linked above.

It works. But i am curious too if there is a better way :-)

Hi there,

I have not implemented frustum culling myself so far, so I can't give you professional advice on that, but  I am currently working on my physics engine, which also involves collision detection, which is basically the same problem. However, I am just starting, so don't take all I say for the truth

If you are not using vector tricks like dot and cross product, I would avoid the angle approach since it usually involves sin and cos functions, which are quite expensive. On the other hand, calculating the new frustum planes is a negligible operation concerning speed. In camera space, they are fixed. Calculate them once and then determine the camera-to-world transformation matrix every frame. Use it to transform the planes into your world space.  We are talking about less then 10 nanoseconds on modern, vectorized hardware. In comparison with the huge number of subsequent culling checks, you should not care about that. Now having the planes, which describe a volume, there are effective collision check methods. Just google a little bit or buy a good book.

I think the most important thing is, that you have an efficient data structure that reduces the cost of each collision check to a minimum without losing precision. 2 things that people usually use is space partitioning (what you mentioned too) and bounding volume hierarchies. Space partitioning bundles multiple objects into smaller groups (octrees, BSP, etc.) and can save you a lot of collision checks while overdoing it has the opposite effect. Finding the right balance is key. Using bounding volume hierarchies means, that your object has more than one bounding box. Every collision check starts with the least complex bounding box and only continues with a more complex one if the previous check has passed. This way you have high precision without losing to much speed due to multiple tests on the same object since the number of objects that need a full and detailed test is usually significantly lower than the ones that fail the first simple test.

For your frustum check, the whole thing could look like this:

- Check if a group bounding sphere is completely inside or outside the frustum. (No intersection with planes). If inside, everything needs to be drawn, and no further checks are needed and if outside, nothing needs to be drawn and no further checks are needed.

- If it is partially inside, you need to check every member and subgroup of the group the same way as before.

- For objects that are on the boundary, you need to perform a full collision check to determine if is partially inside or not.

If you are planning to have a detailed collision system in your engine, you basically get everything you need to perform effective frustum culling for free. So think about that.

Greetings

Ages since I've done this, and I've never done with voxel world, but usually the larger scale optimizations will be a lot more important than the details of the test used which should be easy to google, e.g.

https://sites.google.com/site/letsmakeavoxelengine/home/frustum-culling

• Cull away as much as possible cheaply (e.g. use the octtree to quick reject most zones)
• Don't perform the test once you get down to a level it would be quicker to draw anyway

You can cull in world space, view space, clip space, but if the point - plane distance test is fast then I would have thought world space is a good plan as you only have to transform the frustum planes to world space, rather than each object (which will be a lot more than 6 or so).

As DerTroll says if a bound is outside the frustum, don't traverse further inside it, if it is completely within, don't check more, if it only crosses one plane, you only need to check sub-bounds against this plane... etc etc. The data organisation may be as important as the tests.

I would also try and consider all visibility determination (occlusion culling, backface culling) at the same time to come up with a scheme as sometimes they can be solved by the same method. Is the world dynamic? Or largely static? Can you precalculate visibility? Are there large fixed occluders? Is there e.g. a massive planet in the way of everything behind it?

A screenshot would be helpful here to see what we were dealing with.

Some other big picture options include PVS, portals, various methods of occlusion culling. You also may be able to take advantage of temporal coherence (e.g. if a sphere is massively far from a clipping plane, then unless you turn a large rotation it will be impossible to appear in the next frame).

The most optimal method is also usually pretty deeply tied in with how you render the objects in your world.

In the "Radar Approach", trigonometry is only necessary on zoom or near/far plane changes. The "every frame stuff" is just the three cam vectors.

Intersection tests look pretty effective to me, or am i wrong ? All angles are pre-computed.

(source link in my first post)

intersect_t ViewFrustum::isSphereInFrustum(
		const glm::vec3 &center, const float radius ) const {
	intersect_t result{ INSIDE };
	glm::vec3 v{ center - m_cameraPosition };

	float az = glm::dot( v, m_z );
	// Early out against near and far plane
	if( az > m_farD + radius || az < m_nearD - radius )
		return OUTSIDE;
	if( az > m_farD - radius || az < m_nearD + radius )
		result = INTERSECTS;

	float ay = glm::dot( v, m_y );
	float d = m_sphereFactorY * radius;
	az *= m_tangensAngle;
	if( ay > az + d || ay < -az - d )
		return OUTSIDE;
	if( ay > az - d || ay < -az + d )
		result = INTERSECTS;

	float ax = glm::dot( v, m_x );
	az *= m_ratio;
	d = m_sphereFactorX * radius;
	if( ax > az + d || ax < -az - d )
		return OUTSIDE;
	if( ax > az-d || ax < -az+d )
		result = INTERSECTS;

	return result;
}

Just realized i could switch x and near/far test, as left/right is probably more often culled than near/far in my case. That'll profit more from the early-outs ...

But i am not a programmer just a hobbyist ?

Thanks for all the responses. I suppose I should add a little detail. First my voxels are not Minecraft like voxels. In fact they aren't even cubes nor are they oriented in one direction. They are prisms that radiate from the center of a sphere. This is for planet building (see my blog if you're curious). They are also organized into octrees and chunks for LOD purposes. It's something like the trans-voxel algorithm.

This is why I use loose bounding spheres since it's a pain to use the prisms directly for bounding. I'm not so worried about collision at this stage. I plan on using Just In Time terrain for that. I actually have the code from my old non-voxel world generator and it works pretty well. It actually should be easier with voxels because I can use the spheres instead of cylinders for bounding. For  hight mapped terrain triangles can be tall so spheres don't work so well. Voxels limit their size, at least for marching algorithms.

Back to frustum culling.....from reading your responses and thinking about it more, I guess I it comes down to moving the frustum planes each time the camera moves and then testing the spheres vs those, or doing what you guys are calling the "radar" algorithm. Everything on the CPU side is currently in world coordinates (in double precision) , but I guess I can put the bounding spheres in camera coordinates if it makes calculation on average faster. Also, as far as the graphics goes, the leaf bounding spheres are whole chunks with one or two meshes, so I can't really subdivide that any more than it is. I guess I should just write a test program and bench mark it.

Finally what I'm really looking at, at the moment is just culling for graphics. I already do a lot of LOD and I don't even build the back side of the planet.  I look at the camera altitude, the planet diameter and terrain hight to determine what to build . Everything is built procedurally in memory on the fly in real time. The problem right now is there are a lot of meshes so the frame rate drops, even though the build speed is good since it now uses a lot of threads. My gut feeling is it's the CPU trying to display a lot of off screen meshes rather than a GPU issue.

Don't forget to apply the model matrix to your spheres before testing with the above method ?

There are probably many objects to test against the frustum, so the above method should save considerable computing compared to testing against 6 planes. otoh, if i understand the matter correctly, that method makes further optimization more difficult, like if an object was rejected last time by one of the planes and the camera moves slowly or turns the opposite way, it is likely that the same object will be rejected by the same plane again. Could this optimization be done with the radar thing without too much of organizational effort ?

In my case (heightmap extrusion and cdlod), framerate went up by >factor 10.

Ok here's the postmortem.....

So I finally got this working, although I did it differently than I thought I originally would.  Reading through the responses again helped me organize my thoughts. As I said, currently I'm dealing with terrain and it's all in world space. However when I add trees and buildings, those will most likely be instanced, so If I have to transform my bounding spheres anyway, I figured I might as well go to view space which is easier to calculate culling with.

I ended up not doing the radar approach, but more the standard thing. I just save the normals for the frustum planes in view space with the camera object, and then transform the bounding spheres to view space before culling.  Since I'm just dong the bounding spheres, it's only a point and a radius, and since everything is in an octree, I only need to transform a subset of those.  I'm basically doing what @Green_Baron posted above except since it's in view space and the camera is always at (0.0, 0,0, 0.0), so I can just eliminate the camera position (not really a big deal but I guess it's a few clocks). But the calculation for culling is super easy now. It's just a dot product with the normals of the planes and the centers of the spheres. The result is  compared to the sphere radius. It's a scalar projection:

https://en.wikipedia.org/wiki/Scalar_projection

So I don't have to use any trig functions at all.

I also found a couple bugs in my octree in the process of getting this working, and when all was said and done I went from 15FPS when zoomed in, to over 900FPS. Out of that the frustum culling accounted for about 5X, but I'm still in wire frame so I'm sure that will drop a lot. However at least It's reasonable enough that I can go and add shading  without worrying about it.