Best Of Algorithen

[der ist auch toll]

http://callplayer.wz.cz/data/dtmf_decoder_1_00/src/goertzel.c

[rapso]

troll schrieb:

Meine ebenfalls.

sehr ueberzeugend ..emm ich meinte amuesant.

raytracing ist nun wirklich nicht kompliziert, dafür benötigt man nur gutes grundwissen in geometrie und die sache ist gegessen.

Da merkt man ja schon, dass du keine Ahnung von der Materie hast, wenn deine Vorstellung von einem Raytracer bei Geometrie aufhört.
Wenn man einen echten Raytracer mit Beschleunigungsstrukturen, komplexen Beleuchtungssystem (nicht nur Mirror Reflection ) , Softshadows, Kaustiken, Nebel, Refraktion etc. haben will, wird es recht fix sehr komplex.

lass es lieber mit deinem getrolle, jeder mit auch nur nem hauch ahnung davon weiss dass du hier nur provozierst.
naja, vielleicht ist es ja auch fuer dich wirklich schwer sowas zu implementieren... aber dann hat es nichts mit der komplexitaet von raytracing zu tun.

[sampler]

rapso schrieb:

troll schrieb:

Meine ebenfalls.

sehr ueberzeugend ..emm ich meinte amuesant.

raytracing ist nun wirklich nicht kompliziert, dafür benötigt man nur gutes grundwissen in geometrie und die sache ist gegessen.

Da merkt man ja schon, dass du keine Ahnung von der Materie hast, wenn deine Vorstellung von einem Raytracer bei Geometrie aufhört.
Wenn man einen echten Raytracer mit Beschleunigungsstrukturen, komplexen Beleuchtungssystem (nicht nur Mirror Reflection ) , Softshadows, Kaustiken, Nebel, Refraktion etc. haben will, wird es recht fix sehr komplex.

lass es lieber mit deinem getrolle, jeder mit auch nur nem hauch ahnung davon weiss dass du hier nur provozierst.
naja, vielleicht ist es ja auch fuer dich wirklich schwer sowas zu implementieren... aber dann hat es nichts mit der komplexitaet von raytracing zu tun.

Kann ja auch nix dafür, wenn du bis jetzt nur Raytracer auf Kindergarten-Niveau geschrieben hast.

Ansonsten zeigst du nur mal wieder deine arrogante und uneinsichtige Art (die du ja schon oft als Mod im Grafikforum zur Schau gestellt hast)

[rapso]

troll schrieb:

...blub...

*hehehe* also troll versagst du voll und ganz, sehr putzig

[undsowasistmod]

rapso schrieb:

troll schrieb:

...blub...

*hehehe* also troll versagst du voll und ganz, sehr putzig

Wie oft wiederholst du noch, dass dir nichts mehr einfällt? Mittlerweile dürften genügend Leute dein kindisches Verhalten bemerkt haben.

[Gregor]

Raytracing - oder als vereinfachte Variante Raycasting - finde ich insofern interessant, als diese Algorithmen letztendlich das Resultat einer ganz systematischen und geradlinigen mathematischen bzw. physikalischen Modellierung des Problembereichs sind. Ein super Beispiel dafür, wie einem Hochschulwissen aus verschiedenen Bereichen ein systematisches Vorgehen ermöglicht (falls es darum geht, einen solchen Algorithmus zu entwickeln). Aber auch was das Verständnis eines solchen Algorithmus betrifft, hilft einem hier entsprechendes Wissen weiter.

Ich würde diese Algorithmen allerdings schon als etwas zu speziell ansehen, um sie in einem generellen Algorithmenthread als das Non-Plus-Ultra zu loben. Diese Algorithmen haben IMHO ein relativ kleines Anwendungsgebiet. Für die meisten Leute sind sie also völlig uninteressant.

[rapso]

undsowasistmod schrieb:

rapso schrieb:

troll schrieb:

...blub...

*hehehe* also troll versagst du voll und ganz, sehr putzig

Wie oft wiederholst du noch, dass dir nichts mehr einfällt? Mittlerweile dürften genügend Leute dein kindisches Verhalten bemerkt haben.

