Eigene Repaint-Logik

[Steev]

Hallo zusammen,

ich habe da mal eine Frage an die Allgemeinheit, weil es mich schon seit längerem interessiert:
Ich habe eine Engine geschrieben, die unter anderem einen ganzen Satz Engine-Widgets liefert.
Um den Prozessor etwas zu schonen werden die Widgets natürlich nur dann neu gezeichnet, wenn sich auch was ändert, ansonsten wird der bestehende Backbuffer gerendert. Beim Neuzeichnen (welches bei den Widgets über ein Repaint-Ereignis ausgelößt wird) wird alles, was der Benutzer auf die Bühne hinzugefügt hat neu gezeichnet. Genau das führt mich jetzt zu meiner Frage:
Wie ist der standardmäßige Vorgang, wenn man nur die Bereiche neu zeichnen will, die sich auch geändert haben, und nicht das komplette Bild? Das Problem ist hier halt, dass mehrere (so etwa bis 1000 Objekte) auf einmal neu gezeichnet werden. Von diesen Objekten haben sich aber vieleicht 100 Stück geändert...

Ich habe jetzt schonmal einen Repaint-Buffer gemacht, wo alles reinkommt was neu gerendert werden muss. Das Problem ist halt nur, dass der Benutzer zum einen einen Hintergrund definieren kann und zum anderen können die Objekte übereinander liegen. Wenn jetzt ein Objekt das Repaint-Ereignis auslöst, dass unter einem anderen Objekt liegt, dann müssen die Objekte, die über diesem Objekt liegen ebenfalls neu gerendert werden.
Wie kann man dieses Problem am performantesten lösen, ohne das man für jedes zu renderende Objekt alle anderen Objekte darauf überprüft, ob sie das aktuelle Objekt überlagern?

Ich hoffe ich habe mich verständlich ausgedrückt...

Danke für die (hoffentlich) zahlreichen Antworten
Steev

 

[Steev]

Sollte es tatsächlich so sein, dass in dem größten deutschsprachigen Java-Forum keiner eine Antwort auf diese Frage weis?

 

[Marco13]

"Wissen" ist ein sehr "starkes" Wort. In den allermeisten Fällen wird das, was du beschrieben hast (soweit ich es verstanden habe) durch Swing erledigt. Außer natürlich, wenn man eine eigene Engine schreibt
Innerhalb einer Component gibt es die Möglichkeit, mit repaint(x,y,w,h) den neu zu zeichnenen Bereich zu definieren, und wenn man das in der Zeichenmethode (z.B. durch Abfragen des Clips vom Graphics-Objekt) berücksichtigt, bringt das sogar was. Theoretisch.
Swing selbst regelt das ganze grob gesagt mit einer ausgeklügelten dirty rectangle detection. STARK vereinfacht gesagt: Bei einem repaint(x,y,w,h) wird das Rechteck (x,y,w,h) mit dem Bereits existierenden dirty rectangle vereinigt. Am Ende wird das Dirty Rectangle neu gezeichnet.

 

[Steev]

Danke für die Antwort Marco,

Bei meiner Engine habe ich das ähnlich gemacht. Ich habe eine Interface Paintable die die Methoden paint(XGraphics g), repaint(), und repaint(int x, int y, int width, int height) beinhaltet.
Diese Interface muss alles implementieren was gezeichnet werden soll.
Bei den einzelnen Zeichenobjekten war es bisher so, dass das Zeichenobjekt bei bestimmten Ereignissen wie zum Beispiel bei der Änderung der Position oder der Größe von der übergeordneten Komponente bzw. wenn es keine übergeordnete Komponente gibt von der "Bühne" (das ist bei mir so eine Art Panel oder Container der alle Möglichen Zeichenobjekte beinhaltet) eine Neuzeichnung des eigenen Bereiches anfordert.
Bisher habe ich dann in der "Bühne" (Stage) den Bereich nicht berücksichtigt sondern dann alles komplett neu gezeichnet.
Bei meinen Micky-Maus-Tests mit 20 bis 30 Objekten lief das ohne größere Probleme. Jetzt habe ich aber das Problem wenn sich auf der Bühne nicht 20 sondern einige hundert Objekte befinden.

Beim Neuzeichnen gehe ich momentan folgendermaßen vor:
1. Zeichne den definierten Hintergrund
2. Iteriere durch alle Zeichenobjekte und prüfe ob das Zeichenobjekt sichtbar ist und sich innerhalb des sichtbaren Bereiches befindet.
3. Zeichne das Objekt neu

