john@acorn.co.uk (John Bowler) (05/21/91)
In article <9105160408.AA05642@lightning.McRCIM.McGill.EDU> mouse@lightning.mcrcim.mcgill.EDU (der Mouse) writes: >[approaches to OR'ing colours from two sources] > >Another possibility is to set the GC's clip-mask to the bitmap, the >foreground to fg, and do a FillRectangle; however, I *think* the MIT >server turns clip-masks into lists of rectangles, and if the picture >doesn't decompose nicely into rectangles this will (a) eat up server >memory and (b) draw comparatively slowly. It will also cost some setup >time while the server scans the bitmap and sets up the rectangles. And >what the MIT server does, many other servers pick up. (I'm sure I'll >be corrected if I misread that code....) > >[stuff deleted] > >I'd be surprised if R5 changes anything bearing on my comments above, >except perhaps the bit about the (in)efficiency of clip-masks. I think that this is unlikely. The code in question is the part of the server which deals with a clip mask of type ``CT_PIXMAP''. The device dependent layer could retain the bitmap and use this to clip all drawing operations, rather than converting it to a list of rectangles and intersecting it with the rectangle list generated from the window tree, as the sample server does. Doing this would mean that all those operations which do the actual clipping (most of the device dependent drawing operations normally) would have to be able to clip to either a list of rectangles, or to both a list of rectangles and a bitmap. When I examined the possibility of doing this I came to the conclusion that doing the latter would cause enormous complication of most of the low level drawing code. (And, it is complicated enough already). The worst case in my *current* implementation is probably PolyText with an opaque stipple fill - the drawing operation draws each pixel according to:- 1) The position in the fill stipple (fg or bg colour) 2) The raster op and plane mask (these can be combined easily) 3) Clipped by the character ``bitmap'' 4) Clipped by the actual clip region (intersection of user and window clip rectangles). This is a nightmare to implement in one operation, but the alternative is to use a series of operations with (inefficient) temporary bitmaps - that's why opaque stippled text used to go so slowly compared with a normal filled text operation (and probably still does in the sample server?) Implementing bitmap clip masks this way (use the bitmap at step 3) makes *all* drawing operations this complicated. To avoid slowing down the normal code (by maybe a factor of 2?) bitmap clipping would need to be special cased. This would probably double the ddx drawing code size. After all this what would the actual gains be? Bitmap clipping with a simple shape bitmap (eg a circle, an arbitrary polygon) is probably implemented most quickly by merging the clipping with the rectangle list - the region size does grow (one region per scan line in many cases), but the complexity of the individual scan line is probably no greater (for a simple polygonal shape); the benefit is that there is no need to ``expand'' the (bitmap) stipple for non-plane mapped displays of depth > 1 (this is very expensive). It seems more likely that someone will come up with an extension to do pixel value manipulations which are not simple boolean calculations, ie:- dst := f(src,dst) where f(src,dst) is not simple boolean algebra; in particular where the function is expressed using conditionals:- if (src == val) return src; else return dst; or using a lookup table, eg:- return lookup[src]; These would satisfy the image processing requirement, which is where the unhealthy :-) desire to use totally arbitrary bitmaps as clip masks seems to come from. John Bowler (jbowler@acorn.co.uk)
graeme@labtam.labtam.oz (Graeme Gill) (05/22/91)
In article <7197@acorn.co.uk>, john@acorn.co.uk (John Bowler) writes: > In article <9105160408.AA05642@lightning.McRCIM.McGill.EDU> mouse@lightning.mcrcim.mcgill.EDU (der Mouse) writes: > >I'd be surprised if R5 changes anything bearing on my comments above, > >except perhaps the bit about the (in)efficiency of clip-masks. > R5 hasn't changed this. > [stuff deleted] > > Implementing bitmap clip masks this way (use the bitmap at step 3) makes > *all* drawing operations this complicated. To avoid slowing down the normal > code (by maybe a factor of 2?) bitmap clipping would need to be special > cased. This would probably double the ddx drawing code size. After all > this what would the actual gains be? Bitmap clipping with a simple shape > bitmap (eg a circle, an arbitrary polygon) is probably implemented most > quickly by merging the clipping with the rectangle list - the region size > does grow (one region per scan line in many cases), but the complexity of > the individual scan line is probably no greater (for a simple polygonal > shape); the benefit is that there is no need to ``expand'' the (bitmap) > stipple for non-plane mapped displays of depth > 1 (this is very expensive). > > [stuff deleted] > > John Bowler (jbowler@acorn.co.uk) I had a look at this problem at one stage and came to the same conclusion :- that there would be a more than doubling of code size to support clipping bitmap directly. It does not seem to be a heavily used option in X applications, partly because it is so slow on most servers. Another dis-incentive in implementing a clipping bitmap version of the rendering routines was that many of my current routines just fitted with the number of registers available on the processor I was targeting (32 registers), and adding another bitmap to be scanned into things would have blown the register budget completely! There is another suggestion which could solve some of the problems with round or odd shaped clipping masks, and that is to have an alternate rectangle clipping ordering. At the moment regions within the server are X-Y banded rectangles, and shapes like circles end up with a very in-efficient region description (for a circle it is a list of one pixel high rectangles, each rectangle being the width of the circle at that y co-ordinate). If the region description was arranged to be more like quadtrees, then there would be fewer and larger rectangles making up a region for difficult shapes. The disadvantages are that different and possibly slower algorithms would be needed in the region manipulation library, and it might be more difficult to take advantage of region rectangle ordering at the rendering level, where the X-Y banded approach allows reasonably quick searching. A quadtree region description for X servers is still an interesting and worthwhile topic for further investigation though. Graeme Gill Labtam Australia