Autor Beitrag
Nightwalker_Z
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 33



BeitragVerfasst: Fr 21.11.03 15:55 
Hallöchen..

Ich brauche nen wirklich effizienten Algorithmus um Dreiecke auf ein Canvas zu zeichnen. Die Methode Polygon(Punkte) darf ich nicht verwenden ... (und ich bezweifle, dass diese Methode effizient ist :-)

Wozu das ganze ?
Muss ne 3D Anwendung schreiben (aber nix mit OpenGL oder so ... alles von Hand)

Also ... hat mir jemand ne Lösung ???

Grüsse
Nightwalker_Z
blackbirdXXX

ontopic starontopic starhalf ontopic starofftopic starofftopic starofftopic starofftopic starofftopic star
Beiträge: 1077
Erhaltene Danke: 1

Ubuntu Dapper

BeitragVerfasst: Fr 21.11.03 16:11 
Wieso darfst du Polygon() nicht verwenden? Sonst kannst du es mit LineTo und MoveTo machen. Ist aber anstrengender. Wenn du willst kannst du ja eine Funktion schreiben.

_________________
Klein, schwarz und ärgert Techniker? Jumper!
Nightwalker_Z Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 33



BeitragVerfasst: Fr 21.11.03 16:20 
Ähm... das ist mir schon klar, dass Canvas mir noch andere Zeichenroutinen bereitstellt.
Es geht aber um nen Algorithmus wie ich das händisch mache...
Ich geb mal ein Beispiel:

ausblenden Quelltext
1:
2:
3:
4:
5:
6:
7:
procedure Dreieck(canv:TCanvas; x1,y1,x2,y2,x3,y3:integer; Farbe:TColor)
Begin

  Voll viel Code
  Bitte füllen

end;


sodele ... das Dreieck soll in die Variable "canv" geschrieben werden...
Ich brauch was, das zwischen Begin ... und End kommt :roll:

Klar kann ich auch was "hinklatschen" das Funktioniert, aber das ist ja nicht Sinn & Zweck der Übung. Ich brauch nen optimalen Algorithmus dafür (Zauberwort: Performance). [Bemerkung: Bitte jetzt keinen Diskussion a la "Delphi and Performance" anfangen :lol: ]

Da ich keine Lust hab mir den Algorithmus aus den Fingern zu saugen, frag ich lieber hier. Gibt bestimmt ein paar Leutz, die das schon öfters gemacht haben :-)


Grüssle
Nightwalker_Z
blackbirdXXX

ontopic starontopic starhalf ontopic starofftopic starofftopic starofftopic starofftopic starofftopic star
Beiträge: 1077
Erhaltene Danke: 1

Ubuntu Dapper

BeitragVerfasst: Fr 21.11.03 16:25 
Ich nehme mal an dass du das für die Schule machen musst. Ich gebe dir einen Tipp.

mach
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
canc.PenColor(Farbe) //Setzt die Zeichenfarbe auf die Variable Farbe

canv.MoveTo(x1,y1); //Setzt Zeichenstift nach x1,y1

canv.LineTo(x2,y2); //Zieht von Ausgangspunkt eine Linie nach x2,y2


Wenn du immer noch Probleme hast dann poste hier was genau nicht geht.

_________________
Klein, schwarz und ärgert Techniker? Jumper!
Nightwalker_Z Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 33



BeitragVerfasst: Fr 21.11.03 16:39 
:lol:
MannoMann ... das wird eine Geburt :!:

Wie gesagt... ich kenne die ganzen Routinen wie LineTo, MoveTo ... etc...
Das ist doch alles gar kein Problem ....
Also ... ich nenne mal ein Beispiel *gg* (mal wieder)

Also es gibt ja die Anweisung: Paintbox1.Canvas.Lineto(30,50);
sprich es wird eine Linie von der letztes Position des Stifts nach 30,50 gezeichnet.

Jetzt brauch ich aber eine Routine um ein gefülltes Dreieck auf ein Canvas zu zeichnen. (ich denk du bist dir der Problematik gar nicht bewusst, die dahinter steckt) Mit ein paar LinesTo und MovesTo ist das nicht gegessen.
Ich zeig Dir mal nen Algo zum Dreieckzeichnen:

ausblenden volle Höhe Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
procedure TDreieck.Zeichnen(canv:Tcanvas;ax,ay,bx,by,cx,cy:integer;Farbe:TColor);
var
  y             : integer;       { Schleifenvariable für die Scanzeile  }
  x1,x2,x3      : real;          { x-Werte für Scanline-Algorithmus     }
  m1,m2,m3      : real;          { Increments für die x-Werte           }
begin
  Canv.Pen.Color:=Farbe;
  Canv.Brush.Color:=Farbe;
  x1  := ax;                                    { x-Wert Linie A -> B   }
  x2  := bx;                                    { x-Wert Linie B -> C   }
  x3  := ax;                                    { x-Wert Linie A -> C   }

  m1 := (bx-ax) / (by-ay);                      { Increments   A -> B   }
  m2 := (bx-cx) / (by-cy);                      { Increments   B -> C   }
  m3 := (cx-ax) / (cy-ay);                      { Increments   A -> C   }

  for y := ay to by-1 do                        { erste Teilfläche      }
    begin
      Canv.MoveTo(round(x1), y);
      Canv.LineTo(round(x3), y);
//      Line (round(x1), y, round(x3), y, color); { horiz. Linie          }
      x1 := x1 + m1;
      x3 := x3 + m3
    end;

    for y := by to cy do                          { zweite Teilfläche     }
    begin
      Canv.MoveTo(round(x2), y);
      Canv.LineTo(round(x3), y);
