Bug #167294 (sf1429049) “near-freeze in ObjectSnapper::_findCand...” : Bugs : Inkscape

Revision history for this message

Buliabyak-users (buliabyak-users) wrote on 2006-02-15:

#1

This is caused by snapping code frantically trying to snap
~1000 selected objects. So I'm assigning this to Carl. This
is obviously unacceptable - it hangs for about half an hour
in Inkscape::ObjectSnapper::_findCandidates. Perhaps there
should be a limit on the number of nodes/objects after which
it would not try to snap them. Or there's something wrong
with the findCandidates algorithm - I can't imagine why it's
so slow even on a thousand objects.

To the submitter: workarounds for this are: 1) use keyboard
move by arrow keys (it never snaps); or 2) disable all kinds
of snapping in prefs.

Revision history for this message

Rwst (rwst) wrote on 2006-02-16:

#2

this comment is made to ensure the assignee is being mailed.

(cyreve found out that assigning a bug report does not
generate mail to the assignee)

Revision history for this message

Irisson (irisson) wrote on 2006-02-17:

#3

my personal impression on this is that, when I select
several objects at once I expect them to behave as a whole
rather than as a set of different objects. therefore, I
would expect the selection to snap only to _its_ bouding box
and its "nodes" (the four handles of the rectangular
selection box). this would make snapping more reliable
because, right now, when many objects are selected, the
selection virtually never snaps (or the snapping behavior is
erratic) because there is always another object/node near a
grid line. see attached document for an example.

BTW, the same is true for groups (and maybe even "more
true"): the group bouding box is correclty defined in this
respect but the nodes of the group are all the nodes of the
objects present in the group. I would expect them to be only
the four handles of the whole group in order to have
snapping to nodes behave correctly.

what about this?

Revision history for this message

Irisson (irisson) wrote on 2006-02-17: snapping_killer.svg

#4

snapping_killer.svg Edit (13.0 KiB, image/svg+xml)

Other attachments

Revision history for this message

Rwst (rwst) wrote on 2006-04-25:

#5

the problem is that you are trying to snap thousands of
nodes to thousands of objects, and this with every mouse
movement! there is no efficient algorithm for that because
there is no preferred direction in which to snap, nor are
there preferred nodes or objects. we could restrict the
number of objects being snapped to, by using only the
current layer but this is no solution in principle.

@irisson:"my personal impression on this is that, when I
select several objects at once I expect them to behave as a
whole rather than as a set of different objects."

In this case, you need another option in the desktop
preferences dialog because your expectation, although
natural, is not the only possible.

@bulia: Is there a function that computes the bbox of all
selected objects? If so, I propose to implement the
mentioned behaviour as default, leaving the option for after
release. However, this will not solve the problem of
grouping the same objects and "snap nodes to objects".
should we give a warning? in doc prefs? in the status bar?

Revision history for this message

Buliabyak-users (buliabyak-users) wrote on 2006-04-25:

#6

> Is there a function that computes the bbox of all
selected objects?

Yes, but we also have something more appropriate here: the
"convex hull" function which, given a bunch of points,
returns those points which are on the edge (hull) of the
point set. I think this is what must be used here, not only
by default but always. This function is somewhere in
snapping code, please try to find and use it.

Revision history for this message

Rwst (rwst) wrote on 2006-04-27:

#7

the problem with convex hull is that there are worst cases
(e.g. star-like or circle-like) where the number of nodes of
the convex hull appoximates the number of nodes of all
objects, giving the same behaviour, freezing the system. to
avoid this at all, I would propose switching to bbox
whenever the expected complexity (#(nodes) * #(surrounding
objects)) exceeds a certain fixed limit, say 10k.

also, I'm reassigning to Carl since he's back from the dead.

Revision history for this message

Buliabyak-users (buliabyak-users) wrote on 2006-06-10:

#8

No wonder it's freezing: on each move event (i.e. each
screen pixel of movement), and on each of the 1000+ selected
object's points, it finds bboxes of all of 2000+ objects in
the document. Crazy.

rwst: actually our "convex hull" class is phoney, it does
not do a real convex hull but just a bbox of a set of
points. Anyway, this is what was used before, but for some
reason Carl removed it in rev 10342 of seltrans.cpp. I
restored this, and did the same for bbox snapping too: now
it snaps only on the outer bbox of the entire selection, not
on all selected objects' bboxes. Finally I made recursion in
_findCandidates a bit less stupid so that it avoids getting
bbox of a group and then bboxes of all its children all over
again. All this sped this up enough to close this bug. It
still takes a few seconds to move the 1000 lines, but not
hours as before. Really, one shouldn't ever use object
snapping in such a file, even if it worked correctly (which
it does not).