As I hinted on in my last post, I will be discussing the implementation of culling for planet terrain rendering. When the camera is close to the surface, a lot of the terrain geometry is not visible, so it would not be sensible wasting CPU time on generating it or GPU time on drawing it.
Along with the following picture, my video from last week shows quite well what is going on:
Here only the necessary geometry is generated. The implementation to achieve this uses two methods combined: backface culling and frustum culling. I will discuss both methods here along with the implementation…
Backface Culling
Backface culling can be solved with a relatively simple dot product between the view vector and the normal of the triangle. Since the triangle is on a perfect sphere, we can simply use the position normalised as the normal. Therefore the simple implementation for this is:
vec3 center = (a+b+c)/3;
if(dot(norm(center), norm(center-camPos) ) >= 0) return CULL;
For efficiency the camera and frustum have been transformed into the planets object space.
There is a problem with this though. Since we are subdividing the triangles into a sphere, the children of the triangle will have different angles that might not be backfacing even though the parent is. In this case the diverging angle is halved with every subdivision. So if the level 0 angle difference is 16 degrees, the children at level 1 can have a maximum angle difference of 8, then 4, then 2 and so on.
Since a dot product is the cosine of the angle, we can precalculate the minimum dot product required to cull a triangle per level in a look up table. I ended up using the sin of the angle instead of the cosine, because we want the triangles to be at 90 degrees to cull, not 0. Here is what this calculation looks like:
triLevelDotLUT.clear();
triLevelDotLUT.add(0.5);
float angle = arccos(triLevelDotLUT[0]);
for (int i = 1; i < maxSubdivLevel; i++)
{angle = angle/2;
triLevelDotLUT.add(sin(angle));}
This needs to be recalculated every time the base mesh or the maximum amount of subdivisions changes. We can now use this table in our dot product from before like so:
if(dot(norm(center), norm(center-camPos) ) >= triLevelDotLUT[level]) return CULL;
The result is that only the front facing half of the planet is generated and rendered:
Frustum Culling
The next and more complicated step is frustum culling. The idea here is that if something is not in the screen it should not be rendered or calculated. In the following image, the right point should be removed:
One way of doing this would be to transform every vertex with the world view projection matrix into screen space and then checking it in 2D with the rectangles boundaries. This is rather expensive though, since matrix transformations involve quite a few calculations which is not ideal on the CPU. I was able to avoid transforming all vertices by transforming the camera into object space once at the beginning with the inverse of the planets world matrix.
Therefore, the better solution for the problem is constructing the camera frustum out of 6 planes. Two of them are already familiar as the near and far clipping plane, as OpenGL also uses those. What is left is the Top, Bottom, Left and Right plane. They can be constructed from the corners of the near and far plane, which in turn can be calculated from the camera orientation axes and the width and height of those planes, which in turn can be calculated with the tangent of the FOV:
float normHalfWidth = tan(FOV);
float aspectRatio = width / height;float nearHW = normHalfWidth*nearPlaneDist;
float nearHH = nearHW / aspectRatio;
float farHW = normHalfWidth*farPlaneDist/2;
float farHH = farHW / aspectRatio;
This results in a geometry that looks like a pyramid which has been flattened at the tip:
All those planes are described in their Normal form (a position D and a normal N). When they are constructed in a way that they all face inwards, one can calculate a dot product of the normal and the vector between the planes position and the vertex. If this dot product returns a negative value for any plane, the vertex is outside the view frustum.
bool Frustum::Contains(vec3 P)
{for each Plane
{if (dot(Plane.N, p – Plane.D) < 0)return false;
}
return true;}
This implementation will work if you check every vertex of a triangle in most situations. Triangles outside the frustum will definitely be rejected…
The problem is, this algorithm will reject a few to many cases. Consider the following triangle:
All vertices are outside the frustum, but a part of the triangles surface is still inside. The clean solution for this problem would be an intersection code test of the triangle with the planes, but that would be way to expensive when generating a terrain consisting of thousands of triangles.
The faster way of solving this is saying that ALL vertices of the triangle need to be on the “bad” side of the plane. This may return true for a few triangles that are positioned diagonally next to the corner of the rectangle, but since all triangles are rather small in their final form, the amount of errors is acceptable.
You may think that this solves all problems, but there is a further case in which we cannot allow the triangle to be culled. Because the children of the triangle are curved upwards (and also have terrain that may be above sea level), the children may be inside the screen even though the parent triangle is not.
To solve this, some sort of volume is needed that contains all possible children of the triangle. In classical terrain renderers this is typically handled with axis aligned bounding boxes, but since I am dealing with spherical terrain, an axis aligned box would waste a lot of empty space that could never be reached, and boxes are better with quad tree geometry than triangles anyway. My solution is to instead extrude the triangle up by the maximum height and making sure to only cull if all 6 vertices of the triangles volume are outside the frustum.
The height will differ per subdivision level, but it can also be precalculated in a lookup table like with the backface culling before. It can be determined as a position multiplier for the spherical terrain. Multiplying the vertex positions with the height value will offset the from the centre of the sphere, so the heights of the table can be determined with the dot product of a corner vertex and the centre of the triangle that has the correct height applied to it:
heightMultLUT.clear();
vec3 a = icosahedron[1];
vec3 b = icosahedron[3];
vec3 c = icosahedron[8];
vec3 center = (a + b + c) / 3;//addMaxTerrainHeight here too
center *= planetRadius / length(center);
heightMultLUT.add(1/dot(norm(a), norm(center)));for (int i = 1; i < maxSubdivLevel; i++)
{vec3 A = b + ((c – b)/2);
vec3 B = c + ((a – c)/2);
c = a + ((b – a)/2);
a = A*m_Radius / length(A);
b = B*m_Radius / length(B);
c *= m_Radius / length(c);
heightMultLUT.add(1/dot(norm(a), norm(center)));}
Taking all this into account, the final result looks something like this (I made the frustum FOV smaller than the cameras FOV for visualisation purposes):
Since, when considering all those problems, frustum culling gets quite expensive, I let the culling function return if the volume is outside, intersecting or contained. If the volume is outside, its children are not generated and it is not rendered. If it is intersecting, the algorithm proceeds as usual. If it is contained, the algorithm also continues, but frustum culling is not checked any more for the children triangles, since their parent volume is already completely contained.
You can find the complete culling code in C++ on the GitHub repository:
Before this weeks post I also added screenshot saving to the Framework.
