Hi! Alex was kind enough to give me shell access to his machine so I think I have this beast figured out.
1) The immediate cause of the crash is due to
DistanceOrdering::operator() accessing an invalid pointer
2) The reason for that is std::sort indexing before the array (man, I
hate templates!)
3) In turn, that is because std::sort doesn't do range check instead
assuming the comparison function is consistent
4) the comparison function (the same as in point #1) is apparently not
consistent when compiled with optimization/inlining. This may have
something to do with the 80 bit FPU in x86.
5) the problem arises when comparing the same item to itself
6) the spatialGetClosest is inserting the same item multiple times
into the array, triggering #5.
Tracking down the problem was hard because
* valgrind didn't work
* problem only happened with optimized build
* even debug prints sometimes made the problem go away
Hence, I am not entirely sure about the mechanism involved in #4.
Nevertheless, adding a special case for a==b does seem to fix the
segfault. But that is only symptomatic treatment, so let's have a
little peek at spatialGetClosest:
// base case, simplifes loop to do it seperately here
spatialFilterInBucket(sgBucketOffset(lon, lat, 0, 0), aFilter, result);
for (;result.size() < aN; ++radius) {
That's a wrong start. The nearest items need not be in the same bucket
as the reference point. Consider if the point lies at the edge of the
bucket - its closest neighbour may very well be on the other side of
the boundary. I think the same applies to the loop itself - you can't
simply stop due to having the required number of items because they
are not guaranteed to be the nearest ones. Also, I am not entirely
sure that the current cutoff distance checking is sufficient. Let's
suppose a coordinate system centered on the bucket containing the ref
point at the +,- corner. (See attached diagram) Assume bucket size 1,
requested range 1.05. So the ref point is at +0.5,-0.5. Box left
bottom bucket center at -1,-1 left top at +1,+1, distance from ref
point is 1.58 for both. That satisfies the 1.5 * 1.05 = 1.575 cutoff
condition so the code will never look at the bucket centered +2,0
which could contain a point at +1.5,-0.5 with distance 1.
for ( int i=-radius; i<=radius; i++) {
spatialFilterInBucket(sgBucketOffset(lon, lat, i, -radius),
aFilter, hits);
spatialFilterInBucket(sgBucketOffset(lon, lat, -radius, i),
aFilter, hits);
spatialFilterInBucket(sgBucketOffset(lon, lat, i, radius), aFilter, hits);
spatialFilterInBucket(sgBucketOffset(lon, lat, radius, i), aFilter, hits);
}
That seems to walk the four edges of the box, but it touches the
corners twice. Which is bad because it inserts duplicates that the
rest of the code doesn't expect.
I have attached the quick fix for the benefit of the people plagued by
the segfault.
--
Cheers,
Csaba/Jester
--- old/src/Navaids/positioned.cxx 2009-12-01 20:37:01.000000000 +0100
+++ new/src/Navaids/positioned.cxx 2009-12-11 03:23:03.000000000 +0100
@@ -243,6 +243,7 @@
throw sg_exception("empty reference passed to DistanceOrdering");
}
+ if (a == b) return false;
double dA = distSqr(a->cart(), mPos),
dB = distSqr(b->cart(), mPos);
return dA < dB;
<<attachment: bucket.png>>
------------------------------------------------------------------------------ Return on Information: Google Enterprise Search pays you back Get the facts. http://p.sf.net/sfu/google-dev2dev
_______________________________________________ Flightgear-devel mailing list Flightgear-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/flightgear-devel