//    Line (round(x2), y, round(x3), y, color); { horiz. Linie          }
      x2 := x2 + m2;
      x3 := x3 + m3
    end
end;


stör dich nicht an dem TDreieck... ist nur ne selbst erstellte Klasse.
Dieser Algorithmus ist aber ziemlich schlampig und nicht geeignet für beliebig kleine Dreiecke....
(wie ich im letzten Beitrag schon gesagt hab - so würde das aussehen, wenn man den Code "hinklatscht")

Es gibt doch bestimmt noch elegantere und vor allem performantere Lösungen.... Leute aus dem 3D Bereich, die eigene Engines geschrieben haben dürften das doch kennen :wink:

P.S.: Schulzeit liegt laaaaaaaaaange hinter mir :-)
blackbirdXXX

ontopic starontopic starhalf ontopic starofftopic starofftopic starofftopic starofftopic starofftopic star
Beiträge: 1077
Erhaltene Danke: 1

Ubuntu Dapper

BeitragVerfasst: Fr 21.11.03 18:52 
Ok. Hab nicht gewusst das du das Dreieck ausfüllen musst. Hast nichts davon geschrieben. Das macht das natürlich schwerer.

_________________
Klein, schwarz und ärgert Techniker? Jumper!
Nightwalker_Z Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 33



BeitragVerfasst: Fr 21.11.03 19:27 
nochmal LOL :lol:
Dann war ich ja die ganze Zeit von mir selber genervt *gg*
Wie konnte ich nur das Detail mit den Füllen vergessen :oops:

Ich hab aber auch schon die Lösung:
Den Algo den ich oben beschrieben hab ist schon richtig....

Ich nehme folgende Aussage von mir also zurück:
Zitat:
Dieser Algorithmus ist aber ziemlich schlampig und nicht geeignet für beliebig kleine Dreiecke....


AUSSER !!! :

Bitte die y-Werte sortieren !!!!
d.h. ay<=by<=cy (ay muss der kleinste - cy der grösste Wert sein)
sonst klappt die Sache nicht...

zudem muss die Division durch 0 vermieden werden:

m1 := (bx-ax) / (by-ay);
es muss geprüft werden ob z.B. by-ay =0 ist !!!!


Sodele ... nachdem ich nachgelesen habe, ist das der optimale Algo für
gefüllte Dreiecke ..... (also viel heisse Luft um nix :-) )


:arrow: Wenigstens gibts jetzt in der Suchfunktion auch nen Eintrag darüber :wink:


Grüsse
Nightwalker_Z
Nightwalker_Z Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 33



BeitragVerfasst: Fr 21.11.03 21:16 
Noch ein Nachtrag .... für die Nachwelt und für die, bei denen das Thema vielleicht noch interessant werden könnte. :idea:

Hab jetzt alles fertig Implementiert und auch mal ein paar Tests durchgeführt:

Man kann das Dreieck ja auch mit Canvas.Polygon zeichnen....

Beim vergleich zwischen der fertigen Methode Canvas.Polygon und der manuell erstellten (siehe Code oben) gibt es Performancetechnisch fast keine Unterschiede ....
(Test mit nem Quadrat - zusammengesetzt aus zwei Dreiecken)
Im Endresultat macht das nicht mal 2 FPS aus :lol:

Deshalb kann man (meiner Meinung nach) gertrost Faul sein und sich auf die
Integrierten Routinen in Delphi verlassen *gg*

Grüsse
Nightwalker_Z
obbschtkuche
Gast
Erhaltene Danke: 1



BeitragVerfasst: Fr 21.11.03 22:17 
Nightwalker_Z hat folgendes geschrieben:
Deshalb kann man (meiner Meinung nach) gertrost Faul sein und sich auf die
Integrierten Routinen in Delphi verlassen *gg*


*hüstel* Delphi? Das ist eine integrierte Fkt der GDI->von Windows. Und wenn man sich darauf nicht verlassen könnte... ;)

Bevor jetzt irgendwer kommt und sagt "nänä, das ist doch TCanvas": das ist mir auch klar, aber es wird ja im Prinzip nur windows.polygon aufgerufen.
Nightwalker_Z Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 33



BeitragVerfasst: Sa 22.11.03 00:31 
Was willst du uns jetzt sagen ?

zumindest klappt es :wink:
du musst auch den Arbeitslohn zählen ... zwei Zeilen vs. 50 ... oder so....
von der Performance ... (für Delphi Verhältnisse) ist es auch ansehnlich!!!

Naja .... die ganz harten können mir ja auch ne DLL in Assembler programmieren :twisted:

Gottogottogott

(naja ... wenn ich meine jetztige MFC Vorlesung als Referenz nehme:
4 Stunden für GUI + Finger wund !!! -> MFC
1 Stunde und Maus kaputt -> Delphi


--> 3Ghz oh Wunder !!! Man merkt ja gar nix

naja ... schönes Wochenende + Grüsse an alle Kommandozeilenfreaks
Nightwalker_Z
obbschtkuche
Gast
Erhaltene Danke: 1



BeitragVerfasst: Sa 22.11.03 00:35 
Ich will damit sagen, dass es schlecht sein kann, dass eins wesentlich schneller ist als das andere. Ich hätte sogar eher damit gerechnet dass Polygon schneller ist (ich habe es nicht ausprobiert)

Nightwalker_Z hat folgendes geschrieben:
Die Methode Polygon(Punkte) darf ich nicht verwenden ... (und ich bezweifle, dass diese Methode effizient ist


Dann ist die Frage, warum ein Haufen MoveTo&LineTos schneller sein sollten :roll: