If you simply want yes/no intersection I recommend using GJK. Erin Catto has a nice 2D GJK implementation you can port to 3D without too much trouble. I think Micha Mettke implemented a decent version recently:
Is there a 3D object intersection math library that is not a part of a physics framework?
Author
44 minutes ago, Dirk Gregorius said:Did you check out SOLID. It is written by Gino v.d. Bergen who is an expert in this field:
Yes, I've looked at it, along with OPCODE and ColDet, I'm trying to set something up with them at the moment, but there is absolutely no examples that I could find, it's just down to reading the raw manual and piecing things together, another thing is that solid, in particular, relies on callbacks during collision events, that kind of asynchronous handling is a bit strange for me (my code/engine is not structured to really use these kind of async methods). I just have a straightforward Move function inside my character controller that wants to check if it's ok to move into a location. Is there some place where I can just at least pseudocode implementations of the "separating axes" algorythm? Or better yet a working function?
1 minute ago, VanillaSnake21 said:Is there some place where I can just at least pseudocode implementations of the "separating axes" algorythm? Or better yet a working function?
I gather your boxes are arbitrarily oriented (not axis-aligned). If you're curious about the separating axis test, try searching online for 'obb sat' or 'obb intersection' (although SAT isn't the only way to test for intersection between arbitrarily oriented boxes, it's probably the most commonly documented method). Note that I'm using the term OBB here ('oriented bounding box') not because the algorithm is specific to bounding boxes, but because in practice the term OBB is frequently used when discussing this algorithm.
The SAT for OBBs is widely documented, and I imagine you could probably find some example implementations in the forum archives here on GDNet. A couple of things to be aware of though. First, the algorithm is vulnerable to numerical issues that need to be handled properly for a robust implementation, and not all implementations do so. Also, there are both more and less optimized ways to implement the algorithm, with the more optimized versions being (generally speaking) harder to understand and easier to get wrong. If the test isn't a bottleneck for you, I suggest going with a straightforward implementation that skips the optimizations and is more conceptually clear. (Unless of course you find a reliable source for an optimized version.)
If you find a source and aren't sure if it's correct or reliable, you could post a link here for us to take a look at.
Lastly, as mentioned previously there are other algorithms you could use as well.
Yes you can find all the information you'd ever want on SAT by Dirk's GDC lectures. Go to Box2D.org/downloads and read all of Dirk's resources. Mind you this is a rabbit hole, so if you only need boolean yes/no hittest, I highly recommend getting GJK going - you can easily add arbitrary shapes.
The value of GJK is a few points.
- It's a well designed algorithm. It's very difficult to beat a good GJK implementation in terms of performance.
- It trivially supports new shape types, meaning you write GJK once, and then write N tiny wrappers, where N is the number of shape types. This beats SAT where SAT requires N^2 implementations for case-by-case hand-written routines.
- You get closest points for non-intersecting configurations.
- Results from GJK can be cached, making continuous calls to GJK with the same shapes moving over time extremely fast (like checking players against each other each timestep).
- If you need to use SAT later (e.g. for manifold generation, you can and *should* use GJK inside your SAT implementations to detect different Voronoi region scenarios, like deep vs shallow cases - Dirk's resources mentions this kind of thing) then you are future proof.
- Migrating to swept yes/no hittest with GJK can be nearly trivial for non-rotating shapes, and doable for the rotating case with some clever root finding algorithm (like Catto's bilateral advancement - link to this is in the box2d.org/downloads page). So you are future proof for swept continuous detection if you need it later.
Of course GJK won't help if you need to compute manifolds (information on which axis shapes are penetrating, by how far, and clipping points). This is where SAT is needed.
For OBB here is my post to hand-derive a robust SAT implementation (with example implementation): https://www.randygaul.net/2014/05/22/deriving-obb-to-obb-intersection-sat/
Final note - please be careful which GJK resource you use. Basically all online resources for GJK have gaping problems with robustness, and nobody knows what they are doing. Micha's link is good (check my last post in this thread), and Erin's GJK resources are good. The rest of the GJK resources online are quite poor (even Casey Muratori's video is quite poor in terms of robustness).
Author
2 minutes ago, Randy Gaul said:I highly recommend getting GJK going
I've gotten the Mettekk implementation. One of the example applications he provides lists code for a polyhedra to polyhedra collision test, this is the decleration
polyhedron_intersect_polyhedron( const float *averts, int acnt, const float *apos, const float *arot, const float *bverts, int bcnt, const float *bpos, const float *brot)
What are the arot and brot rotations? My vertices are in world space so I don't have any rotations stored that are associated with the boxes. If I were to calculate these, would it just be relative the center of the object, or is this a world rotation of each axis?
I think I'm just going to write a simple "are any vertices of one box are contained in another box" as @dimi309 suggested. It does miss edge only intersections but I just want to get this implemented and move on.
You can probably pass in NULL or identity rotations. You can ask Micha on Twitter, he’s a nice guy 
6 minutes ago, VanillaSnake21 said:My vertices are in world space so I don't have any rotations stored that are associated with the boxes. If I were to calculate these, would it just be relative the center of the object, or is this a world rotation of each axis?
I think I'm just going to write a simple "are any vertices of one box are contained in another box" as @dimi309 suggested. It does miss edge only intersections but I just want to get this implemented and move on.
If all you have are pre-transformed vertices, the SAT is probably a poor choice anyway (you could probably compute the necessary parameters - center, axes, and extents - from the vertices, but that would be somewhat roundabout). That said, I do wonder what circumstances you're dealing with that lead you to having transformed vertices available but not the underlying parameters (e.g. transforms) themselves.
Even the 'vertex containment' test (which as noted doesn't cover all cases anyway) will require jumping through some hoops if all you have is transformed vertices. (Perhaps that aspect of things is making this more difficult than it needs to be.)
Author
3 hours ago, Zakwayda said:If all you have are pre-transformed vertices, the SAT is probably a poor choice anyway (you could probably compute the necessary parameters - center, axes, and extents - from the vertices, but that would be somewhat roundabout). That said, I do wonder what circumstances you're dealing with that lead you to having transformed vertices available but not the underlying parameters (e.g. transforms) themselves.
Even the 'vertex containment' test (which as noted doesn't cover all cases anyway) will require jumping through some hoops if all you have is transformed vertices. (Perhaps that aspect of things is making this more difficult than it needs to be.)
I'm starting to think that too, every algorithm I see has angles and positions so my implementation is probably not correct to begin with. The reason my vertices are all pre-transformed is my collision boxes are not computed based on geometry, as in they are not bounding boxes. I'd like to get basic obstacles implemented quickly, like world boundaries (so for example my character doesn't fly off the edge of the map), so it's easier right now for me to define these walls based on world coordinates. The function to build the collision box is
CollisionBox(float2 xzStart, float2 xzEnd, float height) So i just define it as a line in xz plane, anchor the bottom to the terrain and set a small width. It doesn't seem right, but it's the only way that I see that allows me to place them accurately within the world. Should I just be creating a unit box, and transforming like I would a regular mesh? But how I would position it accurately? Without an editor/GUI, I would have to just by trial and error until it's positioned right?
For example: I want to create a world boundary. I know the coordinates of the corners of my world, so using my method I just create a box from one corner to the other, already in world coordinates. Using the transform method, I'd have to calculate the length of the box as a scale matrix, then claculate the rotation matrix, position the center piviot on the vertex instead of mesh center and then translate it to the edge of the map.
Is there a better way to do this then what I have right now?
And in the near future, I'm not really planning to have detailed collision detection, for the next few engine iteration cycles it's sufficient for me to just suffice with terrain walls. The more I think about it, the more I just want to use the even plainer, "is one box's vertex inside the other box" method, because realistically, nothing is going to be tumbling in the near future, so I don't even think I have to worry about edge to edge collisions being missed but still, but if you can recommend a better approach, I'd definitely take a look at it.
For what it's worth, if you have a function like this:
CollisionBox(float2 xzStart, float2 xzEnd, float height) That works as you've described, then you have all the information you need for a proper oriented box anyway. I don't know how the CollisionBox() function is implemented, or if it's your own code, but it might interesting to see the code if you wanted to post it.
In any case, all the needed information is implicit in what you're doing already. Based on your description and your diagram, it seems like the code must be implicitly computing the box axes and extents, and the center could be computed easily as well. Then you'd have a box in center-axes-extents form and could use the SAT or perhaps one of the other algorithms suggested in this thread.
As for an overall approach, it might be interesting to know what shape your agents are (sphere? cylinder?), and whether there's a vertical component to motion that matters from the point of view of collision detection and response (e.g. jumping over things) or whether all motion is effectively confined to the ground plane. If the latter, it seems like you could at least entertain the idea of a strictly 2-d solution, which might reduce the complexity a bit.
Also, if you decide to use the SAT but know that all boxes will be aligned with the up axis, you could simplify that test as well.
If more input would be helpful, maybe you could describe the parameters and requirements a bit more. (Based on what you're describing so far, I'm wondering if maybe solutions like arbitrary 3-d SAT or GJK might be needlessly complex.)
Author
37 minutes ago, Zakwayda said:That works as you've described, then you have all the information you need for a proper oriented box anyway. I don't know how the CollisionBox() function is implemented, or if it's your own code, but it might interesting to see the code if you wanted to post it.
CollisionBox::CollisionBox(DirectX::XMFLOAT2 startXZ, DirectX::XMFLOAT2 endXZ, float width, float height)
{
//bottom plane
mPoints[0].x = startXZ.x;
mPoints[0].y = 0.0f;
mPoints[0].z = startXZ.y;
mPoints[1].x = endXZ.x;
mPoints[1].y = 0.0f;
mPoints[1].z = endXZ.y;
mPoints[2].x = endXZ.x + width;
mPoints[2].y = 0.0f;
mPoints[2].z = endXZ.y - width;
mPoints[3].x = startXZ.x + width;
mPoints[3].y = 0.0f;
mPoints[3].z = startXZ.y - width;
//top plane
mPoints[4].x = startXZ.x;
mPoints[4].y = height;
mPoints[4].z = startXZ.y;
mPoints[5].x = endXZ.x;
mPoints[5].y = height;
mPoints[5].z = endXZ.y;
mPoints[6].x = endXZ.x + width;
mPoints[6].y = height;
mPoints[6].z = endXZ.y - width;
mPoints[7].x = startXZ.x + width;
mPoints[7].y = height;
mPoints[7].z = startXZ.y - width;
mCollisionBoxList.push_back(this);
}
Just pretty straight forward offsets from the position. Anchoring the wall at 0 at the bottom, and going up to specified height.
I didn't debug the code yet since the whole system is not working, so probably will have to adjust the addition/subtraction signs in other quadrants, but this works in +x, +z based on how I drew it up (I think)
The layout of the points follow this diagram (see image):
The agents are all boxes, (at least at the moment). If I could get some additional algorithms running I wouldn't mind making the player a capsule and adding spheres to the world, at this point I can't even deal with a box, so if anything I'd be happy if at least this worked.
Vertical component does matter, I do want to incorporate jumps into the next iteration. And yes,all the collision boxes for the foreseeable future will remain parallel with y-axis.
As for the parameters/reqs - very rudimentary. Player with her collision box, world with only bounding walls. At most complexity, think of a maze, tall walls, short walls, being able to go around them. I will eventually transition into more complex objects like doors, maybe a house that could be walked through, but I feel like that's down the line and I'd be able to work it out if I had the basic algorithms down.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
