Clippen von Linien gegen einen Einheitswürfel?

[Vertexwahn]

Ich suche einen Algorithmus zum Clippen von Linien gegen einen Einheitswürfel.
http://turing.fh-landshut.de/~jamann/clipping.PNG

Ich kenne nur den Cohen-Sutherland-Algorithmus für den 2D Fall – angeblich ist es leicht möglich diesen Algorithmus auch für 3D einzusetzen
Beim suchen mit Google bin ich auch über den Cyrus-Beck-Algorithmus gestoßen, der anscheinend das Clippen mit Hilfe der Parameterform von Geraden löst – jedoch auch nur für den 2D Fall, wobei die Umwandlung des Algorithmus für den 3D Fall wieder nicht all zu schwer sein soll

Kennt jemand noch weitere Algorithmen, die ich mir mal ansehen sollte?

Wie clippen OpenGL und Direct3D? Im Prinzip transformieren diese APIs doch auch immer das Sichtvolumen in einen Einheitswürfel (kanonisches Sichtvolumen)

Wenn ich es richtig verstanden habe kann der erweiterte Cohen-Sutherland-Algorithmus für das Clippen im Einheitswürfel eingesetzt werden. Dagegen wird dir erweiterte Cyrus-Beck-Algorithmus meist verwendet um schon im Volumen des Pyramidenstumpfs zu clippen

[rapso]

clip einfach gegen +x,-x,+y,-y,+z.-z und dann bist du fertig, bei einer strecke sollte das sehr trivial sein.

[Headhunter]

Hallo,

du kannst mit OpenGL bis zu sechs "Clippingplanes" verwenden, die kürzen dir deine Linie automatisch. Aber wie schon gesagt, bei einer Strecke sollte es trivial sein.

[mac_bu]

Ich gehe mal davon aus, dass du feststellen willst ob, und wenn ja, wo eine Gerade (Strecke) einen Würfel schneidet.

Eine Gerade wird beschrieben durch x = p + t*v (x, p, v Vektoren, t e R)
also

x1 = p1 + tv1
x2 = p2 + tv2
x3 = p3 + t*v3

berechne nun für x1, x2 und x3
x1:
t11 = (box.m_Min.x1 - ray.m_From.x1) / ray.m_Dir.x1;
t12 = (box.m_Max.x1 - ray.m_From.x1) / ray.m_Dir.x1;

für x2 und x3 entsprechendes
x2:
t21 = ...
t22 = ...

x3:
t31 = ...
t32 = ...
Dabei ist p = ray.m_From und v = ray.m_Dir

Achte darauf, dass du eine Ausnahmebehandlung durchführst, falls eine der Richtungen 0 (oder fast 0) wird!

Du erhältst so 3 Intervalle ([t11, t12], [t21, t22], [t31, t32]). Falls diese Intervalle einen nicht-leeren Schnitt haben scheidet die Gerade den Würfel. Dann liefert dir das größte in allen enthaltene Intervall (also der Schnitt der Intervalle) tMin und tMax, aus denen du dir dann die Schnittpunkte berechnen kannst.

trivial??

Viel Spaß!

[TheTester]

z.B. der Algorithmus von Liang-Barsky

[TGGC]

rapso schrieb:

clip einfach gegen +x,-x,+y,-y,+z.-z und dann bist du fertig, bei einer strecke sollte das sehr trivial sein.

Cohen Sutherland (AFAIK das Szandard Verfahren) sagt gar nichts darüber, wie man mit den Ebenen schneidet, sondern in welcher Reihenfolge und ob überhaupt.

Bye, TGGC (Das Jahr des Helden)

[Vertexwahn]

ohen Sutherland (AFAIK das Szandard Verfahren) sagt gar nichts darüber, wie man mit den Ebenen schneidet, sondern in welcher Reihenfolge und ob überhaupt.

BTW: Das kann ich schlecht beurteilen, da ich das Orginal Dokument von Cohen Sutherland nicht kenne (http://turing.fh-landshut.de/~jamann/Cohen Sutherland Algorithmus.pdf).

Natürlich ist es kein Problem eine Gerade im Einheitswürfel zu clippen (Schnittpunkt Gerade Ebene - das schaff selbst ich noch ;))

