Krzysztof Kosiński wrote:
2010/3/29 Vangelis Katsikaros <vkatsikaros@...1244...>:
Hello
I have briefly described in the past my thoughts on how the render can be improved by introducing spatial indexes.
The render has to find which shapes intersect with the user's viewport. Currently this is done by a full scan in display/sp-canvas.cpp:871 in sp_canvas_group_render() right? (Krzysztof gave some hints in another thread some days ago).
Inkscape recurses into the canvas tree, and renders objects whose bounding box intersects the bounding box of the visible area of the currently rendered tile. In principle this leads to O(N) performance in the worst case, where N is the number of objects in the document. However, I don't think spatial indexing would improve things significantly - the majority of the time is spent rendering the visible items rather than skipping the invisible ones.
Hi!
The performance of the indexing depends on the range query itself and the density of the data. The worst case is that the user's viewport is large enough to contain all the file's shapes. An average case is that the viewport contains some of the file's shapes.
The worst case is O(N). The average case has a complex type that depends of the index properties, the range query itself and the density of the dataset. But indexing performs the same or better than the full scan.
A better idea might be to use spatial indexing for determining which object is under the cursor (nr_arena_shape_pick) - this task takes about 20% of time on each motion event on complex drawings.
The same index can be used for both. Instead of a range query you run a point query, same principal, same algorithm.
- The index should be disk based (so that it can be saved and reused
when Inkscape opens the same file again)
I don't think it's a good idea:
- It will enlarge the SVG file.
- The overhead of parsing the index data might be higher than
creating it from scratch. 3. What if someone edits the SVG in some other editor and the index data goes out of sync with document contents?
Yes the disk based has some issues. 1. It can be a separate file, no need to touch the SVG. 2. I don't remember the numbers here, I'll get back to you. 3. Yes, that's an issue. A check can be made upon opening the file.
We can begin with something not intrusive and see how it goes.
- There should be a way to identify the shapes of the SVG uniquely
(either XML elements or elements from another abstraction Inkscape uses). Can anyone give me some pointers on how I should work for this issue?
Spatial indexing should be done at the SP layer (e.g. sp-path.cpp, sp-image.cpp, sp-item-group.cpp, etc.) or at the rendering layer (NRArenaShape et al); it definitely should not be done at the XML layer.
Ok, thanks for these info. I'll check the places you mention. __________________________________________________ �������������� Yahoo!; ���������� �� ���������� �������� (spam); �� Yahoo! Mail �������� ��� �������� ������ ��������� ���� ��� ����������� ��������� http://mail.yahoo.gr