Frustum culling, VBO and radius transformation for test

I’ve tried thousand of combinations witout success.

I’m trying to implement Frustum Culling with VBO.
The passes are:

[ul]
[li]VBO creation with vertices in object/local space (in other words: from its own origin at 0,0,0 before move the object inthe right world’s place)[/li][li]create sphere center (3D object’s center) with its radius (both of these values are in object/local coordinates like all whole VBO data) for later frustum culling calculations[/li][li]calculate all 6 frustum panels with PVM matrix (I suppose panel’s coords are in camera/view space)[/li][li]create a matrix with all object trasformations and send it to Vertex Shader (to place objects in right world places)[/li][li]TO DO: test if objects are in/out frustum[/li][li]Vertex Shader changes vertices position according with passed matrix (GLSL: “gl_Position = PVM * vertex”)[/li][/ul]

When I execute Frustum Test I’ve got sphere coords and radius value in OBJECT SPACE, so I’m unable to compare those values with frustum panels which are “extracted/calculated” with Projection and View matrices.

I’ve thought to multiply sphere center ([X,Y,Z,1] vector) with PVM matrix (4x4), but this multiplication returns an 1x4 vector which I don’t understand how to use it.
For example “PVM*[X,Y,Z,1]” returns [-2.4345, 0.1234, -3.5545, 103.4356]…but I just need new position point (X,Y,Z), not a vector with the 4th value! :confused:

Another problem: during frustum test all my object’s sphere radius are in OBJECT SPACE. How can I transform it in a way compatible with friustum panel’s data? “PVM*radius” (matrix*scalar)?

PS: I’ve got well objects rendered if I disable frustum test, so my VBOs and Vertex Shader works fine with the right data.

[QUOTE=tdname;1243630]I’m trying to implement Frustum Culling with VBO.
… multiplication returns an 1x4 vector which I don’t understand how to use it.
… Another problem: during frustum test all my object’s sphere radius are in OBJECT SPACE. How can I transform it in a way compatible with friustum panel’s data?[/QUOTE]

Sounds like you’re generally on the right track with some things, but are getting off into the weeds on a few of the details.

First and foremost: get this working on the CPU first. It’s a lot easier to test/debug and prove in your math, particularly if you’re a bit shaky on how the whole culling process works. Then, once it’s working solid on the CPU, map it to the GPU.

Second, you didn’t actually state which space you’re trying to cull “in”, though your references to using PVM to transform OBJECT-SPACE coordinates indicate you’re trying to cull in CLIP-SPACE (a 4D space). If you’re the least bit shaky with how 4D (homogenous) coordinates work, then you don’t want to (and with CLIP-SPACE you may lose some of the cheapness of culling spheres in 3D). I would instead suggest you cull in EYE-SPACE. This is a 3D space, so you don’t need to mess with the .w coordinate (it’s 1), and the coordinates are very intuitive for debugging. Then you just transform the center of your bounding spheres (BSPHEREs) to EYE-SPACE using the VM (MODELVIEW) transform, and do your cull test. Also, EYE-SPACE has the advantage that as your eyepoint moves around in the world (common case), you don’t have to update your frustum definition for culling. It’s exactly the same. It only changes when you change your projection parameters (e.g. glFrustum, gluPerspective, etc.)

Third, decided “how” you’re going to cull. There are at least two basic ways to cull: plane tests and a radar approach. If you need some references, just ask. Or google up the lighthouse3d tutorial on frustum culling.

Finally, as far as how to deal with the 1x4 vectors (aka 4-vectors) of CLIP-SPACE, if you do your culling in EYE-SPACE you don’t have to care. It’s all basic 3D stuff in EYE-SPACE.

However, for what it’s worth, in CLIP-SPACE whenever you see .xyzw, just keep in mind that after hardware clipping occurs, the hardware maps this back to 3D by simply dividing .xyz by the .w coordinate. This 3D space (where what’s in-frustum lies within -1…1 in X, Y, and Z) is called NDC. HOWEVER, you probably don’t want to clip in NDC because (with perspective) there’s a potential divide-by-zero (nasty singularity) involved with the math in getting there – this is the .w = 0 case which corresponds to vertices that are at the same EYE-SPACE Z=0 value as the eyepoint. Not to mention that as you get vertices which are close to the EYE-SPACE Z=0 plane (plane of the eyepoint), you end up dividing by very tiny numbers has similar problems.

Thanks for your quick answer.

I’ll try the CPU-way. But the other problem still remains: my 6 frustum panels are extracted with PVM matrix. If I execute “isInFrustum()” check with only “MV” matrix, I’ll get wrong results.

My matrices:
P: [-2.45456, -0.5456, …]
V: identity
M: [-2.1245, -3.5467, …]

In other words MV = M, and PVM = PM.
I’m unable to compare frustum panel’s data with boundingSpheres coords multiplied just with ModelMatrix: both are in two completly different spaces.
I need “PVM” (= “PM” if considering “V” = identity) during frustum panels extraction, but I need it also to transform data (sphere center and radius) in its right position/dimension before comparison.
I don’t understand why you suggest me to use just MV matrix…
In my case Frustum panels changes, during camera movements, only if I extract them using ProjectionMatrix, so I should use PVM to extract them. And boundingSpheres are valid only in the same space: in other words multiplying sphere’s data with PVM matrix.

Or not? :confused:

The function that you are using to extract the 6 frustum planes from the PVM (ModelViewProjection) matrix – what space does it return the frustum parameters in?

If EYE-SPACE, then the most obvious choice is to perform your cull tests in EYE-SPACE. And you would do so by first transforming the bounding spheres into that space with the MV (ModelView) matrix and then performing the cull testing.

However you can perform the cull test in one of several different spaces – your pick.

I need it also to transform data (sphere center and radius) in its right position/dimension before comparison.

There is no “right” space for culling. You can cull in OBJECT-SPACE, WORLD-SPACE, EYE-SPACE, or CLIP-SPACE. There are pros and cons to each though.

But if you’re saying that your frustum definition and your bounding primitives need to be transformed into the “same” space for cull testing, then yes, you’re absolutely right. That space, however, can be one of several possible spaces.

Consider reading the entire lighthouse3d tutorial on frustum culling.

Sorry but my english is not very good and I havn’t understood completly your first question.
My function for frustum panels extraction I think it’s the most common in the web: it uses PVM matrix and normalization for each panel.
During extraction:

  • M: identity
  • V: identity
  • P: the same matrix that “gluPerspective()” generates (I’ve check this step comparing “glGetFloatv(GL_PROJECTION_MATRIX…” with my own matrix_generation_function, and it’s the same)

I’ve also done another test: moving farPlane far, it increments few frustum panels coords according to the increment. So I think the frustum panels data are right.

When I check if object is IN frustum:

  • M: [-2.1245, -3.5467, …]
  • V: identity
  • P: same matrix as before during extraction
    So I thought to multiply sphere center by PVM (in this case just by PM), but it doesn’t “hides” objects in most of my test. Maybe sphere radius is too big and still always persist “in screen/camera_view”. For that reason I started to work on radius transformation, because “2 units in obejcts space” are not the same in eye_space.

Before using my own matrices I was using standard “Matrix Stack” (glPushMatrix(), glPopMatrix()…but in 3.3 it’s a deprecated way) and my VBO (with all vertices/normals already multiplied by PVM matrix) and Frustum check and extraction was working well as I expected.
Now, with my own matrice system and VBO built in object_space_coords, the frustum_panel_data and objects (vertices objects and boundingSpheres ones) are not in the same space, but multiplying by PVM seems to not solve nothing…or not completly.

Thankyou Dark, now I’ve partially resolved.
I’ve started to read this article: Heresy II - Why 4D Homogeneous Transform/Clip/Project is Wasteful - CodeProject to understand homogenous coordinates.

I’m writing this solution for other ppl even it is a bit stupid if they are more of beginners:

  • I had VBOs in object_space coords
  • I had boundingSpheres (3D object’s center and radius) also in object_space coords
  • Using “PV” matrix I calculate frustum panels (|why not use also ModelMatrix??| please read at the end)
  • Pass a full PVM matrix to Vertex Shader for vertices placing in its right position
  • Multiply boudingSphere coords (1x4 in homogenous, with W=1.0) by PVM (4x4 matrix) to “convert” sphere center coords
  • Divide each resulting array item by resulting array[3] (the “W” part)
  • Discard array[3] item (which is now equal to 1.0 and useless)
  • At the end: the 1x3 boundingSphere center coords converted for frustum comparison

However I don’t understand how to manage Radius trasformation…
Leaving radius in objects_space coords, during comparison with frustum panels, is wrong…should be wrong…but it works. I don’t understand how/why it works without trasform even the radius…Any idea?

  • “|why not use also ModelMatrix??|” ModelMatrix refers to a specified 3D Model with its Translate, Rotations and Scale operations. It is non-sense to use ModelMatrix during frustum panel extraction because we don’t need to calculate frustum panels from object’s point_of_view. It’s right?

Language is proving to be a real obstacle here. I’m not saying you should use the MODELVIEW matrix for frustum plane (not panel, plane) extraction. You of course need your actual projection parameters to compute the frustum planes, or you need the Projection matrix to infer those projection parameters.

What I am saying is that it makes a lot of sense to actually perform sphere-frustum cull tests in EYE-SPACE – and for that (once you have your frustum planes) you use the MODELVIEW matrix to transform your OBJECT-SPACE bounding spheres into EYE-SPACE for cull testing.

However I don’t understand how to manage Radius trasformation…
Leaving radius in objects_space coords, during comparison with frustum panels, is wrong…should be wrong…but it works. I don’t understand how/why it works without trasform even the radius…Any idea?

Assuming you cull in a standard 3D orthonormal space (e.g. OBJECT-SPACE or EYE-SPACE), then radius is coordinate system invariant. 5 units in OBJECT-SPACE is the same as 5 units in EYE-SPACE.

Gets tricky in CLIP-SPACE, and in NDC your sphere isn’t a sphere anymore. So if I were you I’d just use EYE-SPACE – at least at first.

Of course, but I try to do my best :wink:

Impossibile to do that.
The only way to extract Frustum planes is using also ProjectionMatrix to be in clip_space, so I need to execute objects frustumCheck() in the same space.
Extract frustum planes in other space would have no meaning because the resulting matrix doesn’t change when camera moves itself.
So a cull test executed in eye_space it’s physically impossibile…

  • Planes extraction: using PVM matrix
  • Cull test: using PVM matrix to be in the same space of when I’ve extracted planes

So I also use ModeView matrix of course, but I also need ProjectionMatrix when I execute cull test.

I don’t understand your idea…

Now I’ve got right boudingSpheres position but wrong Radius (I tested this situation using a fixed radius of “0.0f” to physically view when the objects becomes visible or invisible in frustum, and the sphere center is precise)

I found and example (http://www.codesampler.com/oglsrc/oglsrc_12.htm#ogl_frustum_culling) which is using PVM during planes extraction and just MV during comparison, but it’s uses fixed Radius of 1.0f for all sphere objects.

I’ve tried to execute cull test with just MV matrix, but many objects doesn’t pass it and becomes invisibile even if they are the middle of the scene/camera…

I’ve found this discussion in other forum:

Extracting the frustum planes from projection*view should give you the frustum in world space

Whaaaaaaaat??? :confused:

However, it looks like you’re transforming the sphere center into camera space. So it’s not surprising that the test isn’t working. You might try this instead: eyeSphereCenter = modelMatrix * sphereCenter

eyeSpace generated without ViewMatrix…unbelivable…

Yes I can work testing varyous random changes: trying to use one matrix. If it doesn’t works try with another, and so on…but I don’t understand reasons behind this theoric math.

Now I’m executing frustumCheck() with only ModelMatrix and it seems to be a bit better, but Radius is still wrong.