nur bin ich mir sicher, das ich nicht der erste bin, der sich mit dem Problem beschäftigt - in jeder 3D Pipeline hat man das Problem

bevor ich also selber zu basteln anfange wollte ich einfach nur wissen auf welchen Algorithmen ich aufsetzen kann

meine Eigenentwicklung hätte etwa so ausgesehen:
Wann ist ein Punkt P nicht Element des Einheitswürfels?
wenn (Betrag(P.x) > 1 || Betrag(P.y > 1))
Damit hätte ich die Strecken in drei Kathegorien eingeteilt:
- komplett sichtbar
- komplett unsichtbar
- Clippingkandidat

beim Clippingkandidat hätte ich folgendes gemacht:
für jede Ebene mit der Gleichung p = v0 + (v1-v0)*t nach t aufgelöst - wenn
0 <= t <= 1 => dann Schnittpunkt berechnen, Punkt der Außerhalb des Einheitwürfels liegt mit berechnetem Schnittpunkt ersetzen

im Prinzip der Cohen Sutherland Algo - einfach Bereichscode um eine Stelle erweitern und dann mal gucken

[ChaosAngel]

In welcher Reihe sitzt du denn ?
Ich mein ja nur, irgendwie kommen hier pünktlich alle Hausaufgaben für ComputerGrafik gleich am ersten Tag hier ins Forum.

[Vertexwahn]

In welcher Reihe sitzt du denn ?
Ich mein ja nur, irgendwie kommen hier pünktlich alle Hausaufgaben für ComputerGrafik gleich am ersten Tag hier ins Forum.

ich studiere an der FH Landshut und hab bestimmt nichts mit deinen Hausaufgaben für Programmierung zu tun

[rapso]

Vertexwahn schrieb:

meine Eigenentwicklung hätte etwa so ausgesehen:
Wann ist ein Punkt P nicht Element des Einheitswürfels?
wenn (Betrag(P.x) > 1 || Betrag(P.y > 1))
Damit hätte ich die Strecken in drei Kathegorien eingeteilt:
- komplett sichtbar
- komplett unsichtbar
- Clippingkandidat

beim Clippingkandidat hätte ich folgendes gemacht:
für jede Ebene mit der Gleichung p = v0 + (v1-v0)*t nach t aufgelöst - wenn
0 <= t <= 1 => dann Schnittpunkt berechnen, Punkt der Außerhalb des Einheitwürfels liegt mit berechnetem Schnittpunkt ersetzen

im Prinzip der Cohen Sutherland Algo - einfach Bereichscode um eine Stelle erweitern und dann mal gucken

ja so in etwa läuft das immer, ein paar modifikationen würde ich vorschlagen. da du linien klippst und keine polygone würde ich das kategorisieren der eckpunkte direkt vor dem klippen machen, erstmal ale vertices zu kategorisieren bringt nur rtwas wenn sie öfter benutzt werden. statt gegen den betrag zu testen, gegen die realen werte testen, da bei einem punkt mit x=-2 und einem mit x=2 deinem algo nach die linie komplett unsichtbar wäre.
für polygone wäre das ein wenig komplexer und ich glaube das ist der eigentlich clue bei Cohen-Sutherland-clipping. für linien ist das klippen recht trivial.

[Vertexwahn]

für polygone wäre das ein wenig komplexer und ich glaube das ist der eigentlich clue bei Cohen-Sutherland-clipping. für linien ist das klippen recht trivial.

ziel sind ja irgendwann Polygone - möchte mir ja einen Softwarerenderer schreiben... bin durch ein paar Zufälle auf sehr brauchbare Quellen gestoßen (die such ich jetzt ca. 3 Jahre - ist halt doof wenn man Bücher über Grafikprogrammierung kauft und der Inhalt eine Kurzfassung des DXSDKs ist - hab da ein paar Fehlkäufe gemacht und in der Bibliothek war auch nichts brauchbares zu finden) - aber jetzt weiß ich, dass ich auf dem richtigen Weg bin

Einen der besten Softwarerenderer (mit Quellcode), den ich jemals gesehen habe:
http://muli3d.sourceforge.net/index.php

Langfristig möcht ich etwas ähnliches programmieren

Wer sich fragt was die brauchbaren Quellen sind:
1. Muil3D (siehe link oben)
2. Lehrbuch der Grafikprogrammierung

so - damit habe ich auch 3 Jahre Literatursuche erspart

der Entwickler von Muli3D meinte gute Quellen sind:
- google
- www.devmaster.net
und www.gamedev.net

er hat keine Bücher empfohlen, was mich verwundert hat

[Sgt. Nukem]

Vertexwahn schrieb:

bin durch ein paar Zufälle auf sehr brauchbare Quellen gestoßen (die such ich jetzt ca. 3 Jahre - ist halt doof wenn man Bücher über Grafikprogrammierung kauft und der Inhalt eine Kurzfassung des DXSDKs ist - hab da ein paar Fehlkäufe gemacht und in der Bibliothek war auch nichts brauchbares zu finden) - aber jetzt weiß ich, dass ich auf dem richtigen Weg bin

Hab' vor paar Jahren mal bei ebay für'n Eurofuffzich so'n unscheinbares rotes kleines Buch "Algorithmen für Grafik" oder so gefunden. (Hab's g'rad' nicht hier, weiß daher jetzt nicht, wie's genau heißt)
Da ist ordentlich Zeug drin. Rasterisierung, Clipping, perspektivische und orthogonale (und davon abgeleitete wie die schiefwinklige etc.), Bezier-Kurven, ...

Desweiteren hat LaMothe ein Werk rausgebracht, das von vorne bis hinten einen Software-Renderer baut.

[rapso]

Sgt. Nukem schrieb:

rotes kleines Buch "Algorithmen für Grafik" oder so gefunden. (Hab's g'rad' nicht hier, weiß daher jetzt nicht, wie's genau heißt)
Da ist ordentlich Zeug drin. Rasterisierung, Clipping, perspektivische und orthogonale (und davon abgeleitete wie die schiefwinklige etc.), Bezier-Kurven, ...

ist zwar nicht rot, klingt aber nach http://www.amazon.de/exec/obidos/ASIN/3528167696

Sgt. Nukem schrieb:

Desweiteren hat LaMothe ein Werk rausgebracht, das von vorne bis hinten einen Software-Renderer baut.

ja, die ausgabequalität ist top, aber das softwaredesign manchmal ein wenig strange(zb hunderte raster-funktionen) und wenn ich mich recht erinnere hällt er nichts von matrizen und clippt wie es die meisten früher gemacht haben, also nichts für leute die einen hardware rasterizer nachbauen wollen.

wir sollten mal einen 1337-rasterizer contest machen

[Sgt. Nukem]

rapso schrieb:

Sgt. Nukem schrieb:

rotes kleines Buch "Algorithmen für Grafik" oder so gefunden. (Hab's g'rad' nicht hier, weiß daher jetzt nicht, wie's genau heißt)
Da ist ordentlich Zeug drin. Rasterisierung, Clipping, perspektivische und orthogonale (und davon abgeleitete wie die schiefwinklige etc.), Bezier-Kurven, ...

ist zwar nicht rot, klingt aber nach http://www.amazon.de/exec/obidos/ASIN/3528167696

Nee, auf keinen Fall.
Das war sowohl vom Schreibstil als auch von der Aufmachung sehr "altbacken", also vielleicht 80er?! K.A.
Eher trocken vorgetragen mit viel Mathe. Aber für so ein relativ kleines Buch viel Inhalt.

Sgt. Nukem schrieb:

Desweiteren hat LaMothe ein Werk rausgebracht, das von vorne bis hinten einen Software-Renderer baut.

ja, die ausgabequalität ist top, aber das softwaredesign manchmal ein wenig strange(zb hunderte raster-funktionen)[/quote]

Generell sind sein komischer C-Stil und seine seltsamen structs sehr gewöhnungsbedürftig IMHO.

[Vertexwahn]

schon etwas her aber: jetzt verwende ich einen erweiterten Cohen Sutherland Algo:
hier beschrieben:
http://turing.fh-landshut.de/~jamann/OrthogonaleProjektion.pdf