[interfacekit] Re: Clipping - what to do, what to do?

On Saturday 10 April 2004 08:57 am, Adi Oanca wrote:
>    Hello!
>
>    Here is a problem for you all: How can we clip drawing instructions?

Are you talking about for the BDirectWindow, or app_server clipping in 
general?  Believe it or not, I am actually working on the regular app_server 
clipping.

>
>    Let me start by telling you what the problem is. Suppose we have the
>    following scenario:
>
>    22222222222222
>    22222222222222
>    1111122222222222222
>    1111122222222222222
>    1111122222222222222
>    1111111111111
>    1111111111111
>
>    Two windows, window '2' overlaps window '1'. What we see here are the
>    visible parts of the two windows. Now, let's not refer the them as being
>    windows, but... layers.
>    When we decide to draw in a surface, we _must_ draw _only_ in its
> visible area, thus when we draw a line from top-left to top-right in layer
> '1', only 5 dots will be actually drawn. That is what lower level clipping
> is about. The line example was a "happy" case, consider drawing a filled
> oval inside surface '1'!

A filled ellipse really isn't that much harder since it is drawn as a series 
of horizontal lines which can be clipped individually.

>    Well... how are we going to do that?
>    Oh, not to forget! 99% of drawing primitives are implemented in software
>    by directly writing in the frame buffer. 2D acceleration can only draw
> one color rectangles and invert them.
>
>    I have come up with 2 solutions, of course each with its advantages and
>    disadvantages.
>
>    We could do it the "hard" way, by checking every pixel if it is in the
>    visible region, by invoking BRegion::Contains(pt), but this will be
>    overkilling for the CPU. This has the advantage that it requires no
>    additional memory.

Working at the pixel level is definitely overworking the CPU.  It is a 
relatively simple procedure to transform figures into lines and then clip 
each of the lines.

>
>    The second proposal, and the one that I vote for, is by using a memory
>    region equal to BRegion::Bounds(). Every layer that needs a part of it
> to be redrawn has a valid fUpdateReg region. This is the region in which,
> this layer is allowed to draw - the clipping region. It is a part of the
> visible region, and it is the minimum region required to be updated. When
> an update is required(of forced: by calling ::Invalidate()) the following
> happens:
>    * [fUpdateReg already is valid]
>    -> an _UPDATE_ message is sent to client side(BeApp)
>    -> just before calling BView::Draw() BWindows inserts a _WILL_DRAW_ to
> be sent to the server.
>    -> ::Draw() gets called and all drawing is done.
>    -> when ::Draw() finishes, _END_DRAW_ is added to queued messages to be
>    sent, and a Sync() is made.
>
>    What do you say if, when we receive _WILL_DRAW_ we allocate(with malloc)
> a memory region the size of fUpdateReg.Bounds()/8, and we set every bit to
> 1 if that (x,y) coordinate is in the region, 0 if not.
>    Please _do not_ start wondering "Why not use one byte per pixel to
> achieve transparency (0-255)?" This _only_ concerns clipping, so leave
>    transparency aside!
>    When we want to paint a pixel, we can determine very quickly if it is
>    visible or not. Using this method, all drawing instructions(d.i.) found
>    inside BView::Draw() are executed, and when app_server receives
>    _END_DRAW_, the allocated memory region is deleted. OK, maybe not
> deleted if there are still views that need to be updated, and we could use
> realloc() for them.

I am not sure I am following you here.  Are you talking about still checking 
on a pixel by pixel basis for clipping, but precomputing which pixels are 
visible to reduce CPU usage?

>    Memory used for this operation is not that much as you might have
> thought. Every surface is managed by an app_server thread, and at a given
> moment, it only draws for _one_ surface, and only one memory region is used
> by all surfaces associated with that specific thread.
>    Now you would say: OK that was for the update mechanism, what if drawing
>    is made from outside ::Draw() of from another thread? IMO, the answer is
>    quite simple. Because BWindow thread must be locked, all drawing
>    instructions are serialized so all d.i. are from outside ::Draw(). When
>    the first d.i arrives at server, a memory region equal to
>    layer::_visibleRegion.Bounds() is allocated to help with the clipping
>    process. The second, third,... d.i. still use this memory region
> assuming layer's visible region was not modified. If it was, the memory
> region is freed and a new one will be created when the next d.i. arrives.
> Finally, if no d.i. is received in half a second, it is deleted(freed).
> [how???] There is a concern about Resize/Move methods inside ::Draw(), but
> this a problem that is not of immediate priority.
>
>    Well, what do you think? Is this algorithm good enough? Other ideas?
>    Improvements?

I think we can avoid low-level clipping altogether by doing the appropriate 
work at higher levels.  If you are intending this for general app_server 
clipping, don't worry about it since, contrary to appearances, I am actually 
working on it and have the hard issues worked out (I just need to get them 
into the code).  I hope to have all of the clipping code (except for text) 
implemented and checked in within the next couple weeks.


Gabe

Other related posts: