[Solved] View Frustum Culling

marcuiulian13 · March 29, 2013, 8:56am

I give up! Hello everyone!

I am struggling to get the frustum culling working for the last day, but i can’t find what’s wrong with what i do.
Here is my code for updating the frustum (called eveytime camera is moved) and checking if a point (a box) is in frustum.


public void update() {
        FloatBuffer modelMatrixBuffer = BufferUtils.createFloatBuffer(16);
        glGetFloat(GL_MODELVIEW_MATRIX, modelMatrixBuffer);
        modelMatrixBuffer.rewind();

        Matrix4f modelMatrix = new Matrix4f();
        modelMatrix.load(modelMatrixBuffer);

        planes[0] = new Plane(modelMatrix.m30 + modelMatrix.m00, modelMatrix.m31 + modelMatrix.m01, modelMatrix.m32 + modelMatrix.m02, modelMatrix.m33 + modelMatrix.m03);
        planes[1] = new Plane(modelMatrix.m30 - modelMatrix.m00, modelMatrix.m31 - modelMatrix.m01, modelMatrix.m32 - modelMatrix.m02, modelMatrix.m33 - modelMatrix.m03);
        planes[2] = new Plane(modelMatrix.m30 + modelMatrix.m10, modelMatrix.m31 + modelMatrix.m11, modelMatrix.m32 + modelMatrix.m12, modelMatrix.m33 + modelMatrix.m13);
        planes[3] = new Plane(modelMatrix.m30 - modelMatrix.m10, modelMatrix.m31 - modelMatrix.m11, modelMatrix.m32 - modelMatrix.m12, modelMatrix.m33 - modelMatrix.m13);
        planes[4] = new Plane(modelMatrix.m30 + modelMatrix.m20, modelMatrix.m31 + modelMatrix.m21, modelMatrix.m32 + modelMatrix.m22, modelMatrix.m33 + modelMatrix.m23);
        planes[5] = new Plane(modelMatrix.m30 - modelMatrix.m20, modelMatrix.m31 - modelMatrix.m21, modelMatrix.m32 - modelMatrix.m22, modelMatrix.m33 - modelMatrix.m23);
    }

    public static boolean inFrustum(int x, int y, int z) {
        Frustum camFrustum = Camera.getInstance().fow;

        Vector4f vCube[] = new Vector4f[] {
            new Vector4f(x, y, z, 1f),
            new Vector4f(x + 1, y + 1, z + 1, 1f)
        };

        for(int v = 0; v < 2; v++) {
            for(int i = 0; i < 6; i++)
                if(distanceToPlane(vCube[v], camFrustum.planes[i]) < 0)
                    return false;
        }

        return true;
    }

    public static float distanceToPlane(Vector4f vertex, Plane plane) {
        return plane.a * vertex.x + plane.b * vertex.y + plane.c * vertex.z + plane.d;
    }

The Plane class is containing only the a, b, c and d from the plane’s equation.

For the moment i just want to see it working and then i will try to optimize it.
Can anyone please help me?

Roquen · March 29, 2013, 1:01pm

I stopped reading after I saw you pulling matrix info from OpenGL. You’re right to not think about speed to start with and just make it work first…I’d stick with that notion for the first (conceptual) part as well.

Using the same kind of logical steps I do on the complex number wiki page let me babble about step #1, point inside the near & far plane. You have a camera at position C with a forward facing vector of F and a test point P. We can translate the system such that we can think of the camera as being at the origin: P' = (P-C). Now all we need to know is the parallel projection of P’ into F: If positive it’s forward, negative behind and zero at the plane…moreover if F is a unit vector then the result is the distance from the plane. So we have: dist = dot(F, P'). Now this is the distance from the plane which contains the camera and our near plane will be some positive distance forward from that. We’ll call that distance ‘n’…so if dist-n >= 0 then the point is forward or on the near plane and likewise for the far plane at distance ‘f’, if f-dist >=0 then we’re inside the far plane.

steg90 · March 29, 2013, 2:03pm

Just a thought, when doing frustum culling you will need some form of spatial partitioning also otherwise you could be checking 1000’s of chunks…Octree comes to mind.

Roquen · March 29, 2013, 2:15pm

Yeah, that’s part of the optimization part. If you have a region oct-tree and values for the four outer points, then next level values are simply the mid-point values. Assuming you’re doing a tree walk you can classify the planes and ignore all children when outside of all (planes), and likewise you don’t need to test with a given plane once a node is inside it.

marcuiulian13 · March 29, 2013, 5:12pm

