Jump to content
  • Advertisement
VanillaSnake21

Is there a 3D object intersection math library that is not a part of a physics framework?

Recommended Posts

I'll just mention that the function you posted doesn't actually seem to handle arbitrarily oriented boxes as your earlier diagram seems to suggest (at least as far as I can tell). It looks to me like in some cases the boxes will end up skewed or degenerate.

Are you visualizing the boxes somehow? If so, do they look correct? Or do some of them look skewed or otherwise malformed?

To be specific, it looks like the second set of vertices is always offset by (width, -width) from the first set (thinking in 2-d terms here). That'll only result in a 'proper' box (rectangular prism) for boxes of a certain orientation, and even then the width of the box won't actually be the value of 'width'.

Maybe I'm misreading the code, but I'm just wondering if it actually does what you intend.

Share this post


Link to post
Share on other sites
Advertisement
Posted (edited)
37 minutes ago, Zakwayda said:

I'll just mention that the function you posted doesn't actually seem to handle arbitrarily oriented boxes as your earlier diagram seems to suggest (at least as far as I can tell). It looks to me like in some cases the boxes will end up skewed or degenerate.

Are you visualizing the boxes somehow? If so, do they look correct? Or do some of them look skewed or otherwise malformed?

To be specific, it looks like the second set of vertices is always offset by (width, -width) from the first set (thinking in 2-d terms here). That'll only result in a 'proper' box (rectangular prism) for boxes of a certain orientation, and even then the width of the box won't actually be the value of 'width'.

Maybe I'm misreading the code, but I'm just wondering if it actually does what you intend.

 

I just painstakingly drew it out again, with a steep angle and it appears you're right, the steeper the angle of the box the more it turns into a trapezoid. The first time I drew it out it looked correct so I never double checked. I guess I have to solve dot products for 90 deg angles to generate the orthogonal vertices? But even then I would not be generating any implicit parameters. Do you think I should fix it or move to some other way of generating it? This was just a really comfortable way, but I guess since I have to rewrite everything anyways, might as well generate it in such a way as to generate required parameters for the algorithms to use.

20190528_202503.jpg

Edited by VanillaSnake21

Share this post


Link to post
Share on other sites

Yes, your drawing demonstrates the kind of issue I was referring to.

Creating the boxes properly would just involve a little vector math, which someone could probably easily sketch out for you here if you're interested. It would also give you the parameters you'd need for something like the SAT.

As for what direction to go overall, it probably depends on where you want to focus your energies. Using an existing physics library of some sort is one option, of course. If you want to do it yourself, you may find that getting good, robust collision detection and response behavior can be nontrivial, but it can be simplified somewhat depending on what constraints there are on the environment.

If you eventually plan on having an arbitrary 3-d environment with multilevel architecture (e.g. bridges, multiple floors) and arbitrary surface orientations, that might call for something fairly sophisticated. If on the other hand it's more or less a '2.5-d' environment where there's a height element, but everything is up-axis-aligned and there's only one 'layer', that could probably be done much more simply. It really depends on the details. If you want to pursue the box-based approach though, I or someone else can probably point you in the right direction on that.

Share this post


Link to post
Share on other sites
1 minute ago, Zakwayda said:

Creating the boxes properly would just involve a little vector math, which someone could probably easily sketch out for you here if you're interested. It would also give you the parameters you'd need for something like the SAT.

Thanks, it's just a dot product right? Solving for the unknown vector, I've done something like that for the camera, could probably get it to work, but what parameters will it produce that I can plug into SAT? From what I can see it's just going to give me correct orthogonal points (instead of the skewed ones) but I'm still only left with world space vertices at the end?

Share this post


Link to post
Share on other sites
22 minutes ago, VanillaSnake21 said:

Thanks, it's just a dot product right? Solving for the unknown vector, I've done something like that for the camera, could probably get it to work, but what parameters will it produce that I can plug into SAT? From what I can see it's just going to give me correct orthogonal points (instead of the skewed ones) but I'm still only left with world space vertices at the end?

There's a lot to cover here, but I'll try to provide a little more info to try to point you in the right direction.

First, I'll offer a suggestion that's just based on personal opinion and preference. It's about coordinate systems, which is sort of a controversial topic that people can feel very strongly about :| So I may get some pushback on this, but again, it's just opinion.

My suggestion is to switch to a coordinate system where the z axis points up or down. This would make the ground plane the XY plane, with z representing height/depth, which I think can be more intuitive for this sort of thing. But it's just a suggestion.

