Bug in cpSpaceSegmentQueryFirst

[Beta Carotene]

I am currently frustrated beyond anything I can even express. I have lost more than 3 days to whatever the hell this is. I find this bug utterly indescribable.

I am using cpSpaceSegmentQueryFirst for ray casting. Its just a simple ray cast from the enter of the character down to the ground. Sometimes however, if I am walking on a flat ground and come up to a ramp, I simply pass through it. I have debug drawn literally every part of the system and *everything* shows that the ray is simply not registering that its intersecting with the ramp. I have tried this with the regular segment query function as well, it does the exact same thing.

This problem is extremely hard to reproduce, it does not happen consistently. It seems to change with the time that I start the engine and the surrounding scenery (such as if there are boxes laying around in the general area, NOT touching any of the involved shapes).

I have tried literally everything down to the point that I have placed 2 lines of ray casting code next to each other that are identical and stateless and they do different things. One detects the ramp, the other doesn't.

Given the unpredictable nature of this and the fact that the surrounding scenery seems to effect it, I'm thinking this is almost certainly some kind of bug in the spatial index. I have stripped down my own code to bare bones and I can find nothing wrong.

Is there any possible leads that you could offer? I have a project based on this due in a few days and this is the only thing which is keeping me from finishing.

[Beta Carotene]

Oh thats just... terrific. It seems that the bug also does not happen if the camera is not following the player. A part of the system that could not have any less of a relation (and by that I mean absolutely no relation) to the physics system.

[slembcke]

Hmm. That sounds bad. A bit like something is using the value of an uninitialized variable somewhere. (Especially when you say that the camera seems to influence it.) There is only a few dozen lines of code involved and I didn't see anything there. I don't know of anything else could be causing the issue. Haven't had any bug reports related to the spatial indexing or queries for over a year, so I don't know what it could be. The last know bug was due to occasionally missing queries that passed directly through segment shape endpoints.

Do you have any suspicions about what is happening that I can try to make some tests from? Like it happens only at certain boundary conditions or something?

When you say: "I have placed 2 lines of ray casting code next to each other that are identical and stateless and they do different things. One detects the ramp, the other doesn't." Do you mean something like this?

Code: Select all

cpShape *shape1 = cpSpaceSegmentQueryFirst(space, a, b, layers, group, NULL);
// absolutely nothing happens in between
cpShape *shape2 = cpSpaceSegmentQueryFirst(space, a, b, layers, group, NULL);
// and then sometimes shape1 != shape2 ?


I have absolutely no idea how that could be possible. :-\ cpSpaceSegmentQueryFirst() is a completely pure function other than the final out parameter for the query info. The very first thing it does is to initialize it to a default state. I don't see anywhere it's using uninitialized variables in cpSpaceSegmentQueryFirst, SegmentQueryFirst (the helper function), cpBBTreeSegmentQuery, SubtreeSegmentQuery, or cpBBSegmentQuery.

If the above is true, then I hate to say it because it's so often wrong and so hard to verify, but maybe it's a compiler bug? I've come across 4 or so between GCC and Clang that I've had verified and fixed. So now I'm only mostly (instead of entirely) skeptical of the idea of compiler bugs. What compiler/OS combination is this for? Does it happen with a different compiler?

Another thing to try is to try the spatial hash instead of the bounding box tree.

[Beta Carotene]

well some... fascinating things happened when I switched to the spatial hash.

1) the loading time of my engine quadrupled

2) I doubt the bug is gone but I cant get it to happen now

3) I have a static platform moving at one point in the level. I know im not supposed to do that, but its not anywhere near where this problem is occurring. Before it just passed though items, and now its randomly pushing them. That may be just undefined behavior doing its thing, but it seems odd.

One more thing that may be kind of important, but its a bit hard to explain....

I got the idea that dealing with platform physics might be easier if I moved the character with respect to local space of the platform he is currently on instead of world space. It works beautifully in that I get the character syncing himself with the platform movements (whether rotating or moving linearly). I also can easily get the speed of his surface point so it contributes to things like running jumps.

However, when move with world space, the bug does not seem to happen anymore. I've been breaking my skull on my keyboard trying to figure out how in the hell those two problems are related. Its not like the character is detecting the ramp and sticking to the platform underneath, the ray casting from his just doesn't detect the ramp AT ALL.

[Beta Carotene]

also, Im using Windows 8 and MS Visual Studio 2010

[Beta Carotene]

Yeah it looks like turning on the spatial hash seems to make this go away (for now). Obviously that's not an acceptable solution at all though.

Here's another interesting thing. This happens on different ramps at different times, but they are all on the same vertical level. If I move the entire floor up or down by 0.5, it doesn't happen anymore, and when I move them back to those positions, it starts again.

[Beta Carotene]

yet another revelation... this one.... I don't know wtf.

Ok... so I have 2 rays.... one is being cast from the mouse, one cast from the character... both the same length and direction.

The one from the character sometimes (about the same frequency as the other bug) will start flickering on and off when it touches the floor. That is. One frame the ray will detect the floor, and the next frame it will not. It just alternates.

Now, the ray from the mouse will always detect the floor. HOWEVER, when I make the y coordinate of the origin of the mouse ray EXACTLY THE SAME (not more, not less) as the y coordinate of the character, the same flickering effect happens. The ray is casting down much further than the characters height, so this is not a rounding issue.

[slembcke]

"I have a static platform moving at one point in the level. I know im not supposed to do that, but its not anywhere near where this problem is occurring."

Ooohhh.... So here's a crazy hunch. Are you not calling one of the cpSpaceReindex*() functions promptly after moving the platform? So when the raycast descends the tree's nodes, it checks the two children in the order that the raycast intersects their bounding boxes. That way if the raycast hits something before it would even enter the second child node's bounding box, it knows it can skip that subtree. If you don't reindex a shape after moving it, then AABB node in the tree (and any of it's parent nodes) will have out of date bounding boxes. If the raycast hits both the out of date bounding box in the tree AND the shape after it's been moved it could definitely cause it to incorrectly reject entire subtrees. If it happens in the first few levels of the tree then the proximity of the platform is irrelevant. It can still cause nearly random false negatives across the entire indexed space.

Also, if you are moving a static shape, then you really want to be using a rogue (not added to the space) body. Create a body with infinite mass and moment, don't add it to the space, and manually update it's position and velocity.

[slembcke]

The spatial hash wasn't meant as a solution, just to see if it did anything interesting to help figure out what is going on.

Another thing which might help validate my theory is calling cpSpaceReindexStatic() immediately before where you call your queries. The more you describe the issue the more probable it sounds to me that entire subtrees are getting skipped in the tree due to some shape's bounds being outside of it's last indexed bounds. It would give you exactly the sort of seemingly random and very positionally sensitive issues that you describe. It really just depends on the specific structure of the tree.

[Beta Carotene]

unfortunately I tried that too... made no difference. That was actually the first thing that came to mind.

There's only one thing, but it doesn't seem like it should matter. I'm not calling it directly AFTER I move it, but rather directly before the ray cast. Does that still cause issues?