Dynamic Multilevel SD Update Algorithm -------------------------------------- This is aimed at small clusters of pixels with animation which are either in constant location or move "continuously" It also covers rectangular windows of activity This is a "simple" implementation. It can be more sophisticated Consider basic blocks -- these could be 1X1 pixel or more likely perhaps 4X4 to 16X16 take the framebuffer -- divide into basic blocks and label each basic block (bX,bY) as a binary tree in X and Y. This labelling could be a non binary tree (e.g. tree base 4) if needed Consider two time cycles (more sophisticated versions can have as many cycles as levels in tree) T1 is major cycle T2 is minor or update cycle If say at any time 5% of pixels are changing, one's goal is to make T2 about 10 times faster than T1 and scan the places where updates are likely at interval T2 and everything with interval T1 Ratio of T2 to T1 depends on fraction of pixels changing So at time interval T1, all pixels are examined and some standard SD update produced. One flags a) All basic blocks where pixels change their value b) All basic blocks that are (nearest) neighbors to changed basic blocks (This is to catch animation moving across framebuffer) c) One goes up the tree of basic blocks flagging nodes where at least one basic block under this node has changed. This could allow faster algorithms to scan flagged basic blocks. It can also be basis of more sophisticated algorithms using different time scans at different tree levels At time interval T2, one scans down tree to identify blocks to be examined All flagged type a),b) blocks are examined for change. If a type b) block (nearest neighbour) has changed, change it to type a). If a type a) block has NOT changed, change it to type b). Remove any old type b) blocks that are no longer neighbours of the blocks now in type a) category. Update tree c) Send updates for changed basic blocks Iterate .....