I must have missed a week somewhere because it’s nearly May already.
I had some problems with false positives/false negatives with my collision detecting algorithm. It works fine when the shapes involved are roughly the same size, but when the shapes have significantly different sizes, the midpoint-trick doesn’t work.
The problem specifically breaks down if the midpoint of the shapes falls inside the bounds of one of the shapes, which is often the case for a very large shape coming closer to a comparatively smaller shape. As I am using very large triangles for my scenes, and comparatively small ones for my bounding boxes, this is a major issue.
I’ll be looking at solutions to this problem this week, as well as alternate implementations to consider. Now the math revision is basically complete I hope to knock this problem off on Tuesday.
I notice I still haven’t done any more Unity tutorials. I became addicted to the sweet feeling of pushing my own engine further and further to a deploy state. I still want to do these tutorials so I’ll need to properly factor them in to my project plan and not just say “Do them on Thursday” because I discovered that I would shunt all my necessary outside-world tasks (shopping/housework/laundry/etc) on to those days so that I could spend more days programming.
Tuesday Midday: I couldn’t find a reasonable algorithm so I’m just going to brute force it. I’ll make it cute later if I need to.
So I’m going to take the triangle in question and see if it intersects the bounding box.
To do this, I’m first going to assess if the plane that the triangle is on intersects the box – I can simply see if all the points of the box are on one side, or the other. If they are, no intersection, early exit.
If there’s a split, then there could be an intersection.
I then need to take any two points of the triangle and make a plane out of it, that is parallel to the surface normal of the triangle, and then repeat the ‘all-or-none’ test with the points above/below this new plane.
If all the points are on the ‘outside’ of the plane/triangle, there’s no intersection – exit.
As soon as I find some points on either side of the plane/triangle, there’s an intersection – resolve and exit.
If all the points are on the ‘inside’ of the plane/triangle, then I need to take another two points and make another plane, and repeat the same set of checks.
If I still haven’t got an exit, then I need to check the third plane, only this time if all the points are on ‘inside’ then we have got an intersection.
I’ve got the code for the ‘if the hitbox intersects the plane’ working.
Now, I need to generate a plane from two points of a triangle.
I can generate a third point by multiplying one of these two points by the existing surface normal.
I can then work out a surface normal for this plane using the cross product of the edge I had just made, and the original edge.
This will then give me the surface normal.
I can then perform the ‘if the hitbox intersects the plane’ test on this new plane.
I must do this for all three edges of the triangle. This will allow me to pick up all triangle/box interactions I can think of.
The code is basically done (to my understanding) but I’m still getting many false positives/false negatives.
I wrote a lot of unfamiliar code so I’ll need to desk check it to make sure it’s doing what it’s supposed to.
My eyes have kind of glazed over from coding all day so I think I’ll leave it here and have a fresh look in the morning.
Where I left it last night;
There’s four checks in total that I need to make to work out if a triangle is intersecting the box, or not.
1 – The first check is the “Is the triangle’s plane intersecting the box”.
If yes, then the second check is:
2 – Are all the points ‘on one side’ of the triangle?
If yes, and that side happens to be the ‘outside’, then there’s no intersection.
Otherwise, if SOME points are on either side of the triangle, there’s an intersection.
If ALL the points are on the ‘inside’ of the triangle, then I need to repeat test 2 for each of the other sides of the triangle, until either I resolve there’s an intersection somewhere, or I get ‘inside’ for all three tests – which means the box is entirely enclosed by the triangle; and there’s an intersection.
The second test is fundamentally more complex, and that’s what I’m working on now.
However, today my wife is at home so I’m not sure how much work I’ll get done.
Test 2 appears to be working. I found that I had not been converting the vertexes in the test triangles to the same coordinate space as the hitbox. I’ve temporarily fixed this by converting in the physics section, I’ll later consider if it’s worth converting the scene coordinates to world coordinates at compile time, for scenes that don’t move (e.g rooms) this is acceptable. For scenes that do move (e.g an elevator, or space ships flying around) this won’t work.
It appears that the algorithm doesn’t work for triangles that aren’t aligned with an x, y, or z axis.
I will have to redo it using the boxes sides instead of the triangles sides.
Here’s the current test scene. The blue block is my actor. It’s currently flagging a collision, but if I angle it around the middle left/right or forwards/backwards, collisions fail, even though it’s clearly embedded in the wall.
I think the correct way to do this is to use the ‘separating axis test’. I’d seen this a couple of times but I mistakenly thought it was flawed like the ‘midpoint-plane’ test, I had started with.
This test is described in detail here and there is even some code I can review. This website is the support website for the book I’m using, “3D Math Primer for Graphics and Game Development”, Fletcher Dunn & Ian Parberry. This is also the book that taught me the finer details of 3D camera math, so they have proved themselves so far.
The main problem is that I do not intuitively understand what’s going on here. I understand the concept of ‘If you can draw a line that separate the points, you win’ but I’m not sure how to pick this line. I’ll have to look in to it.
Before then, I need to reduce the actors hit box into a 2D shape that lies along the same plane as the triangle. This will require performing a ‘point that ray intersects plane’ test, and compiling the results into whatever shape that results (could be a triangle, quadrilateral, pentagon or heptagon).
So that’s what I’ll do.