# Vierecke zeichnen



## Scotty (6. Mai 2005)

ich habe ein programm geschrieben, dass vierecke auf dem bildschirm zeichnen soll. bei etwa 100000 vierecken gerät das programm ins stottern. nun weiß ich nicht, ob das an der berechnung der vierecke liegt, oder am zeichnen. moderne 3d beschleuniger können mehrere millionen dreicke pro sekunde verarbeiten und das liegt nicht daran, dass ein dreieck eine ecke weniger besitzt, als ein viereck. wie können 3d spiele so flüssig gerendert werden? ich meine, die kochen doch auch nur mit wasser.


----------



## dyrathror (6. Mai 2005)

Und wie sieht Dein Coding aus mit dem Du die Rechtecke zeichnen läßt?


----------



## Scotty (6. Mai 2005)

nachdem die rechtecke berechnet und coloriert wurden, läuft im endeffekt alles auf drawPolygon hinaus. also 100000 mal drawPolygon(). so viele möglichkeiten gibbet da ja nicht, ein rechteck zu zeichnen. man könnte anstatt der zig polygone noch zig bufferedimage mit der entsprechenden farbe erstellen, aber das würde wohl kaum einen unterschied machen. überdeckungen könnten noch mittels clipping und culling eliminiert werden, aber das sind in etwa auch nur maximal 50% der rechtecke. also mir fällt nix mehr ein, wie man da die performance optimieren könnte.


----------



## Scotty (6. Mai 2005)

ich habs mal gemessen: für die berechnung braucht das programm etwa ne halbe sekunde, zum zeichnen ne viertelste, also fast eine sekunde pro durchlauf. ich kann den berechnungsalgorithmus leider nich posten, das wäre zu umfangreich, da hab ich auch schon ne idee... nur das mit dem zeichnen dauert mir noch zu lang.


----------



## Scotty (6. Mai 2005)

oke, ich hab nochmal an verschiedenen punkten des codes messungen vorgenommen. es gibt da zwei doppelschleifen, die pro zyklus 6 mal durchlaufen werden. die erste produziert insgesamt 64 millis, lässt sich aber nicht vermeiden, die zweite dafür über 300:

```
for(int i=0;i<=this.grid.x;i++)
{
	for(int j=0;j<=this.grid.y;j++)
	{
		v[i][j]=m.get(new Vector(i*xINC,j*yINC,0));
	}
}
for(int i=0;i<this.grid.x;i++)
{
	for(int j=0;j<this.grid.y;j++)
	{
		r.add(new Rect(new Matrix(
			v[i][j],
			v[i+1][j],
			v[i+1][j+1],
			v[i][j+1]),this.c[i][j]),new Point(i,j));
	}
}
```


----------



## Beni (6. Mai 2005)

Versuch mal diese "new"'s rauszubringen. Objektherstellung gehört zum langsamsten was es gibt.
Vielleicht kannst du alte Rects und etc benutzen?


----------



## dyrathror (6. Mai 2005)

Beni hat gesagt.:
			
		

> Versuch mal diese "new"'s rauszubringen. Objektherstellung gehört zum langsamsten was es gibt.
> Vielleicht kannst du alte Rects und etc benutzen?



Du bist mir zuvorgekommen, das ist auch das erste was mir aufgefallen ist  8) 

Und dann die Frage, hast Du es mal mit BufferedImage versucht?
Viereck einmal berechnen und in ein BufferedImage malen und dieses
dann immer wieder in das Panel zeichnen?


----------



## Scotty (7. Mai 2005)

ok, ich hab jetzt versucht, alle überflüssigen new's - und das waren nicht grade wenig - im ganzen programm über set methoden zu regeln. das ist ca. 6 mal schneller, als die andauernde erstellung neuer objekte. über back culling konnte ich auch noch etwa die hälfte aller rechtecke eliminieren, sodass auch das zeichnen optimiert wurde. bufferedimage... naja, ich könnte die rechtecke alle auf ein bufferedimage zeichnen und dann das bufferedimage ins panel, aber ich glaube, das macht keinen großen unterschied im vergleich zu graphics.


----------



## Grizzly (7. Mai 2005)

Klingt nach einer Software 3D Engine. 

Schau Dir mal VolatileImage an. Ist etwas komplizierter als die Verwendung von BufferedImage, dafür aber Hardware beschleunigt.


----------



## Scotty (7. Mai 2005)

da sag ich jetzt mal nix dazu.   
das problem ist dabei nur immer die performance. also, wenn da einer nen guten tipp auf lager hat, nur her damit!


----------



## Grizzly (7. Mai 2005)

Scotty hat gesagt.:
			
		

> da sag ich jetzt mal nix dazu.   [...]


Hab' ich was falsches gesagt? :bahnhof:


----------



## Scotty (7. Mai 2005)

Grizzly hat gesagt.:
			
		

> Scotty hat gesagt.:
> 
> 
> 
> ...


nee, is vollkommen korrekt. 
zum thema: warum werden eigentlich bei sowas immer dreicke verwendet? ich seh darin gegenüber vierecken keinen vorteil. außerdem hab ich noch nie ein koordinatensystem, was aus dreicken besteht gesehen. das verdoppelt doch nur die anzahl der objekte.


