Planes and Point-Plane Collision

Discuss programming topics for the various GPL'd game engine sources.
Post Reply
Baker
Posts: 3666
Joined: Tue Mar 14, 2006 5:15 am

Planes and Point-Plane Collision

Post by Baker »

I've been reading up on plane math lately (watching YouTube vids, reading web sites). The collision parts in the engine with dist < 0 and such are beginning to make a lot of sense.

This one I've found has been the most helpful: http://gamedeveloperjourney.blogspot.co ... ction.html And in particular I love this part. Killer!

Image

I find the above priceless because I understand 2D math, 2D circles (sin/cos/tangents/chords), 2D polygons rather well from some exhaustive reading and maybe 30 sheets of paper working out problems earlier in the year. The sum of all the angles in any concave polygon is 360 degrees and the above uses this to detect if point x, y, z lies inside a polygon.
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: Planes and Point-Plane Collision

Post by Spike »

distancefromplane = dotproduct(planenormal, point) - planedist;
if (distancefromplane < 0)
pointisbehindtheplane();

nothing to do with angles.
works in 2d and 1d too, of course (though in 1d, your plane normal is either 1 or -1, and the dotproduct comes out as basically 'point').
Baker
Posts: 3666
Joined: Tue Mar 14, 2006 5:15 am

Re: Planes and Point-Plane Collision

Post by Baker »

I meant for after comparing a confirmed plane collision point to the potential polygon of collision after using the plane formula to verify a line (segment) collision.

The above part about the angles would be a slow substitution for this kind of thing:

(probably more accurate as the below looks biased towards quadrilaterals, which in a Quake map most of the surfaces tend to be)

Code: Select all

		ds = (int)((float)DotProduct (mid, surf->texinfo->vecs[0]) + surf->texinfo->vecs[0][3]);
			dt = (int)((float)DotProduct (mid, surf->texinfo->vecs[1]) + surf->texinfo->vecs[1][3]);
			// out of range
			if (ds < surf->texturemins[0] || dt < surf->texturemins[1]) continue;

			ds -= surf->texturemins[0];
			dt -= surf->texturemins[1];

			// out of range
			if (ds > surf->extents[0] || dt > surf->extents[1]) continue;
As I understand it, which I'm still working through these things, so my level of understanding is a bit vague.
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: Planes and Point-Plane Collision

Post by andrewj »

That piece of code figures out the texture coordinate of a point on a polygon.

What's that got to do with collisions?

I wanna say something helpful, but I don't know what you're trying to do.
Baker
Posts: 3666
Joined: Tue Mar 14, 2006 5:15 am

Re: Planes and Point-Plane Collision

Post by Baker »

andrewj wrote:That piece of code figures out the texture coordinate of a point on a polygon.

What's that got to do with collisions?

I wanna say something helpful, but I don't know what you're trying to do.
I was just trying to explain what the polygon angles summation was for in post #1 (very precise polygon collision).

The code in my immediate above post (ds, dt, extents, etc ...) is the code in RecursiveLightPoint in the Quake engine where it checks a polygon collision after the plane match is confirmed (and if ds, dt are out of range, it moves on to the next surface but the way it checks for a match uses 4 corners = rectangle).