Wie drollig, da hab ich sogar nen troll vom thema abgebracht

@Topic&Gregor
Viele Algorithmen sind wegen ihrer einfachheit und maechtigkeit so schoen. ich finde das Trifft bei Raytracing sehr zu, denn wie du sagtest, reicht schulwissen um sowas zu implementieren (nicht umsonst schreiben soviele leute dann auch nen raytracer). schnittpunkte, reflektionen und ein bisschen blending und schon kann man (sofern man die zeit hat) super aussehende dinge produzieren, so ein feedback haben nicht viele algorithmen.

ich finde wavelettransform dennoch den schoeneren algo

[sampler]

Schön, dass du mich bestätigst. Für dich ist Raytracing ein bißchen Schnittest, Reflektionen und Blending => ROFL.

[Justso]

sampler schrieb:

Schön, dass du mich bestätigst. Für dich ist Raytracing ein bißchen Schnittest, Reflektionen und Blending => ROFL.

Das ist es ja auch, auf dieser Basis funktioniert der ganze Algorithmus, mehr brauchst du nicht zum Raytracen. Alles Zusätzliche ist ein netter Zusatz wie man es bei jedem anderen Algorithmus auch machen kann.

Vielleicht solltest du dir einfach durchlesen wie man Algorithmus definiert.

Unter einem Algorithmus versteht man allgemein eine genau definierte Handlungsvorschrift zur Lösung eines Problems oder einer bestimmten Art von Problemen in endlich vielen Schritten.

Entsprechend einfach ist die Definition von Raytracing

Raytracing (dt. Strahlenverfolgung, in englischer Schreibweise meist ray tracing, seltener ray shooting) ist ein auf der Aussendung von Strahlen basierender Algorithmus zur Verdeckungsberechnung, also zur Ermittlung der Sichtbarkeit von dreidimensionalen Objekten von einem bestimmten Punkt im Raum aus. Ebenfalls mit Raytracing bezeichnet man mehrere Erweiterungen dieses grundlegenden Verfahrens, die den weiteren Weg von Strahlen nach dem Auftreffen auf Oberflächen berechnen.

Beschleunigungsstrukturen und pipapo sind dabei nicht Teil der Definition, genausowenig wie beim Binärsuchealgorithmus die Beschleunigunsstrukturen eine Rolle spielen.

Vermisch also nicht Implementierungsdetails mit den eigentlichen Algorithmen.

[sampler]

Justso schrieb:

sampler schrieb:

Schön, dass du mich bestätigst. Für dich ist Raytracing ein bißchen Schnittest, Reflektionen und Blending => ROFL.

Das ist es ja auch, auf dieser Basis funktioniert der ganze Algorithmus, mehr brauchst du nicht zum Raytracen. Alles Zusätzliche ist ein netter Zusatz wie man es bei jedem anderen Algorithmus auch machen kann.

Vielleicht solltest du dir einfach durchlesen wie man Algorithmus definiert.

Unter einem Algorithmus versteht man allgemein eine genau definierte Handlungsvorschrift zur Lösung eines Problems oder einer bestimmten Art von Problemen in endlich vielen Schritten.

Entsprechend einfach ist die Definition von Raytracing

Raytracing (dt. Strahlenverfolgung, in englischer Schreibweise meist ray tracing, seltener ray shooting) ist ein auf der Aussendung von Strahlen basierender Algorithmus zur Verdeckungsberechnung, also zur Ermittlung der Sichtbarkeit von dreidimensionalen Objekten von einem bestimmten Punkt im Raum aus. Ebenfalls mit Raytracing bezeichnet man mehrere Erweiterungen dieses grundlegenden Verfahrens, die den weiteren Weg von Strahlen nach dem Auftreffen auf Oberflächen berechnen.

Beschleunigungsstrukturen und pipapo sind dabei nicht Teil der Definition, genausowenig wie beim Binärsuchealgorithmus die Beschleunigunsstrukturen eine Rolle spielen.

Vermisch also nicht Implementierungsdetails mit den eigentlichen Algorithmen.