Anyway, back to the boxes. You don't need the dot product or to solve for a vector per se. This will be pseudocode, and off the top of my head, so I can't guarantee correctness, but here are the basics:

p0 = one end of box
p1 = other end of box

// Vector from one endpoint to the other.
vector3 diff = p1 - p0;

// Length of box.
float length = diff.length();

// Y axis is always the world y axis.
vector3 yAxis(0, 1, 0);

// Normalize to get an x axis for the box (or z - you can do it either way).
vector3 xAxis = diff.normalized();

// Use cross product to get z axis.
vector3 zAxis = cross(xAxis, yAxis);

// X extent is half the length.
float xExtent = length * 0.5;

// Y extent is half the height (whatever that is).
float yExtent = height * 0.5;

// Z extent is half the width (whatever that is).
float zExtent = width * 0.5;

// The center can be computed as follows (assuming the endpoints lie on the
// ground plane as in your images).
vector3 center = p0 + xAxis * xExtent + yAxis * yExtent;

At this point you have center/axes/extents, which is what you need for the SAT and perhaps other algorithms. You can also compute the world-space vertices, if you need them, from this same data. Note that this formulation centers the box along p0 and p1 rather than putting them at the corners as your current code does, but you can do it either way.

Again, the above was just typed into the post and not reviewed or tested, so there may be errors. Ideally you'll be able to figure out what the intent is and review it for accuracy yourself.

Lastly I'll just mention that there are various other ways you could go about this. For example, you could treat it as a '2.5-d' problem, with collision detection and response basically done in 2-d, and with jumping or whatever handled specially. You could, among other things, use 2-d lines or boxes for the walls and represent your agent using a circle or cylinder, and use closest-point tests to get sliding behavior (which you may or may not want). There are various things you might have to consider, such as tunneling and discrete vs. continuous tests, but my point is that there are other options (and that they might be preferable to what you have in mind currently, depending on the circumstances).

Share this post


Link to post
Share on other sites
1 hour ago, Zakwayda said:

Anyway, back to the boxes. You don't need the dot product or to solve for a vector per se. This will be pseudocode, and off the top of my head, so I can't guarantee correctness, but here are the basics:

Thank you so much, you've helped me so much! I had to draw everything you had in your pseudo code on paper to see it properly but it makes sense now. We have the vector basis, the center and the half lengths of all the axes. Giving me a complete representation of the box, no need to keep track of the points anymore. I've also finally found the OBB SAT implementation https://gamedev.stackexchange.com/questions/112883/simple-3d-obb-collision-directx9-c with exactly the parameters you described. I actually have a feeling this is going to work this time, THANKS!

Share this post


Link to post
Share on other sites

@Zakwayda

Hey, I think I got it to work, everything is colliding properly, but I'm just a little confused about the "center" propery and how it relates to the SAT algorithm, and was wondering if you can just explain it in a few words. 

I've gotten this implementation of the algorithm on the stackexchage page I've provided in the last comment, the signature it has for collision function is this

 

	bool mGetSeparatingPlane(const XMVECTOR& RPos, const XMVECTOR& Plane, const XMVECTOR& AxisX, const XMVECTOR& AxisY, const XMVECTOR& AxisZ, const XMVECTOR& Extents);

 

For the RPos, I'm just passing in the difference between the center coordinates of the two boxes I'm trying to compare (RPos = box1.Center - box2.Center), but the way you had the center calculated originally (I just copied it the way you typed it) is 

// The center can be computed as follows (assuming the endpoints lie on the
	// ground plane as in your images).
	XMVECTOR center = startXZv + xAxis * xExtent + yAxis * yExtents;

 

From what I can see center is just an artificial point that we define to be anywhere, it could even be on the outside of the object. In the way you defined it, it lies at the center of the XY plane face of the box. So my question is, how does the algorithm know that? Since it doesn't know how we compute the center, and it's not the true center of the object.

 

Another question I had is why did you place the center as the center of the XY plane? I've had a bit of an issue with that because in order to set the position of the collision box I use this function (it simply sets a new center for the box)

 

void CollisionBox::SetPosition(XMVECTOR newPos)
{
	mCenter = newPos;
}

 

but lets say I wanted to move the box to SetPosition(100, 0, 200) in my world, since my terrain is on (or close to) ground plane, I'm at y = 0

the box would appear to be in mid air. So I changed the centering to be just

// The center can be computed as follows (assuming the endpoints lie on the
	// ground plane as in your images).
	XMVECTOR center = startXZv + xAxis * xExtent;

To eliminate the Y and that worked to bring the box to rest on the ground level. What I'm asking is why does my SetPosition function have to know the way I create the center coordinate? I mean I still have to consider that the center coordinate is half way up the xAxis even with existing code. Or is there another way to set positions that I'm missing?

 

Thanks.

Share this post


Link to post
Share on other sites
Posted (edited)
bool mGetSeparatingPlane(const XMVECTOR& RPos, const XMVECTOR& Plane, const XMVECTOR& AxisX, const XMVECTOR& AxisY, const XMVECTOR& AxisZ, const XMVECTOR& Extents);

Maybe you could post your code for the above function. Your version only seems to take one box as an argument (represented as three axis vectors and an extents vector), but it seems like it should take two boxes (as the code you appear to be following does).

Quote

For the RPos, I'm just passing in the difference between the center coordinates of the two boxes I'm trying to compare (RPos = box1.Center - box2.Center)

That looks correct.

XMVECTOR center = startXZv + xAxis * xExtent + yAxis * yExtents;

That should be 'yExtent', but yes, that looks right.

Quote

From what I can see center is just an artificial point that we define to be anywhere, it could even be on the outside of the object.

Not so much. The center is a specific reference point - the geometric center of the box. (It's the point you'd most likely intuitively think of as the 'center of the box'.)

Quote

In the way you defined it, it lies at the center of the XY plane face of the box.

That may be what's causing the confusion. The key bit is this from my earlier post:

Quote

Note that this formulation centers the box along p0 and p1 rather than putting them at the corners as your current code does, but you can do it either way.

In one of your drawings from earlier, your start and end points are located at two corners of the box, but my code treats the start and end points as lying midway along two of the edges (the short edges, in your drawing). If you want to treat the start and end points as lying at the corners, you'll need to take this:

XMVECTOR center = startXZv + xAxis * xExtent + yAxis * yExtents;

And also add 'zAxis * zExtent' to get to the center of the box.

As for resting the box at ground level, you can do that via other means if you need (e.g. storing a position that's separate from the center), but you'll need to use the actual geometric center for the SAT (at least the way you're implementing it currently).

I hope clearing up the confusion about where the center is will help clear up some of the other issues :) But post back if not.

One more thing. I didn't fully review the reference implementation you linked to, but I can see that it doesn't deal with numerical issues and therefore isn't robust, technically speaking.

However, the fact that your boxes are always up-axis aligned should simplify things for you. With the SAT, you don't need to check the same axis more than once. In other words, if you already checked against vector A, you don't need to check against vector B if B is parallel to A.

I didn't work through it myself, but I think you'll find that when boxes always share an axis (y in this case), all the cross products yield either zero vectors (mathematically speaking) or vectors that are parallel to an axis from one of the boxes. Therefore, if I'm not mistaken you can skip the cross-product axes, which is where the numerical issues are introduced, meaning you don't have to worry about said issues. Also, you don't need to check the shared axis twice, which reduces the test to a mere five axes (x and z for both boxes, and the shared y axis). This makes intuitive sense because it's essentially a 2-d test, with a separate test (conceptually) to account for the height element.

I'm just typing this on the fly, and as usual I'll disclaim that I may have overlooked something or made a conceptual or technical error somewhere. As such, if you haven't already done so, I recommend digging into the SAT and trying to understand exactly how it works so you can independently confirm (or disconfirm) the information I'm giving you.

Hope that helps :)

Edited by Zakwayda

Share this post


Link to post
Share on other sites
Posted (edited)

@Zakwayda

I had to just change some minor things, to fit into my existing class and to use the DirectX vector math, but overall it's the same function. The reason it only has one box in the argument is because it compares that box to the internal box that's represented by the class. I tried looking over the code, but it's just a jumble of cross products, I don't feel like I know enough about it to start simplifying/optimizing it to fit my needs. Here is what it looks like after my changes:

 

bool CollisionBox::mGetSeparatingPlane(const XMVECTOR& RPos, const XMVECTOR& Plane, const XMVECTOR& AxisX, const XMVECTOR& AxisY, const XMVECTOR& AxisZ, const XMVECTOR& Extents)
{
	XMFLOAT3 ExtentsF;
	XMStoreFloat3(&ExtentsF, Extents);

	XMVECTOR PosPlaneDot = XMVector3Dot(RPos, Plane);
	XMFLOAT3 PosPlaneDotF;
	XMStoreFloat3(&PosPlaneDotF, PosPlaneDot);

	XMVECTOR XAxisPlaneDotSelf = XMVector3Dot(mXAxis*mXExtent, Plane);
	XMFLOAT3 XAxisPlaneDotSelfF;
	XMStoreFloat3(&XAxisPlaneDotSelfF, XAxisPlaneDotSelf);

	XMVECTOR YAxisPlaneDotSelf = XMVector3Dot(mYAxis*mYExtent, Plane);
	XMFLOAT3 YAxisPlaneDotSelfF;
	XMStoreFloat3(&YAxisPlaneDotSelfF, YAxisPlaneDotSelf);

	XMVECTOR ZAxisPlaneDotSelf = XMVector3Dot(mZAxis*mZExtent, Plane);
	XMFLOAT3 ZAxisPlaneDotSelfF;
	XMStoreFloat3(&ZAxisPlaneDotSelfF, ZAxisPlaneDotSelf);

	XMVECTOR XAxisPlaneDotOther = XMVector3Dot(AxisX*ExtentsF.x, Plane);
	XMFLOAT3 XAxisPlaneDotOtherF;
	XMStoreFloat3(&XAxisPlaneDotOtherF, XAxisPlaneDotOther);

	XMVECTOR YAxisPlaneDotOther = XMVector3Dot(AxisY*ExtentsF.y, Plane);
	XMFLOAT3 YAxisPlaneDotOtherF;
	XMStoreFloat3(&YAxisPlaneDotOtherF, YAxisPlaneDotOther);

	XMVECTOR ZAxisPlaneDotOther = XMVector3Dot(AxisZ*ExtentsF.z, Plane);
	XMFLOAT3 ZAxisPlaneDotOtherF;
	XMStoreFloat3(&ZAxisPlaneDotOtherF, ZAxisPlaneDotOther);


	return (fabs(PosPlaneDotF.x) >
		(fabs(XAxisPlaneDotSelfF.x) +
			fabs(YAxisPlaneDotSelfF.x) +
			fabs(ZAxisPlaneDotSelfF.x) +
			fabs(XAxisPlaneDotOtherF.x) +
			fabs(YAxisPlaneDotOtherF.x) +
			fabs(ZAxisPlaneDotOtherF.x)));
}

 

The above function is called by the other function listed below, which does all the heavy lifting:

 

bool CollisionBox::mCheckForCollision(const CollisionBox& box)
{

	//static XMVECTOR RPos;
	
	XMVECTOR RPos;
	RPos = box.GetCenter() - mCenter;

	XMVECTOR XXCross = XMVector3Cross(mXAxis, box.GetXAxis());
	XMVECTOR XYCross = XMVector3Cross(mXAxis, box.GetYAxis());
	XMVECTOR XZCross = XMVector3Cross(mXAxis, box.GetZAxis());
	XMVECTOR YXCross = XMVector3Cross(mYAxis, box.GetXAxis());
	XMVECTOR YYCross = XMVector3Cross(mYAxis, box.GetYAxis());
	XMVECTOR YZCross = XMVector3Cross(mYAxis, box.GetZAxis());
	XMVECTOR ZXCross = XMVector3Cross(mZAxis, box.GetXAxis());
	XMVECTOR ZYCross = XMVector3Cross(mZAxis, box.GetYAxis());
	XMVECTOR ZZCross = XMVector3Cross(mZAxis, box.GetZAxis());


	return !(mGetSeparatingPlane(RPos, mXAxis, box.GetXAxis(), box.GetYAxis(), box.GetZAxis(), box.GetExtents()) ||
		mGetSeparatingPlane(RPos, mYAxis, box.GetXAxis(), box.GetYAxis(), box.GetZAxis(), box.GetExtents()) ||
		mGetSeparatingPlane(RPos, mZAxis, box.GetXAxis(), box.GetYAxis(), box.GetZAxis(), box.GetExtents()) ||
		mGetSeparatingPlane(RPos, box.GetXAxis(), box.GetXAxis(), box.GetYAxis(), box.GetZAxis(), box.GetExtents()) ||
		mGetSeparatingPlane(RPos, box.GetYAxis(), box.GetXAxis(), box.GetYAxis(), box.GetZAxis(), box.GetExtents()) ||
		mGetSeparatingPlane(RPos, box.GetZAxis(), box.GetXAxis(), box.GetYAxis(), box.GetZAxis(), box.GetExtents()) ||
		mGetSeparatingPlane(RPos, XXCross, box.GetXAxis(), box.GetYAxis(), box.GetZAxis(), box.GetExtents()) ||
		mGetSeparatingPlane(RPos, XYCross, box.GetXAxis(), box.GetYAxis(), box.GetZAxis(), box.GetExtents()) ||
		mGetSeparatingPlane(RPos, XZCross, box.GetXAxis(), box.GetYAxis(), box.GetZAxis(), box.GetExtents()) ||
		mGetSeparatingPlane(RPos, YXCross, box.GetXAxis(), box.GetYAxis(), box.GetZAxis(), box.GetExtents()) ||
		mGetSeparatingPlane(RPos, YYCross, box.GetXAxis(), box.GetYAxis(), box.GetZAxis(), box.GetExtents()) ||
		mGetSeparatingPlane(RPos, YZCross, box.GetXAxis(), box.GetYAxis(), box.GetZAxis(), box.GetExtents()) ||
		mGetSeparatingPlane(RPos, ZXCross, box.GetXAxis(), box.GetYAxis(), box.GetZAxis(), box.GetExtents()) ||
		mGetSeparatingPlane(RPos, ZYCross, box.GetXAxis(), box.GetYAxis(), box.GetZAxis(), box.GetExtents()) ||
		mGetSeparatingPlane(RPos, ZZCross, box.GetXAxis(), box.GetYAxis(), box.GetZAxis(), box.GetExtents()));
	
}

 