Durch diese Iteration sowie durch das Neuzeichnen der Objekte geht dann natürlich mit einer steigenden Anzahl von Objekten eine Menge Performance verloren, daher war mein erster Ansatz dahingehend, dass beim anfordern des Repaints durch die Zeichenobjekte einfach das Objekt mitgegeben und in einen Repaint-Puffer eingetragen wird. Beim Neuzeichnen bin ich dann wie folgt vorgegangen:
1. Zeichne den definierten Hintergrund
2. Iteriere durch den Repaint-Puffer und prüfe ob das entsprechende Objekt sichtbar und im sichtbaren Bereich ist.
3. Zeichne das Objekt neu.

Bei diesem Ansatz hatte ich dann folgende Probleme die mich dazu geführt hatten den vorherigen Ansatz wieder zurückzuspielen:
1. Die Objekte, die nicht neu gezeichnet werden mussten wurden durch den Hintergrund überlagert und waren folglich auch nicht mehr sichtbar.
2. Wenn mehrere Objekte übereinander lagen, von denen die Objekte in unterschiedlichen Abständen neu gezeichnet werden mussten änderte sich mit jedem Zeichnen die Sortierung.

Ich suche eine Lösung wo ich nicht über alle Objekte iterieren muss und trotzdem nur das zeichne, was unbedingt neu gezeichnet werden muss...

Gruß
Steev

 

[Tomate_Salat]

import java.awt.BorderLayout;

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JTextArea;
import javax.swing.SwingUtilities;


public class CompAtTest
{
	public static void main(String[] args)
	{
		final JFrame frame	= new JFrame();
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		
		JPanel panel		= new JPanel();
		panel.setLayout(new BorderLayout());		
		panel.add(new JTextArea());
		
		frame.add(panel);
		
		frame.setSize(300, 300);		
		
		SwingUtilities.invokeLater(new Runnable()
		{
			@Override
			public void run()
			{
				frame.setVisible(true);
				System.out.println(SwingUtilities.getDeepestComponentAt(frame, 100, 100));
			}
		});
	}
}

vllt kannst du damit etwas anfangen. Als ausgabe bekomme ich:

javax.swing.JTextArea[,0,0,284x262,layout=javax.swing.plaf.basic.BasicTextUI$UpdateHandler,alignmentX=0.0,alignmentY=0.0,border=javax.swing.plaf.basic.BasicBorders$MarginBorder@18558d2,flags=296,maximumSize=,minimumSize=,preferredSize=,caretColor=sun.swing.PrintColorUIResource[r=51,g=51,b=51],disabledTextColor=javax.swing.plaf.ColorUIResource[r=184,g=207,b=229],editable=true,margin=javax.swing.plaf.InsetsUIResource[top=0,left=0,bottom=0,right=0],selectedTextColor=sun.swing.PrintColorUIResource[r=51,g=51,b=51],selectionColor=javax.swing.plaf.ColorUIResource[r=184,g=207,b=229],colums=0,columWidth=0,rows=0,rowHeight=0,word=false,wrap=false]

also hat er das JTextArea gefunden, welches ja sichtbar ist.

 

[Marco13]

Hm. Es ist schwer, aus so einer Beschreibung schon konkrete Tipps abzuleiten. Es ist nicht klar, an welcher Stelle von Swing (oder nicht Swing?) sich die Engine "einhakt". Solche Fragen, wie z.B. wer das "Coalescing" von repaint-Aufrufen übernimmt, damit nur EINmal neu gezeichnet wird, wenn auf 10000 Objekten "repaint" aufgerufen wird, sind auch wichtig. Aber ich schreibe einfach mal frei raus irgendwelchen Pseudo(!!!)code, und warte dann auf die Sätze, die mit "Das geht bei mir nicht, weil..." anfangen

class Painter extends JPanel // oder "Bühne"
{
    private List<Paintable> paintables = ...

    private Rectangle dirty = ...

    public void markDirty(Rectangle d) { dirty.union(d); }

    public void paintComponent(Graphics g)
    {
        super.paintComponent(Graphics g);
        for (Paintable paintable : paintables)
        {
            paintable.paintOn(g, dirty);
        }
        dirty.clear();
    }
}


class Paintable
{
    public void repaint()
    {
        owningPainter.markDirty(this.getBounds());
    }
    public void repaint(int x, int y, int w, int h)
    {
        owningPainter.markDirty(new Rectangle(x+this.getX(), y+this.getY(), w, h));
    }

    public void paintOn(Graphics g, Rectangle dirty)
    {
        Rectangle toPaint = getBounds().intersect(dirty);
        if (!toPaint.isEmpty()) paintInternal(g, toPaint);
    }

    private void paintInternal(Graphics g, Rectangle toPaint) { ... }

}

Die Abfragen, OB gezeichnet werden muss, könnten ggf. auch in der Painter-Klasse gemacht werden, wenn sowas wie

