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).
The idea is to implement an index, so that the renderer performs the range query faster than the full scan.
Some basic ideas on the project. * The index is going to be a standard one like R-star (used in oracle, postgis, sqlite).
* This R-trees can support 3 dimensions without any performance penalty (if the index has many dimensions performance deteriorates and other kind of indexes perform better). If we do this project we can implement a third dimension (time), for future usage, and leave it there until Inkscape goes into animation.
* It would be better if the project is hosted in lib2geom. In this way Inkscape's code base undergoes the minimal changes (ideally no more than a few lines of code).
* The index should be disk based (so that it can be saved and reused when Inkscape opens the same file again)
* 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?
Any ideas are welcome.
Regards Vangelis
__________________________________________________ Χρησιμοποιείτε Yahoo!; Βαρεθήκατε τα ενοχλητικά μηνύματα (spam); Το Yahoo! Mail διαθέτει την καλύτερη δυνατή προστασία κατά των ενοχλητικών μηνυμάτων http://mail.yahoo.gr
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.
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 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: 1. It will enlarge the SVG file. 2. 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?
- 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.
Regards, Krzysztof
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
participants (2)
-
Krzysztof Kosiński -
Vangelis Katsikaros