Closed prime31 closed 5 years ago
To add to this, it looks like perfectly horizontal contacts also exhibit the same behavior as perfectly vertical ones.
The normal is also incorrect when a circle collides with the corner of an AABB, but only at very specific hit angles. In the following image the blue circle is cast up/down/left/right. The orange circles are the TOI collision positions based on the velocity and time. The yellow lines are the normal and contact position. You can see that the normals are all reversed and not where you would expect them to be based on the circle cast when hitting a horizontal/vertical AABB side. When hitting a corner, the contact position is correct but the normal is off at certain hit angles.
Hmm I thought I found and fixed these bugs, but apparently not all of them! Some of these code paths are a little new or not thoroughly tested, so I appreciate you posting them up.
Am I going to be able to copy + paste your scenario into the c2 demo, along with all the other test scenarios? I am a bit busy for the next few days, but I am likely to have time this weekend to dedicate looking into any scenarios you find and post here. It will be especially helpful if I'm able to copy + paste and immediately see the debug rendering of the problem scenario.
I see you removed the version info from the header. Just to be sure, which header version were you using? Is it latest?
Here are examples of other bugs people have report. I've been storing them as a collection of visual tests, sort of like unit tests. If you find a buggy scenario and post something I can easily make a function (like the code in your OP), then that's perfect for me: https://github.com/RandyGaul/cute_headers/blob/master/examples_cute_gl_and_c2/main.cpp#L859-L1008
I did the test with the latest version of the header as of a couple hours ago. Below is some copy/pasteable code that shows the contact_point bug for horizontal and vertical hits. I'll see if I can whip up a simple bit of code to show that AABB corner normal bug. That one will be a bit trickier to get data for but I'll update this issue with it tomorrow.
c2Circle circle;
circle.p = c2V(100, 500);
circle.r = 50;
c2AABB aabb;
aabb.min = c2V(1260, 0);
aabb.max = c2V(1280, 720);
c2AABB aabbTop;
aabbTop.min = c2V(0, 0);
aabbTop.max = c2V(100, 20);
c2AABB aabbBottom;
aabbBottom.min = c2V(0, 1000);
aabbBottom.max = c2V(1000, 1020);
c2v normal;
c2v contact_point;
c2v vel = c2V(5000, 0);
float toi = c2TOI(&circle, C2_CIRCLE, NULL, vel, &aabb, C2_AABB, NULL, c2V(0, 0), 1, &normal, &contact_point, NULL);
printf("toi: %f, normal: (%f,%f), contact_point: (%f,%f)\n\n",
toi, normal.x, normal.y, contact_point.x, contact_point.y);
vel = c2V(0, -5000);
toi = c2TOI(&circle, C2_CIRCLE, NULL, vel, &aabbTop, C2_AABB, NULL, c2V(0, 0), 1, &normal, &contact_point, NULL);
printf("toi: %f, normal: (%f,%f), contact_point: (%f,%f)\n\n",
toi, normal.x, normal.y, contact_point.x, contact_point.y);
vel = c2V(0, 5000);
toi = c2TOI(&circle, C2_CIRCLE, NULL, vel, &aabbBottom, C2_AABB, NULL, c2V(0, 0), 1, &normal, &contact_point, NULL);
printf("toi: %f, normal: (%f,%f), contact_point: (%f,%f)",
toi, normal.x, normal.y, contact_point.x, contact_point.y);
And the runnable version here: https://onlinegdb.com/BkWyutrcV
For the corner normal bug, the following code will repro it. This just starts with a circle cast down onto an aabb's top-right corner, moving the circle one pixel to the right each iteration. The expected result would be as show in the image.
c2Circle circle;
circle.p = c2V(525, 0);
circle.r = 50;
c2AABB aabb;
aabb.min = c2V(475, 200);
aabb.max = c2V(525, 250);
for (int i = 0; i < 25; i++)
{
circle.p.x += 1;
c2v normal;
c2v contact_point;
c2v vel = c2V(0, 500);
float toi = c2TOI(&circle, C2_CIRCLE, NULL, vel, &aabb, C2_AABB, NULL, c2V(0, 0), 1, &normal, &contact_point, NULL);
if (normal.y == 1.0)
printf("------- Normal jumped to (%.4f,%.4f). circle.p (%.1f,%.1f), aabb.min (%.1f,%.1f), aabb.max (%.1f,%.1f)\n",
normal.x, normal.y, circle.p.x, circle.p.y, aabb.min.x, aabb.min.y, aabb.max.x, aabb.max.y);
printf("corner bug toi: %f, normal: (%.4f,%.4f), contact_point: (%.1f,%.1f)\n",
toi, normal.x, normal.y, contact_point.x, contact_point.y);
}
The output of this shows how the normal jumps to directly vertical with some input combinations. The same happens for horizontal collisions.
corner bug toi: 0.300020, normal: (-0.0217,0.9998), contact_point: (525.0,200.0)
corner bug toi: 0.300080, normal: (-0.0407,0.9992), contact_point: (525.0,200.0)
corner bug toi: 0.300180, normal: (-0.0603,0.9982), contact_point: (525.0,200.0)
------- Normal jumped to (0.0000,1.0000). circle.p (529.0,0.0), aabb.min (475.0,200.0), aabb.max (525.0,250.0)
corner bug toi: 0.300321, normal: (0.0000,1.0000), contact_point: (525.0,200.0)
corner bug toi: 0.300501, normal: (-0.0999,0.9950), contact_point: (525.0,199.9)
------- Normal jumped to (0.0000,1.0000). circle.p (531.0,0.0), aabb.min (475.0,200.0), aabb.max (525.0,250.0)
corner bug toi: 0.300723, normal: (0.0000,1.0000), contact_point: (525.0,200.0)
corner bug toi: 0.300985, normal: (-0.1392,0.9903), contact_point: (525.0,199.9)
------- Normal jumped to (0.0000,1.0000). circle.p (533.0,0.0), aabb.min (475.0,200.0), aabb.max (525.0,250.0)
corner bug toi: 0.301288, normal: (0.0000,1.0000), contact_point: (525.0,200.0)
------- Normal jumped to (0.0000,1.0000). circle.p (534.0,0.0), aabb.min (475.0,200.0), aabb.max (525.0,250.0)
corner bug toi: 0.301633, normal: (0.0000,1.0000), contact_point: (525.0,200.0)
------- Normal jumped to (0.0000,1.0000). circle.p (535.0,0.0), aabb.min (475.0,200.0), aabb.max (525.0,250.0)
corner bug toi: 0.302020, normal: (0.0000,1.0000), contact_point: (525.0,200.0)
corner bug toi: 0.302450, normal: (-0.2747,0.9615), contact_point: (525.0,200.0)
corner bug toi: 0.302923, normal: (-0.1644,0.9864), contact_point: (525.0,200.0)
corner bug toi: 0.303439, normal: (-0.2941,0.9558), contact_point: (525.0,200.0)
corner bug toi: 0.304000, normal: (-0.2499,0.9683), contact_point: (525.0,200.0)
corner bug toi: 0.304606, normal: (-0.2855,0.9584), contact_point: (525.0,200.0)
------- Normal jumped to (0.0000,1.0000). circle.p (541.0,0.0), aabb.min (475.0,200.0), aabb.max (525.0,250.0)
corner bug toi: 0.305258, normal: (0.0000,1.0000), contact_point: (525.0,200.0)
corner bug toi: 0.305957, normal: (-0.3464,0.9381), contact_point: (525.0,200.0)
corner bug toi: 0.306705, normal: (-0.3549,0.9349), contact_point: (525.0,200.0)
corner bug toi: 0.307501, normal: (-0.3815,0.9244), contact_point: (525.0,200.0)
corner bug toi: 0.308348, normal: (-0.4002,0.9164), contact_point: (525.0,200.0)
------- Normal jumped to (0.0000,1.0000). circle.p (546.0,0.0), aabb.min (475.0,200.0), aabb.max (525.0,250.0)
corner bug toi: 0.309248, normal: (0.0000,1.0000), contact_point: (525.0,200.0)
corner bug toi: 0.310200, normal: (-0.4384,0.8988), contact_point: (525.0,200.0)
corner bug toi: 0.311208, normal: (-0.4611,0.8873), contact_point: (525.0,200.0)
corner bug toi: 0.312273, normal: (-0.4800,0.8773), contact_point: (525.0,200.0)
corner bug toi: 0.313397, normal: (-0.4991,0.8666), contact_point: (525.0,200.0)
Link to run the code: https://onlinegdb.com/H14kFSUqE
The expected result for this would be for the toi to increase very slightly each iteration of the loop, and the normal to rotate from directly vertical, clockwise as the circle moves. The actual results have the normal flipped and when it triggers the "directly vertical normal" bug, you can see the contact point gets a little crazy and is no longer on the aabb.
Thanks for the great repro! I’m eager to take a close look.
I've got one more for you, or at least I think I do. If I am understanding things, if c2Collided
finds a collision c2AABBtoCapsuleManifold
should always produce a manifold with at least one contact point. Is that right? If so, the following code seems to fail. Basically, its just a capsule with an aabb overlapping it. c2Collided
seems to pick up the collision but c2AABBtoCapsuleManifold
produces a manifold with no points.
c2Capsule capsule;
capsule.r = 25;
capsule.a = c2V(0, 0);
capsule.b = c2V(0, 50);
c2AABB aabb;
aabb.min = c2V(0, 0);
aabb.max = c2V(100, 10);
if (c2Collided(&capsule, NULL, C2_CAPSULE, &aabb, NULL, C2_AABB))
{
printf("c2Collided\n\n");
c2Manifold mc;
c2AABBtoCapsuleManifold(aabb, capsule, &mc);
printf("mc.count: %d\n\n", mc.count);
}
On a side note, do you want me to open separate issues for each of these or should I just keep sticking them all in here?
Posting them all here works just fine :)
I just wanted to report that raycasts are looking solid so far. Everything is coming back as expected on that front!
That's good the hear! The raycasting code is a lot more hardened than the TOI stuff. I have only done some basic usage of the TOI code, mostly here: https://github.com/RandyGaul/player2d
But this doesn't cover everything :)
Hey I didn’t forget. Just had a busy weekend. I blocked out some time Monday night to work on this (tomorrow).
I had to reform your first test to fit on screen.
Looks like TOI is correct but normal/point are not. I identified a logical error in the TOI result reporting code. An alternative idea is to query a support point on the resulting shape given the previous iteration's normal. I may have to tweak this a little bit, since I think there are still cases where the normal can change dramatically - however this should be a good solution at least for now, and is definitely an important improvement regardless of which normal is used.
I'll have to think a little more about the normal note... For another time :)
Very good catch on the Capsule to AABB bug. I found the culprit: I needed to adjust <
to <=
within the c2KeepDeep
function.
Commit coming along shortly.
Note in the animating case the "contact point" slides up the circle and isn't actually contacting the aabb. I think this is OK for now. Similarly to normal points I described earlier, I think I will have to spend a little more time thinking about a good way to report contact data.
But for now I think it's a pretty good solution.
https://github.com/RandyGaul/cute_headers/commit/dfaa33cf93af5e1db684da96c9d5a5e761d6bc0a
Closing for now, but feel free to comment more if you like, or open another issue if you find more problems!
Oh by the way, if you post up your C# port on github please open a pull request linking to your port in the documentation of cute_c2.h! That way people can find your port just by looking in the cute_c2.h docs :)
Or I can modify the docs if you just post up the link here.
I currently have the C# port in a gist but at some point it will make its way into a proper repo. I am currently testing the collision code in a private repo that isn’t ready to be made public yet (huge mess of an engine that is in progress).
I’ll try out the fixes today. Many thanks!
I just had a go at testing out the changes. The stability is definitely improved drastically though there are still some very out of range return values. I'll get you some proper repro data for these but using the "moving circle" method from the previous repro produces these results. The image below is a cast directly left of a circle into the two aabbs. You can see the normal is off by quite a bit for the one that collided into the left-most aabb:
The same exact test but with casting aabbs also has some odd results. The blue aabb is where the cast started. Orange aabb is the hit location based on the t
returned. Light blue box is the contact point, which as you can see is in a very odd location for aabbs. Yellow line is the normal which is also off for sure. I'll try to whip up proper repro's for these when I have a spare minute.
The current version of the C# port is here. The code will probably scare away 99% of C# devs though due to it almost entirely unmanaged structs and pointers to them.
Yeah I'll have to rethink the reporting. I will try a different strategy and report back.
OK trying out a different strategy to handle AABB/circle test cases. It also works quite well for my 2d platformer demo for capsules. Please try this out and let me know if you have more problems!
https://github.com/RandyGaul/cute_headers/commit/5d6ac0ea8ae7d6fb75d5235af5b6ff3d4531a12f
If I'm thinking through this correctly, now only configurations which are already colliding, or are too close for the TOI solver to work, will have trouble reporting accurate results.
Your link to the C# gist appears broken :(
P.S. I appreciate the time you've taken to post up all these reproductions! It's a great contribution to cute_c2. I'll add you onto the list of contributors once I get any problems you find hammered down.
If I'm thinking through this correctly, now only configurations which are already colliding, or are too close for the TOI solver to work, will have trouble reporting accurate results.
That would be absolutely perfect for my use case. My intention is do first do an overlap test and if that fails fall back to toi using the toi normal to deal with stick/bounce/slide responses.
C# gist here with the latest update. This link works for sure. It is very un-C# like, so you should enjoy the code. Uses a few techniques that would make most C# devs cry ;)
That last update seems to have fixed up the aabb contact point and made the circle to aabb normal more stable as well. Capsule c2Collided
and c2Collide
both seem still off but capsule toi seems spot on. Here is a gif showing the new stability for the circle-to-aabb stability:
I appreciate the time you've taken to post up all these reproductions! It's a great contribution to cute_c2.
My pleasure. I have a fantastic knack for breaking things. One of my best skills ;) I'm sure I will break more things as I get to actually integrating the cute methods into my in-progress engine/experiment.
I did copy paste your capsule manifold + collided code into my big list of bug scenarios. You mean there's still another bug with capsule to AABB manifold?
Edit: Wow I didn't even know C# could do pointers. That is wild.
If you can simply capture a gif of the problem scenario, I can easily write a mimick reproduction as long as I can see in the gif any visual errors. That way you don't have to write any C test cases.
C# gives you access to pointers much like C but if and only if it is unmanaged code (raw primitive only). Hence the really interesting structs I had to make of byte arrays (poly for example). You can only have a fixed size array if you want a pointer and the array can’t be to a c2v. Has to be a primitive so I use byte and just mess with the pointer directly to get array-like access.
I’ll whip up a little demo that prints out the C code on screen as a capsule is moved around in a few mins and post it back here.
Sounds good. I’m busy the next couple days, but will get to anything you post ASAP.
It's no rush at all. Take your time.
Here are the capsule issue details from what I have gathered so far. What it is doing is just calling c2AABBtoCapsule
for all the aabb's in the scene (just two in this demo). Then it calls c2Collide
and if a manifold is returned it will draw it.
Here is the hi-res video so you can read the debug text which dumps the aabb and capsule details.
if (c2AABBtoCapsule(aabb, capsule))
{
DrawText($" -------- Collided c2AABBtoCapsule(aabb, capsule). frame:{Time.frameCount}");
c2Manifold mc;
c2Collide(&capsule, null, C2_TYPE.C2_CAPSULE, &aabb, null, C2_TYPE.C2_AABB, &mc);
DrawText($" Manifold.count: {mc.count}");
if (mc.count > 0)
draw_manifold(mc);
}
I must have introduced a regression. I actually think I should create some unit tests for cute_c2.
Hi, just wanted to mention that I've been messing around with cute_c2 recently and I've been having a similar issue with capsule and AABB manifolds. Using essentially the code from your player2d repository in my own project, I find that the TOI stuff works great but the NGS "skinning" solution (in order to get TOI > 0 to stop the TOI algorithm failing next step) did not work when colliding a capsule into an AABB to the left or right of it - below seems to work fine, not sure about above.
Upon further inspection, it appears that the c2Collide function returns a manifold with a count of zero, despite the fact that there is clearly a collision between capsule and AABB (as the TOI is zero). Strangely enough if I decrease the height of the capsule to zero (essentially using a circle), the c2Collide function works fine and my "capsule" does not get stuck in the AABB as TOI is always slightly above zero (as intended).
Sorry for the lack of an example with this comment - when I get home from work I can mess around with the parameters and see if I can spot what the issue is?
That’s quite odd! Thanks for reporting. I’ll be taking a look soon. Any information you guys have is valuable for me to find the big faster, especially gif recordings. You can use licecap to easily record gifs on Windows.
That one sounds just like the capsule bug I detailed. The end caps seem to report a collision but only if it’s shallow. The sides don’t report a collision at all. I’ll get you a gif to go along with the code snippet I left up a few comments later today.
Here is a video showing the issue. In the top-left, the collision data is printed and when a collision is returned the normal and point is drawn on the capsule itself.
https://giphy.com/gifs/RKLvGGMSWRwS5vxJge
~Click on "media" and then you can see the full size mp4 so the text is visible.~ Click on "media" and then "source" and then you can see the full size mp4 so the text is visible.
I wasn't quite able to get a repro for some reason.
void prime31_cap_to_aabb_bug2()
{
c2AABB bb;
bb.min = c2V(-100.0f, -30.0f);
bb.max = c2V(-50.0f, 30.0f);
#if 1
c2Capsule capsule;
capsule.r = 10;
capsule.a = c2V(0, -25);
capsule.b = c2V(0, 25);
static uint64_t frame_count;
frame_count++;
int i = (frame_count / 3) % 60;
capsule.a.x -= i * 1.0f;
capsule.b.x -= i * 1.0f;
#else
c2Capsule capsule;
capsule.r = 10;
capsule.a = c2V(-75, 50);
capsule.b = c2V(25, 50);
static uint64_t frame_count;
frame_count++;
int i = (frame_count / 3) % 60;
capsule.a.y -= i * 1.0f;
capsule.b.y -= i * 1.0f;
#endif
c2Manifold m;
#if 1
c2Collide(&bb, NULL, C2_AABB, &capsule, NULL, C2_CAPSULE, &m);
#else
c2Collide(&capsule, NULL, C2_CAPSULE, &bb, NULL, C2_AABB, &m);
#endif
if (m.count)
{
DrawManifold(m);
gl_line_color(ctx, 1.0f, 0.0f, 0.0f);
}
else gl_line_color(ctx, 5.0f, 7.0f, 9.0f);
DrawAABB(bb.min, bb.max);
gl_line_color(ctx, 0.5f, 0.7f, 0.9f);
DrawCapsule(capsule.a, capsule.b, capsule.r);
}
I think next step would be to get exactly a reproduction case for me to try debugging.
Interesting. I’m in the process of putting together a little framework in straight C. I’ll whip up a repro for you once I get debug rendering in.
Cool, is this going to be some kind of open source framework for games, or something?
As of now, it’s just an experimental framework for my personal use. I’m basically going to mimic the pure ECS I’ve been building in C# but in C.
If I can put together a succinct, easy to explain and fun to use framework then I’ll open source it. Making a pure ECS “simple and fun to use” is the big challenge though. My goal is to have something easy enough that newish coders can use straight away.
Sounds interesting. What are the data structures for storing components, how do they get updated, and how does that relate to the entities? (my mind has been on a similar topic for a while)
Flecs baby. it’s still in early development but it’s already powerful. It stores Entities by archetype (groups of Components). Tables are all archetype based so iteration is crazy fast. Check it out on GitHub. It’s gonna be an interesting ecosystem to watch.
Oh yeah I've taken a look at flecs. I noted a few problems.
But if you're making a framework that already sets up the expectation that your framework's style would be imposed on the user. So I think an entity management or component system of some kind would make a lot more sense in a framework.
So maybe your experiment will turn out more successful than flecs :)
Yeah, my goal is to impose some sort of style for sure. I want to be able to whip something up fast with it and also have other people be able to understand it quickly and get rolling straight away. That being said, the C# framework I've been building is orders of magnitude more simple than Flecs and straight C. Its very free-form as well which is nice. You can basically "build your own engine" with it. Just slap some Component structs in there and define Systems to process them and you can do whatever you need.
ECS is a touchy subject these days, which is actually why i decided to make the second iteration of my framework an ECS. I think it might actually be able to be done really well, simply and elegantly. Maybe I'm wrong and Ill end up never going public with any of this crap! Who knows. Its worth a shot I suppose ;)
Regarding the issue replicating the error I was using quite large AABBs compared to the size of the capsule, and it appears the same is the case in prime31's gif. I notice that the AABB is quite small in your attempted replication, perhaps this has something to do with it?
Any updates here? If I don't get a repro for this case, I will eventually do thorough testing and an audit of c2 in its entirety. I'm actually planning to release my unit test header and write tests for all the functions in c2, but this is still a ways out, so if you'd like this last bug fixed sooner please do send along a repro!
Sorry about the delay getting a repro! I'm still in the process of getting my C framework up and running. It's taking longer than expected. At some point I'll have it running and will be able to get you a proper repro in C...
https://github.com/RandyGaul/cute_headers/issues/155
Made some good updates to c2TOI. Let me know if either of you still have problems! I’d love to get them all nailed down.
Going to close this out. Feel free to reopen it if needed :)
First off, thanks for posting the awesome code in this repo! I just converted cute_c2 over to C# and have been playing around with it.
I have been finding some very odd results for different configurations. I havent dug into why the issue is happening yet (seeing as how I am still cleanup up the C# port) but there are a few that are really easy to repro.
The first is a c2TOI of a circle (travelling right) against an AABB (not moving). Here is a full demo of the issue: https://onlinegdb.com/Sy3F1DScE with the code below:
Whenever a circle collides with an unrotated AABB, directly hitting its vertical edge the returned normal is flipped and the contact_point is way off. Notice in the demo the x normal is +1. If the edge collided with is not perfectly vertical (for example, the corner of an AABB) then the result is correct.
I'll separate out the other bugs into separate issues but first I want to test them in C to make sure it is cute_c2 and not my port!