Right Distance For Sphere Entirely in Frustum

Discuss programming topics that involve the OpenGL API.
Post Reply
Baker
Posts: 3666
Joined: Tue Mar 14, 2006 5:15 am

Right Distance For Sphere Entirely in Frustum

Post by 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.
The night is young. How else can I annoy the world before sunsrise? 8) Inquisitive minds want to know ! And if they don't -- well like that ever has stopped me before ..
andrewj
Posts: 133
Joined: Mon Aug 30, 2010 3:29 pm
Location: Australia

Re: Right Distance For Sphere Entirely in Frustum

Post by 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
Posts: 2621
Joined: Thu Jan 24, 2008 12:04 pm
Location: inside tha debugger

Re: Right Distance For Sphere Entirely in Frustum

Post by revelator »

Old one from tenebraes shadow volume code. Uses 6 planes (near and far) but can probably be cooked down to 4 unless you want those.

Code: Select all

float SphereInFrustum(vec3_t o, float radius)
{
   int		p;
   float	d = 0;

   for( p = 0; p < 6; p++ )
   {
      d = frustumPlanes[p][0] * o[0] + frustumPlanes[p][1] * o[1] + frustumPlanes[p][2] * o[2] + frustumPlanes[p][3];

      if(d <= -radius)
	  {
         return 0;
	  }
   }
   return (d + radius);
}
Productivity is a state of mind.
Spike
Posts: 2914
Joined: Fri Nov 05, 2004 3:12 am
Location: UK
Contact:

Re: Right Distance For Sphere Entirely in Frustum

Post by 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
Posts: 3666
Joined: Tue Mar 14, 2006 5:15 am

Re: Right Distance For Sphere Entirely in Frustum

Post by Baker »

Spike wrote: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);
In Quake terms, the plane_normal is pitch, yaw roll, correct?

(I know the normal is a perpendicular line going out from the plane, and despite having 2 of those only the outside one counts because it is used for collision and rendering and such.)
The night is young. How else can I annoy the world before sunsrise? 8) Inquisitive minds want to know ! And if they don't -- well like that ever has stopped me before ..
Spike
Posts: 2914
Joined: Fri Nov 05, 2004 3:12 am
Location: UK
Contact:

Re: Right Distance For Sphere Entirely in Frustum

Post by Spike »

no, its x,y,z... normalized. in worldspace.
this ain't no angles thing.
mh
Posts: 2292
Joined: Sat Jan 12, 2008 1:38 am

Re: Right Distance For Sphere Entirely in Frustum

Post by mh »

All you need is the center and radius of the sphere; use the exact same frustum planes as before.

Code: Select all

bool R_CullSphere (float *center, float radius, int clipflags)
{
	int		i;
	mplane_t *p;

	for (i = 0, p = frustum; i < 4; i++, p++)
	{
		if (!(clipflags & (1 << i))) continue;
		if ((DotProduct (center, p->normal) - p->dist) <= -radius) return true;
	}

	return false;
}
The clipflags thing is just a test for trivially skipping the test on a frustum plane side; it can be removed if you want.
We had the power, we had the space, we had a sense of time and place
We knew the words, we knew the score, we knew what we were fighting for
taniwha
Posts: 401
Joined: Thu Jan 14, 2010 7:11 am
Contact:

Re: Right Distance For Sphere Entirely in Frustum

Post by taniwha »

A quick crash course (very incomplete) in vectors :)

While vec3_t in quake is used for both position and angles, plane normals always (in quake, anyway) uses position vectors. Position vectors simply describe how far along each axis you need to move to get to the point described by the vector.

Normals are usually unit vectors (makes using them a little easier) which means their length is 1 (ie, sqrt(x*x + y*y + z*z) == 1, or in quake terms: sqrt (DotProduct (vec, vec)) == 1). Converting a vector to a unit vector is easy; in terms of quake: VectorScale (vec, 1.0/sqrt(DotProduct (vec, vec)), unit). Normals (unit or not) are perpendicular to the surface to which they belong (much like spines on a sea urchin).

mh's code demonstrates why you want to use unit vectors for normals whenever you can (especially in anything (mostly) static). DotProduct(a,b) produces a value equal to length(a)*length(b)*cos(angle_between_a_and_b). If b is a unit vector, then the result is length(a)*cos(angle_between_a_and_b), ie the projection of a onto b (how far along b you need to go such that the line between a and your position on b forms a right angle with b).

If your vector is calculated on the fly, there are often tricks to avoid using sqrt (expensive!). One method (very good for checking whether a point is within a certain distance of another point) is to instead square the distance being checked. eg:

Code: Select all

// is point a (vec3_t) within r units from b (vec3_t)?
vec3_t d
VectorSubtract (a, b, d);
//slow:
sqrt (DotProduct (d, d)) <= r;
//fast
DotProduct (d, d) <= r*r;
There are other tricks depending on the math involved.

BTW, mh's example code checks if the sphere is entirely on (or touching) the back side of the plane. For checking the front side, simply change the test to ">= radius" (no minus).
Leave others their otherness.
http://quakeforge.net/
revelator
Posts: 2621
Joined: Thu Jan 24, 2008 12:04 pm
Location: inside tha debugger

Re: Right Distance For Sphere Entirely in Frustum

Post by revelator »

mh's function is actually based on the code in software quake :) its a pretty neat little bugger.
A variant i use in realm uses lord havocs PlaneDiff macro.

Code: Select all

qboolean R_CullSphere (const vec3_t centre, float radius)
{
    if ((PlaneDiff(centre, &frustum[0]) <= -radius) ||
        (PlaneDiff(centre, &frustum[1]) <= -radius) ||
        (PlaneDiff(centre, &frustum[2]) <= -radius) ||
        (PlaneDiff(centre, &frustum[3]) <= -radius))
    {
        return true;
    }
    return false;
}
Productivity is a state of mind.
mh
Posts: 2292
Joined: Sat Jan 12, 2008 1:38 am

Re: Right Distance For Sphere Entirely in Frustum

Post by 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.
We had the power, we had the space, we had a sense of time and place
We knew the words, we knew the score, we knew what we were fighting for
revelator
Posts: 2621
Joined: Thu Jan 24, 2008 12:04 pm
Location: inside tha debugger

Re: Right Distance For Sphere Entirely in Frustum

Post by 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.

http://code.google.com/p/realm/download ... z&can=2&q=
Productivity is a state of mind.
revelator
Posts: 2621
Joined: Thu Jan 24, 2008 12:04 pm
Location: inside tha debugger

Re: Right Distance For Sphere Entirely in Frustum

Post by 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
Productivity is a state of mind.
Post Reply