Fragen zu einem Schattierungsalgorithmus

randa

moin
Ich versuche gerade folgendes Problem zu lösen: Wie bewerkstellige ich es, das ein Objekt Schatten wirft?
Nach Umfassender Analyse des Problems habe ich mir folgende Schritte ausgedacht, habe aber noch fragen zu konkreten Mathematischen Fragen:

1)Wie beim Phong Shading möchte ich für jeden Pixel einen Vektor ermitteln. Dieser Vektor zeigt vom Pixel zur Lichtquelle
2)Durch für mich noch nicht ganz klare Algorithmen will ich ermitteln, ob der Strahl vom Pixel zur Lichtquelle auf irgendein Hindernis trifft. Das macht mir die größten Probleme:
2a)Die "Kollisionsabfrage" dürfte sehr rechenaufwendig sein.
2b)Wie kann man eine solche Kollision ermitteln? Ich dachte mir, ich
prüfe, ob sich die Gerade mit einer beliebigen Ebene eines Polygons
schneidet. Das müsste für jede Polygonebene durchgeführt werden. Nachdem der Schnittpunkt bekannt ist, muss ich noch checken, ob dieser
Schnittpunkt innerhalb des Bereichs der Polygonfläche ist.
3)Wenn ein Hindernis da ist, wird der Pixel dunkel. Andernfalls ist er normal.

(Vorläufig geht es nicht um den rechenaufwand, ich will vom Prinzip erstmal Schatten erzeugen. Später interessiert mich dann auch die Performance)

Nun zu meinen Fragen:
Ist das obige vernünftig?

Zum 1. Punkt: Wie kann ich die 3Dimensionale Position eines Pixels bestimmen, damit ich von dieser Position aus einen Vektor zur Lichtquelle Berechnen kann?
Die Anzahl der Pixel variiert ja vom aktuellen zustand des Objekts, ist also keine feste Größe. Ich dachte mir zuerst ich mach das wie bei einer Normalen Linearen Interpolation, aber wie bekomme ich die Anzahl der Pixel? Ideen reichen schon

Zum Punkt 2b)Hat jemand Ideen, wie ich eine solche Prüfung möglicherweise geschickter durchführen könnte?

Das Zeug da oben hab ich mir selbst ausgedacht. Wie arbeiten andere Schattierungsalgorithmen (schematisch)?

Ein paar Ideen reichen schon, vielleicht kann ich das Problem dann schritt für schritt erörtern.

dot

zu deiner lösungsidee:

im prinzip arbeiten raytracer so.
aber ich würd mal nicht meinen, dass das ganze so wirklich performant läuft ( ich weis es gibt echtzeit raytracer, aber... )

wenn du das alles in echtzeit haben willst, überleg dir folgendes:

soll es dynamisch ( schatten reagiert auf bewegungen von lichtquelle oder modell ) oder statisch sein?

schau dir mal diese techniken an:

dynamisch:
Shadow Volumes ( Stencil Shadowing )
Shadowmaps

statisch:
Lightmaps
etc.

randa

Natürlich dynamisch, sonst würde ich mir nicht so einen Aufwand machen.
Mit texturen etc. will ich das noch künftig implementieren, ist jedoch zur Zeit nicht das Aufgabengebiet. Dies soll für einheitlich colorierte Flächen ohne Texturen auch möglich sein.
Wie sicher auch hervorkommt, is nix mit DX oder OGL. Bei mir ist grad selber machen angesagt
Die Techniken kann ich mir mal anschauen, primär geht es mir aber um die Idee, dich ich oben beschrieben hab. Ich möchte aus Prinzip diese Probleme lösen und es damit versuchen.

Edit: Raytracer? Das ist aber langsam *g*
Mir war klar, das das einigen Rechenaufwand erfordert...aber wenn ich mir mal Phong Shading angucke
Naja also echtzeit soll es schon sein.

Edit2: Nicht das ich Phong Shading mit Raytracing vergleichen will
Aber ich habe mit meinem Software Renderer schon recht viele Phong-Geshadete Objekte auf einmal darstellen können, flüssig. Egal, beim Software-Rendering erwarte ich ja auch keine Peformance, es geht mir im Prinzip um die Bildqualität

dot

beide ansätze, sowohl Shadowmaps als auch Shadow Volumes, benötigen entweder einen ZBuffer oder einen Stencil Buffer.

wenn du in software schon sowas hast (?), dann fällt die entscheidung leichter.

allerdings würd ich sagen die prüfung von strahlen vom pixel zum licht auf kollision is ein wenig sehr aufwendig...

randa

zbuffer hab ich selbstverständlich schon, das sind basics, die sind drin.
Was ein Stencil Buffer ist, weiß ich (noch) nicht. Was wird darin gespeichert? Wie groß ist der?

Also: Kann mir jemand hilfestellung zu den obigen fragen geben?

otze

du kannst mit nem sehr guten shadow volume algorithmus extrem gute und scharfe schatten erreichen,multiple lichtquellen machen kaum probleme,und mit den shadow volumes lassen sich noch weitere extrem schöne effekte zeichnen(zb indem man die shadowvolumes mit nem hohen alphawert mitzeichnet, dann kann man sogar das in den schatten "eintauchen" super zeigen,perfekt für ein düsteres ambiente...

aber wenn du dann trotzdem deinen eigenen algorithmus nehmen willst, dann werd ich dich nich abhalten^^

//edit ein stencil buffer ist ein buffer der eigentlich nix kann, ausser ganzzahlige werte für jeden pixel zu speichern.
normalerweise mahct der stencil buffer garnichts, aber du kannst zb bestimmen, dass bei jedem pixel innerhalb eines shadowvolumes der stencil buffer um eins rauf gesetzt ist,und ganz zum schluss kannst du dann mit den stencil werten was machen, zb dort wo der wert über 3 ist den pixel verdunkeln

randa

ich werd meinen Algorithmus so oder so versuchen, wie ich sagte, es ist Prinzipsache. Ich will es einfach so zum Laufen bringen. Wenn ich mich nicht anstrengen würde und meinen Gedankengang zuendeführe, was soll ich dann später bei anderen eigenen Algorithmen machen?

Aber ich bin absolut offen für Shadow Volumes und würde das auch implementieren, ohne frage. Ich hab übrigens nach Büchern gesucht, in denen solche Sachen erklärt sind, hab aber nix gefunden. Kennt jemand ein Buch das sich mit den Implementierungs- und Mathematikdetails in diesem Bereich befasst?

Nur googeln und ein paar lasche Seiten reicht ja meist nicht um sich in das Thema zu vertiefen.

Aber nun zurück zum Topic

Edit: @otze: ich bekomme ne wage idee, aber auf welche weise kommt man dazu, bestimmte Werte im Buffer zu speichern. Oder Klarer: Woher kommt z.B. der Wert 3?

otze

in directx ist der stencil buffer ein teil des zbuffers, und genau wie es beim zbuffer einen vergleich gibt der überprüft ob der alte oder neue pixel übernommen werden soll,so gibt es auch beim stencil buffer so eine abfrage.

an den wert 3 kommt man zb, wenn man sagt dass der stencil test immer bestanden wird, der stencil wert um 1 erhöht wird wenn der test positiv verläuft, und der pixel 3mal überzeichnet wird.

//edit das buch welches man bei scherfgen-software findet handelt diese ganze theorie inklusive schatten und lightmaps ab(auch wenn das erst ganz am ende geschieht)
alternativ gehste auf www.flipcode.com die haben alles(aber nur auf englisch)

dot

otze schrieb:

in directx ist der stencil buffer ein teil des zbuffers

afaik gilt das für moderne grakas allgemein ( nicht nur DirectX )

otze schrieb:

//edit das buch welches man bei scherfgen-software findet handelt diese ganze theorie inklusive schatten und lightmaps ab(auch wenn das erst ganz am ende geschieht)
alternativ gehste auf www.flipcode.com die haben alles(aber nur auf englisch)

seit wann kommen im scherfgen buch lightmaps vor?
außer einer kurzen erklärung was lightmaps sind is mir da noch nicht viel mehr untergekommen.

flipcode ist imho

auf GameDev ( imho noch mehr ) wirst du sicher auch einiges finden

otze

im buch werden die prinzipien der lightmaps imho relativ gut erklärt,mit dem text und von ner andren seite die algos, und du bist fit

TomasRiker

Light-Maps beschreibe ich in meinem Buch so gut wie gar nicht. Bei der Implementierung gibt es da nämlich sehr viel mehr zu beachten als bei der Stencil-Buffer-Variante, vor allem bei Direct3D ist das ziemlich problematisch. Die meisten Demos, die man findet, arbeiten mit OpenGL.

TGGC

Chaotischer Thread. Ich versuche mich nochmal auf die "originalen" Fragen zu beziehen, da ich sonst nicht wüsste, was du eigentlich wissen willst.

zu 1. Du musst einen eigenen Rasterizer schreiben, weil du die Pixel ja auf der CPU shaden willst. Der könnte die diese Informationen ausspucken.

zu 2b. Man müsste wahrscheinlich irgendein hierachisches System wie einen Octree verwenden. Zusätzlich könntest du noch für jedes Face die Occluder cachen und im nächsten Frame als early out test verwenden.

Bye, TGGC \-/

rapso

TomasRiker schrieb:

Light-Maps beschreibe ich in meinem Buch so gut wie gar nicht. Bei der Implementierung gibt es da nämlich sehr viel mehr zu beachten als bei der Stencil-Buffer-Variante, vor allem bei Direct3D ist das ziemlich problematisch. Die meisten Demos, die man findet, arbeiten mit OpenGL.

Eigentlich ist es in oGL und d3d das gleiche von der implementierung her.

dass man mehr demos für oGL findet liegt daran, dass die NV jungs damit lieber prototypen und weil dort die extensions früher vorhanden sind. aber von der implementierung her ist es auf beiden APIs eigentlich gleich
(sorry für den flame )

randa schrieb:

ber ich habe mit meinem Software Renderer schon recht viele Phong-Geshadete Objekte auf einmal darstellen können, flüssig. Egal, beim Software-Rendering erwarte ich ja auch keine Peformance, es geht mir im Prinzip um die Bildqualität

für phong mußt du ja auch nur einen vector interpolieren und dann ein paar dot3 und vielleicht noch paar normalise.
jetzt mußt du pro pixel den du setzt durch die welt raytracer. je 3polys die du testest werden mindestens soviel zeit ziehen wie dein phongshading.

aber ich würde sehr gerne deine demo davon sehen wenn es läuft ;D. btw vielleicht solltest du dir "deffered rendering" anschauen, für so rechenintensive rasteriser wie du den machen möchtest könntest du sehr viel performancesteigerung bekommen

rapso->greets();

randa

TGGC schrieb:

Chaotischer Thread. Ich versuche mich nochmal auf die "originalen" Fragen zu beziehen, da ich sonst nicht wüsste, was du eigentlich wissen willst.

zu 1. Du musst einen eigenen Rasterizer schreiben, weil du die Pixel ja auf der CPU shaden willst. Der könnte die diese Informationen ausspucken.

zu 2b. Man müsste wahrscheinlich irgendein hierachisches System wie einen Octree verwenden. Zusätzlich könntest du noch für jedes Face die Occluder cachen und im nächsten Frame als early out test verwenden.

Bye, TGGC \-/

Danke, die erste Antwort auf meine gestellten fragen.

Ich habe einen eigenen Rasterizer, sonst hätte ich ja auch keinen Software Renderer. Ich benutzte, wie gesagt, kein DX (außer für den Screen Pointer, den ich über DirectDraw hole), sondern code selber.
Edit: Ok, die Frage ist schwachsinn, der Rasterizer hat die Informationen eh schon. Hatte irgendwie einen Blackout, sonst hatt ich das selber gemerkt.

2)Immer diese Anglizismen Was ist ein Occluder, was ist ein early out test?
Eine Hierarchische Struktur wäre wohl sinnvoll, damit ich nicht linear durch alle Polygone der Welt iterieren muss um den Kollisionscheck zu machen.