Neither of those are exposed, the public function that interfaces with the other code is this:

 

bool CollisionBox::checkForCollision()
{

	for (CollisionBox* box : mCollisionBoxList)
	{
		if (box == this)
			continue;

		
		if (mCheckForCollision(*box))
			return true;
	}

	return false;
}

 

15 hours ago, Zakwayda said:

 

 Not so much. The center is a specific reference point - the geometric center of the box. (It's the point you'd most likely intuitively think of as the 'center of the box'.)

 

 

It's the geometric center of the box? But how? 

XMVECTOR center = startXZv + xAxis * xExtent + yAxis * yExtents;

Starting at point0 and moving down 1/2 of the x axis and then moving up 1/2 the y axis don't we just end up on the face of the box? Can you take a look at the picture and see where I'm getting it wrong? Don't we need to have the zAxis * zExent to get the geometric center of the box? But even at the moment, my center is defined as

XMVECTOR center = startXZv + xAxis * xExtent; 

I had to remove the y component to lower it to the ground, but the SAT is still working fine, why is that? 

 

This is the picture of how I understand it:

 

Also you can you see how my collision boxes are still miss-aligned? It's because of the center coordinate offset I believe:

 

 

 

Untitled-1.jpg

Edited by VanillaSnake21

Share this post


Link to post
Share on other sites

There seem to be several open issues, but for now I'll focus on what seems to be of most immediate relevance.

Quote

I had to remove the y component to lower it to the ground, but the SAT is still working fine, why is that?

If you're not using the geometric centers for your boxes but the test still seems to be working, I suspect it's only working incidentally, and that given different input you'd find that the results are not in fact correct. I can't be more specific without knowing more about the circumstances, but just because your code seems to be working under certain circumstances, I wouldn't assume that it's actually correct.

Quote

Starting at point0 and moving down 1/2 of the x axis and then moving up 1/2 the y axis don't we just end up on the face of the box? Can you take a look at the picture and see where I'm getting it wrong? Don't we need to have the zAxis * zExent to get the geometric center of the box?

We may be talking past each other a bit here. I actually covered this in my last post, but I understand it's a lot of information and it's easy for things to slip by.

Anyway, the issue is that you have the reference points positioned at corners of the box, whereas in my example code I treated the reference points as being midway along the edges. You are correct that if you're starting at a corner, you need to add 'zAxis * zExtent' to get to the geometric center (I mentioned this in my last post, but again, there was a lot of information there).

Your most recent drawing looks correct to me: you start at the corner, and add each axis times the corresponding extent to get to the geometric center. If you want the reference points to be corners (which it appears you do), then that is indeed how to compute the geometric center.

Based on what you've posted, it seems to me that clearing up the confusion regarding the box centers is probably the highest priority at the moment.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!