Algorithmus zum zeichnen eines Polygons (2D)?
-
während des durchlaufes der h-line passen wohl nicht alle daten in die register, wo sind sie dann wenn nicht auf dem stack?
rapso->greets();
-
Original erstellt von rapso:
während des durchlaufes der h-line passen wohl nicht alle daten in die register, wo sind sie dann wenn nicht auf dem stack?Ich würde schon sagen, das diese zwei Werte in die Register passen könnten. Was soll'n das überhaupt für'ne Begründung für unnütze Arrays werden, wenn's fertig ist?
-
also bei bresenham hat man pro kante 2positionen, ein delta und ein schwellenwert (jetzt so ma auf die schwelle), man bekommt alle register eigentlich schön gefüllt, da sind dann einige stackoperationen...
ob man nun die kanten daten auf den stack packt und dann jeweils eine h-line schreibt, oder ob man die kantenposition in ein arrays stopft und erst alle h-line positionen berechnet, das ist total egal.
aber ihr müßt ja in jedem kleinem fitzel beweisen das eure idiologie besser ist *fg*
übrigens läuft der softwarerenderer von Unreal auf eine ähnliche weise wie der von mir vorgegebene algorithmus, weil
- man danach besser optimieren kann
- es egal ist wieviel ecken ein poly hat, weil jede ecke nur für sich betrachtet wird
- man nicht sortieren muss
- es keinerlei nachteile gegenüber den alten algorithmen gibt
- es total billig ist beliebig geformte polys zu zeichnen, concave, convexe, sich schneidende kanten beinhaltende...rapso->greets();
-
das eine schwelle soll schnelle heißen
und
"ob man nun die kanten daten auf den stack packt und dann jeweils eine h-line schreibt, oder ob man die kantenposition in ein arrays stopft und DANN erst alle h-line positionen berechnet, das ist total egal."
-
Der Framebuffer wird möglicherweise dein tolles Array swappen. Bei Unreal gibts nur Dreiecke, also warum für andere Polygone optimieren?
-
weil man so an kanten automatisch zwei nebeneinander liegende kanten aufheben kann wenn sie in einer ebene liegen
so sicher bin ich mir nicht, dass bei unreal (wohgemerkt1) dreiecke waren, denn die levels bestanden immer aus rechtekigen flächen (vielleicht intern 2dreiecke, das weiß ich nicht)
die mußten ja sowieso die edges für z.B. vodoo karten generieren.b-buffer soweit ich weiß...
rapso->greets();
-
Original erstellt von rapso:
weil man so an kanten automatisch zwei nebeneinander liegende kanten aufheben kann wenn sie in einer ebene liegenNö, bei Unreals Softwarerenderer geht das nicht. Gibt wohl doch keine Vorteile.
-
Wie wärs wenn ihr beide einfach ein kleines Programm schreibt und die Perfomance misst. Das ist jetzt nur blanke Theorie.
-
Original erstellt von Lars:
Wie wärs wenn ihr beide einfach ein kleines Programm schreibt und die Perfomance misst. Das ist jetzt nur blanke Theorie.Ok, schreib ein Framework dazu!
-
tja, keine vorteile und der unreal renderer macht das, man müssen die blöd sein... jedenfalls falls deine erfahrung mit b-buffern wirklich so superior sind, dass nichtmal die coder von der engine mit dir mithalten können.
rapso->greets();
-
Original erstellt von rapso:
**tja, keine vorteile und der unreal renderer macht das, man müssen die blöd sein... jedenfalls falls deine erfahrung mit b-buffern wirklich so superior sind, dass nichtmal die coder von der engine mit dir mithalten können.rapso->greets();**
Was kann ich dafür, wenn die keinen Plan haben. BTW kenn ich mich auch mit A und C-Buffern aus.
-
Um z. B. zu entscheiden, ob ein Punkt innerhalb eines Polygons liegt, betrachtet man die Summe der Winkel zwischen dem zu untersuchenden Punkt und allen Eckpunkten des Polygons.
Ist die Winkelsumme Null, so liegt der Punkt außerhalb des Polygons.
Bei überschneidungsfreien Polygonen beträgt die Winkelsumme für einen inneren Punkt 360°; bei sich überschneidenden Polygonen (wie etwa das Pentagramm) haben Punkte auf der Überschneidungsfläche ein Vielfaches davon.
-
Beim Dreieck ist der Ansatz mit den Winkeln aber nicht empfehlenswert, da es viel schnellere Algorithmen gibt. Unter www.geometryalgorithms.com findest Du was dazu.
Aber Dein Vorschlag ist doch nicht wirklich, Pixel für Pixel auf dem Bildschirm durchzugehen und zu prüfen, ob er sich innerhalb eines der zu zeichnenden Polygone befindet, oder? Das wäre doch absolut langsam... pro Pixel und pro Polygon wären dann etliche atan2's nötig.
Nein, man geht einfach jedes Polygon durch (dabei sollte es schon in Form von Dreiecken vorliegen) und zeichnet es Zeile für Zeile.
-
Ich habe ja auch keineswegs behauptet, daß der Algorithmus schnell sei.
Jedoch glaube ich, daß die bisherigen Lösungsvorschläge nur für die besonders gutartigen, konvexen Polygone problemlos funktionieren.
Aber was machst Du z. B. bei der mit "?" markierten Innenfläche des Pentagramms? Ausfüllen oder nicht? Und wie ist die Dreieckszerlegung?.........../|.......... ..........|*|.......... ..........|**\......... .--------/---+-------.. ..\*****|????|*****/... ....\***|?????\**/..... ......\/??????|/....... ......|*\????/|........ ...../****\/***\....... ....|****/..\**|....... ....|**/......\|....... ....|/.................
-
Original erstellt von Krösus:
Und wie ist die Dreieckszerlegung?Algo dafür:
solange in der Polylist nicht alles Dreiecke
nimm zwei Eckpunkte eine Polys
teile das Poly an der Verbindungslinie, wenn die keine Begrenzungslinie des Polys schneidetSo, jetzt kannste los-/zerlegen!
-
Original erstellt von Krösus:
Aber was machst Du z. B. bei der mit "?" markierten Innenfläche des Pentagramms?Ein Pentagramm stellt wohl eine Ausnahme dar. Ich glaube auch nicht, dass man es ohne "innere" Füllung (da, wo die Fragezeichen sind) irgendwie mit nur 5 verschiedenen Punkten darstellen kann. Entweder ganz ausfüllen (dann wäre es ein "normales" Polygon) oder - wenn Du die Fragezeichen nicht ausgefüllt haben willst - in 5 Dreiecke zerlegen.
-
Ein beliebiges Polygon einfach so in Dreiecke zu legen ist nicht so trivial, wie man es sich vielleicht denkt. Es darf einige Schritte, die nicht zu einfach sind. Der erste Schritt waere das Polygon in konvexe Polyone zu zerlegen, die dann sehr leicht zu triangulieren sind. Aber fuer das einen effizienten Alg. findet ist sehr schwer. Es wird dann dauer auf eine monotone Zerlegung ausgewichen, die rel einfach ist...blabla...einfach nicht so einfach. Aber wenn das Polygon eh nur aus 5 vertices besteht dann sollte jeder Triangulierungs-Alg. ausreichen.~tOmUsA
-
Original erstellt von tOmUsA:
Ein beliebiges Polygon einfach so in Dreiecke zu legen ist nicht so trivial, wie man es sich vielleicht denkt. [...]Selbst wenn es sehr kompliziert ist, so ist es doch viel sinnvoller eine solche Routine per Poly laufen zu lassen, als per Pixel eine Menge Zeit zu verschwenden.
-
Original erstellt von TGGC:
Ok, schreib ein Framework dazu!Was wie wo? Ich hab wollt nur ein Tip geben wie ihr die Diskussion lösen könnt, denn irgendwie dreht ihr euch im Kreis, denn beide behaupten stur ihre Lösung sei schneller.
-
Original erstellt von Lars:
[quote]Original erstellt von TGGC:
[qb]Ok, schreib ein Framework dazu!Was wie wo? Ich hab wollt nur ein Tip geben wie ihr die Diskussion lösen könnt, denn irgendwie dreht ihr euch im Kreis, denn beide behaupten stur ihre Lösung sei schneller.[/QB][/QUOTE]
Aber wie soll man das denn vergleichen, wenn nicht beide Routinen in dem selbem Framework laufen müssen? ICh behaupte ausserdem nix, ich sag nur wie es ist ;).
