Hi!

I don't know how to call this. Maybe "frustrum coordinate list generation"? I'd like to generate a list of "quadrant coordinates" (/integer 3d points) from my "view" variables (render range, view matrix, projection matrix, maybe FOV?) instead of starting out with a full list and culling the ones that aren't between frustum planes.

At the moment I have at my disposal...:
- A view matrix and a projection matrix.
- A quasi infinite set of objects / particles (partially procedurally generated, partially in database / hash lists etc)
- A very cheap method of testing which objects are in quadrant [x, y, z] (shouldn't be a problem to do this each frame for every quadrant inside the view frustum with enough time left over to render all the objects).

- A "camera" object, that - at the moment - is limited to always pointing straight down so I can do my "reverse" culling with a simple / easy loop until I figure out how to cram my view/projection matrix (probably also need FOV for the x/y-range increment per z slice somehow?) into that thing...:

   for (int z = 0; z<RENDERRANGE && stuffloaded; ++z) {
      for (int x = -z *xviewratio; x < z*xviewratio; ++x)
         for (int y = -z*yviewratio; y < z*yviewratio; ++y)
         {
            Quadrant* qu = GetQuadrant(vec3i(RenderCenter.x + x,  RenderCenter.y + y,  RenderCenter.z - z));
            if (qu->GetQuadrantWANTstatus() <  QuadrantStatus_e::RenderReady) {
               qu->setWantParticleRender();
            } else if (qu->GetQuadrantCURRENTstatus() ==  QuadrantStatus_e::RenderReady)
            { qu->DrawAllParticlesInHere(); }
         }
   }

My usual "trial + error" approach to math hasn't worked so far because there's just too many steps that I'd have to figure out correctly all at once since smaller steps in between won't render anything for me to use as feedback... And trying to wrap my head around all of them at once hurts my brain -.-. Tried reading some random matrix / math / linear algebra articles, hoping that stuff would just start looking more transparent to me at some point, but that has not worked so far either.

So... Any hints?

I think you might be overthinking this. If there is ever a moment something is more complex than another option, and the math is more involved, it generally means it's probably not the efficient way to go about things. Remember that Computers step through the methods that we write, and can never skip the process.

But yeah... as Spiro said... the best method would probably be collision detection against AABB and Spheres.

Thanks!

I think your problem is identical to voxelising the frustum shape, so perhaps you could direct your google searches in that direction.

It's not something I know anything about really. Maybe picking a point that you know is inside the frustum and then flood-filling the voxel grid would be an OK approach (I'm sure it's far from optimal though!).

Hmm... I don't really have any obstacles for "flood filling", so, if I understand flood filling right, that would just give me a giant sphere?

I guess I could create a "voxel frustum" as a set of vertices and iterate over that... but isn't that just about the same thing my loops (above) currently do already and then I'd still have to figure out how to use my matrices?

No, regular frustum-culling suffices. A frustum against an AABB or bounding sphere. Nothing more.


L. Spiro

And that I don't understand at all. For frustum culling I first need a list of all objects, right? I can't make a list of infinite objects... I could initialize a big sphere of quadrants and then the objects in there, then I could do culling on that finite set. But that way I'd end up working with a lot of useless processing compared to only initializing the objects that are in the frustum in the first place...

Maybe I just didn't manage to describe my problem properly? It's probably trivial, but for some reason I just can't handle my matrices (and conversions from one coordinate space to a different one) in this context and I can't figure out why -.-

So... as an example... after my most recent streak of failed attempts, I ended up with this (as the coordinates for the Quadrants inside the loops / see OP above):

glm::vec4 gtmp = proj_mat * view_mat * glm::vec4(x * QuadrantSize,  y * QuadrantSize, z * QuadrantSize,  1);
tmp = vec3i((int)gtmp.x / QuadrantSize + 0.5,  (int)gtmp.y  / QuadrantSize + 0.5,  (int)gtmp.z  / QuadrantSize + 0.5);

Which does render *something* on the screen, flickers when I move the camera and I can't figure out what exactly it's doing. I think it shows that at this point I'm so confused I have no idea what I'm doing any more.

Maybe this is more clear: I guess the 3 loops could be interpreted as a frustum shaped field of points (= quadrant coordinates) starting with the narrow "tip" at 0,0,0 and pointing into direction z (unless I messed up there already)... and I just don't manage to generate this frustum shaped field of coordinates where it is supposed to be (in front of the camera, which has a projection matrix and view matrix, I'm ignoring the fov for now because I've got enough problems without it already), so that I can then get the renderable objects from those Quadrants.

What I'm trying to get from the matrices aren't frustum planes, but a frustum shaped "cloud" of Quadrant coordinates...

collision detection against AABB and Spheres.

I don't have anything to do collision detection with unless I initialize some objects first... and that's what I need the frustum thing for, so I don't have to initialize a whole huge sphere with radius *sight_range of objects when I only need those few inside the view frustum... not sure how I could do it any other way without wasting a lot of resources...

Oh... I think now I'm slowly beginning to understand where I went wrong.

I was practically constructing a frustum shape in an "integer quadrant coordinate space" with my for loop... then I tried to transform that with the float world matrices so it would match the camera position + orientation... and then I expected all the points of that cloud to "fall back" into exactly the right quadrant coordinates again after division trough quadrant size + truncating during the (int)float casting... that can never work, can it?

This would certainly explain, why the best I could manage was getting some sort of "chequerboard" effect with quadrants blinking in and out of existence almost randomly as I move the camera...

You could first make a list of the quadrants within the camera's frustrum, and then frustrum cull that list.

Wait, I thought that was what I was trying to do? That might be the thing that I don't manage to do... Unless I missed something else, if I somehow manage to get that list, there should be no more culling to do though...

. You can represent such a list simply with a start xyz and an end xyz (min and max xyz of the camera's 8 frustrum corners).

I don't know what to do with that representation though... so.. I need to figure out how to... loop trough that skewed space, that isn't aligned with the world axes...? Then that might be why/how exactly my...:

problem is identical to voxelising the frustum shape,

?

So - I guess I should treat my "quadrants" as "chunks" and my "particles" as "voxels", even though there aren't really any cubes...? Just from the sound of it so far - could the problems I'm having be related to "volume rendering" somehow? I'm not a all sure if I'm looking for stuff I should read even remotely in the right places...

Tried to draw what seems to be the root of my problem, no matter which way I try (and probably the reason why fixing the various other things I'm doing wrong never worked out). Didn't really help so far, but there it is:

[attachment=26192:Untitled.png]

Unless the inaccuracies of my drawing betray me, the reason why my method worked fine as long as I didn't rotate the frustum is, that that's the only way plain simple "1D truncating" the float to integer is guaranteed to work - see the second frustum, where I put in some of the truncated "Quadrant / chunk" coordinates.

If I try to simply do the same thing after rotating the frustum, I get collision points and a missing quadrant (X) next to each collision as a result.

So... this almost sounds like it could be a rather trivial problem that I just wasn't aware of (due to my total lack basic geometry knowledge -.-" ) after all...?

- Does it look as if I'm at least partly on the right track? Or did I just get myself even more confused due to assumptions made on the basis of inaccurate / messy drawings?

- Could it solve my problem if I pushed the float-dots to the geometrically nearest coordinates instead of just truncating (/rounding) the x/y/z values separately?

- And if so: is there some sort of "multidimensional number rounding" that I should be aware of? So I don't have to calculate the distance to all 8 possible integer coordinate points to figure out which one's closest to the float coordinate point? No idea how something like that could be called / what to look for...

edit.:

After looking at some more stuff that might be more or less related... to somewhat similar problems... possibly... (p.E.: http://bigwww.epfl.ch/publications/unser9502.pdf ) I came to the conclusion, that this is way too complicated for me at the moment. Am I right to assume, that sort of direct "integer based rotation" like I tried to implement is absolutely (mathematically) impossible when I'm working with something like "chunk coordinates" that can not be discarded or copied for the sake of interpolation, even if I managed to implement some sort of nearest neighbour (is that what that "multidimensional rounding" is called?) algorithm that isn't too expensive for the occasion?

I'm still not entirely sure if I'm (a) really learning stuff or (b) just reading random things I don't understand, getting myself more and more confused / misinformed.

And still can't shake the feeling that there just HAS to be an easy + cheap way to get that freaking list of quadrants-in-frustum coordinates somehow, even if the frustum is rotated and not just translated.