nanogui: Thread: Area Copies and clipping code

Hello all,

I need an optimized screen scroller, which I'm not sure is implemented
right now?

Ricard mentioned some time back IIRC that he had tried the blitter but
that it was both slow (generic code probably), and that it didn't handle
overlapping copies (other than copying towards the upper left corner of
the screen).  I haven't had the time to investigate the details myself,
so I hope you can help me out a little here before I start coding. Thanx!

These are problems I intend to solve if not already solved, but I'd like to
do it properly - but properly in this context means handeling clipping
properly, which is kind of a challenge.  I may not implement clipping
in the first version (we will not need it), but this should be kept in mind.

My ideas on the subject:

Set up the clipping rectangles for the source area to copy.  For each
of the source rectangles, calculate the corresponding destination
rectangle, set up clipping rectangles once more for the destination,
and perform the equivalent of a GdArea operation using the AreaCopy
driver operation  for each of the destination rectangles (from the
single source rectangle).

Several problems here:

  1) We need to have two sets of rectangles available, the source
     rectangles that we go through one by one and copy, and the
     destination rectangles which must be set up from scratch every
     time we move to a new source rectangle.

  2) We need to have "hidden rectangles", e.g. the entire
     source area needs to be spit into rectangles that are visible,
     and rectangles that are invisible - totaling the entire area.
     This is so that we can copy the background color onto those parts
     of a window that "slides out from underneath" another window - e.g.
     those parts of the destination area whose source is hidden.

  3) Overlapping copies.  Solving the overlapping copy problem at the
     driver level is easy, just reverse the loops or use temporary
     storage depending on X and Y direction of copy.  But at the
     higher level, we have to make sure the rectangles that eventually
     gets copied is copied in the right order.

I don't think (1) is available today, but should be possible to implement
without to much effort.

As for (2), I don't know if it is available.  I suspect it to be "not
entirely simple" if not available today.  Solving (3) may have to be done
by making up a "play-list" of all rectangles that needs to be copied and
blanked, and then sort them (X and Y directions as criteria) and then copy,
or sort the source rectangles and do them in "the right order".  Setting
aside some space inside the rectangle struct for this sorting may provide
helpful.

This is fairly complicated, but I think (3) is quite doable.  I'm worried
about (1) and (2) as I don't know the clipping/rectangle code too well,
and it may have to be changed, possibly drastically (for 2).
Note that (2) is not only for painting in the background color, but for
creating optimized expose events as well (if we decide to do this).

OK, let me what you think.

Regards,
Morten Rolland, Screen Media

Morten,
    I like very much your ideas on the scrolling code.  I've been 
very underwater here just this past week, put will be coming
back up for air soon.  I agree with your algorithm with
one small change: I want to make sure that the scroll
code works more at the engine level, rather than just
for the nano-x api.  With this in mind, instead of
painting the background, the scroll code should
basically "expose" the area, which then for Nano-X
would paint the background, but for win32 would end
up sending a WM_PAINT event, which may or
may not paint the background, and then ask
the app to redraw.  This is almost what you are suggesting,
I think.

Also, for setting up the source rectangles to essentially
"tile" the plane, here's an idea of how to accomplish that:
If the engine region function GdSubtractRegion were used to 
subtract the union of all higher-z-order windows
from the source rectangle, then the result could be used
as the "hidden" rectangles, I think.  I've not had time
to fully visualize this, the hidden rectangles may have
to be heightened by the scrollup value.

I'll post some more specific comments shortly.

Regards,

Greg

: 
: I need an optimized screen scroller, which I'm not sure is implemented
: right now?
: 
: Ricard mentioned some time back IIRC that he had tried the blitter but
: that it was both slow (generic code probably), and that it didn't handle
: overlapping copies (other than copying towards the upper left corner of
: the screen).  I haven't had the time to investigate the details myself,
: so I hope you can help me out a little here before I start coding. Thanx!
: 
: These are problems I intend to solve if not already solved, but I'd like to
: do it properly - but properly in this context means handeling clipping
: properly, which is kind of a challenge.  I may not implement clipping
: in the first version (we will not need it), but this should be kept in mind.
: 
: My ideas on the subject:
: 
: Set up the clipping rectangles for the source area to copy.  For each
: of the source rectangles, calculate the corresponding destination
: rectangle, set up clipping rectangles once more for the destination,
: and perform the equivalent of a GdArea operation using the AreaCopy
: driver operation  for each of the destination rectangles (from the
: single source rectangle).
: 
: Several problems here:
: 
:   1) We need to have two sets of rectangles available, the source
:      rectangles that we go through one by one and copy, and the
:      destination rectangles which must be set up from scratch every
:      time we move to a new source rectangle.
: 
:   2) We need to have "hidden rectangles", e.g. the entire
:      source area needs to be spit into rectangles that are visible,
:      and rectangles that are invisible - totaling the entire area.
:      This is so that we can copy the background color onto those parts
:      of a window that "slides out from underneath" another window - e.g.
:      those parts of the destination area whose source is hidden.
: 
:   3) Overlapping copies.  Solving the overlapping copy problem at the
:      driver level is easy, just reverse the loops or use temporary
:      storage depending on X and Y direction of copy.  But at the
:      higher level, we have to make sure the rectangles that eventually
:      gets copied is copied in the right order.
: 
: I don't think (1) is available today, but should be possible to implement
: without to much effort.
: 
: As for (2), I don't know if it is available.  I suspect it to be "not
: entirely simple" if not available today.  Solving (3) may have to be done
: by making up a "play-list" of all rectangles that needs to be copied and
: blanked, and then sort them (X and Y directions as criteria) and then copy,
: or sort the source rectangles and do them in "the right order".  Setting
: aside some space inside the rectangle struct for this sorting may provide
: helpful.
: 
: This is fairly complicated, but I think (3) is quite doable.  I'm worried
: about (1) and (2) as I don't know the clipping/rectangle code too well,
: and it may have to be changed, possibly drastically (for 2).
: Note that (2) is not only for painting in the background color, but for
: creating optimized expose events as well (if we decide to do this).
: 
: OK, let me what you think.
: 
: Regards,
: Morten Rolland, Screen Media
: 

Greg Haerr wrote:
> 
> I agree with your algorithm with
> one small change: I want to make sure that the scroll
> code works more at the engine level, rather than just
> for the nano-x api.

I intended to make it a Gd* function, too - if that is
what you mean?

> With this in mind, instead of
> painting the background, the scroll code should
> basically "expose" the area, which then for Nano-X
> would paint the background, but for win32 would end
> up sending a WM_PAINT event, which may or
> may not paint the background, and then ask
> the app to redraw.  This is almost what you are suggesting,
> I think.

OK, I'm not very familiar with the microwindows code.  The
background can be painted in nano-X when the expsoe event is
delivered, and pass the event on to the application as well.
Elegant idea.

> Also, for setting up the source rectangles to essentially
> "tile" the plane, here's an idea of how to accomplish that:
> If the engine region function GdSubtractRegion were used to
> subtract the union of all higher-z-order windows
> from the source rectangle, then the result could be used
> as the "hidden" rectangles, I think.  I've not had time
> to fully visualize this, the hidden rectangles may have
> to be heightened by the scrollup value.

Ah, eh - OK?! :-)  I follow the math and if there are
functions that can be used for this - good!  Right now
it would be best to agree on the API, and state that it
*will* eventually clip correctly, so that we can get
something working soon - we need it for Opera.

