2009/7/2 Vangelis Katsikaros <vkatsikaros@...1244...>:
Currently Inkscape looks *all* the shapes in order to find which are in the user's window (correct me if I am wrong). This is actually a spatial 2D query and has been solved efficiently in GIS database systems. Now, lib2geom offers a simple R-Tree solution, allowing for 2D spatial querying. There are still a couple of small tasks to do, and then we should go from memory-only indexing to memory-and-disk indexing (so the project isn't complete yet :)
Memory-and-disk indexing is not necessary for graphics applications. We are not going to process GIS-like quantities of data, and even then we can just use virtual memory.
By the way, the current R-tree implementation in 2Geom is somewhat ugly, for example it exposes naked pointers to nodes, so I'd be hesitant to use it right now.
Making heavy use of spatial indexing requires some significant architectural changes, so it gives me another thought. Our current double-tree architecture, where every element stores both its "semantic" content (SVG) and "representation" content (XML) is rather wasteful when it comes to memory, particularly when it comes to embedded images. Storing only the semantic representation and generating the XML representation on demand when saving could help with the memory hog problem. It would also make easier e.g. conditionally writing svg:path instead of svg:rect when the given rectangle has markers, or using svg:polyline instead of svg:path when a path has straight segments only. Abandoning the 1:1 XML-SP correspondence could give us more flexibility, and promote better coding (right now some places use XML tree calls where they should evidently operate on the SP tree).
On the other hand, this approach is more bug-prone. It's not clear to me now how to implement undo. We would most likely need to sacrifice the editing capability of the XML Editor and turn it into an XML Inspector.
Another area of potential improvement is the renderer. I heard from others that migrating to Cairo could halve the total memory usage.
Regards, Krzysztof