Z-Buffering (Mal wieder ^^)

[milos]

Hallo,

ich habe ja vor einigen Monaten nach Hilfe gefragt um Backface-Culling und Z-Buffering in mein Isometrie-Zeichenprogramm einzubinden.
Leider hatte ich aufgrund von Zwischenfällen die mir einige Zeit und Nerv geraubt hat keine Zeit mich weiter um das Programm zu kümmern und konnte in der Zeit nur Backface-Culling implementieren und habe das Z-Buffering stehen gelassen.

Vor einigen Tagen kam mir jedoch eine Idee wie ich das (theoretisch) einfach lösen kann und momentan sieht es schon ziemlich gut aus, habe jedoch einen kleinen Fehler drinnen.
Und zwar probiere ich es gerade so, dass ich jedes Polygon einzeln auf ein Bitmap zeichnen lasse in der Position die es später auch haben soll. (Dazu sind noch Bilder angefügt, da Bilder bekannterweise mehr als 1000 Worte sagen ;))

Nun habe ich pro Polygon ein Bitmap bei der ich dann Pixel für Pixel nach gezeichneten Stellen suche und, falls ein gezeichneter Pixel vorhanden ist, dessen Position im 3D-Raum zurückrechne um dann berechnen zu können wie "nah" der Pixel von der Kamera ist. Am Schluss kombiniere ich einfach alle Bitmaps zu einem und lasse anhand der Pixeltiefe entscheiden ob es zu sehen ist oder nicht. Ich glaube genau da liegt der Fehle, beim bestimmen welche Tiefe der Pixel hat. (Im Bild im Anhang kann man den Fehler gut erkennen wenn man reinscrollt und beide Ergebnisse mal ein vergleicht. Beim vom Programm erzeugten sieht verläuft zum beispiel die Linie vom 2. Polygon nicht parallel zu den anderen vom 1. Polygon, das kann ja schon mal nicht stimmen :D)


Um die Koordinate wieder zurück zu rechnen benutze ich folgende Methode: (Das ganze Projekt ist auch im Anhang)

Delphi-Quellcode:

TPolygon3D = array of TVector3D;

function CalculateCoordinate(APolygon3D : TPolygon3D; APoint : TPointF) : TVector3D;
var
  APolygon : TPolygon;
  LLength,c : integer;
  LDistance, LMaxDistance : double;
  LPercent : double;

  LX,LY,LZ : double;
begin
  APolygon := Polygon3Dto2D(APolygon3D);
  LLength := Length(APolygon);


  LMaxDistance := 0;
  
  for c := 0 to LLength-1 do
  begin
    LDistance := APoint.Distance(APolygon[c]);
    LMaxDistance := LMaxDistance + LDistance;
  end;

  LX := 0;
  LY := 0;
  LZ := 0;
  
  for c := 0 to LLength-1 do
  begin
    LDistance := APoint.Distance(APolygon[c]);
    LPercent := (1 / LMaxDistance) * LDistance;
    LX := LX + (APolygon3D[c].X * LPercent); 
    LY := LY + (APolygon3D[c].Y * LPercent); 
    LZ := LZ + (APolygon3D[c].Z * LPercent); 
  end;

  Result := Vector3D(LX,LY,LZ);
end;

um einen 3D Isometrischen Punkt ins 2D zu berechnen das hier:

Delphi-Quellcode:

function Polar2D(AX,AY,AAngle,ADistance : Double) : TPointF;
begin
  Result.x := (Cos(DegToRad(AAngle)) * ADistance) + AX;
  Result.y := (Sin(DegToRad(AAngle)) * ADistance) + AY;
end;

function IsoToScreen(AVector : TVector3D) : TPointF;
var
  LPoint : TPointF;
begin
  LPoint := PointF(0,0);

  LPoint := Polar2D(LPoint.X, LPoint.Y, 30, AVector.X);
  LPoint := Polar2D(LPoint.X, LPoint.Y, 150, AVector.Y);
  LPoint := Polar2D(LPoint.X, LPoint.Y, 270, AVector.Z);

  Result := LPoint;
end;

Das erstellen der "PixelMatrix"

Delphi-Quellcode:

procedure TPixelBuffer.CreateMatrix(APolygon: TPolygon3D; AFillColor : TAlphaColor);
var
  LBitmap : TBitmap;
  LData : TBitmapData;
  x: Integer;
  y: Integer;
  LX,LY : integer;
  LRect : TRect;
  LCam : TVector3d;
