CODEWITHSUNDEEP
c#algorithmgraphicsdrawingsearch
Wayne
Wayne

Reputation: 2989

How to efficiently draw only visible objects in the current graphics region?

How to efficiently select only the graphics objects which are visible in the current drawing view?

I'm working with an open source charting library, ZegGraph, for graphing billions of objects. The design in ZedGraph was to loop through every object and calculate whether it's visible in the current scaled view given the upper left corner and the height and width of the object. That was fine for thousands of items but it gets slow for millions. Now we have billions of items that exceed PC memory so we're caching them to disk. That, of course, makes looping through them all from disk to find only a handful that are in the current view, unthinkable.

One useful constraint is that the objects all have vertical coordinates that are close enough so that if they are visible horizontally then they at 90% chance to be in view. So that means that the algorithm can simply find objects based on the left and right edges whether the overlap with the visible region.

My first thought was to keep them sorted by the X coordinate of the left corner. However, the objects can have varying widths, they can be larger than the visible region so the left corner may be off the screen but the object may still be partially visible.

Of course, given X1 and X2 are the left and right edges of the region and x1 and x2 are the left and right edges of each object, we need every object that has x1 < X2 and x2 > X1.

So far, it appears that we somehow keep shorted list of all the x1 (left edge) with references to the objects. And also an a sorted list of all the x2 (right edge) with a references to each object.

So is the next step to find the first on the x1 list that satisfies the x1 < X2 condition using a binary search? Then we find the first on the x2 list the satisfies the x2 > X1 condition?

But how to them find the intersection of the x1 and x2 without scanning every item?

Upvotes: 1

Views: 528

Answers (1)

Karthik T
Karthik T

Reputation: 31952

Break up the entire region into discrete regions, divide your objects into these regions, and only render those regions which are visible.

Update regions that they belong to if they move.

Upvotes: 2

Related Questions