フレーム バッファの更新を最小限に抑えるための「ダーティ レクタングル」を計算するためのアルゴリズムの実装に関するリファレンスはどこにありますか? 任意の編集を許可し、表示の更新に必要な「ビット ブリット」操作の最小セットを計算する表示モデル。
Foo bar
質問する
15934 次
6 に答える
4
Vexiはこれのリファレンス実装です。このクラスはorg.vexi.util.DirtyList （Apache License）であり、本番システムの一部として使用されます。つまり、徹底的にテストされ、十分にコメントされています。
注意点として、現在のクラスの説明は少し不正確です。「インテリジェントな合体を使用して、再描画が必要な長方形の領域のリストを保持するための汎用データ構造」。 実際には、現在、合体は行っていません。したがって、これはdirty（）リクエストとのみ交差して、重複するダーティ領域がないことを確認するという点で、これを基本的なDirtyList実装と見なすことができます。
この実装の1つのニュアンスは、Rectまたは別の同様の領域オブジェクトを使用する代わりに、領域がintの配列に格納されることです。つまり、1次元配列の4intのブロックに格納されます。これは実行時の効率のために行われますが、振り返ってみると、これに多くのメリットがあるかどうかはわかりません。（はい、実装しました。）使用中の配列ブロックの代わりにRectを使用するのは簡単なはずです。
クラスの目的は速くすることです。Vexiでは、ダーティはフレームごとに数千回呼び出される可能性があるため、ダーティ領域とダーティリクエストの交差は可能な限り迅速にする必要があります。2つの領域の相対位置を決定するために、4つ以下の数値比較が使用されます。
合体が欠落しているため、完全に最適ではありません。ダーティ/ペイントされた領域間のオーバーラップがないことを保証しますが、最終的には領域が整列し、より大きな領域にマージされる可能性があります。したがって、ペイント呼び出しの数が減ります。
コードスニペット。ここでオンラインの完全なコード。
public class DirtyList {
/** The dirty regions (each one is an int[4]). */
private int[] dirties = new int[10 * 4]; // gets grown dynamically
/** The number of dirty regions */
private int numdirties = 0;
...
/**
* Pseudonym for running a new dirty() request against the entire dirties list
* (x,y) represents the topleft coordinate and (w,h) the bottomright coordinate
*/
public final void dirty(int x, int y, int w, int h) { dirty(x, y, w, h, 0); }
/**
* Add a new rectangle to the dirty list; returns false if the
* region fell completely within an existing rectangle or set of
* rectangles (i.e. did not expand the dirty area)
*/
private void dirty(int x, int y, int w, int h, int ind) {
int _n;
if (w<x || h<y) {
return;
}
for (int i=ind; i<numdirties; i++) {
_n = 4*i;
// invalid dirties are marked with x=-1
if (dirties[_n]<0) {
continue;
}
int _x = dirties[_n];
int _y = dirties[_n+1];
int _w = dirties[_n+2];
int _h = dirties[_n+3];
if (x >= _w || y >= _h || w <= _x || h <= _y) {
// new region is outside of existing region
continue;
}
if (x < _x) {
// new region starts to the left of existing region
if (y < _y) {
// new region overlaps at least the top-left corner of existing region
if (w > _w) {
// new region overlaps entire width of existing region
if (h > _h) {
// new region contains existing region
dirties[_n] = -1;
continue;
}// else {
// new region contains top of existing region
dirties[_n+1] = h;
continue;
} else {
// new region overlaps to the left of existing region
if (h > _h) {
// new region contains left of existing region
dirties[_n] = w;
continue;
}// else {
// new region overlaps top-left corner of existing region
dirty(x, y, w, _y, i+1);
dirty(x, _y, _x, h, i+1);
return;
}
} else {
// new region starts within the vertical range of existing region
if (w > _w) {
// new region horizontally overlaps existing region
if (h > _h) {
// new region contains bottom of existing region
dirties[_n+3] = y;
continue;
}// else {
// new region overlaps to the left and right of existing region
dirty(x, y, _x, h, i+1);
dirty(_w, y, w, h, i+1);
return;
} else {
// new region ends within horizontal range of existing region
if (h > _h) {
// new region overlaps bottom-left corner of existing region
dirty(x, y, _x, h, i+1);
dirty(_x, _h, w, h, i+1);
return;
}// else {
// existing region contains right part of new region
w = _x;
continue;
}
}
} else {
// new region starts within the horizontal range of existing region
if (y < _y) {
// new region starts above existing region
if (w > _w) {
// new region overlaps at least top-right of existing region
if (h > _h) {
// new region contains the right of existing region
dirties[_n+2] = x;
continue;
}// else {
// new region overlaps top-right of existing region
dirty(x, y, w, _y, i+1);
dirty(_w, _y, w, h, i+1);
return;
} else {
// new region is horizontally contained within existing region
if (h > _h) {
// new region overlaps to the above and below of existing region
dirty(x, y, w, _y, i+1);
dirty(x, _h, w, h, i+1);
return;
}// else {
// existing region contains bottom part of new region
h = _y;
continue;
}
} else {
// new region starts within existing region
if (w > _w) {
// new region overlaps at least to the right of existing region
if (h > _h) {
// new region overlaps bottom-right corner of existing region
dirty(x, _h, w, h, i+1);
dirty(_w, y, w, _h, i+1);
return;
}// else {
// existing region contains left part of new region
x = _w;
continue;
} else {
// new region is horizontally contained within existing region
if (h > _h) {
// existing region contains top part of new region
y = _h;
continue;
}// else {
// new region is contained within existing region
return;
}
}
}
}
// region is valid; store it for rendering
_n = numdirties*4;
size(_n);
dirties[_n] = x;
dirties[_n+1] = y;
dirties[_n+2] = w;
dirties[_n+3] = h;
numdirties++;
}
...
}
于 2011-06-29T12:50:54.287 に答える
4
再描画が必要なすべての領域を含む最小の長方形を作成するには:
- 空白の領域から始めます (おそらく、0,0,0,0 に設定された四角形 - 「更新不要」として検出できるもの)
追加されたダーティ エリアごとに:
- 新しい領域を正規化します（つまり、左が右よりも小さく、上が下よりも小さいことを確認してください）
- ダーティな四角形が現在空である場合は、指定された領域に設定します
- それ以外の場合、ダーティな四角形の左と上の座標を {dirty,new} の最小値に設定し、右と下の座標を {dirty,new} の最大値に設定します。
Windows は、少なくとも、通知された変更の更新領域と、ウィンドウが隠されたり明らかになったりするために実行する必要がある再描画を維持します。領域は、不連続な可能性のある多くの長方形、多角形、および楕円で構成されるオブジェクトです。InvalidateRect を呼び出して、再描画が必要な画面の一部を Windows に伝えます。より複雑な領域には InvalidateRgn 関数もあります。次の WM_PAINT メッセージが到着する前に何らかの描画を行うことを選択し、それをダーティ エリアから除外したい場合は、ValidateRect 関数と ValidateRgn 関数があります。
BeginPaint でペイントを開始するときは、ペイントする必要があるものに関する情報を Windows が入力する PAINTSTRUCT を指定します。メンバの 1 つは、無効な領域を含む最小の四角形です。小さな無効な領域が複数ある場合に描画を最小限に抑えたい場合は、GetUpdateRgn を使用して領域自体を取得できます (BeginPaint はウィンドウ全体を有効としてマークするため、BeginPaint の前にこれを呼び出す必要があります)。
これらの環境が最初に作成されたとき、Mac と X では描画を最小限に抑えることが重要だったので、更新領域を維持するための同等のメカニズムがあると思います。
于 2008-09-16T22:46:57.083 に答える
3
必要なのは、画面にレンダリングする各シェイプのバウンディングボックスのようです。ポリゴンのバウンディングボックスは、「左下」（最小点）と「右上」（最大点）として定義できることに注意してください。つまり、最小点のx成分は、ポリゴン内の各点のすべてのx成分の最小値として定義されます。yコンポーネント（2Dの場合）とバウンディングボックスの最大点に同じ方法を使用します。
ポリゴンごとにバウンディングボックス（別名「ダーティレクタンギュラー」）があれば十分です。これで完了です。全体的な複合バウンディングボックスが必要な場合は、同じアルゴリズムが適用されますが、1つのボックスに最小ポイントと最大ポイントを入力するだけです。
これをすべてJavaで実行している場合は、メソッドAreaを使用して（任意のShape）のバウンディングボックスを直接取得できます。getBound2D()
于 2008-11-21T16:00:36.433 に答える
2
私はつい最近、2 つの画像の差分四角形を計算する Delphi クラスを作成しましたが、その実行速度に非常に驚きました。短いタイマーで実行するのに十分な速さで、画面アクティビティを記録するためのマウス/キーボード メッセージの後に実行できます。
それがどのように機能するかのステップバイステップの要点は次のとおりです。
画像を長方形で論理的な 12x12 に分割します。
各ピクセルをループし、違いがある場合は、ピクセルが属するサブ長方形に、そのピクセルの 1 つと場所に違いがあることを伝えます。
各サブ長方形は、それ自体の左端、上端、右端、および下端の違いの座標を記憶しています。
すべての違いが見つかったら、違いのあるすべてのサブ長方形をループし、それらが隣り合っている場合はそれらからより大きな長方形を形成し、左端、上端、右端、および下端を使用します。これらのサブ長方形のほとんどの違いを使用して、実際の違いの長方形を作成します。
これは私にとって非常にうまくいくようです。独自のソリューションをまだ実装していない場合は、お知らせください。必要に応じてコードをメールでお送りします。また、今のところ、私は StackOverflow の新しいユーザーなので、私の回答に感謝する場合は、投票してください。:)
于 2008-11-26T22:15:55.067 に答える
2
どの言語を使用していますか? Python では、Pygame がこれを行うことができます。RenderUpdates グループと、image および rect 属性を持ついくつかの Sprite オブジェクトを使用します。
例えば：
#!/usr/bin/env python
import pygame
class DirtyRectSprite(pygame.sprite.Sprite):
"""Sprite with image and rect attributes."""
def __init__(self, some_image, *groups):
pygame.sprite.Sprite.__init__(self, *groups)
self.image = pygame.image.load(some_image).convert()
self.rect = self.image.get_rect()
def update(self):
pass #do something here
def main():
screen = pygame.display.set_mode((640, 480))
background = pygame.image.load(open("some_bg_image.png")).convert()
render_group = pygame.sprite.RenderUpdates()
dirty_rect_sprite = DirtyRectSprite(open("some_image.png"))
render_group.add(dirty_rect_sprite)
while True:
dirty_rect_sprite.update()
render_group.clear(screen, background)
pygame.display.update(render_group.draw(screen))
Python+Pygame を使用していない場合は、次のようにします。
- update()、move() などの Sprite クラスを作成します。メソッドは「ダーティ」フラグを設定します。
- スプライトごとに四角形を維持する
- API が四角形のリストの更新をサポートしている場合は、スプライトがダーティな四角形のリストでそれを使用します。SDL では、これは SDL_UpdateRects です。
- API が rects のリストの更新をサポートしていない場合 (SDL 以外を使用する機会がなかったのでわかりません)、blit 関数を複数回呼び出すか、または 1 回呼び出す方が速いかどうかをテストします。大きな長方形。1 つの大きな rect を使用した API の方が高速になるとは思えませんが、SDL 以外は使用していません。
于 2008-09-16T23:09:09.450 に答える