[I may be confusing people because I'm interested in the geometry angle of all of this ... ]
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: Planes and Point-Plane Collision

Post by Spike »

the texture vectors are basically just more planes. each gives the 'normal' of a plane upon the previous plane, where the central texture coord is 0. Texture scaling is given by the scale of the normal. The texture extents then give the minimum and maximum bounds of the actual rectangle of the surface.
(Actually, this is a somewhat simplistic view, as the texinfo is not guarenteed to be aligned to the surface, only that the x/y relative to the surface is the same, the z value can be quite different, depending on scale, however that's not relevent as the deviation to the side is effectively nullified by the dotproduct).
This is all 'simple' plane equations, nothing to do with sin or cos or any angles. Its just across the plane rather than infront of the plane. Hence the use of the tangent/bitangent, and yes, combined with the normal, you have a 3d box region and can work out the exact corners of the potentially visible surface, by using its extents.
Baker
Posts: 3666
Joined: Tue Mar 14, 2006 5:15 am

Re: Planes and Point-Plane Collision

Post by Baker »

Spike wrote:the texture vectors are basically just more planes. each gives the 'normal' of a plane upon the previous plane, where the central texture coord is 0. Texture scaling is given by the scale of the normal. The texture extents then give the minimum and maximum bounds of the actual rectangle of the surface.
I see. It would appear it works differently than I expected then. It really is all plane collisions in that code. I thought it was a texcoord comparison essentially (s0, t0 - s1, t1 in whatever style WinQuake would have stored them in the 32 pixels per unit sense), not planes.
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: Planes and Point-Plane Collision

Post by Spike »

well that is basically what its doing.

my earlier point was more that with your earlier chunk of code, trying to think of it in terms of angles is just going to confuse you - dotproducts can yield an angle when combined with normalised vectors and acos, but for this case, everything is kept purely as directions. Angles are only meaningful when you're comparing two directions (aka: 3 points), while this is a point and a plane.
But yeah, the texture vectors are two planes that state the direction in which the s+t coords increase, with the dist moving 0 away from the origin.
Of course, the texture vectors are shared between multiple surfaces, so the distance value is generally lower than abs(texturesize), so you need the mins+extents to check if the point being tested against these planes is within the quad.

if the point is outside the surface but within the triangle, you'll probably hit redundant info sticking out into space, yes. I guess the chances are that the light values in the non-existant part of the surface are more accurate than those on the ground below.
the leafs are all convex regions, so you'll not find a surface randomly jutting out of nowhere.
If you really want to constrain the samples to the region of the poly, you'll have to generate a plane from the edge lists and verify that the point is within ALL edge planes.
But really, that should be overkill as you know that you hit a solid, and that the other side of the node is solid, and that your current leaf is empty.
I suppose its possible that you get a single leaf with a diagonal v-shaped bottom, in which case yes you'll sample black from the cut surface half the time (depends on the qbsp). You can probably mitigate that by ensuring that the impact point ('mid') is within an epsilon of the surface plane, which should reject the bad plane (if they're co-planer, they should both have correct light samples).
Baker
Posts: 3666
Joined: Tue Mar 14, 2006 5:15 am

Re: Planes and Point-Plane Collision

Post by Baker »

If anyone is willing or interested, could someone explain the signbits for the planes that Quake uses.

In the standard engine itself, it only generates PLANE_ANYZ (frustum), so to backtrace I'd have to run the BSP compiler in debug mode to watch the plane signbit calculations.

Code: Select all

// 0-2 are axial planes
#define	PLANE_X			0
#define	PLANE_Y			1
#define	PLANE_Z			2

// 3-5 are non-axial planes snapped to the nearest
#define	PLANE_ANYX		3
#define	PLANE_ANYY		4
#define	PLANE_ANYZ		5
My guesses: Plane_X is a plane with X = 0, PLANE_Y and PLANE_Z the same. No clue as to what PLANE_ANYX, etc. mean. Further compound things, BoxOnPlaneSide uses 8 cases. I know these are for quick testing, but since the values aren't generated in the engine it makes watching the construction of the sign bits somewhat of a pain in the arse.
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: Planes and Point-Plane Collision

Post by andrewj »

Baker wrote:The code in my immediate above post (ds, dt, extents, etc ...) is the code in RecursiveLightPoint in the Quake engine where it checks a polygon collision after the plane match is confirmed
It does NOT do a proper polygon collision check though, it only checks that the point is inside the lightmap on that surface.

PLANE_X is when the normal of the plane is '1 0 0' or '-1 0 0'.
Similarly for PLANE_Y and PLANE_Z.

PLANE_ANYX is when the normal is closer to '1 0 0' or '-1 0 0' than to the other axes. In other words, it is closer to being PLANE_X than to being PLANE_Y or PLANE_Z.

PLANE_Z and PLANE_ANYZ are handy for knowing if the surface is a "floor" plane (when normal has positive Z component), or a "ceiling" when normal vector has negative Z component.
taniwha
Posts: 401
Joined: Thu Jan 14, 2010 7:11 am
Contact:

Re: Planes and Point-Plane Collision

Post by taniwha »

Baker wrote:

Code: Select all

// 0-2 are axial planes
#define	PLANE_X			0
#define	PLANE_Y			1
#define	PLANE_Z			2

// 3-5 are non-axial planes snapped to the nearest
#define	PLANE_ANYX		3
#define	PLANE_ANYY		4
#define	PLANE_ANYZ		5
PLANE_X is where the plane normal's Y and Z are 0 and X is 1. Similar for PLANE_Y and PLANE_Z. Thus using plane.type as an index into the point vector is a shortcut for the dot product (normal dot point).

PLANE_ANYX tells you that the plane normal's X component is larger than the other two components. I don't know how useful they are, but they seem to be used for selecting which axes to use for the s and t vectors (sw renderer: look in r_draw.c).
Leave others their otherness.
http://quakeforge.net/
Spike
Posts: 2914
Joined: Fri Nov 05, 2004 3:12 am
Location: UK
Contact:

Re: Planes and Point-Plane Collision

Post by Spike »

the texture vectors are axial. a floor polygon 64*64 with a slight incline at one side will be ANYZ. this means that the slope tiles correctly with respect to its neighbouring (flat) floor polygons upon the same grid. The same is true for beveled corners on walls, etc.
If it wasn't like that, you'd need to consider the length of the hypotenuse when texturing. Yes, this means angled surfaces have slightly lower texture resolution in at least one axis. This is of course what makes texture locking when rotating quite so painful.
There's no boxonplaneside advantage to ANYX etc. Its really only worth optimising only the major axis, and possibly their negatives, but as negatives are implemented using a 'planeback' flag instead, those do not need to be optimised for.
mh
Posts: 2292
Joined: Sat Jan 12, 2008 1:38 am

Re: Planes and Point-Plane Collision

Post by mh »

Just to elaborate further on how the dotproduct shortcut works:

If the normal is 1|0|0 then point dot normal is point.x * 1 + point.y * 0 + point.z * 0, which comes out as point.x; likewise for 0|1|0 and 0|0|1, so this is calculated in advance and the shortcut used if appropriate.

I haven't benched this but my gut feeling is that with a reasonably modern CPU the cost of the branch is going to be more expensive than the cost of just doing the calculation anyway, so it's most likely a case of an optimization that was valid in 1996 but is not any more.
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
Baker
Posts: 3666
Joined: Tue Mar 14, 2006 5:15 am

Re: Planes and Point-Plane Collision

Post by Baker »

Just want to say I understand all of this now. I really was making it too hard. I worked through several formulae and scenarios and it finally all made sense.

And some of the explanations above proved invaluable, more or less to reinforce that I was on the right track as I worked through the equations and what they meant. And some of the above posts give some added depth to how to apply/use the infos usefully.

[MH's dynamic light on brush models tutorial oddly enough is going to prove to be useful for some of the experimentation I may end up doing with this stuff.]
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 ..
Post Reply