← Back to team overview

kicad-developers team mailing list archive

Re: RTree implementation


Am Mo., 6. Aug. 2018 um 15:49 Uhr schrieb Seth Hillbrand <seth@xxxxxxxxxxxxx

> Am Mo., 6. Aug. 2018 um 14:18 Uhr schrieb Tomasz Wlostowski <
> tomasz.wlostowski@xxxxxxx>:
>> On 06/08/18 18:35, Seth Hillbrand wrote:
>> >
>> > There's another 32-bit RTree issue that is showing its face
>> > (https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=905221).  The last
>> > one (https://bugs.launchpad.net/kicad/+bug/1774316), we hacked around
>> > for v5 but as this seems to be a recurring theme, I'd like to address it
>> > with some finality.
>> >
>> > We could maintain the RTree implementation ourselves with updates to
>> > correct these errors.
>> > Or, we could use the Boost-based implementation
>> > (
>> https://www.boost.org/doc/libs/1_67_0/libs/geometry/doc/html/geometry/reference/spatial_indexes/boost__geometry__index__rtree.html
>> ).
>> >
>> > I have a basic framework for shifting to the Boost-based
>> > implementation.  In tests, I don't see a speed difference in running.
>> > Compiling might be modestly slower.
>> Hi Seth,
>> I would be careful with anything related to geometry in Boost. Good
>> things from Boost sooner or later end up in the standard C++ library
>> (e.g. unordered). We had a lot of trouble in the past with crashes in
>> boost::polygon that nobody could debug or even understand because of the
>> vast complexity of Boost code. We struggled for few months to replace it
>> with Clipper, since then, we've seen no crashes in polygon boolean ops.
>> If the solution to fix the current R-tree to work on 32-bit platforms is
>> to use doubles instead of floats, why not try it out? By changing to
>> boost::geometry, we'll likely have to report bugs there. I'm also quite
>> surprised this bug surfaced on one particular OS (Debian) 5 years after
>> this R-tree implementation had been introduced to pcbnew. Does anyone
>> here know why it crashes on Debian and not on other 32-bit systems?
>> Tom
> Hi Tom-
> You make good points here.  I'm happy to wait on the boost:geometry
> revision until we see if the double-fix addresses the issue.  I can't
> recreate the currently reported issue, so I'm not certain whether the
> double-fix addresses it as well as the original bug but it definitely makes
> sense to try it out.
> There may or may not have been a second report of this bug under Fedora
> (see comment 19 and below at https://bugs.launchpad.net/kicad/+bug/1774316)
> that may or may not have been 32-bit.  I'm vague on the details as the
> original reporter did not follow up.
> In the meantime, I'll push the double-fix to 5.0.1 and 5.1.
> -Seth

Hi All-

Heads up that we have another 32-bit Debian bug [1] that looks like the
same type of issue as before.  I've rebased and pushed my test replacement
of the RTree to [2] in case anyone would like to test it out.  Currently,
it only replaces the connectivity RTree but if there are no objections,
I'll continue to update the other RTree uses as well.

Also, Tom I checked with the boost dev team and the person who is
responsible for boost::polygon (1 guy) is not involved with the
boost::geometry team.


[1] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=911559
[2] https://code.launchpad.net/~sethh/kicad/+git/kicad/+ref/boost_polytri

Follow ups