begin
  LBitmap := TBitmap.Create(500,500);
  LBitmap.Canvas.BeginScene();
  LBitmap.Canvas.Fill.Color := AFillColor;
  LBitmap.Canvas.FillPolygon(Polygon3dTo2d(APolygon),1);
  LBitmap.Canvas.EndScene;

  LBitmap.SaveToFile(Random(10).ToString + '.png');

  LBitmap.Map(TMapAccess.Read,LData);
  LRect := PolygonRect(Polygon3Dto2D(APolygon));

  for x := LRect.Left to LRect.Right do
  begin
    for y := LRect.Top to LRect.Bottom do
    begin
      if LData.GetPixel(X,Y) <> $00000000 then
      begin
        LX := X;
        LY := Y;
        Pixels[LX,LY].Color := LData.GetPixel(LX,LY);
        Pixels[LX,LY].Vector := CalculateCoordinate(APolygon,PointF(LX,LY));
        LCam := Vector3D(Pixels[LX,LY].Vector.X-Pixels[LX,LY].Vector.Z,Pixels[LX,LY].Vector.Y-Pixels[LX,LY].Vector.Z,0);
        Pixels[LX,LY].Depth := LCam.Distance(Pixels[LX,LY].Vector); // Hier wird die Tiefe berechnet
      end;
    end;
  end;

  LBitmap.Free;
end;

Und das Rendern:

Delphi-Quellcode:

procedure TRenderer.Render(APolygons: array of TPolygon3D);
var


  c: Integer;
  LBuffer : TPixelBuffer;

  Colors : array of TAlphaColor;

  LBitmap : TBitmap;
  LData : TBitmapData;
  x: Integer;
  y: Integer;

begin
  Colors := [$FFFF0000,$FFFF00FF,$FF00FF00,$FF0000FF];

  for c := 0 to Length(Apolygons)-1 do
  begin
    LBuffer := TPixelBuffer.Create(500,500);
    LBuffer.CreateMatrix(APolygons[c],Colors[c]);
    Buffers.Add(LBuffer);
  end;

  LBitmap := TBitmap.Create(500,500);
  LBitmap.Map(TMapAccess.Write, LData);

  LBuffer := TPixelBuffer.Create(500,500);
  for x := 0 to 499 do // Hier wird noch mal die finale Matrix erstellt
    begin
      for y := 0 to 499 do
      begin
        for c := 0 to Buffers.Count-1 do
        begin
          if (Buffers[c].Pixels[x,y].Depth < Lbuffer.Pixels[x,y].Depth) then // Überprüfung ob der Pixel gezeichnet werden soll oder ob er überdeckt ist
          begin
              Lbuffer.Pixels[x,y].Depth := Buffers[c].Pixels[x,y].Depth;
              Lbuffer.Pixels[x,y].Height := Buffers[c].Pixels[x,y].Height;
              LBuffer.Pixels[x,y].Color :=  Buffers[c].Pixels[x,y].Color;
          end;
        end;
      end;
    end;

  for x := 0 to 499 do
  begin
      for y := 0 to 499 do
      begin
        LData.SetPixel(X,Y,LBuffer.Pixels[X,Y].Color);
      end;
  end;

  LBitmap.SaveToFile('./test.png');
end;

Im anhang sieht man das es auch schon fast funktioniert, jedoch glaube ich das die Tiefenberechnung fehlerhaft ist oder das vielleicht die CalculateCoordinate auch nicht wirklich gut gelöst ist :/
Ich hoffe ich habe mich so ausgedrückt das man mein Anliegen gut versteht, ist schon ziemlich spät und muss nun schlafen sonst raubt mir Delphi wieder mal die ganze Nacht... und den Tag darauf sowieso! :lol:

Edit: Ach ja der code wurde auf die schnelle geschrieben als "proof of concept", im Zeichenprogramm hat der nichts zu suchen :D

Freundliche Grüsse

[Rollo62]

Du hast dir aber viel vorgenommen ...
Am Besten schaust du mal wirklich bei den Profis nach, wie das gemacht wird.

Wenn ich deine Schleifen sehe

Delphi-Quellcode:

 for x := 0 to 499 do // Hier wird noch mal die finale Matrix erstellt
    begin
      for y := 0 to 499 do
      begin
        for c := 0 to Buffers.Count-1 do
        begin

vermute ich mal das es schnell ein Performance und Speicher Problem geben wird, je nachdem wieviele
Ebenen du brauchst.
Deshalb ist Backface culling ja so ein komplexes Thema, und es gibt sicher ein viele mathematische Tricks dazu.

http://myweb.lmu.edu/dondi/share/cg/hsr.pdf
http://www.mttcs.org/Skripte/Pra/Mat...vorlesung6.pdf
http://www.gamedev.net/page/resource...ernative-r1485

Bei deinem Ansatz würde ich mal versuchen statt Pixel, ein sorted Array für jedes Pixel in der Ebene zu benutzen.
Dann sollte nur das erste Element der Arrays gecheckt werden müssen, in welcher Ebene das liegt.
Ob das schneller ist kann ich nicht sagen, aber ich vermute mal das es schon besser ist als
ein Algorithmus der sich mit O^3 skaliert.

