Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!wuarchive!rex!spool.mu.edu!munnari.oz.au!labtam!graeme
From: graeme@labtam.labtam.oz (Graeme Gill)
Newsgroups: comp.windows.x
Subject: Re: Speeding up use of a bitmap as a clip mask
Summary: Other region orderings may help.
Message-ID: <10569@labtam.labtam.oz>
Date: 22 May 91 03:03:28 GMT
References: <9105160408.AA05642@lightning.McRCIM.McGill.EDU> <7197@acorn.co.uk>
Organization: Labtam Australia Pty. Ltd., Melbourne, Australia
Lines: 52

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