Algorithmus für Polygon Image Fill

Question

Ich möchte einen effizienten Algorithmus zum Füllen von Polygon mit einem Bild, ich möchte ein Bild in Trapez füllen. zur Zeit ich es in zwei Schritten
1) Zuerst Führen StretchBlt auf Bild mache,
2) Führen Sie Spalte für Spalte vertikale StretchBlt,

Gibt es eine bessere Methode, um dies zu implementieren? Gibt es einen generischen und schnellen Algorithmus, der jedes Polygon füllen kann?

Danke, Sunny

Answer 1

Ich kann Ihnen mit der Verzerrung Teil nicht helfen, aber Polygone Füllung ist ziemlich einfach, vor allem, wenn sie konvex sind.

Für jede Y-Scanzeile muss eine Tabelle mit Y indiziert werden, die ein minX und maxX enthält.

Führen Sie für jede Kante einen DDA-Linienzeichnungsalgorithmus aus, und verwenden Sie diesen, um die Tabelleneinträge auszufüllen.

Für jede Y-Linie haben Sie jetzt ein minX und maxX, so dass Sie nur dieses Segment der Scanlinie füllen können.

Der schwierige Teil ist ein mentaler Trick - denken Sie nicht an Koordinaten als Pixel. Stellen Sie sich Koordinaten wie liegend zwischen die Pixel vor. Mit anderen Worten, wenn Sie ein Rechteck haben, das von Punkt 0,0 zu Punkt 2,2 geht, sollte es 4 Pixel aufleuchten, nicht 9. Die meisten Probleme mit Polygon-Füllung drehen sich um dieses Problem.

HINZUGEFÜGT: OK, es klingt wie das, was Sie wirklich fragen, wie man das Bild zu einer nicht-rechteckigen Form (aber trapezförmig) streckt. Ich würde es in Bezug auf die Parameter s und t tun, ausgehend von 0 bis 1. Mit anderen Worten, ein Ort im ursprünglichen Rechteck ist (x + w0*s, y + h0*t). Definieren Sie dann eine Funktion, so dass s und t auch auf Positionen im Trapez abgebildet werden, z. B. ((x+t*a) + w0*s*(t-1) + w1*s*t, y + h1*t). Dies definiert eine Koordinatenzuordnung zwischen den zwei Formen. Dann scannen Sie einfach x und y, umwandeln in s und t und Mapping-Punkte von einem zum anderen. Wahrscheinlich möchten Sie lieber einen Glättungsfilter als eine direkte Kopie haben.

HINZUGEFÜGT, um eine bessere Erklärung zu geben: Ich nehme an, dass sowohl Ihr Rechteck als auch Ihr Trapez die obere und untere Kante parallel zur X-Achse haben. Die untere linke Ecke des Rechtecks ​​ist <x0,y0>, und die untere linke Ecke des Trapezes ist <x1,y1>. Ich nehme an, dass die Breite und Höhe des Rechtecks ​​<w,h> sind. Für das Trapez, ich nehme an, es hat Höhe h1, und dass es eine niedrigere Breite ist w0, während es obere Breite w1 ist. Ich nehme an, dass die linke Kante um eine Entfernung von a "geneigt" ist, so dass die Position ihrer oberen linken Ecke <x1+a, y1+h1> ist. Angenommen, Sie durchlaufen <x,y> über das Rechteck. Berechnen Sie an jedem Punkt s = (x-x0)/w und t = (y-y0)/h, die beide im Bereich 0 bis 1 liegen. (Ich lasse Sie herausfinden, wie Sie das tun, ohne Fließkomma zu verwenden.) Dann konvertieren Sie das in eine Koordinate im Trapez, wie xt = ((x1 + t*a) + s*(w0*(1-t) + w1*t)), und yt = y1 + h1*t. Dann ist <xt,yt> der Punkt im Trapez entsprechend <x,y> im Rechteck. Jetzt lass ich dich herausfinden, wie man das Kopieren macht :-) Viel Glück.

P.S.Und bitte vergiss nicht - Koordinaten fallen zwischen Pixel, nicht auf ihnen.

Answer 2

Wäre es möglich, das Problem zu umgehen und OpenGL für Sie zu verwenden? OpenGL kann zu Speicherkontexten rendern und wenn Sie die Hardwarebeschleunigung dadurch nutzen können, werden alle Code-Optimierungen, die Sie auf der CPU vornehmen können, komplett in den Schatten gestellt (obwohl bei älteren Karten das Speicherkontext-Rendering möglicherweise nicht genutzt werden kann) die Hardware).

Wenn Sie dies vollständig in Software tun möchten MESA kann eine Option sein.