Test auf Polygon-Außenkante

[aths]

Folgendes Problem:

Ich habe eine Liste von 3D-Vektoren. Diese Vektoren liegen im Raum, dort aber in einer Ebene. Zöge man von allen Punkten zu allen anderen Punkten eine Linie, ergäbe sich ein konvexes Polygon. Einige Vektoren liegen aber im Polygon.

Ich habe nun zwei Vektoren und möchte wissen, ob die Verbindungslinie dieser Vektoren auf dieser Polygon-Außenkante liegt, oder nicht.

Siehe Bild:

[aths]

Dieses Bild entsteht durch eine Projektion. Von einem konvexen 3D-Objekt werden alle Flächenaußenkanten auf eine Ebene projiziert. Die neuen Polygone werden ausgefüllt, was den Schatten macht. Um weiche Kanten hinzukriegen, sollen zusätzliche "weiche" Quads um die Ränder gemalt werden. Damit das nicht total hässlich aussieht, dürfen aber nur die Schattenpolygonaußenkanten weich gezeichnet werden.

[Kant]

Hi,

Das einfachste wird sein, du baust dir einen Index auf, in dem für jedes Face die Nachbar-Faces gelistet sind. Dann prüfst du für jedes Face mit einer einfachen Plane-Equation, ob dieses Face beleuchtet wird, oder nicht.
Wenn ein Face beleuchtet wird, ein Nachbar aber nicht, ist die Verbindungslinie dieser beiden Faces eine Schatten-Kante.

So habe ich es zumindest bei meinen Volume-Shadows gemacht, ob das für deine Zwecke funkt bin ich mir nich sicher.

[Achill]

ic habe war nicht so viel Ahnung - ich weiss aber nicht ob die Idee wirklich so gut ist, (sieht aus wie ein TSP-Problem) - des weiteren hast du konkave Figuren nicht gelöst, wenn du es trozdem umsetzt und alle Punkte zu allen anderen Punkten prüfen willst, so sieht dass sehr bescheiden aus, du hast n punkte, zu n-1 punkten ziehst du Verbindungslinien/vektoren, der nächste punkt hat dann noch zu n-2 Verbingungsvektoren, der nächste "nur" noch n-3 usw.

Das machen also n+n-1+n-2+ ... +2+1 = (n+1)+((n-1)+2)+ ... + ((n/2)+(n+1)/2) = n/2*(n+1) Verbindungsvektoren die du prüfen musst.

Als nächstest bräuchstet du noch die Menge aller Vektoren, die die reihnen Außenkanten sind (keine Ahnung wie das schnell geht), wenn du diese Menge hättest, bräuchtest du glaube ich nicht mehr auf Schnitt prüfen, da du sie ja schon hast.

Gibt es m Kantenvektoren, so musst du im schlimsten fall (Letzter Vektor ist Schnittvektor bzw. kein Schnitt bei allen m Vektoren, liegt also innerhalb) m*(n/2*(n+1)) Prüfungen durchführen.

obs richtig ist, weiss ich nicht, ist schon spät und wegen Rechtschreibung besser nicht schaun ;)

[Achill]

Original geschrieben von aths
Dieses Bild entsteht durch eine Projektion. Von einem konvexen 3D-Objekt werden alle Flächenaußenkanten auf eine Ebene projiziert. Die neuen Polygone werden ausgefüllt, was den Schatten macht. Um weiche Kanten hinzukriegen, sollen zusätzliche "weiche" Quads um die Ränder gemalt werden. Damit das nicht total hässlich aussieht, dürfen aber nur die Schattenpolygonaußenkanten weich gezeichnet werden.

hmm, vielleicht geht es so, die punkte müssten ja schon um einen mittelpunkt angeordnet sein.
Zwei Punkte A,B - sowie der Mittelpunkt M.
Du nimmst einen Punkt (soll mal A sein).
Dann bestimmst du die Gerade/Vektor von diesem Punkt zum Mittelpunkt.
es gibt jetzt zwei Winkel (alpha), die von AB und AM aufgespannt werden, du nimmst den kleineren von beiden und merkst dir die Drehrichtung.
Nun musst du überprüfen, ob es einen Punkt (C) gibt, der bei der gleichen Drehrichtung einen größeren Winkel erzeugt.
Der Winkel selber darf aber nicht >180° sein.
Wenn kein Punkt mit einem Winkel größer alpha, aber kleiner gleich 180° gefunden wurde, so ist es eine Außenkante.

einfach mal aufmalen... offe es geht so.

[zeckensack]

aths,
das was Kant geschrieben hat, ist der normale Silhouettenalgorithmus, der für Stencil-Schatten einsetzbar ist. Eine Außenkante ist genau da, wo ein 'front face' ein 'back face' berührt.

Du brauchst also backface culling: Skalarprodukt aus Oberflächennormale und dem 'Vorwärtsvektor' deiner Kamera bilden.
>0 => back face
<0 => front face
=0 => Grenzfall :D

Wenn du keine fertigen Oberflächennormalen hast, und diese auch nicht vorberechnen willst/kannst, dann reicht es übrigens anstatt einer richtigen Normale das Kreuzprodukt der Vektoren zwischen zwei Eckpunktpaaren einer Fläche zu bilden. Das setzt jedoch zwingend ein konsistentes 'winding' voraus.

Wenn du keine vollen Stencil-Schatten planst, sondern nur Projektion auf eine Fläche, kannst du dir die Silhouette gleich ganz sparen. Dann genügt es, einfach nur die front faces zu projizieren (das wird jedoch nicht gut mit deinen geplanten weichen Schatten harmonieren; es geht, aber die Lösung benötigt wieder den stencil buffer).

[micki]

was du machen könntest und was einfach wäre, wäre wenn du mit mehreren passes die polygone gescaled zeichnest.

dafür müßtest du zwar jedes poly einzeln behandeln, aber dafür wäre es unabhängig vom stencilbuffer und ohne siluettenbildung.

du vergrößerst jedes poly von seinem center nach außen, dann zeichnest du es z.B. mit 0.8 intensität, dann wiederhollst du das, aber zeichnest es ein wenig kleiner und mit einer niedrigereren intensität, am ende kommst du mit der schattenintensität und der orginalgröße raus.
dafür mußt du auch nicht blenden, weil der nachfolgende pass die inneren flächen füllt und die kannten "soft shaded" lässt.

damit du den effekt verbesserst, könntest du das scaling mit der entfernung zur lichtquelle verrechnen, sodass nahe objekte scharfe kanten und entfernte objekte weiche kannten bekommen. (das sollte sogar pro vertex klappen)

wenn du zu jedem vertex die position des centers mitspeicherst, könnte das im vertexshader/vertexprogramm sehr leicht zu relisieren sein, auch wenn jedes poly seine eigenen 3 vertices bräuchte.


ich hoffe ich hab das einigermassen verständlich erklärt, probiert hab ich das noch net, die idee kamm mir erst gerade :D

MfG
micki