Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | RSS feed

  1.  
  2.         Smart Dirty Rectangle Management
  3.         --------------------------------
  4.  
  5. pig_dirty() contains an algorithm that tries to find
  6. the the best dirtyrect candidates for merging. While
  7. searching, it looks out for perfect or sufficiently
  8. good candidates.
  9.  
  10. (Perfect candidate:)
  11.         The merged rectangle is of the same size
  12.         as the largest of the two input rectangles:
  13.  
  14.                 Amerged <= MAX(A1, A2)
  15.  
  16.   We don't actually test for this, but rather for...
  17.  
  18. Instant Pick candidate:
  19.         Not Perfect, but good enough to be treated
  20.         as such, considering the cost of going on
  21.         searching for a better candidate:
  22.                 Amerged 100 / MAX(A1, A2) - 100 <= PIG_INSTANT_MERGE
  23.  
  24.         (That is, the area of the merged rect must be
  25.         no more than PIG_INSTANT_MERGE % bigger than
  26.         the area of the larger of the two input rects.)
  27.  
  28.         Note that this is also about how likely it is
  29.         that thereis* a better candidate. Assuming
  30.         that PIG_INSTANT_MERGE is set to a sensible
  31.         value, it is not very likely at all. There
  32.         would have to be another dirtyrect nearby, and
  33.         the chance of that being a better match is
  34.         rather low, since that would most likely have
  35.         caused it to be merged with the tested dirtyrect
  36.         long before our new rect came in.
  37.  
  38. (Good candidate:)
  39.         The area of the merged rectangle is smaller
  40.         than the total area of the two input rectangles:
  41.  
  42.                 (Amerged - A1 - A2) < 0
  43.  
  44.   We don't actually test for this, but rather for...
  45.  
  46. Acceptable candidate:
  47.         The area of the merged rectangle is larger
  48.         than the total of the two input rectangles, but
  49.         since there is some per-rectangle overhead,
  50.         merging is still a win:
  51.  
  52.                 (Amerged - A1 - A2) <= PIG_WORST_MERGE
  53.  
  54.         The default setting assumes that the cost of a
  55.         rectangle is in the range of 300 pixels. One
  56.         should probably benchmark a few different systems
  57.         to see if that's reasonable.
  58.  
  59. Unacceptable candidate:
  60.         The area of the merged rectangle is larger than
  61.         the total of the input rectangles to the degree
  62.         that merging is a definite loss:
  63.  
  64.                 (Amerged - A1 - A2) > PIG_WORST_MERGE
  65.  
  66. The algorithm instantly returns Perfect candidates as
  67. solutions. If there are only Good and Acceptable
  68. candidates, the best one (lowest number of wasted
  69. pixels) is the solution.
  70.  
  71. If there are only Unacceptable candidates, there is no
  72. sensible merger solution, so pig_dirty() will try to add
  73. a new dirtyrect.
  74.  
  75. If that fails (table full), the best candidate is used,
  76. even though it would have been Unacceptable under normal
  77. circumstances.
  78.  
  79.  
  80. TODO: Thereare* more alternatives than just "merge" or
  81. TODO: "don't merge"! For example, it might pay off to
  82. TODO: detect overlapping and clip dirtyrects to avoid
  83. TODO: it, when merging is not a viable option.
  84.