Ich muss mir die Formeln für den Geraden-Ebenen Schnittpunkt nochmal anschauen, denke aber das krieg ich schon hin. Aber bei der Überprüfung, ob der ermittelte Schnittpunkt tatsächlich auf der Fläche liegt, hab ich meine Probleme. Durch eine simple if-Abfrage ist es nicht getan, die ebene (bzw. die Polygonfläche) kann ja beliebig im Raum stehen. Wäre die Fläche z.B. parallel zu xy, könnte ich leicht durch "if (x>... && x<... && y>... und y<...) " die Prüfung machen.
Aber wie könnte ich die Prüfung für beliebige positionierte Flächen machen?
Das ist zur Zeit das einzige, wozu ich noch keine rechte Lösung hab.

TomasRiker

rapso schrieb:

Eigentlich ist es in oGL und d3d das gleiche von der implementierung her.

Ich habe ja auch nichts Anderes behauptet. Das Prinzip ist dasselbe, aber bei Direct3D gibt es laut diesem Artikel einige Dinge bei der Texturprojektionsmatrix, die etwas komplizierter sind: http://developer.nvidia.com/attach/6811

rapso

TomasRiker schrieb:

rapso schrieb:

Eigentlich ist es in oGL und d3d das gleiche von der implementierung her.

Ich habe ja auch nichts Anderes behauptet.

Bei der Implementierung gibt es da nämlich sehr viel mehr zu beachten als bei der Stencil-Buffer-Variante, vor allem bei Direct3D ist das ziemlich problematisch.

ja, oGL hat glPolygon offset und bei d3d muss man sich die matrix selbst generieren, aber ob das als implementierungsunterschied durchgeht?. das alte paper kenn ich, aber die haben es endlich geschaft die paper vom letzten workshop online zu legen, da gibt es ja ein schönes neues paper, das problem ist dort einigermassen gut gelöst und in deren demo sah das auch fehlerfrei aus.

rapso->greets();

TomasRiker

rapso schrieb:

TomasRiker schrieb:

Bei der Implementierung gibt es da nämlich sehr viel mehr zu beachten als bei der Stencil-Buffer-Variante, vor allem bei Direct3D ist das ziemlich problematisch.

Aussage: Implementierung Shadow-Map ist komplizierter als Stencil-Buffer-Variante. Bei Direct3D gibt es zudem noch zusätzliche Schwierigkeiten.

rapso

TomasRiker schrieb:

rapso schrieb:

TomasRiker schrieb:

Bei der Implementierung gibt es da nämlich sehr viel mehr zu beachten als bei der Stencil-Buffer-Variante, vor allem bei Direct3D ist das ziemlich problematisch.

Aussage: Implementierung Shadow-Map ist komplizierter als Stencil-Buffer-Variante. Bei Direct3D gibt es zudem noch zusätzliche Schwierigkeiten.

mit dem komma dazwischen klang es als würdest du dich mit "besonders problematisch" auf die implementierung beziehen.... wir korrintenkacker wir.

rapso->greets();

TGGC

zu 1) Ok, funktioniert jetzt eigenltich genau wie Texturemapping, nur das nicht die TexCoords sondern die Vektoren der Eckpunkte interpoliert werden.

zu 2) Occluder= Verdecker, early out test= früh raus Überprüfung (kauf dich mal ein Wörterbuch)

Bye, TGGC \-/

randa

TGGC schrieb:

zu 2) Occluder= Verdecker, early out test= früh raus Überprüfung (kauf dich mal ein Wörterbuch)

dich auch

Danke für die Hilfe.