Using rectangles for clipping is fairly simple to implement, as it is easy to check against a rectangle bounds. It is also fairly simple to create a list of rectangles that represent the area that is visible when only rectangles are blocking the view in front of the rectangle you wish to draw to. So this seems to be a good method of clipping, especially for a windowing system, just use rectangles.

Many Window Managers use this method for clipping, including the RISC OS WIMP. It makes sense as it is easy to implement. That and it is fast for cases where there are not that many overlapping rectangles.

This method is very good in many situations, though it does have one fatal flaw in potential efficiency. That is that for each added rectangle you add 2*n+2 (where n is the number of rectangles behind the rectangle being considered) possible new rectangles (worse case) for each foreground rectangle, thus making the growth rate way too much to handle fast in some cases. Normally the rate will not be an issue, though take the case of a stack that is 8 rectangles deep, the worse case is then (2*7+2) + (2*6+2) + (2*5+2) + (2*4+2) + (2*3+2) + (2*2+2) + (2+2) = 16 + 14 + 12 +10 + 8 + 6 + 4 = 70 rectangles in the visible list, and that is just for 8 rectangles deep worse case. The worse case for 128 levels deep (the limit of most window Managers) is 16510 visible rectangles within the rear most rectangle (calculated with the BASIC V line T%=0: FORX%=127TO1STEP-1: T%+=2*X%+2: NEXT: PRINTT%), remember this is the absolute worse possible case.

It is still worth studying the method of using single rectangles for clipping, as well as the method of using rectangle lists to handle the case of multiple overlapping rectangles. If for no reason other than it being easy to implement, and in some cases fast. Not to mention that it is quite widely used.

In normal usage it is extremely rare to encounter the worse case. In more than 99.8% of cases in a Windowing System using this methods there will be fewer than 16 rectangles in the visible rectangle list for a partially covered window that has the most covering windows of any visible on screen. Thus in the majority of cases it is effecient enough to be practical, though there is always the possibility of getting quite out of hand. Looking at my RISC OS Desktop Screen as I type this, the current bad case has 12 visible rectangles, thus it is quite doable (though Regions would be faster for that particular case). Most of the Windows open on my current Desktop Screen in RISC OS are either non-visible (completely covered) or have nothing infront of them (either 0 or 1 visible rectangles).

Clipping against a rectangular area is pretty simple, as it just takes bounds checking and allows for runs within bounds between checking. Bounds range checking is quite simple.

Even when we use Lists of visible rectangles within our target we still only draw to a single rectangle at a time, so the method is the same.

Keep in mind the potential of extreme cases, even if they are very rare. It is possible to have things get a bit slow depending on the case at hand. That being said most cases Rectangle Lists are usually an effecient means of clipping.

Here we will look at how to build a visible rectangle list that contains no overlapping rectangles and prefers wider than tall where possible. This is the most efficient for graphics output.

The above code is only to illistrate the algorithm, and likely contains some errors. The above code takes two rectable lists as input, and works through them. Each entry in the rectangle lists has the form of (Index const variable name, folowed by offset, then description):

• Nxt% &00 : Next rectangle address.
• Prv% &04 : Previous Rectangle address.
• Type% &08 : List type (&0080 for Rectangle)
• Size% &0C : Entry Size in bytes (32 bytes for rect).
• Lft% &10 : Left most coords.
• Top% &14 : Top most coords.
• Rgt% &18 : Right Most Coords.
• Btm% &1C : Bottom Most Coords.

All entries in the standard list entry, as well as in the Rectangle list entry are 32-bit words, as this is easy to work with in RISC OS. If you wish to convert to RISC OS coords reverse the position of Top% and Btm% then replace every !Top% reference with !Btm% and every !Btm% with !Top%.

The rectangle Tgt% is the target rectangle, the rectangle Fore% is the current foreground rectangle.

The function FNRemItem removes the specified item from the list, and returns the next valid Item after that one, or NULL if no more entries in list. The Function FNAddVis adds a rectangle to the end of the visible rectangle list containing the passed in rectangle, returning the address of the new rectangle. The variable NewF% contains TRUE if any additions were made to the list, and FALSE otherwise