Rollo

[Namenloser]

Den Code habe ich jetzt nicht nachvollzogen, aber deine Beschreibung klingt für mich, als hättest du mehr oder weniger Ray Tracing neu erfunden. Vielleicht solltest du komplett auf Ray Tracing setzen, dann kannst du auf die „Zwischen-Bitmaps“ und auf den Z-Buffer verzichten. Dadurch sollte das ganze nicht nur speichereffizienter sondern auch einfacher werden. Doom I und II haben übrigens auch Ray Tracing verwendet.

[P_G]

Such mal nach "Peter Bone" und "Engine3D" (http://www.glorioustrainwrecks.com/m.../engine3d.html). Der hat vor Jahren Backface-Culling und Z-Buffering in eine kleine Delphi-Engine integriert, die allein mit dem Canvas und ohne OpenGL oder DirectX arbeitet. Vielleicht hilft dir das (zu Studienzwecken) weiter.
Auf der oben genannten Seite kann man nicht mehr auf die zip-Datei zugreifen, aber das ganze schwirrt noch im Netz herum - einfach mal suchen... :-D

[HolgerX]

Zitat:

Zitat von P_G (Beitrag 1336520)

Such mal nach "Peter Bone" und "Engine3D" (http://www.glorioustrainwrecks.com/m.../engine3d.html). Der hat vor Jahren Backface-Culling und Z-Buffering in eine kleine Delphi-Engine integriert, die allein mit dem Canvas und ohne OpenGL oder DirectX arbeitet. Vielleicht hilft dir das (zu Studienzwecken) weiter.
Auf der oben genannten Seite kann man nicht mehr auf die zip-Datei zugreifen, aber das ganze schwirrt noch im Netz herum - einfach mal suchen... :-D

Ganz unter auf der Seite befinden sich 'Alternative links:'.
Diese funktionieren ;)

[milos]

Hey,

danke das ihr euch Zeit genommen habt mein Anliegen anzusehen :)

Zitat:

Zitat von Namenloser

Den Code habe ich jetzt nicht nachvollzogen, aber deine Beschreibung klingt für mich, als hättest du mehr oder weniger Ray Tracing neu erfunden. Vielleicht solltest du komplett auf Ray Tracing setzen, dann kannst du auf die „Zwischen-Bitmaps“ und auf den Z-Buffer verzichten. Dadurch sollte das ganze nicht nur speichereffizienter sondern auch einfacher werden. Doom I und II haben übrigens auch Ray Tracing verwendet.

Ja du hast so ziemlich genau Recht (hätte ich auch nicht anders von dir erwartet ;)), ich versuche den Z-Buffer hinzubekommen in dem ich jedes Polygon auf einen Bitmap zeichne und dann die Tiefe jedes gezeichneten Pixels berechne. Nach dem ich dies für alle gemacht habe, zeichne ich die Pixel aller Ebenen auf das "End-Bild" wobei nur die Sichtbaren (anhand der berechneten Tiefe) gezeichnet werden, bzw die nicht sichtbaren überschrieben.

Ich habe mir Ray Tracing angesehen, aber da habe ich wieder ähnliche Probleme mit der Mathematik und werde wieder nachfragen müssen und um das Isometrisch hinzukriegen müsste ich wieder rum experimentieren, da würde ich lieber einfach schnell meine Idee ausprobieren und falls das klappt in meine schon funktionierende Orthogonale Render-Umgebung implementieren :/

Ich glaube ich habe das Problem auch gefunden und zwar liegt es wahrscheinlich an der Berechnung eines Pixels vom 2-Dimensionalen in den 3-Dimensionalen Raum. Das wäre der erste Code-Teil den ich gepostet habe. Die Berechnung stimmt so nicht und muss auf eine andere weise berechnet werden, muss wohl noch ein wenig nachforschen. Und wenn die Berechnung klappt wird der Z-Buffer ziemlich sicher funktionieren. Über jede Hilfe bin ich natürlich sehr dankbar.

Zitat:

Zitat von Rollo62 (Beitrag 1336490)

Du hast dir aber viel vorgenommen ...
Am Besten schaust du mal wirklich bei den Profis nach, wie das gemacht wird.

Wenn ich deine Schleifen sehe

Delphi-Quellcode:

 for x := 0 to 499 do // Hier wird noch mal die finale Matrix erstellt
    begin
      for y := 0 to 499 do
      begin
        for c := 0 to Buffers.Count-1 do
        begin

vermute ich mal das es schnell ein Performance und Speicher Problem geben wird, je nachdem wieviele
Ebenen du brauchst.