Dem kann ich zustimmen. Der REINE KERN eines Raytracers ist in der Tat simpel. Aber in einem echten Raytracer (eben etwas, das wirklich gute Bilder erzeugt) steckt beliebig komplexe Mathematik (alleine an unserer cg Fakultät gibt es aktuell 2 Doktorarbeiten).
Mich hat einfach rapsos wiederholt arrogante Art genervt.

[Justso]

sampler schrieb:

Dem kann ich zustimmen. Der REINE KERN eines Raytracers ist in der Tat simpel.

Darum geht es bei einem Algorithmus. Wie komplex du es implementierst hat dann wohl kaum noch mit der Definition zu tun.

Aber in einem echten Raytracer (eben etwas, das wirklich gute Bilder erzeugt) steckt beliebig komplexe Mathematik (alleine an unserer cg Fakultät gibt es aktuell 2 Doktorarbeiten).

Hat weniger mit Mathematik zu tun, die ist Simpel. Strahl verfolgen, mittels Schnittpunkten, Reflektionen und Refraktionen und adequatem Blenden.
Mehr ist da wirklich nicht, Optimierungen sind nur obligatorisch.

Mich hat einfach rapsos wiederholt arrogante Art genervt.

Hat er mehr gesagt als ?:

raytracer
einfache idee, einefache implementierung und ohne cheaten recht langsam.

Bist du vielleicht nur ein wenig eingeschossen?

[trayraycaster]

@sampler :
Ich glaube Justso meinte mit vermischen, daß sich Begriffe wie 'echt', 'wirklich' und 'gut' nicht in einem Algorithmus erfassen lassen.

[sampler]

Wenn auf den expliziten Hinweis, wie viel Hirn in einem Raytracer stecken kann:

Wenn man einen echten Raytracer mit Beschleunigungsstrukturen, komplexen Beleuchtungssystem (nicht nur Mirror Reflection ) , Softshadows, Kaustiken, Nebel, Refraktion etc. haben will, wird es recht fix sehr komplex.

so eine Antwort kommt:

naja, vielleicht ist es ja auch fuer dich wirklich schwer sowas zu implementieren

dann ist das pure Arroganz im Sinne: ist doch alles trivial. Sowas progg ICH (der große tolle Rapso) jedes Wochenende. Hätte er vernünftig geantwort a la "dann haben wir wohl unterschiedliche Auffassungen von Raytracern", wäre es ja ok gewesen. Aber in seiner infantilen Arroganz muss er natürlich gleich die Troll-Keule auspacken.

@Justso: Wie ich bereits geschrieben habe: die Mathematik ist beliebig komplex. Offenbar hast du noch keinen größeren geschrieben. Sonst wüsstest du, wie komplex Dinge wie Radiance Transfer Estimate, Scattering oder Sampling sein können.

[Justso]

Zum einem hast du behauptet, dass thork keine Ahnung hat, weil er andrer Meinung ist als du. Zum anderen zittierst Rapsos Text somit ohne den Zusammenhang und bist zudem Gast, dass nicht ohne Grund. Regel das ausserhalb vom Forum, statt hier wegen ihm alle als unwissend abzustempeln.

Nacht

[BorisDieKlinge]

raytracing kann ich mir auch nich soo kompliziert vorstellen, bisschen ne ahnung in physikalischer Optik, Geometrie etc.

Das Problem ist ehr die Kunst , den Algorithmus so zu optimieren um viel performance rauszuholen..

[Gregor]

rapso schrieb:

denn wie du sagtest, reicht schulwissen um sowas zu implementieren (nicht umsonst schreiben soviele leute dann auch nen raytracer).

Das habe ich nicht gesagt. Ich habe von Hochschulwissen geredet. Ich habe mich zwar bisher nur mit Raycasting beschäftigt, da habe ich aber schon diverse Dinge aus meinen Mathematikvorlesungen angewendet. Speziell aus der Linearen Algebra. Wenn ich so in meinen alten Code gucke, dann frage ich mich doch wirklich, ob Du zum Beispiel Basistransformationen in der Schule hattest. Ich sage nicht, dass man entsprechendes mathematisches Wissen unbedingt benötigt, aber es hilft doch sehr, wenn man in diesem Bereich Algorithmen implementieren möchte. Wenn man entsprechendes Wissen hat, dann wird es einem nicht so schwer fallen, so einen Algorithmus zu implementieren. Und man wird dabei auch relativ eleganten Code produzieren können. Aus Sicht eines Schulkinds stellt so ein Algorithmus hingegen sicherlich eine wirkliche Herausforderung dar.

...zur allgemeinen Belustigung kommt hier mal ein bischen Code aus dem Umfeld meines Raycasters. Es ist nicht der Raycaster selbst, sondern eine Methode, um den Blickwinkel zu ändern.

public synchronized void rotate(final double horizontalAngle, final double verticalAngle)
   {
      final Matrix baseMatrix = new Matrix(new double[3][3]);
      for (int y = 0 ; y < 3 ; ++y)
      {
        baseMatrix.setComponent(0, y, rightDirection.getComponent(y));
        baseMatrix.setComponent(1, y, upDirection.getComponent(y));
        baseMatrix.setComponent(2, y, direction.getComponent(y));
      }
      final Matrix inverse = baseMatrix.createInvertedMatrix();
      final Matrix rotationMatrix = 
         LinearAlgebraMethods.createRotationMatrix(verticalAngle, horizontalAngle, 0);
      final Matrix functionMatrix = baseMatrix.mulBack(rotationMatrix).mulBack(inverse);
      rightDirection = functionMatrix.mulBack(new Vector(rightDirection));
      upDirection = functionMatrix.mulBack(new Vector(upDirection));
      direction = functionMatrix.mulBack(new Vector(direction));
   }

Was meinst Du, wie ein Schulkind so eine Methode schreiben würde? Ähnlich? Und wie lange würde es für diese Methode brauchen? Ich glaube, das Schulkind würde sich da etwas schwer tun. Für einen Studenten mit entsprechendem Hintergrundwissen ist es hingegen nur ein kleines Problem, so einen Code innerhalb kurzer Zeit in den Rechner reinzurotzen.

[rapso]

Gregor schrieb:

rapso schrieb:

denn wie du sagtest, reicht schulwissen um sowas zu implementieren (nicht umsonst schreiben soviele leute dann auch nen raytracer).

Das habe ich nicht gesagt. Ich habe von Hochschulwissen geredet.

hm, naja, ich hatte sowas in der 12ten klasse in einer klausur, schattierung eines pyramide, dafuer auch schnittpunktberechnungen vom blickfeld mit der ebene auf der sie stand und dann ob dieser punkt richtung sonne die pyramide schneidet, wobei, wenn ich mich recht erinnere, die sichtstrahlen vorgegeben waren. (nur 3strahlen oder so)

Ich habe mich zwar bisher nur mit Raycasting beschäftigt, da habe ich aber schon diverse Dinge aus meinen Mathematikvorlesungen angewendet. Speziell aus der Linearen Algebra. Wenn ich so in meinen alten Code gucke, dann frage ich mich doch wirklich, ob Du zum Beispiel Basistransformationen in der Schule hattest. Ich sage nicht, dass man entsprechendes mathematisches Wissen unbedingt benötigt, aber es hilft doch sehr, wenn man in diesem Bereich Algorithmen implementieren möchte.

wie du schon sagst, braucht man es nicht um Raytracing zu implementieren. die grundidee ist sehr simpel, die grundidee zu implementieren ist dementsprechend auch simpel. was du danach machst, sind optimierungen, in bildqualitaet, laufzeit, flexibilitaet usw. aber sobald du weisst wie man schnittpunkte mit ebene, kugel, kegel etc. berechnet (notfalls mit formelbuch), kannst du es implementieren.

Wenn man entsprechendes Wissen hat, dann wird es einem nicht so schwer fallen, so einen Algorithmus zu implementieren. Und man wird dabei auch relativ eleganten Code produzieren können. Aus Sicht eines Schulkinds stellt so ein Algorithmus hingegen sicherlich eine wirkliche Herausforderung dar.

Kommt wohl auf das kind an... darueber koennten wir uns einfach nur streiten ;), wieviele kinder in welchem alter das problem loesen.

public synchronized void rotate(final double horizontalAngle, final double verticalAngle)
   {
      final Matrix baseMatrix = new Matrix(new double[3][3]);
      for (int y = 0 ; y < 3 ; ++y)
      {
        baseMatrix.setComponent(0, y, rightDirection.getComponent(y));
        baseMatrix.setComponent(1, y, upDirection.getComponent(y));
        baseMatrix.setComponent(2, y, direction.getComponent(y));
      }
      final Matrix inverse = baseMatrix.createInvertedMatrix();
      final Matrix rotationMatrix = 
         LinearAlgebraMethods.createRotationMatrix(verticalAngle, horizontalAngle, 0);
      final Matrix functionMatrix = baseMatrix.mulBack(rotationMatrix).mulBack(inverse);
      rightDirection = functionMatrix.mulBack(new Vector(rightDirection));
      upDirection = functionMatrix.mulBack(new Vector(upDirection));
      direction = functionMatrix.mulBack(new Vector(direction));
   }

Was meinst Du, wie ein Schulkind so eine Methode schreiben würde? Ähnlich? Und wie lange würde es für diese Methode brauchen? Ich glaube, das Schulkind würde sich da etwas schwer tun.

ich kann dir sagen wie ich meinen ersten raytracer schrieb, ich hab mir je einen start und einen endwinkel for horizontal und vertikal errechnet, bin die dann in schritten von einem pixel abgelaufen (mit cos+sin kann man den strahl erzeugen) und hab meine schnittpunkte errechnet. alles ohne eine einzige matrixberechnung. schnittpunkte hab ich uebrigens auch nur durch naehrung in vielen iterationen errechnet (also in gleich grossen schritten bis die erste kugel Radius>pytagoras(kugelcentrum,strahlpunkt) war), weil mir damals in der 9ten klasse keine mathematisch sinnvolle loesung einfiel (jedenfalls glaub ich dass es 9te war als wir cos und sin hatten). btw. das war in basic und eh sterbens langsam, aber wenn man morgens aufstand und dann der ultraschnelle 386DX ein bild anzeigte, war der tag gerettet
wie ich schattierte sag ich euch lieber nicht, das ist noch peinlicher und hat laenger gerechnet als das ultralangsame raytracing

Für einen Studenten mit entsprechendem Hintergrundwissen ist es hingegen nur ein kleines Problem, so einen Code innerhalb kurzer Zeit in den Rechner reinzurotzen.

ja, aber da ist man ja wieder bei der implementierung. Beim Raytracing algorithmus sagt dir niemand wie du es zu implementieren hast. Die grundidee ist nur dass ein strahl vom Auge in die Scene geworfen wird und man das was er trifft dann als pixel setzt. das kann man auch rekursiv weitermachen. wie du es implementierst ist dann deine sache. Ansonsten wäre ein Binarysearch auch sehr komplex weil es dir kaum ein schulkind implementieren kann.

[EigeneNase]

sampler schrieb:

@Justso: Offenbar hast du noch keinen größeren geschrieben. Sonst wüsstest du...

sampler schrieb:

dann ist das pure Arroganz im Sinne: Sowas progg ICH ...

..."du kannst das unmöglich schon gemacht haben, denn ICH studiere".

Es wirkt auch von dir sehr arrogant jedem anderen Vorzuwerfen er hätte es wohl noch nicht programmiert und deswegen keine Ahnung, nur weil er deine Meinung nicht teilt. Zu glauben Justso, rapso, Jester und thordk wären dazu unfähig, obwohl du niemanden von Ihnen kennst

Justso schrieb:

...und bist zudem Gast...

...sprach der Gast.

[bwbg]

Aus Sicht eines "Hobbyprogrammierers" (im Sinne des Programmierens als Hobby, ich schreibe keine Hobbies):

Der beste Algorithmus ist der, den man nicht braucht.

Grüße... Heiko

[rapso]

bwbg schrieb:

Der beste Algorithmus ist der, den man nicht braucht.

du meinst sowas wie

while(vec.NotSorted())
{
  swap(vec[rand()%vec.size()],vec[rand()%vec.size()]);
}

?