Game Development Community

[Beta 5 Bug] Vector<> Does Not Sort Properly with dQsort()

by Ryan Mounts · in Torque 3D Professional · 09/12/2009 (3:08 pm) · 5 replies

I noticed this while working with MeshRoad. If you create a long, winding road and then do a container raycast that intesects multiple meshroad segments, they do not get sorted correctly by qsort in MeshRoad::castRay(). The sorted array should be from closest segment to farthest segment, so that the collision code can early-out, but they always end up sorted from farthest to closest, even if you reverse the logic of the qsort callback. With the array sorted backwards, the hit point ends up on the farthest segment instead of the nearest. It looks like the problem is qsort does not work properly with the Vector<> template class, because I replaced "Vector<MeshRoadHitSegment> hitSegments" with a regular array, "MeshRoadHitSegment hitSegments[]", and it sorted properly.

There are places all over the code where a Vector<> is sorted with dQsort(), which makes me think there are many places that suffer from this problem and could potentially be the culprits behind some really strange and hard to find bugs.

#1
09/13/2009 (9:53 pm)
Logged as THREED-744. Will investigate when I get a chance.
#2
09/14/2009 (3:39 am)
Ryan,have you tried using sort() instead of qsort() ?
I believe it will work well,even faster.
#3
09/14/2009 (11:58 pm)
No I haven't... maybe I'll try that tomorrow. But still, there are tons of places throughout the codebase where a Vector gets sorted with qsort(), and they don't seem to play nice together, at least from my experience with MeshRoad. I haven't really been able to troubleshoot it because I've never messed directly with Assembly code, which qsort() is written in for speed.
#4
09/16/2009 (1:44 am)
OK, figured this one out... it's not that the Vector class does not work with qsort(). They work fine together. The problem is the qsort callback in MeshRoad returns an F32 instead of an S32. The conversion issue leads to strange results. Here are the other places I've found in the codebase that share the same problem:

cmpDecalDistance (T3D/decal/decalManager.cpp)
cmpPortalDistance (sceneGraph/sceneRoot.cpp)
compareHitSegments (environment/river.cpp)
WindEmitter::_sortByScore (T3D/fx/windEmitter.cpp)
cmpZonePortalDistance (T3D/zone.cpp)

#5
09/16/2009 (4:01 pm)
nice catch.