QGraphicsView v/s QCanvas

[kiranraj]

Hi guys,

I am planning to port an application in Qt3.3.6 to Qt4.2.
I have to check the memory usage in Qt4.2.
So created a canvas with 100k rects and millions of lines.

Custom rect class is derived from QPolygonalItem
and Line from QCanvasItem.(Qt3.3.6).

Initially in Qt4.2 i used the convinience QGraphicsRect and QGraphicsLine classes ,But the amount of memory consumed was almost same as that in Qt3.3.6.(approx 1.2g)

Since double type is used to store the co-ordinates in QGraphicsLine and QGraphicsRect.I just copied their implementation and changed the type of co-ordinates to int.

After that Memory usage was reduced to 50%.

guys y does Qt4.2 consumes less memory than Qt3.3.6. Is it the chunks concept in Qt3.3.6 that comes in to picture here??

Thanks .

[wysota]

Not only that. The overhead is mostly in the items themselves - for example all QCanvasItems are animation capable which means that each item stores things like velocity even if it's never used. With QGraphicsView you have to use QGraphicsItemAnimation explicitely.

[kiranraj]

Hi Wysota,

I read the QCanvasItem Source code.
As u said :
The overhead is mostly in the items themselves - for example all QCanvasItems are animation capable which means that each item stores things like velocity even if it's never used:

But,
Each QGraphicsItem contains QCanvasExtra * ( Pointer to a struct that holds the velocity information ) .

When a QGraphicsItem is created .QCanvasExtra * extra is set to Null.So no information regarding velocity is
stored in the item( for static objects) only 4 bytes is wasted in storing the extra pointer in each item.

Even if QCanvasExtra *extra isn't NULL. And if our CanvasItem is static. We will be wasting only ( 16 bytes
(size of QCanvasExtra) per item -Assuming size of double is 8 bytes).

Therefore i dont think that's the reason y i got such a reduction in memory.
And also there is 24 bytes difference in sizes of QGraphicsItem ( 64 bytes -include QGraphicsItemPrivate) and
QCanvasItem (40 bytes ).
Plzz let me know if iam wrong.

Coming to chunks concept.

I have no idea how, the Binary space partitioning takes less space than the chunks.
Please suggest me -

Which parts of the source code i should go through
Reasons for y BSP'S are used in Qt4.2

[wysota]

But,
Each QGraphicsItem contains QCanvasExtra * ( Pointer to a struct that holds the velocity information ) .

When a QGraphicsItem is created .QCanvasExtra * extra is set to Null.So no information regarding velocity is
stored in the item( for static objects) only 4 bytes is wasted in storing the extra pointer in each item.

Even if QCanvasExtra *extra isn't NULL. And if our CanvasItem is static. We will be wasting only ( 16 bytes
(size of QCanvasExtra) per item -Assuming size of double is 8 bytes).

Are you sure you're not mixing the classes? I doubt QGraphicsItem has a "QCanvasExtra" member... Maybe you're talking about QCanvasItem?

Therefore i dont think that's the reason y i got such a reduction in memory.

I didn't say that was the reason. I said one of the reasons is that QGraphicsItem occupies less memory than QCanvasItem - nothing more.

And also there is 24 bytes difference in sizes of QGraphicsItem ( 64 bytes -include QGraphicsItemPrivate) and
QCanvasItem (40 bytes ).
Plzz let me know if iam wrong.

If you want to compare those items, compare their subclasses as both QGraphicsItem and QCanvasItem are not used in practice. But the item volume is not everything that counts. Some data is stored for each item in the canvas/graphicsscene itself - for example the chunk/BSP-index data.

Coming to chunks concept.

I have no idea how, the Binary space partitioning takes less space than the chunks.
Please suggest me -

I don't think I understand your doubt... You want to know why BSP takes less space than chunks? First of all I don't know if it is true - I never suggested that. But I believe there is a good chance that this is true, because BSP may have a very limited number of nodes - it's complexity depends on the number and position of items, whether I believe the chunk system has a more complex structure.

For instance if you only have items in the upper-left quarter of the scene, you'll only need two nodes (+root) of the BSP tree to hold them all.

Reasons for y BSP'S are used in Qt4.2

Because it is very fast for non-moving objects. You only need at most log(n) comparisons to find all items occupying a particular position in the scene (where "n" stands for the number of "cuts" used to partition the scene).

[kiranraj]

Are you sure you're not mixing the classes? I doubt QGraphicsItem has a "QCanvasExtra" member... Maybe you're talking about QCanvasItem?

Sry ....I was talking bout QCanvasItem over there.

If you want to compare those items, compare their subclasses as both QGraphicsItem and QCanvasItem are not used in practice

Yes ,Since they are abstract classes we cannot create objects of these classes.

In Qt3.3.6 the custom rect created was derived from
QCanvasPolygonalItem( Contains - QBrush and QPen ).

In Qt4.2 the custom rect created was derived from QAbstractGraphicsShapeItem which
also contains QBrush and QPen.
So i looked at the sizes of QGraphicsItem and QCanvasItem.

For instance if you only have items in the upper-left quarter of the scene, you'll only need two nodes (+root) of the BSP tree to hold them all

I browsed the source code of QCanvas.
Yeah ,In the above case ,redundant chunks are created and only few chunks maintains
item information.

Because it is very fast for non-moving objects. You only need at most log(n) comparisons to find all items occupying a particular position in the scene (where "n" stands for the number of "cuts" used to partition the scene).

In Qt3.3.6 from what i understood.
QCanvas maintains QCanvasData *d member ,which contains
QPtrDict<void> *itemDict (which is simple hash table-based on linear probing ).

So,in the average case searching here takes O(1)-constant time right??-faster than
O(log n) algo.


Please correct me if iam wrong ...n thank you for ur invaluable explanation.
Could u plzz give a nice link explaing BSP's.

[wysota]

So,in the average case searching here takes O(1)-constant time right??-faster than O(log n) algo.

The problem is not finding an item but finding all items colliding with another item (in other words finding all items occuping fragments of the scene occupied by a particular item). If you wouldn't have any caching/heuristic mechanism, you'd have to do a linear search through all the items. With BSP you simply check the nodes occupied by an item (so checking is probably O(1), but moving the item in the tree is O(lgn) which is greater than O(1) so the overall cost of manipulating the tree is O(lgn)).

Not going into details - run the 40000 chips demo from Qt4, but change the number of items to 1E+6. Check memory usage and usability. Then do the same with QCanvas and Qt3. Again check memory usage and application responsiveness.

[Bitto]

Our memory measurements have shown that a QGraphicsItem on average (depending on the compiler and compiler options) consumes about 80 bytes, and QCanvasItem consumes about 64 bytes. On 64 bit systems, you can add about 16-32 bytes to each of the two classes. As for the BSP tree, a flat tree will use 4 bytes for a vector pointer, some overhead for allocation, and 4 bytes extra for each item (basically an integer index in a vector). A 1 depth tree will use about 24 bytes: 4-8 bytes extra for each node (one root, and two leaves), but still only 4 bytes are spent per item. So it's very memory efficient for reasonably sized trees. Of course, a tree that's 25-30 levels deep will exhaust your memory.

In 4.3, items are temporarily moved out of the tree and into a intermediate structure that gives immediate lookup while they are moving. So even with a large tree full of static content that gives close to O(log(N)) lookup, you will be able to move large chunks of items around very quickly. After the items have been left for a while, they are silently re-added to the BSP tree in the background.