Right Distance For Sphere Entirely in Frustum

[Baker]

Just jotting some notes here.

What I want to do is make 2 functions:

1. Determine X, Y, Z of camera back from origin X, Y, Z that a sphere (or a bounding box) is entirely visible in a frustum (at the nearest possible distance, of course).
2. Determine if a sphere of bounding box is in a frustum (the bounding box calc is already in Quake/FitzQuake/other Q engines and a sphere can roughly be converted to a bounding box easily enough taking the radius and making the 8 points. I imagine this could be used for a "is a point in the frustum" as well.

I guess to crack #1, I'd have to take all eight points of the frustum, determine X Z "Quake slopes" (Z is supposed to be depth in OpenGL, but is vertical in Quake) ...

So I guess what I'd really want is the "near plane" "width" (greater of depth or width for simplicity) and height of bounding box (not the far plane) with some sort of padding optional (in case not wanting edges touching edge of screen).

Then based on FOV figure out the "depth and height" slopes for the frustum (X and Z), take the "width" and height and divide by the slopes to get X dist and Z dist and then take the larger one. So ideal camera location is X, Y, Z of object minus Y dist. But that's too simple, need to v_forward walk it (using Quake pitch, yaw, roll).

Am I talking to myself ... well, I guess I am. Sigh 3D maths. But at least I can wrap my head around them and work through the necessary calculations, and I'm really not 100% on when exactly this stuff sunk in.

[andrewj]

(2) is fairly straighforward, the frustum is just 4-6 planes (depends if you count near and far), and you get the distance from a point to a plane by a simple equation which I forget now (something like (p - a) * n where p is a point on the plane, a is the coordinate, * is dotproduct, and n is unit normal of plane).

So test the sphere center against the planes and find the minimum distance (will be negative if sphere center is outside frustum)

[revelator]

[Spike]

a plane can be expressed as the direction the plane is facing (its normal) and the distance along that direction from '0 0 0'.
thus distance from plane = (dotproduct(plane_normal, point) - plane_dist);
as the plane normal should be normalised, you can push the plane forwards or backwards by the radius of the sphere by just adding or subtracting the radius to the plane dist.

really though, the maths is kinda vauge. a plane normal could have been expressed positive or negative, while a distance is normally expressed as positive, but quake favours negating those because negate is a smaller opcode on x86 or something silly.
this is useful to bear in mind, especially if you want to see if the sphere is entirely within the frustum, partially within, or entirely outside.

vanilla glquake's code only generates the side planes. the near plane will generally be clipped by the sides anyway, and the far plane is further away than all visible geometry (though linear/exp2fog might have something to say about that). reckless's code is not a direct port, but should otherwise work. I don't get the return value though. I'm guessing p==5 is the near clip plane or something?

[Baker]

[Spike]

no, its x,y,z... normalized. in worldspace.
this ain't no angles thing.

[mh]

[taniwha]

[revelator]

[mh]

I actually pulled the baseline for that particular function from Alien Arena, but frustum/sphere checks are well-known and well-documented. For me it was a handy shortcut to avoid the head-wrecking mathematical theory side of it that I'm too old to deal with these days.

There's a clear balancing act going on here. A frustum/sphere check is obviously going to run much much faster than a frustum/bbox test, but it may not cull as tightly. Depending on your target hardware either may be preferable to the other.

Great observation by Spike about the near/far planes too - in particular the l/r/t/b planes will intersect not too far from the near plane so skipping the near plane check entirely is viable.

Software Quake also trivially accepts or rejects entire planes based on whether or not the plane(s) of parent node(s) have already been checked and passed (or failed); in general the only case that needs to be tested is if a parent intersects the frustum - if a parent is fully outside then all children are also guaranteed to be fully outside, and likewise for fully inside. A handy optimization.

[revelator]

Based on some of the info here i made a build of tenebrae which works with recent drivers. I removed tenebraes 6 plane frustum extraction code and replaced it with mh's + the SphereInFrustum function was replaced
with the above code. Funny side effect the shadow volumes look really good now
I might do some more work on it now that most of the extra gank has gone (replacing the watershaders with glsl based ones, fixing the model poke through etc).
Still has a load of bugs like sometimes switching light of after being in slime or lava (weirdly enough it does not happen in water) i hope to fix that sometime.

get the executable here.

[revelator]

hmm ok not expected but i dont complain it seems the new code also fixes the wall poke through (gl_calcdepth 1).
Atm trying to refurbish the old texture managment system but im running into a few problems which are a bit weird as the codebase im using was something i cooked up for tenebrae2 and it works as it should there.
What happens is that all doors plats etc go fullbright with some line distortion effect visible :S