!leaf_replaced assert triggered in csKDTree, when doing culling

[xordan]

This assert is occasionally triggered, it seems to happen fairly randomly.

 	crystalspace-1.9-vc9_d.dll!CS::Debug::DebugBreak()  Line 875	C++
 	crystalspace-1.9-vc9_d.dll!CS::Debug::AssertMessage(const char * expr=0x6b095d94, const char * filename=0x6b0abfc4, int line=218, const char * msg=0x00000000)  Line 82	C++
 	crystalspace-1.9-vc9_d.dll!csKDTree::DebugExit()  Line 218 + 0x23 bytes	C++
>	crystalspace-1.9-vc9_d.dll!csKDTree::DistributeLeafObjects()  Line 457	C++
 	crystalspace-1.9-vc9_d.dll!csKDTree::Distribute()  Line 591	C++
 	frustvis.dll!FrustTestBox_Front2Back(csKDTree * treenode=0x1f27e8c8, void * userdata=0x009ae2a0, unsigned int cur_timestamp=9808, unsigned int & __formal=0)  Line 662	C++
 	crystalspace-1.9-vc9_d.dll!csKDTree::Front2Back(const csVector3 & pos={...}, bool (csKDTree *, void *, unsigned int, unsigned int &)* func=0x663d6d30, void * userdata=0x009ae2a0, unsigned int cur_timestamp=9808, unsigned int frustum_mask=0)  Line 787 + 0x13 bytes	C++
 	crystalspace-1.9-vc9_d.dll!csKDTree::Front2Back(const csVector3 & pos={...}, bool (csKDTree *, void *, unsigned int, unsigned int &)* func=0x663d6d30, void * userdata=0x009ae2a0, unsigned int frustum_mask=0)  Line 849	C++
 	frustvis.dll!csFrustumVis::VisTest(const csBox3 & box={...})  Line 712	C++
 	engine.dll!csEngine::GetNearbyMeshList(iSector * sector=0x17ff4a0c, const csBox3 & box={...}, csArray<iMeshWrapper *,csArrayElementHandler<iMeshWrapper *>,CS::Memory::AllocatorMalloc,csArrayCapacityFixedGrow<16> > & list={...}, csSet<csPtrKey<iSector>,CS::Memory::AllocatorMalloc> & visited_sectors={...}, bool crossPortals=true)  Line 2369 + 0x18 bytes	C++
 	engine.dll!csEngine::GetNearbyMeshes(iSector * sector=0x17ff4a0c, const csBox3 & box={...}, bool crossPortals=true)  Line 2434	C++
 	crystalspace-1.9-vc9_d.dll!csColliderActor::CollisionDetect(iCollider * collider=0x1317fe30, iSector * sector=0x17ff4a0c, csReversibleTransform * transform=0x009aebf4, csReversibleTransform * old_transform=0x009aec4c)  Line 766 + 0x41 bytes	C++
 	crystalspace-1.9-vc9_d.dll!csColliderActor::AdjustForCollisions(const csVector3 & oldpos={...}, csVector3 & newpos={...}, const csVector3 & vel={...}, float delta=0.013285376)  Line 992 + 0x26 bytes	C++
 	psclient.exe!psCollisionDetection::AdjustForCollisions(csVector3 & oldpos={...}, csVector3 & newpos={...}, csVector3 & vel={...}, float delta=0.013285376, iMovable * __formal=0x1317f5d4)  Line 94	C++
 	psclient.exe!psLinearMovement::MoveV(float delta=0.013285376)  Line 501 + 0x33 bytes	C++
 	psclient.exe!psLinearMovement::MoveSprite(float delta=0.013285376)  Line 423 + 0xf bytes	C++
 	psclient.exe!psLinearMovement::ExtrapolatePosition(float delta=0.10200000)  Line 766	C++
 	psclient.exe!psLinearMovement::TickEveryFrame()  Line 787	C++

[anonymous]

When this happens can you go to line 454 in csKDTree::DistributeLeafObject() (file libs/csgeom/kdtree.cpp) and print out the values of split_axis, bbox_min, and bbox_max. Use either printf or print in debugger when the assert occurs.

[Lanarel]

With these crashes the debugexit prints some more info, which gives the core of the problem:

no leaf_replacedDistributeLeafObjects failed: !leaf_replaced
  This node contains the following objects:
    0: 'gobble' (1.#QNAN,-4.86345,-124.616)-(1.#QNAN,-3.75459,-123.391)

There may be more objects listed, they may be NPCs, players, or items, but
always one has a NAN (often in x-coordinate). I was able to reproduce such
a crash several times, and could see that bbox (which is printed above and
will cause bbox_min and max to be NAN as well) for that object is not
correct, from as far back as I can trace the existance of that object as
part of the sector. As I cannot find where this list is made, I got stuck there though.

If you want me to test something more specific, let me know.

[jorrit]

In revision r31800 I added additional testing to frustvis and dynavis (only in debug mode!) which should catch these problems earlier. Please try to reproduce the crash again and when it crashes and tell me the message you get.

[anonymous]

Finally got things running with CS 1.9 again. I reproduced the crash in a similar way (running into a wall), and got a similar message, this time for the char itself, as shown also by the first line, which is due to the added check from rev31800:

The transformed bounding box of 'stonebm' is invalid!
DistributeLeafObjects failed: !leaf_replaced
  This node contains the following objects:
    0: 'stonebm' (-1.#QNAN,5.61333,-147.534)-(-1.#QNAN,7.0605,-146.259)
Assertion failed: false
Location:         d:\prog\cs\libs\csgeom\kdtree.cpp:218

No other messages are seen in the many minutes before when trying to make it crash. While debugging in MSVC I can see that the problem exists at least 10 calls deep in the call stack (which is slightly different from above when going deeper). FOr example, when calling DoElasticPhysics(isElastic, elapsedTicks, deltaIdeal, actorSector); in psCamera::Draw(),

looking at actorSector, I find that the culler in there has an object that has a

kdtree that has objects of which minbox and maxbox have NAN values (and other values as printed in console).

Things must already go wrong when defining the bbox, but I cannot find where that is.

[xordan]

 http://svn.gna.org/viewcvs/cal3d/trunk/cal3d/src/cal3d/corebone.cpp?rev=533&r1=525&r2=533

It might be worth updating cal3d to this revision and testing again. This fixes a bug that caused bones with no vertices attached to have very large collision volumes. It may or may not be related, but it's worth a try.

[Lanarel]

That cal3d fix sounded promising, but unfortunately did not avoid the crash. Also, they did an API change just before this revision, so having CS use revision 533 requires some CS changes as well (which I gave up on :) ).

I will continue testing. If anyone has bright ideas, I am all ears :)

[xordan]

#618 seems to crash in the same place - on animesh meshes this time. So it's not a cal3d related bug.

[Lanarel]

Making some progress. In csFrustumVis::CalculateVisObjBBox, I printed the transformation info before and after doing the transformation. It would show good values a few times, and then just before it crashes, it shows that the rotation maxtrix is still the same, but the translation is NAN,NAN,NAN. Now I only have to find where that translation is changed. Any hints?

[Lanarel]

Found it. At least I hope there are not other 'it's. There is an uninitialized variable in cs, in collider.cpp (csColliderActor::AdjustForCollisions). In line 1005 vector bestBounce is not initialised. It is then used to check if some other values are larger and if so, use bestBounce to compute a new bounce, etc. This new bounce (with NaNs) is then used to compute a new position, which is set in a coordinate transform which is used in the frustvis culler to transform bounding boxes, which will then have Nans, and finally cause the !leaf_replaced bug.

If I change line 1005 to:

csVector3 bestBounce(0);

my very reproducible crashes are gone. I am not sure this is the best initial value though. It may have to be initialized with a position?

[res]

Depends: if bestBounce is a minimum of something it should be initialized with FLT_MAX, if it's a maximum with -FLT_MAX.

Or maybe the real bug is actually that bestBounce is used though it was never written to, in which case the fix would be to not letting that happen.

[anonymous]

It appears this loop is computing a best bounce , where bounce is something related to the velocity and the normal to the colliding obstacle. The bounce is computed in the loop, then compared with a best bounce, which is updated if it fits better. In the end, the best bounce is used to update the velocity (and position, transformation, etc). So I agree a 0 value is not a good initialization. It seems that it was intended that the first run through the loop (when bounced is false), it should ALWAYS set bestBounce=bounce. It then sets bounced to true, so the next time it will only change bestBounce when bounce is better.

So my (more educated :) ) guess now is that the if statement in line 1039 should read:

if(!bounced (localvel - bounce).SquaredNorm() < (localvel - bestBounce).SquaredNorm())

bestBounce = bounce;

[khaki]

The uninitialised variable should be fixed now in r32139.

[sunshine]

Closing as fixed. Re-open if problem persists.

[xordan]

- Merged to 1.4 branch, r32140.