Algorithmen für Grafikberechnung

Hallo,

ich möchte mir gerne eine eigene Grafikbibliothek programmieren. Sie soll eigentlich nicht viel können, außer primitive 2D-Objekte (Rechtecke, Kreise, Polygone) mit Anti-Aliasing in verschiedenen Farben per CPU zu zeichnen.
Nur leider fehlt mir da völlig der Startpunkt. Die Funktionen sollten nicht allzu langsam sein, deshalb dachte ich mir, ich könnte da teilweise auf Prozessorfeatures wie MMX zurück greifen. Aber gibt es auch bestimmte Algorithmen, mit denen sich Objekte schnell berechnen lassen? Ich denke da vor allem an die Kreise und Polygone.

C++ Forumbot

Dieser Thread wurde von Moderator/in rüdiger aus dem Forum Rund um die Programmierung in das Forum Spiele-/Grafikprogrammierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

hellihjb

gibt es auch bestimmte Algorithmen, mit denen sich Objekte schnell berechnen lassen? Ich denke da vor allem an die Kreise und Polygone.

Die Eckpunktpositionen v[0]..v[n] eines konvexen Polygons seien zb. im Uhrzeigersinn gegeben.
Suche den Index "top" des obersten Eckpunktes.
Die linke Kante verlaeuft zum Eckpunkt v[top-1], die rechte zum Eckpunkt v[top+1] (Arraygrenzen beachten).
Interpoliere fuer jede Zeile die linke und rechte Seite des Polygons und fuelle den Bereich dazwischen.
Wenn auf einer Seite ein neuer Eckpunkt erreicht ist geht's mit neuer Steigung weiter bis der unterste Eckpunkt erreicht ist.

Fuer Kreise interpoliert man ueber die einzelnen Zeilen die Y-Koordinate des Einheitskreises (-1..+1) und berechnet daraus jeweils die X-Koordinate mit sqrt(1-y*y)*radius.
Je nach Aufloesung und Radius ist eine einfache iterative Approximation fuer sqrt hinreichend. Bei grossen Radien koennen die X-Koordinaten ueber mehrere Zeilen linear Interpoliert werden. Wegen Symmetrie ergibt sich ein Grossteil der Koordinaten aus horizontaler/vertikaler/diagonaler Spiegelung.

Fuer Anti-Aliasing kann man die Aussenkanten zb als Wu-Lines behandeln.

rapso

fuer MMX bzw SSE bietet sich an anders vorzugehen. du kannst erst grob rausfinden in welchem bereich sich dein objekt befindet, dann pro pixel berechnen ob du innerhalb oder ausserhalb vom objekt bist und entsprechend zeichnen.

das hat (neben nachteilen;) ) auch sehr schoene vorteile.
1. du kannst mit sse 4pixel auf einmal abarbeiten
2. du kannst erst im groben raster testen und dann feiner
3. du kannst sehr einfach antialiasing implementieren (du testest halt mehrere punkt pro pixel, da du nicht pixelweise zeichnest, sondern mit float testen kannst, hast du subpixel genauigkeit).
4. du kannst so auch komplexere formen rasterisieren die du mathematisch beschreibst, das ist mit anderen algirthmen nicht immer einfach.
5. bei sehr vielen kleinen objekten ist das oft viel schneller als das normale zeichnen, weil der aufwand zum aufsetzen des zeichnens billig ist
6. fuer grundkoerper ist das trivial wenn man ein paar grundlagen von mathe kann.
7. garkein clipping notwendig (das ist nicht so trivial wie es oft klingt wenn es gut sein soll )

als beispiel

for y 0 to height
for x 0 to width
  if insideSphere(x,y,sphere)
    pixel(x,y,color);

function insideSphere(x,y,sphere)
   return (x-sphere.x)*(x-sphere.x)+(y-sphere.y)*(y-sphere.y)<sphere.radius*sphere.radius