I'm also working on a couple of patches that will result in a
few new features of Nano-X.  I'd like comments on this
functinoality, as I may have overlooked something, or go about
it the wrong way.  Others may be working on similar stuff, too.
The features are:

   * Keyboard/mouse event injection into Nano-X.  We will use an
     external application to handle keyboard input, which may
     originate from a standard keyboard or an onscreen keyboard,
     or possibly even other unknown devices like voice recognition
     or braile devices.
     We need to provide a HUB external to Nano-X to handle this
     well (unicode translation, touch screen timing, calibration,
     filtering etc.).

   * The keyboard event structure needs to be updated to include a
     full 32-bit GR_UNICODE variable, for shipment of true
     unicode values.

   * In order to properly handle 8-bit and 32-bit unicode in
     applications, there are some ways to do this:

          a) A new pair of keyboard events are defined; the
             unicode equivalent of KEY_DOWN and KEY_UP.
          b) Providing a new 'GrAttribute()' function to
             enable/disable attributes in Nano-X for the
             application, like unicode support.
          c) Change the key down event API, and state that one
             should always look at the valid bits to determine
             if the key event contains useful information.

     The most intrusive (codewise) is (a), but it can be made to
     be fully backwards compatible.  However, it seems the event
     mask is fully occupied on systems with 16-bit int.  I think
     this is a very bad idea and clutters up the API.

     The solution in (b) has the disadvantage that it is not
     always clear what data is actually returned in an event.
     This will cause problems or complicate coding when linking
     several libraries / applications that uses Nano-X in
     different "modes".  If a widget set requires a certain mode,
     it may place restrictions on other parts of the application
     (Plugins into a browser is another example).

     Personally I would prefer (c) as it has the cleanest API and
     opens up for some nice functionality, but it is not 100%
     backward compatible.  But the incomatibility is so small
     that I think it acceptable (A '?' or similarly returned
     when a character not in the 8-bit range/codepage is pressed).
     See below for more details on this.

   * Focus rejection for windows.  Some of our windows are touch/
     mouse input only, like the on-screen keyboard, and we don't
     want a mouse button down event in the on screen keyboard to
     change focus, because the keyboard event would then go back
     to the on-screen keyboard itself!!  We can work around this
     with a small patch outside of Nano-X, which we will probably
     do initially, as the code to deliver keyboard events in
     Nano-X seems to be state less, e.g. check where mouse pointer
     is on every key pressed - this may be complicated to change.

Regarding the unicode key event delivery; this is my idea for an
API:

  Each keyboard (down) event has the following variables:

     GR_CHAR ch;           8-bit unsigned character
     GR_UNICODE uch;       32-bit unsigned unicode character
     unsigned int special; Special key/function
     unsigned char status; Status of characters in event

  The 'status' indicates through a bitfield if:

     1) 8-bit char is a "character proper" (e.g. usable)
     2) 8-bit char is part of an escape sequence (needs parsing)
     3) 32-bit char is a "character proper"
     4) special is a "function key" like F1, arrows,"Home" etc.

There are some nice properties with this solution:

     a) Old applications will work as before, as *all* keyboard
        down events have a (semi-) valid 8-bit character code.
        (when unicode-only codes are entered, a '?' could be
        delivered to non-unicode apps through the 'ch' variable).
     b) Semi-smart 8-bit applications can avoid parsing escaped
        characters as they can test if the character is real.
        They can use status+special to get arrow keys and similar.
     c) Smart 32-bit applications will look at the status variable
        and decide if there is an ordinary key or a special key,
        or none at all (only 8-bit escape sequence).

NOTE: In a single key down event, both 8-bit proper, 32-bit proper
      *and* special may have valid values at the same time!
      Example: Both 'ch' and 'uch' may have the value 127 (delete)
      when pressing backspace - the special variable would then
      indicate 'Backspace'.  So the (smart) application may want
      to investigate a special key first (to get more accurate
      info) and use the character proper if no code to handle
      the special key exists (like when pressing a keypad numeral,
      'special' will indicate a keypad numeral, but if this is
      not handeled in a special way, the 'ch' and 'uch' variables
      will hold the ASCII numeral value).

NOTE: Several keyboard down events may be delivered without
      containing any unicode or special characters.  This is
      because several events may be needed to transfer the
      escape sequence over the 8-bit channel.

The Mouse/keyboard insertion code is done and works, the details
of the API is not fully coded as I wanted your opinions first.
Please let me know what you think so I can code this and submit
it asap.

Thanks.

Regards,
Morten Rolland