QGraphicsSceneBspTreeIndex::estimateTopLevelItems sometimes selects too many QGraphicsItems

Hello,

I have run into what appears to be a rather serious bug/limitation of the BSP implementation found in the QGraphicsScene/View framework. I am running Qt 4.6. I ran into the problem while coding on a large project so I've created a simple test application to demonstrate the problem. The test application (attached) has two modes of operation and several configuration parameters to help probe the issue.

The basic issue is that for some configurations of objects in a scene, the BSP massively over-selects items when calling q->estimateTopLevelItems. I will provide more details about where the bug is below, but first a top level description of the cases, along with instructions on how to reproduce them using the same code provided.

I have constructed two cases (SCATTER and STACK). The first one is handled very well by the framework and the second one is not.

(1) SCATTER: Generate 5000 squares of size 150x150 and place them over a large field such that the average converage density is one. The test is to call QGraphicsView::items(QGraphicsView::rect()) and count the number of times the framework calls the boundingRect method of the squares. In this scene and for a view size of 1200x1000, typically about 65 items are returned and about 135 calls to boundingRect are made. This is a very sensible and good result. If the view is made smaller, the number of items returned shrinks and the number of calls to boundingRect shrinks correspondingly. The BSP appears to be working as advertised.

(2) STACK: Generate 5000 rectangles of size 1000x35, arranged in a vertical stack with a spacing of 5 between them. Again, call QGraphicsView::items(QGraphicsView::rect()). With a view size of 1200x1000, 25 items are returned but 2565 calls to boundingRect are made. This is a serious problem because it grows with the size of the scene, not with the size of the view. This case is why I am submitting this report.

I've looked into the QGraphicsScene code to figure out why it is doing this. The relevant call stack is:

QGraphicsSceneBspTree::climbTree
QGraphicsSceneBspTree::items
QGraphicsSceneBspTreeIndexPrivate::estimateItems
QGraphicsSceneBspTreeIndex::estimateTopLevelItems
QGraphicsSceneIndexPrivate::items_helper
QGraphicsSceneIndex::items
QGraphicsScene::items
QGraphicsView::items

It appears that the BSP is being constructed in a highly unbalanced way. For fewer than 5000 items (i.e., for shallower tree depths), it is possible to inspect the QGraphicsSceneBspTree::nodes and QGraphicsSceneBspTree::leaves members to see the unbalanced nature of the tree. You can do this, e.g., by placing a conditional breakpoint on line 152 of qgraphicsscene_bsp.cpp.

A deeper analysis indicates that the problem appears to result from the space partitioning choices in QGraphicsSceneBspTree::initialize. It appears that this function slices the space without regard to the what objects are in the scene and without regard to the aspect ratio of the scene. I can understand wanting a static partitioning of the space to avoid data-dependent processing, but the tree should be constructed so that a very tall and narrow scene has many more Node::Vertical nodes than Node::Horizontal nodes. But it is clear from line 205 of qgraphicsscene_bsp.cpp that the splits are alternated irrespective of the aspect ratio of the space being considered.

(Ideally splits are made in the dimension of maximum data variance. Since you are not constructing a data-dependent tree, you should assume a uniform distribution of objects and split along the largest dimension of the sub-rectangle under consideration.)

There are a number of other parameters in the test application that should be self-explanatory.

I have two suggestions:

(1) Please fix the implementation of the BSP tree.
(2) Please make QGraphicsScene::items virtual (or some other equivalent framework change) so that framework users can replace the defective tree.

Please let me know if you are able to reproduce the bug and confirm my analysis of the root cause. Finding a temporary solution to this problem is essential in the short term and it would be great if a framework update would solve it in the long term.

Best Regards,
James