for (Paintable paintable : paintables)
{
    if (dirty.intersects(paintable.getBounds())
    {
        ...
    }
}

gehen würde oder so.

Aber nochmal: Da ist SO viel weggelassen (Clipping, Coalescing usw.) dass das vermutlich nicht direkt umsetzbar wäre...

 

[Steev]

Hallo Marco,

ich verwende Swing bzw. AWT eigendlich nur noch zum Anzeigen des gerenderten Bildes. Hier habe ich alle Repaints abgeschaltet und verwende BufferStrategy um zu zeichnen.

Grundsätzlich habe ich ja meinen Repaint-Puffer der erstmal eine Reihe von Repaint-Aufrufen sammeln soll, damit nicht für jedes Objekt einzeln gezeichnet wird.

Bei deinem Ansatz bin ich mir noch nicht so ganz sicher, ob die Verwendung des Standards bei Rectangle nicht zur folge haben könnte, dass zu viele Objekte erzeugt werden und ich die Performance, die ich durch das Zeichnen spare dann für den Grabage-Collector wieder verliere. Vom Grundsatz her hört sich das aber recht brauchbar an, ich werde damit wahrscheinlich noch etwas herumexperimentieren...

Grundsätzlich bin ich mit dem "Iteriere über alles und gucke was neu gezeichnet werden muss"-Ansatz aber noch nicht so glücklich, da dann viel zu viele Iterationen durchgeführt werden, die eigendlich nicht notwendig sind.

Vieleicht habe ich ja einfach nur einen Knoten im Hirn Aber mir kommt gerade folgende Idee:
Könnte man nicht die Datenhaltung der Zeichenobjekte dahingehend optimieren, dass die Objekte nach Position des Mittelpunktes sortiert werden oder den Zeichenbereich in Sub-Bereiche eingeteilt wird, die jeweils eigene Objekte beinhalten, sodass man nur noch prüfen muss, in welcher Sub-Bereich neugezeichnet werden muss.
Eventuell kann man ja auch etwas mit binären Bäumen etwas basteln...
Keine Ahnung ob das brauchbare Ideen sind...

 

[Marco13]

Das mit dem Baum klingt ... naja, einerseits nicht verkehrt, andererseits auch aufwändig. Es kommt wohl darauf an, WAS genau gezeichnet werden soll. Wenn das ganze nur Images sind, dürfte ein Zeichnen wohl schneller sein, als erst eine aufwändige Suche in einer Datenstruktur. Wenn es kleine Mandelbrotfraktale sind, die bei jedem Neuzeichnen neu berechnet werden, düfte sich nahezu jedes gesparte Zeichnen lohnen
Aber sowas wie ein drüberiterieren über eine Liste sollte wirklich erst bei SEHR vielen Objekten relevant werden. Man muss sich auch überlegen, was die Alternativen sind. Angenommen, es gibt 1 Million objekte, und das drüberlaufen dauert "lange" (es wäre sicher noch verschwindend wenig verglichen mit dem eigentlichen Zeichnen, aber egal). Wenn nun 5 Objekte neu gezeichnet werden müssen, könnte man die in einer Liste speichern, und da natürlich schneller drüberlaufen. Wenn aber 500000 Objekte neu gezeichnet werden müssen, sieht das ganze schon anders aus...

Das mit den Rectangles war ja nur gröbster Pseudocode. Nicht umsonst gibt es genau wegen des angesprochenen Punktes (allokation) solche Sachen wie SwingUtilities (Java Platform SE 6)...

 

[Steev]

Ein Problem sehe ich dabei trotz allem: Wenn man per Rectangle oder generell zwei Rechtecke per union verbindet, dann wird nur das Rechteck so vergrößert, dass beide Rechtecke in dem neuen Rechteck enthalten sind. Wenn jetzt oben links und unten rechts zwei Objekte ein Repaint anfordern würden, dann würde das gesamte Bild neu gezeichnet werden.
Daher habe ich eine Klasse DirtyRegion erstellt, die einen Array vom Typ XBounds (das ist mein Rectangle) beinhaltet, der dynamisch bis zu einer bestimmten Maximalgröße erweitert wird.
Meine Methode intersects dieser Klasse iteriert dann über alle Bounds und prüft ob eine Überschneidung vorliegt.
Das was mir jetzt an dieser Lösung nicht gefällt ist, dass ich jetzt n^m Iterationen habe...

Hast du vielleicht eine bessere Lösung parad?

 

[Marco13]

Nochmal: So "remote" ist das schwierig. Man könnte sich ausgeklügelte Sachen überlegen, mit BSP und Quadtrees, oder irgendwas für die Dirty Rectangle Detection wo (in Anlehnung an dein Beispiel) zwei Rechtecke nur dann wirklich als Union vereinigt werden, wenn sie sich Überschneiden und ansonsten beide einzeln in einem Array gespeichert werden, bis der Array eine bestimmte Größe hat. Oder dass man die Fläche des resultierenden Rechteckes noch mit einbezieht (NUR die Anzahl zu berücksichtigen ja eigentlich keinen Sinn macht). Aber man investiert dabei vielleicht viel Arbeit, um etwas zu erreichen, was man mit einem anderen Ansatz leichter hätte erreichen können. (Ich will dich nicht auf eine falsche Schiene manövrieren ). Um mal so einen möglichen(!) GANZ anderen Ansatz anzudeuten: Müssen die Objekte alle gezeichnet werden, oder liegen die auf verschiedenen "Ebenen", so dass man von 1000 zu zeichnenden Objekten vielleicht 990 ignorieren kann, weil sie ohnehin von den übrigen 10 überpinselt werden würden?

 

[Steev]

Hi Marco,

die Objekte die feiert werden, müssen tatsächlich auch alle gezeichnet werden, da Sie sich innerhalb des Kamera-Fachbereiches befinden. Alle anderen Objekte werden schon von vorneherein ignoriert. Wenn ein objekt nicht gezeichnet werden müsste, da es von einem anderen Objekt überlagert wird kann dies nur schlecht bis gar nicht ermittelt werden, da die Objekte erstens nicht rechtmäßig sind und zweitens auch transparent sein oder transparente stellen beinhalten können. Deine Ideemit der bedingten union finde ich gut. Das werde ich noch einbauen um den dirty-Region-Puffer möglichst klein zu halten.
Dann während dieser Ansatz aber auch schon fast ausgereizt...
Ansonsten gibt es ja noch die Möglichkeit, den Zeichenbereich in mehrere Unterbrechen zu unterteilen.
Ich werde einfach mal beide Möglichkeiten implementieren und gucken, was schneller ist.

 

[Steev]

So, ich habe jetzt mal etwas herumgebastelt und habe das ganze jetzt soweit fertig, dass wirklich nur das neu gezeichnet wird, was auch gezeichnet werden muss. Ich habe mal ein kleines Beispiel gezimmert wo man gleichzeitig etwas mit dem PLAF (plugable look and feel) der Engine herumspielen kann.
Es währe nett, wenn ihr mir sagen könntet, welche durchschnittliche Frame-Rate auf euren Systemen erreicht wird. Bzw. ob das sich das Programm überhaupt ausführen lässt. (Wenn es sich nicht ausführen lässt dann wäre es nett, wenn ihr mir eine Exception oder etwas in der Art senden könntet.

Die Datei kann hier heruntergeladen werden:
http://steev.st.ohost.de/RepaintTestcase#1.jar

 

[Apo]

FPS: 63
DurchschnittsFPS: 62
Average FPS to MAX: 104%
Rendering Time in Nano: ~200000

 

[Marco13]

Also auf der alten Kiste an der ich gerade sitze (1400er Athlon, GeForce 2(!)) läuft's mit 60fps. Bei Größenänderungen gibt's übles Flackern, aber das ist vielleicht nur ein Detail....

 

[Steev]

Super,

danke für´s testen ihr beiden.
Dann scheint das ganze ja zu funktionieren... (Das Flackern sollte daher kommen, dass nach einem Skalieren die gesamten "alten" Puffer verworfen und neue Puffer erstellt und gefüllt werden.)

Gruß
Steev

 

[Tomate_Salat]

Das kenne ich von dem Projekt hier drin. Den fehler den ich Gastredner (glaube ich wars) gemeldet habe, ist immernoch drin. Ich erinnere aber gerne nochmal daran:

sobald ich das Programm auf meinen sekundären Bildschirm ziehe, habe ich keine Maus mehr im Fenster => verkleiner/vergrößer ich das Fenster, erkennt man: der repaint funktioniert nicht mehr.

 

[Marco13]

Oh ja: Wenn man es auf den zweiten Monitor schiebt, verschwindet (nicht nur der Mauszeiger, sondern ) der komplette Bildinhalt - ziemlich genau dann, wenn mehr als die Hälfte des Fensters auf der anderen Seite ist.
Die andere Seite ist dunkel. Sehr dunkel.
(Halt's Maul, Yoda, und friß endlich deinen Toast! :joke: )

 

[Steev]

Hmm dass ist komisch. Ich arbeite selbst mit zwei Monitoren, dass muss ich mal ausprobieren...
Keine Ahnung woran das liegen könnte. Ich hatte einen Teil des Kernels vor einiger Zeit mal für JCup missbraucht... Daher kam euch das bekannt vor (weil dieselben Grafiken verwendet wurden...). Ich dachte aber eigentlich dass ich den Fehler jetzt gefunden hätte.
Danke für den Hinweis.