Edit AllPages

Recently I ran into the need to optimise the performance of drawing many tens of thousands of objects. I started to notice that the time to traverse a linear array discovering which objects needed to be drawn (according to NSView’s -needsToDrawRect: method) was becoming significant. What I describe here is one possible solution to the problem of discovering objects needing to be drawn from an arbitrarily large set. Other solutions are also well-known, such as RTrees, but I’ll leave that for another day.

This solution makes use of a common search algorithm - that of the BinarySearch - in fact given a sorted list of objects, the binary search is the fastest known method to find a given object.

Here, a binary search is extended into 2 dimensions, and the criterion for determining the location of any given object is its bounding rectangle. This is called Binary Search Partitioning, and is a well-known divide-and-conquer method for graphics.

The overall area of a given view is alternately divided and subdivided horizontally and vertically into two partitions, forming a binary tree. The whole view is the root, and the leaves represent some small area of the view. The tree depth determines how small this area is. If the tree depth is 1, there is only one leaf, and the system is equivalent to the linear array case. The number of objects stored at each leaf will usually depend on the depth also - the more finely divided the view, the fewer objects tend to be stored at any given leaf, assuming that on average they are distributed evenly within the view.

The advantage of this approach is that we can quickly return a small set of objects that intersect the view’s drawing update area without having to test every one - the input to the tree is a rectangle, and the result is a list of objects that intersect it. NSView has the method -getRectsBeingDrawn:count: which will return a list of rectangles needing update. We can use this as input to our tree.

We might also need to consider the front-to-back ordering (Z-order) of the objects. The tree code here doesn’t handle this part, but it’s easy enough to do if each object maintains a Z-value - the returned list can simply be sorted according to Z. Naturally the Z-value must be maintained as objects are inserted and deleted into the storage.

The tree code is presented below. To add or remove an object from the tree, a bounds parameter must be supplied which locates the object in 2-dimensional space. Typically an object would supply its own bounds, but in this code that is handled externally. In addition, should an object move, it needs to be repositioned in the tree. This is most easily accomplished by removing it using its old bounds value then adding it back with the new bounds. The tree itself uses recursion to accomplish the tree traversal, and the code here optimises the object-C method call to make that as fast as possible. It also makes use of toll-free bridging to CFArray and friends to speed up other operations. When a complex drawing is being repeatedly redrawn (as when scrolling for example) these optimisations are worth having. An object needs to respond to -setMarked: which is just a flag that the tree uses to avoid including the same object more than once. The objects should have this flag reset before the next search, on eopportunity to do this is when you iterate the returned list to draw the objects.

Hope this is useful to someone - a more complete implementation is found in DrawKit. –GrahamCox.

typedef enum { kOperationInsert, kOperationDelete, kOperationAccumulate } BSPOperation;

typedef enum { kNodeHorizontal, kNodeVertical, kNodeLeaf } LeafType;

@interface BSPTree : NSObject { @protected NSMutableArray* mLeaves; NSMutableArray* mNodes; NSSize mCanvasSize; BSPOperation mOp; @public id mObj; NSMutableArray* mFoundObjects; unsigned mObjectCount; }

// tree returns mutable results so that they can be sorted in place without needing to be copied


#pragma mark -

/// node object - only used internally with BSPTree

@interface BSPNode : NSObject { @public LeafType mType; union { float mOffset; unsigned mIndex; }u; }



static inline unsigned childNodeAtIndex( unsigned nodeIndex ) { return (nodeIndex « 1) + 1; }

@implementation BSPTree

static unsigned sLeafCount = 0;

// if set to 1, recursive function avoids obj-C message dispatch for slightly more performance

#define qUseImpCaching 1

#define USE_CF_APPLIER 1

static void addValueToFoundObjects( const void* value, void* context ) { id obj = (id)value;

if(![obj isMarked] && [obj visible])
	BSPTree* tree = (BSPTree*)context;
	[obj setMarked:YES];
	CFArrayAppendValue((CFMutableArrayRef)tree->mFoundObjects, value );
} }

#pragma mark -

@implementation BSPNode