----------



## Grizzly (7. Mai 2005)

Liegt wohl daran - denke ich mal - dass ein Dreieck die geometrische Fläche mit den wenigstens Punkten ist und damit besser 3D Körper gebildet werden können (man denke bspw. an eine Kugel).

Texturierst Du eigentlich Deine Polygone?


----------



## Scotty (7. Mai 2005)

ja. und deshalb auch die performanceschwierigkeiten. ohne texturen wär das alles  kein problem. es gibt da sicher noch eine effizientere methode, flächen zu texturieren, als wie ich das gemacht habe. man müsste gleich die images drehen können...

edit: kugeln sind aber relativ selten. ich mag vierecke.  8)


----------



## Grizzly (7. Mai 2005)

Zum Texture Mapping hab' ich bisher zwei Links gefunden:
http://www.geocities.com/pcgpe/tmap.html
http://www-lehre.inf.uos.de/~cg/2004/skript/node153.html

Allerdings werd' ich aus dem ganzen Zeug nicht arg schlau. Hast Du irgendetwas einfacheres zu dem Thema?


----------



## Scotty (7. Mai 2005)

für mich klingt das alles bissle wie böhmische dörfer.
die texturierung hab ich noch basierend auf meinem schulwissen hinbekommen. mathe unterricht 11/12 analyisis. eigentlich ist es ganz einfach, wenn man es weiß. du ermittelst 3 punkte der zu texturierenden fläche, deren geraden orthogonal zueinander sind und ermittlelst damit dann die ebenengleichung v=v0+a*(v1-v0)+b*(v2-v0). durch einsetzen von a und b erhällst du jeden punkt auf der fläche. dann rasterst du das ganze in ein 2d array und weist jedem punkt die farbe des entsprechenden bildpunktes der textur zu. fertig.


----------



## Grizzly (8. Mai 2005)

Versteh' ich jetzt nicht ganz. Normalerweise hat mein Polygon bzw. Dreieck ja 3 Koordinate - für jede Ecke eine.

Bspw.

```
P1 = (0,1,0)
P2 = (2,1,1)
P3 = (3,0,0)
```

Und wie soll ich da jetzt weiter verfahren? Rein theoretisch müsste ich jetzt die Punkte auf 2D sprich den Bildschirm projizieren.

Bspw. (ich weiss, dass das natürlich so nicht stimmt, bin aber zu faul da eine wirklich Projektion zu machen  )

```
P1 = (0,1)
P2 = (2,1)
P3 = (3,0)
```

Jetzt müsste ich jeden der Punkte in dem 2D Dreieck abfahren und zurückrechnen auf das 3D Dreieck. Und von da aus müsste ich dann auf die Texture umrechnen, oder? ???:L 

Wie würden die Rechnung mit Deiner Formel da aussehen?


----------



## Scotty (8. Mai 2005)

ja, so in etwa haut das schon hin, wie du das sagst. aber die meisten berechnungen, also rotation von körpern, bewegung und auch die rasterung der flächen als vorbereitung für die texturen findet noch in der 3d welt statt. die reihenfolge wäre dann ungefähr so:

:eckkoordinaten der objekte berechnen (sind bei echten engines glaube in den level daten enthalten)
:rotieren/bewegen
:flächen rastern
:raster mit bildern versehen
:2d projektion
:zeichnen

das größte problem hierbei ist, dass sich aus der rasterung höllisch viele koordinaten ergeben, die zwar nich rotiert, aber dafür berechnet und projeziert werden müssen. und das drückt auf die performance.

nach meiner formel schnappst du dir die 3 eckpunkte des dreickes und setzt sie in der richtigen reihenfolge (mitte,links,rechts oder mitte,rechts,links) in die formel ein:

dreieck: 
p0(0|0|0)
p1(1|0|0)
p2(0|1|0)

v=(p0+(p1-p0)*a+(p2-p0)*b)

p.x=(p0.x+(p1.x-p0.x)*a+(p2.x-p0.x)*b)
p.y=(p0.y+(p1.y-p0.y)*a+(p2.y-p0.y)*b)
p.z=(p0.z+(p1.z-p0.z)*a+(p2.z-p0.z)*b)

v ist dann der spezielle punkt auf deinem dreicke, besser gesagt, auf deiner ebene, denn mit der formel erhällst du alle punkte für a,b geht gegen +/- unendlich. da musste noch bissle probieren, wie a und b halt aussehen müssen. es würde sich dann für die fläche ein 2d array von punkten ergeben.

jetzt erstelltst du aus dem raster noch rechtecke, damit wir auch richtige flächen, und nicht nur punkte haben, lädst das image, wandelst es in ein bimage um, damit du die farbwerte entnehmen kannst und überträgst diese auf das eben creierte array[][] von rechtecken. 2d projektion, zeichnen, und neuer durchlauf von schritt 2.  8)


----------



## Grizzly (8. Mai 2005)

Das mit der 3D Welt und der Projektion und so hab' schon. Mir fehlen nur die Texturen auf den Polygonen. Werd' mir das mal anschauen und ausprobieren. 
Aber soweit mal danke.


----------