Ich bin mir bewusst dass das wie es jetzt ist nicht wirklich gut ist, jedoch hatte ich mit dem Code wie gesagt nur vor zu testen ob die Möglichkeit wie ich es mir erdacht habe wirklich funktioniert. Die 3^for-schleife liesse sich ganz einfach um ein vielfaches schneller machen indem man die 3. mit der 1. tauscht und dann nur noch die tatsächliche 2D Breite und Höhe jeder Ebene durchgeht. Dann könnte ich das Bild noch in mehrere Teilen und mit mehreren Threads arbeiten und das speichern der Pixel auch viel Resourcem freundlicher lösen und so weiter, da ist noch vieles das man am code ganz einfach optimieren kann... Geschätzt sind das bestimmt 80% weniger die das Programm durch Schleifen und Berechnungen muss. Wie gesagt, der Code ist keinesfalls optimiert und nur da um die Theorie zu "beweisen" ;)

Ich glaube auch nicht das ich mir da "zu viel vorgenommen" habe, denn theoretisch sollte es mit der Methode, wie ich es mir so denke, ja eigentlich wirklich einfach sein, sobald die Formeln stimmen.

Zitat:

Zitat von P_G

Deshalb ist Backface culling ja so ein komplexes Thema, und es gibt sicher ein viele mathematische Tricks dazu.

Backface-Culling ist nicht mehr das Problem, das konnte ich eigentlich ziemlich einfach lösen und funktioniert tadellos :)

Zitat:

Zitat von Rollo62 (Beitrag 1336490)

Such mal nach "Peter Bone" und "Engine3D" (http://www.glorioustrainwrecks.com/m.../engine3d.html). Der hat vor Jahren Backface-Culling und Z-Buffering in eine kleine Delphi-Engine integriert, die allein mit dem Canvas und ohne OpenGL oder DirectX arbeitet. Vielleicht hilft dir das (zu Studienzwecken) weiter.
Auf der oben genannten Seite kann man nicht mehr auf die zip-Datei zugreifen, aber das ganze schwirrt noch im Netz herum - einfach mal suchen...

Danke für den Link hab sowas für Delphi nirgends gefunden! :) Werde ich mir ansehen aber ich glaube DAS ist wirklich zu komplex :D Und vorallem ist das leider nicht orthogonal :/

[P_G]

Zitat:

Werde ich mir ansehen aber ich glaube DAS ist wirklich zu komplex :D Und vorallem ist das leider nicht orthogonal

Interessanterweise ist es gar nicht sonderlich komplex. Der Code ist sehr sauber und vorbildlich. Orthogonalität kannst du leicht erzeugen, indem du bei der Berechnung der Screen-Koordinaten den Z-Wert ignorierst. Der ist nur wichtig bei der Berechnung der Reihenfolge, in denen die Polygone zu zeichnen sind.

[Memnarch]

Fürs Backfaceculling:
Normale des Polygons kalkulieren, falls Negativ fällts weg

Z-Buffering:

Ich versteh nicht wieso du immer vor und zurück rechnest.
Du brauchst mehrere matrizen. Minimal:
ObjectPositionMatrix
WorldPositionMatrix
ProjectionMatrix

Die ObjectMatrix*Worldmatrix*Projectionsmatrix; Letztere wird dabei so gefüttert, dass sie eine Isometrische Ansicht erzeugt(wobei ich die Werte dafür nochmal nachschlagen müsste). Dann kannst du später die Z-Werte der Vertices über das Polygon im Screenspace interpolieren und hast pro Pixel die normalisierte Tiefe(0-1). Dann kannst du die Z-Werte in einen ZBuffer schreiben und für jeden Pixel gucken ob der neue ZWert näher ist, bevor du zeichnest.

Ich empfehle DRINGENST(!):
Bau dir eine Unit für Matrizen und deren Mathematik. Das willst du nicht im ganzen Source verstreut haben. Hab mir für meine Softwarerenderer damals diese Unit geschrieben:

https://github.com/Memnarch/Software...ter/Math3D.pas

Wobei ich die heute anders schreiben würde, mehr mit Records und operatorüberladungen.

[Namenloser]

Zitat:

Zitat von milos (Beitrag 1336558)

Ich habe mir Ray Tracing angesehen, aber da habe ich wieder ähnliche Probleme mit der Mathematik und werde wieder nachfragen müssen und um das Isometrisch hinzukriegen müsste ich wieder rum experimentieren,

Das sollte der leichteste Teil sein. Der einzige Unterschied ist, dass bei der isometrischen Ansicht (orthografische Projektion) die Strahlen, die von den Pixeln ausgehen, parallel verlaufen, statt einen "Kegel" zu bilden wie bei der perspektivischen Projektion. Das macht es im Grunde sogar noch einfacher.

Ansonsten kann ich mich nur dem Ratschlag von Memnarch anschließen.

[Medium]

Ich komme auch noch dazu und unterstütze die Aussage. Sehr sogar. Alles andere schlägt einem wenig später rücklings mitten ins Gesicht. Ich hab das getestet! :stupid: