Hidden-Lines-Algorithmus

[Behrendt]

Hallo Leute!
Im Zuge meiner Informatik-Facharbeit Jgst. 12 habe ich die Aufgabe bekommen mit Delphi den Hidden-Lines-Algorithmus zu programmieren. Als ich das Thema bekommen habe, war ich erstmal etwas perplex, da wir in Delphi zuvor nie viel mehr als ein paar simple Canvas-Spielereien gemachth haben. Aber ich habe jetzt mal angefangen mich dieser Thematik anzunehmen. Erstmal habe ich die Umwandlung von dreidimensionalen Koordinaten auf 2-dimensionale Koordinaten geschrieben. Desweiteren habe ich schon mal ein bisschen mit Verbindungen der Punkte rumgespielt, aber ich denke die ganz normale LineTo-Methode ist nicht sehr geeignet für das was ich vorhabe oder? Da wäre ja viel zu viel Rechenaufwand mit verbunden. Es wäre sicherlich einfacher die Punkte bzw. die zu zeichnenden Polygone vorzusotieren und dann nacheinander übermalen zu lassen. Geritten von dieser Idee habe ich mir mal den Polygon-Befehl angeguckt, aber steige da noch nicht ganz durch, da ich ja dafür irgendwie ein TPoint-Array benutzen muss. Aber über die globale Deklarieung des selbigen komme ich auch garnicht raus. Das Handbuch bzw. die Hilfe gibt da auch nicht sehr viel her. Ich hänge euch mal meinen Code an, ich hoffe ihr steigt da so weit durch, ist bestimmt ein Horror für euch, denn ich bin ungeübt im programmieren muss ich sagen! Bin für alle Tipps dankbar, nicht nur die zum Polygon-Zeichnen, sondern auch was Lesbarkeit, Redundanz, etc. angeht könnt ihr kritisieren was das Zeug hält!

Delphi-Quellcode:

var
  Form1: TForm1;
  x,xp,y,yp,z,d,h,a:integer;
  Ko_X:array [1..100] of Real;
  Ko_Y:array [1..100] of Real;
  Ko_Z:array [1..100] of Real;
  Ko_Xp:array [1..100] of Real;
  Ko_Yp:array [1..100] of Real;
implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
var i,j:integer;
begin
a:=Trunc(Image1.Width/2); // Verschiebt den Ursprung des Koordinatensystems auf der Leinwand
d:=StrToInt(Edit1.Text); // Beschreibt den Abstand des Betrachters zur Bildebene
h:=Trunc(Image1.Height/2); // Verschiebt den Ursprung des Koordinatensystems auf der Leinwand

// Koordinaten der Punkte des Würfels
Ko_X[1]:=(100);
Ko_Y[1]:=(100);
Ko_Z[1]:=(100);
Ko_X[2]:=(100);
Ko_Y[2]:=(100);
Ko_Z[2]:=(200);
Ko_X[3]:=(200);
Ko_Y[3]:=(100);
Ko_Z[3]:=(200);
Ko_X[4]:=(200);
Ko_Y[4]:=(100);
Ko_Z[4]:=(100);
Ko_X[5]:=(100);
Ko_Y[5]:=(200);
Ko_Z[5]:=(100);
Ko_X[6]:=(100);
Ko_Y[6]:=(200);
Ko_Z[6]:=(200);
Ko_X[7]:=(200);
Ko_Y[7]:=(200);
Ko_Z[7]:=(200);
Ko_X[8]:=(200);
Ko_Y[8]:=(200);
Ko_Z[8]:=(100);

with Image1.Canvas do
  begin
  { Einstellen der Farbe, in der gezeichnet wird }
  Brush.Color := clblack;
  Pen.Color := clblack;
  { Umrechnen der gegebenen 3-dimensionalen Koordinaten
    in 2-dimensionale Koordinaten auf der Bildebene }
  for i:= 1 to 8 do
    begin
      Ko_Xp[i]:=a+(d/(d+Ko_Z[i]))*Ko_X[i];
      Ko_Yp[i]:=h+(d/(d+Ko_Z[i]))*Ko_Y[i];
    end;
  i:=1;

  // Kanten
  for j:= 1 to 8 do
    begin
      moveto(Trunc(Ko_Xp[i]),Trunc(Ko_Yp[i]));
      if i=4 then i:=0;
      if i=8 then i:=4;
      lineto(Trunc(Ko_Xp[i+1]),Trunc(Ko_Yp[i+1]));
      if i=0 then i:=5;
      i:=i+1;
    end;
  end;
end;

procedure TForm1.Button2Click(Sender: TObject);
// Löschen der Bildebene
begin
  with Image1.Canvas do
    begin
    Brush.Color := clwhite;
    Pen.Color := clwhite;
    rectangle(0,0,Trunc(Image1.Width),Trunc(Image1.Height));
    end;
end;


end.

MfG
Behrendt

[Zacherl]

Was mir spontan auffällt sind die vielen Trunc() Befehle an eigentlich unnötigen Stellen. Koordinaten werden sowieso immer als ganze Zahlen angegeben, von daher musst du sie nicht erst durch Trunc jagen. Das gillt sowohl für MoveTo, LineTo, RectAngle sowie auch für Image.Width / Height, etc

Die einzige Trunc Stelle die sinnvoll ist wäre diese:
Trunc(Image1.Width/2) Aber selbst hier würde ich ein
Image1.Width div 2 bevorzugen.

[Behrendt]

Ohne Trunc klappt es aber nicht. Dann krieg ich immer "Interger nicht kompatibel zu Extended" als Fehlermeldung beim kompilieren. Was ja auch logisch ist, die LineTo Befehle können ja nur Integer Zahlen sein weil ganze Pixel, aber die Berechnungen habe ich extra in Real gemacht, damits da genauer bliebt. Ob das dann aber wieder notwendig ist weiß ich auch nicht, aber sicher ist sicher.

[Kroko1999]

(a) in Button2Click ist das Trunc unnötig
(b) Width shr 1; ist noch schneller als div
(c) zu deinem Problem mal google bzw. Tiefensortierung als Stichwort

[Zacherl]

Wieso bitte ist in Button2 das Trunc notwendig?

[Behrendt]

Ok stimmt, das habe ich übersehen, bei den Buttons kann und werde ich es dann entfernen. Mit den Koordinaten meinte ich die Koordinaten der Punkte im Raum, da hab ich für die Umrechnung Real gewählt.
Und wie ist das mit dem Polygon - geht das nur über TPoint-Array? Wenn ja wie funktionieren diese? Meine Versuche haben da bisher kläglich fehlgeschlagen :/

[Kroko1999]

(A) Mal die Hilfe gelesen

Zitat:

Zeichnet eine Folge von Linien auf der Zeichenfläche. Dazu werden die in Points übergebenen Punkte durch Linien miteinander verbunden. Zuletzt wird die Form durch eine Linie zwischen dem Letzten und dem ersten Punkt geschlossen.

Klasse
TCanvas

Syntax


[Delphi] procedure Polygon(var Points: array of TPoint);


Beschreibung
Mit der Methode Polygon können Sie unter Verwendung des aktuellen Stifts eine in sich geschlossene, vieleckige Form zeichnen. Die fertiggestellte Form wird mit den aktuell für Brush festgelegten Parametern gefüllt.

Der Parameter Points ist ein Array mit den Scheitelpunkten des Polygons.

, also geht es nur so
(B) Tipp: Wandle den array of "Float"-points in ein Array of "Integer"-Points einma komplett um und zeichne dann dein(e) Polygon(e)
(C) verwende statt Trunc Round(wird genauer)!

[mimi]

Delphi-Quellcode:

Ko_X:array [1..100] of Real;
  Ko_Y:array [1..100] of Real;
  Ko_Z:array [1..100] of Real;
  Ko_Xp:array [1..100] of Real;
  Ko_Yp:array [1..100] of Real;

Das könntest du auch noch optimieren:

Delphi-Quellcode:

  TMyPoint = record
    y,z:Real
  end;

  ko, koP:array[100] of TMyPoint

Ich hoffe du kannst damit was anfangen.

dann kannst du mit: ko[index].y:=wert z.b. auf einzelne Fehler zurückgreifen.

Ein Record sammelt einfach nur Variablen. Damit ersparst du dir viel Abreit !

[Behrendt]

Da bin ich wieder. Ich habe mir mal die Tipps hier zu Gemüte geführt und dann heute etwas optimierungsarbeit geleistet. Ist zwar jetzt etwas mehr Code glaube ich, aber viel angenehmer zu lesen und leichter zu handhaben. Desweiteren denke ich, dass das erlernen des records ziemlich gut war für mich.

Delphi-Quellcode:

unit m_beta02;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, ExtCtrls;

type
  TPoly = record
    Punkt1,Punkt2,Punkt3,Punkt4: TPoint;
  end;

type
  TMyPoint = record
    X_Koordinate,Y_Koordinate,Z_Koordinate: Real;
  end;

  type
  TForm1 = class(TForm)
    Image1: TImage;
    Button1: TButton;
    Edit1: TEdit;
    Label1: TLabel;
    Button2: TButton;
    procedure Button2Click(Sender: TObject);
    procedure Button1Click(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;
  Punkt:array [1..100] of TMyPoint;
  Ko_B:array [1..100] of TPoint;
  poly:array [1..100] of TPoly;
implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
var i,d,h,a:integer;
begin
a:=Image1.Width div 2; // Verschiebt den Ursprung des Koordinatensystems auf der Leinwand
d:=StrToInt(Edit1.Text); // Beschreibt den Abstand des Betrachters zur Bildebene
h:=Image1.Height div 2; // Verschiebt den Ursprung des Koordinatensystems auf der Leinwand

// Koordinaten der Punkte des Würfels
with Punkt[1] do
  begin
    X_Koordinate:= (100);
    Y_Koordinate:= (100);
    Z_Koordinate:= (100);
  end;

with Punkt[2] do
  begin
    X_Koordinate:= (100);
    Y_Koordinate:= (100);
    Z_Koordinate:= (200);
  end;

with Punkt[3] do
  begin
    X_Koordinate:= (200);
    Y_Koordinate:= (100);
    Z_Koordinate:= (200);
  end;

with Punkt[4] do
  begin
    X_Koordinate:= (200);
    Y_Koordinate:= (100);
    Z_Koordinate:= (100);
  end;

with Punkt[5] do
  begin
    X_Koordinate:= (100);
    Y_Koordinate:= (200);
    Z_Koordinate:= (100);
  end;

with Punkt[6] do
  begin
    X_Koordinate:= (100);
    Y_Koordinate:= (200);
    Z_Koordinate:= (200);
  end;

with Punkt[7] do
  begin
    X_Koordinate:= (200);
    Y_Koordinate:= (200);
    Z_Koordinate:= (200);
  end;

with Punkt[8] do
  begin
    X_Koordinate:= (200);
    Y_Koordinate:= (200);
    Z_Koordinate:= (100);
  end;

{ Umrechnen der gegebenen 3-dimensionalen Koordinaten
  in 2-dimensionale Koordinaten auf der Bildebene }

  for i:= 1 to 8 do
    begin
      Ko_B[i]:=Point
                ( round(a+(d/(d+Punkt[i].Z_Koordinate))*Punkt[i].X_Koordinate),
                  round(h+(d/(d+Punkt[i].Z_Koordinate))*Punkt[i].Y_Koordinate));
    end;
{ Definition der Polygone }

with poly[1] do
  begin
    Punkt1:= Ko_B[2];
    Punkt2:= Ko_B[3];
    Punkt3:= Ko_B[7];
    Punkt4:= Ko_B[6];
  end;

with poly[2] do
  begin
    Punkt1:= Ko_B[5];
    Punkt2:= Ko_B[6];
    Punkt3:= Ko_B[7];
    Punkt4:= Ko_B[8];
  end;

with poly[3] do
  begin
    Punkt1:= Ko_B[1];
    Punkt2:= Ko_B[2];
    Punkt3:= Ko_B[6];
    Punkt4:= Ko_B[5];
  end;

with poly[4] do
  begin
    Punkt1:= Ko_B[3];
    Punkt2:= Ko_B[4];
    Punkt3:= Ko_B[8];
    Punkt4:= Ko_B[7];
  end;

with poly[5] do
  begin
    Punkt1:= Ko_B[1];
    Punkt2:= Ko_B[4];
    Punkt3:= Ko_B[8];
    Punkt4:= Ko_B[5];
  end;

with poly[6] do
  begin
    Punkt1:= Ko_B[1];
    Punkt2:= Ko_B[2];
    Punkt3:= Ko_B[3];
    Punkt4:= Ko_B[4];
  end;


{ Zeichnen des Objektes }

with Image1.Canvas do
  begin
  { Einstellen der Farbe, in der gezeichnet wird }
    Brush.Color := clwhite;
    Pen.Color := clblack;
  { Zeichnen der Polygone in richtiger Reihenfolge }
    for i:= 1 to high(poly) do
    Polygon([poly[i].Punkt1,poly[i].Punkt2,poly[i].Punkt3,poly[i].Punkt4]);
 end;
end;

procedure TForm1.Button2Click(Sender: TObject);

// Löschen der Bildebene

begin
  with Image1.Canvas do
    begin
      Brush.Color := clwhite;
      Pen.Color := clwhite;
      rectangle(0,0,Image1.Width,Image1.Height);
    end;
end;


end.

So wie das Programm jetzt ist kriege ich schon nen anständigen Würfel gezeichnet. Mehr als ich mir zu Anfang hätte erträumen lassen. Allerdings steckt dahinter ja noch kein Algorithmus. Also muss ich es irgendwie hinkriegen, dass jedem zu zeichnendem Polygon eine gewisse Priorität zugewiesen wird, so dass ich diese dann sortieren kann und in einer Schleife zeichnen lassen kann. Ich denke so Sachen wie Z-Buffer sind hierfür zu komplex oder? Ich lese mir gerade etwas zur erwähnten Tiefensortierung durch und da wird schon mit Normalen gearbeitet. Was meint ihr? Sind diese Sachen notwendig, und wenn ja überhaupt machbar? Habe die Abgabe am 10.März!
MfG
Christian

[mimi]

Also der code ist schonmal nicht schlecht, Aber du kannst ihn weiter verkürzten

Delphi-Quellcode:

with poly[6] do
  begin
    Punkt1:= Ko_B[1];
    Punkt2:= Ko_B[2];
    Punkt3:= Ko_B[3];
    Punkt4:= Ko_B[4];
  end;

Das wiederholst du acht mal. Schau mal nach was Funktionen bzw. Proceduren sind. Dann könnte man das so zusammen fasssen:

Delphi-Quellcode:

procedure From1.SetPoly(const Index, index1, index2, index3, index4:Integer);
begin
  poly[index].Punkt1:= Ko_B[index1];
  poly[index].Punkt2:= Ko_B[index2];
  poly[index].Punkt3:= Ko_B[index3];
  poly[index].Punkt4:= Ko_B[index4];
end; //  From1.SetPoly

// aufgerufen könnte diese Procedure so werden:
SetPoly(1,2,3,7,6);

ich hoffe das Prinzip ist dir Klar...
Hier findest du noch mehr Interessante sachen:
http://www.delphi-treff.de/tutorials/