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.

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.

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).

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

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.