Which container used for path nodes?
I'm not sure where in the source tree to look for this, so I'll ask this here.
What container does Inkscape use to store the nodes of its paths? I mean, a drawing program would often use (in STL terminology) push_back, pop_back, insert and erase. (I don't think push_front would often be needed.) The contained value type would probably contain a few flags in addition to the x,y coordinates. So I'm curious what container you people chose to cater to these requirements.
Thanks.
-- Shriramana Sharma ஶ்ரீரமணஶர்மா श्रीरमणशर्मा
2013/4/22 Shriramana Sharma <samjnaa@...400...>:
I'm not sure where in the source tree to look for this, so I'll ask this here.
What container does Inkscape use to store the nodes of its paths? I mean, a drawing program would often use (in STL terminology) push_back, pop_back, insert and erase. (I don't think push_front would often be needed.) The contained value type would probably contain a few flags in addition to the x,y coordinates. So I'm curious what container you people chose to cater to these requirements.
I wrote a custom container based on boost::intrusive::list. This kind of container works like a doubly-linked list and additionally allows one to obtain an iterator from a reference to an element in constant time, which is a very common operation required in Inkscape.
Regards, Krzysztof
Hello and thanks for replying.
On Mon, Apr 22, 2013 at 7:30 PM, Krzysztof Kosiński <tweenk.pl@...972.....> wrote:
I wrote a custom container based on boost::intrusive::list.
Can you please point me to the exact location of this template in the source code? And is it like tied into Inkscape's internals in any way or easily adaptable to other value types.
This kind of container works like a doubly-linked list and additionally allows one to obtain an iterator from a reference to an element in constant time, which is a very common operation required in Inkscape
Why would one want that particularly in a vector editing application?
Thanks for your patient replies.
-- Shriramana Sharma ஶ்ரீரமணஶர்மா श्रीरमणशर्मा
2013/4/22 Shriramana Sharma <samjnaa@...400...>:
Hello and thanks for replying.
On Mon, Apr 22, 2013 at 7:30 PM, Krzysztof Kosiński <tweenk.pl@...847...0...> wrote:
I wrote a custom container based on boost::intrusive::list.
Can you please point me to the exact location of this template in the source code? And is it like tied into Inkscape's internals in any way or easily adaptable to other value types.
src/ui/tool/node.h and .cpp, class NodeList. Note that this is not a template. It's "based on" boost::intrusive::list in the sense that the structure is the same - it doesn't actually use it. It would require some work to adapt it for use outside of Inkscape.
This kind of container works like a doubly-linked list and additionally allows one to obtain an iterator from a reference to an element in constant time, which is a very common operation required in Inkscape
Why would one want that particularly in a vector editing application?
The list members are control points and receive GUI events through callbacks, which are their member functions. You need to be able to get an iterator to the element from the reference to the element itself, because the element reference is all you've got within the callback. (This sounds a little convoluted but I hope you get the idea.)
Regards, Krzysztof
On Tue, Apr 23, 2013 at 9:29 PM, Krzysztof Kosiński <tweenk.pl@...972.....> wrote:
src/ui/tool/node.h and .cpp, class NodeList. Note that this is not a template. It's "based on" boost::intrusive::list in the sense that the structure is the same - it doesn't actually use it.
Hi Krzysztof,
A few more questions regarding this:
1) A doubly-linked list is costly in terms of having to store the prev and next pointers per item. This cost is justified if the item-size is quite greater than the size of two pointers. Is that true in case of the Inkscape path nodes? Other than the X, Y coords, what other data would you store per node?
2) From what I could learn from the code, it seems as if you store off-curve i.e. handle points separately as part of the linked list and not as adjuncts of on-curve points, i.e. for a single cubic bezier you would have:
p1 (x,y,prev,next) c1 (x,y,prev,next) c2 (x,y,prev,next) p2 (x,y,prev,next)
and not something like:
p1 (x, y, pre.x, pre.y, post.x, post.y, prev, next) p2 (pre.x, pre.y, point.x, point.y, post.x, post.y, prev, next)
Is that right? This allows you to cut down the storage requirements in case of linear segments but at significant cost (many more prev,next) pointers in case of cubic segments. Was the tradeoff found acceptable?
Thanks!
2013/7/6 Shriramana Sharma <samjnaa@...400...>:
On Tue, Apr 23, 2013 at 9:29 PM, Krzysztof Kosiński <tweenk.pl@...847...0...> wrote:
src/ui/tool/node.h and .cpp, class NodeList. Note that this is not a template. It's "based on" boost::intrusive::list in the sense that the structure is the same - it doesn't actually use it.
Hi Krzysztof,
A few more questions regarding this:
- A doubly-linked list is costly in terms of having to store the prev
and next pointers per item. This cost is justified if the item-size is quite greater than the size of two pointers. Is that true in case of the Inkscape path nodes? Other than the X, Y coords, what other data would you store per node?
The trivial "cost" of two pointers is justified, because many algorithms operating on the nodes require the ability to insert / delete nodes at arbitrary positions and to splice two node lists together. These operations are constant time on a list, but linear time on a vector.
The nodes also store attributes related to their appearance and type.
- From what I could learn from the code, it seems as if you store
off-curve i.e. handle points separately as part of the linked list and not as adjuncts of on-curve points, i.e. for a single cubic bezier you would have:
p1 (x,y,prev,next) c1 (x,y,prev,next) c2 (x,y,prev,next) p2 (x,y,prev,next)
and not something like:
p1 (x, y, pre.x, pre.y, post.x, post.y, prev, next) p2 (pre.x, pre.y, point.x, point.y, post.x, post.y, prev, next)
Is that right? This allows you to cut down the storage requirements in case of linear segments but at significant cost (many more prev,next) pointers in case of cubic segments. Was the tradeoff found acceptable?
No, you must have misunderstood the code. Each Inkscape::UI::Node has two Inkscape::UI::Handle members, regardless of the type of the node. Handles are not stored in the linked list.
Before 0.48, the old node tool did store the handles in a linked list together with the nodes.
Regards, Krzysztof
participants (2)
-
Krzysztof Kosiński -
Shriramana Sharma