I understand what you say. I will optimize the algorithm after i will manage this to work. First i want to make this work, because i understand how it works, but there is a problem with it. Am i using the right matrix? How can i calculate the W component of the points vector? What am i doing wrong in my code?
The second thig is that i’m 10th grade (in Romania), this is 2nd grade of high school and I didn’t learned matrix and planes at mathematics.
I am very towards to learning stuff in advance, just tell me what i should do.

steg90 · March 29, 2013, 5:15pm

Take look at this:


http://www.crownandcutlass.com/features/technicaldetails/frustum.html

Regards

marcuiulian13 · March 29, 2013, 6:00pm

I already checked that tutorial, trust me, i did all the research possible on this subject. Is the normalization of planes a must?

theagentd · March 29, 2013, 7:33pm

Of course.

Roquen · March 29, 2013, 8:57pm

If you want to cut straight to the chase, then there’s this (as well): http://www8.cs.umu.se/kurser/5DV051/HT12/lab/plane_extraction.pdf

Note we’re now talking about the projection matrix.

[quote]Is the normalization of planes a must?
[/quote]
No, not if you don’t need to know the distance. If you have a normalized plane and plug in some point which returns a distance of 2 and the multiply the plane values by say 3 (and is now not normalized) if you plug the same point into the equation you’d get 6. So for a given point the sign tells you on which side of the plane the point falls (and is still zero if on the plane)…no normalization required.

theagentd · March 29, 2013, 9:42pm

Oh, Roquen’s right. I’ve been using culling spheres though, in which case I need to have exact distance values to compare them against the sphere’s radius.

marcuiulian13 · March 29, 2013, 11:28pm

Allright. Finally i found some source code of a Frustum class and i use that.
If anyone is interested in that, tell me and i will post it.

Next up: implementing quad / octal trees.

Opiop · March 29, 2013, 11:34pm

Yes please, could you post the code?

marcuiulian13 · March 30, 2013, 7:35am

Here it is. I can’t really tell who’s the owner, because i found this on google without any description.


import org.lwjgl.BufferUtils;

import java.nio.*;

import static org.lwjgl.opengl.GL11.*;

public class Frustum
{
    public static final int RIGHT   = 0;
    public static final int LEFT    = 1;
    public static final int BOTTOM  = 2;
    public static final int TOP     = 3;
    public static final int BACK    = 4;
    public static final int FRONT   = 5;

    public static final int A = 0;
    public static final int B = 1;
    public static final int C = 2;
    public static final int D = 3;

    float[][] frustum = new float[6][4];

    FloatBuffer modelBuffer;
    FloatBuffer projectionBuffer;

    public Frustum() {
        modelBuffer = BufferUtils.createFloatBuffer(16);
        projectionBuffer = BufferUtils.createFloatBuffer(16);
    }

    public void normalizePlane(float[][] frustum, int side) {
        float magnitude = (float) Math.sqrt(frustum[side][A] * frustum[side][A] + frustum[side][B] * frustum[side][B] + frustum[side][C] * frustum[side][C]);

        frustum[side][A] /= magnitude;
        frustum[side][B] /= magnitude;
        frustum[side][C] /= magnitude;
        frustum[side][D] /= magnitude;
    }

    public void calculateFrustum() {
        float[] projectionMatrix = new float[16];
        float[] modelMatrix = new float[16];
        float[] clipMatrix = new float[16];

        projectionBuffer.rewind();
        glGetFloat(GL_PROJECTION_MATRIX, projectionBuffer);
        projectionBuffer.rewind();
        projectionBuffer.get(projectionMatrix);

        modelBuffer.rewind();
        glGetFloat(GL_MODELVIEW_MATRIX, modelBuffer);
        modelBuffer.rewind();
        modelBuffer.get(modelMatrix);

        clipMatrix[ 0] = modelMatrix[ 0] * projectionMatrix[ 0] + modelMatrix[ 1] * projectionMatrix[ 4] + modelMatrix[ 2] * projectionMatrix[ 8] + modelMatrix[ 3] * projectionMatrix[12];
        clipMatrix[ 1] = modelMatrix[ 0] * projectionMatrix[ 1] + modelMatrix[ 1] * projectionMatrix[ 5] + modelMatrix[ 2] * projectionMatrix[ 9] + modelMatrix[ 3] * projectionMatrix[13];
        clipMatrix[ 2] = modelMatrix[ 0] * projectionMatrix[ 2] + modelMatrix[ 1] * projectionMatrix[ 6] + modelMatrix[ 2] * projectionMatrix[10] + modelMatrix[ 3] * projectionMatrix[14];
        clipMatrix[ 3] = modelMatrix[ 0] * projectionMatrix[ 3] + modelMatrix[ 1] * projectionMatrix[ 7] + modelMatrix[ 2] * projectionMatrix[11] + modelMatrix[ 3] * projectionMatrix[15];

        clipMatrix[ 4] = modelMatrix[ 4] * projectionMatrix[ 0] + modelMatrix[ 5] * projectionMatrix[ 4] + modelMatrix[ 6] * projectionMatrix[ 8] + modelMatrix[ 7] * projectionMatrix[12];
        clipMatrix[ 5] = modelMatrix[ 4] * projectionMatrix[ 1] + modelMatrix[ 5] * projectionMatrix[ 5] + modelMatrix[ 6] * projectionMatrix[ 9] + modelMatrix[ 7] * projectionMatrix[13];
        clipMatrix[ 6] = modelMatrix[ 4] * projectionMatrix[ 2] + modelMatrix[ 5] * projectionMatrix[ 6] + modelMatrix[ 6] * projectionMatrix[10] + modelMatrix[ 7] * projectionMatrix[14];
        clipMatrix[ 7] = modelMatrix[ 4] * projectionMatrix[ 3] + modelMatrix[ 5] * projectionMatrix[ 7] + modelMatrix[ 6] * projectionMatrix[11] + modelMatrix[ 7] * projectionMatrix[15];

        clipMatrix[ 8] = modelMatrix[ 8] * projectionMatrix[ 0] + modelMatrix[ 9] * projectionMatrix[ 4] + modelMatrix[10] * projectionMatrix[ 8] + modelMatrix[11] * projectionMatrix[12];
        clipMatrix[ 9] = modelMatrix[ 8] * projectionMatrix[ 1] + modelMatrix[ 9] * projectionMatrix[ 5] + modelMatrix[10] * projectionMatrix[ 9] + modelMatrix[11] * projectionMatrix[13];
        clipMatrix[10] = modelMatrix[ 8] * projectionMatrix[ 2] + modelMatrix[ 9] * projectionMatrix[ 6] + modelMatrix[10] * projectionMatrix[10] + modelMatrix[11] * projectionMatrix[14];
        clipMatrix[11] = modelMatrix[ 8] * projectionMatrix[ 3] + modelMatrix[ 9] * projectionMatrix[ 7] + modelMatrix[10] * projectionMatrix[11] + modelMatrix[11] * projectionMatrix[15];

        clipMatrix[12] = modelMatrix[12] * projectionMatrix[ 0] + modelMatrix[13] * projectionMatrix[ 4] + modelMatrix[14] * projectionMatrix[ 8] + modelMatrix[15] * projectionMatrix[12];
        clipMatrix[13] = modelMatrix[12] * projectionMatrix[ 1] + modelMatrix[13] * projectionMatrix[ 5] + modelMatrix[14] * projectionMatrix[ 9] + modelMatrix[15] * projectionMatrix[13];
        clipMatrix[14] = modelMatrix[12] * projectionMatrix[ 2] + modelMatrix[13] * projectionMatrix[ 6] + modelMatrix[14] * projectionMatrix[10] + modelMatrix[15] * projectionMatrix[14];
        clipMatrix[15] = modelMatrix[12] * projectionMatrix[ 3] + modelMatrix[13] * projectionMatrix[ 7] + modelMatrix[14] * projectionMatrix[11] + modelMatrix[15] * projectionMatrix[15];

        // This will extract the LEFT side of the frustum
        frustum[LEFT][A] = clipMatrix[ 3] + clipMatrix[ 0];
        frustum[LEFT][B] = clipMatrix[ 7] + clipMatrix[ 4];
        frustum[LEFT][C] = clipMatrix[11] + clipMatrix[ 8];
        frustum[LEFT][D] = clipMatrix[15] + clipMatrix[12];
        normalizePlane(frustum, LEFT);

        // This will extract the RIGHT side of the frustum
        frustum[RIGHT][A] = clipMatrix[ 3] - clipMatrix[ 0];
        frustum[RIGHT][B] = clipMatrix[ 7] - clipMatrix[ 4];
        frustum[RIGHT][C] = clipMatrix[11] - clipMatrix[ 8];
        frustum[RIGHT][D] = clipMatrix[15] - clipMatrix[12];
        normalizePlane(frustum, RIGHT);

        // This will extract the BOTTOM side of the frustum
        frustum[BOTTOM][A] = clipMatrix[ 3] + clipMatrix[ 1];
        frustum[BOTTOM][B] = clipMatrix[ 7] + clipMatrix[ 5];
        frustum[BOTTOM][C] = clipMatrix[11] + clipMatrix[ 9];
        frustum[BOTTOM][D] = clipMatrix[15] + clipMatrix[13];
        normalizePlane(frustum, BOTTOM);

        // This will extract the TOP side of the frustum
        frustum[TOP][A] = clipMatrix[ 3] - clipMatrix[ 1];
        frustum[TOP][B] = clipMatrix[ 7] - clipMatrix[ 5];
        frustum[TOP][C] = clipMatrix[11] - clipMatrix[ 9];
        frustum[TOP][D] = clipMatrix[15] - clipMatrix[13];
        normalizePlane(frustum, TOP);

        // This will extract the FRONT side of the frustum
        frustum[FRONT][A] = clipMatrix[ 3] + clipMatrix[ 2];
        frustum[FRONT][B] = clipMatrix[ 7] + clipMatrix[ 6];
        frustum[FRONT][C] = clipMatrix[11] + clipMatrix[10];
        frustum[FRONT][D] = clipMatrix[15] + clipMatrix[14];
        normalizePlane(frustum, FRONT);

        // This will extract the BACK side of the frustum
        frustum[BACK][A] = clipMatrix[ 3] - clipMatrix[ 2];
        frustum[BACK][B] = clipMatrix[ 7] - clipMatrix[ 6];
        frustum[BACK][C] = clipMatrix[11] - clipMatrix[10];
        frustum[BACK][D] = clipMatrix[15] - clipMatrix[14];
        normalizePlane(frustum, BACK);
    }

    public boolean cubeInFrustum(float x, float y, float z, float size) {
        for(int i = 0; i < 6; i++ ) {
            if(frustum[i][A] * (x - size) + frustum[i][B] * (y - size) + frustum[i][C] * (z - size) + frustum[i][D] > 0)
                continue;
            if(frustum[i][A] * (x + size) + frustum[i][B] * (y - size) + frustum[i][C] * (z - size) + frustum[i][D] > 0)
                continue;
            if(frustum[i][A] * (x - size) + frustum[i][B] * (y + size) + frustum[i][C] * (z - size) + frustum[i][D] > 0)
                continue;
            if(frustum[i][A] * (x + size) + frustum[i][B] * (y + size) + frustum[i][C] * (z - size) + frustum[i][D] > 0)
                continue;
            if(frustum[i][A] * (x - size) + frustum[i][B] * (y - size) + frustum[i][C] * (z + size) + frustum[i][D] > 0)
                continue;
            if(frustum[i][A] * (x + size) + frustum[i][B] * (y - size) + frustum[i][C] * (z + size) + frustum[i][D] > 0)
                continue;
            if(frustum[i][A] * (x - size) + frustum[i][B] * (y + size) + frustum[i][C] * (z + size) + frustum[i][D] > 0)
                continue;
            if(frustum[i][A] * (x + size) + frustum[i][B] * (y + size) + frustum[i][C] * (z + size) + frustum[i][D] > 0)
                continue;

            return false;
        }

        return true;
    }
}

Opiop · March 30, 2013, 10:47am

If only I knew what any of that meant Time to print it out and study up on my math

Roquen · March 30, 2013, 1:39pm

Don’t bother. This is reconstructing information which you already have. If you want to dig into math, then learn how to directly build the planes instead. But it should be all layed out in the paper I linked and here’s an additional reference: http://fgiesen.wordpress.com/2012/08/31/frustum-planes-from-the-projection-matrix/

Opiop · March 30, 2013, 6:36pm

So I’m a little confused. I have to create a new instance of the frustum class and then call

calculateFrustum()

correct? Then in my block rendering code, I call

cubeInFrustrum

for every block. But it doesn’t work! Basically, this is what I do:

When I create a new instance of a chunk, I create a new frustum object.
I call a method that calls the method

calculateFrustum()

.
3. In my rebuild method, I have 3 for loops that handle the blocks. I call

cubeInFrustum()

for every block.

After all of that, nothing still shows up. What am I doing wrong here?

marcuiulian13 · March 30, 2013, 8:17pm

Make sure you call calculateFrustum everytime your camera moves. I’m pretty sure this is the problem you have.

Longor1996 · March 30, 2013, 9:00pm

Hi there!

I think the problem is, that you are trying to frustum-cull every single block.
But you have to frustum-cull the chunks to determine if they should be rendered or not.

Longor1996

marcuiulian13 · March 31, 2013, 1:54pm

Now i’ve made this work i’m struggling to potimize it.

How i use the frustum culling:


if (cameraHasMoved) {
    updateFrustum();
    recalculateVBOOfEveryChunk();
}

I already implemented the octree (one octree per chunk).
The problems are:

the fps drops from 50-60fps to 5-15fps when i am moving the camera
memory usage >800mb when moving the camera

Tell me what part of code you need and i will post it.

theagentd · March 31, 2013, 8:23pm

The whole point of VBOs is that you don’t have to recalculate the VBOs each frame. -_-