Hab mal eine mathematische Frage, die erstmal nichts mit OpenGL zutun hat, aber vielleicht weiss es einer:

Ich habe eine 2D-Fläche mit einem Dreieck und einem Viereck. Ich suche nun eine Formel, die mir sagt, ob beide Flächen sich irgendwie eine gewisse Fläche teilen, wieviel ist egal. Bisher schaue ich nur nach, ob ein Punkt im Dreieck liegt und benutze dazu Determinanten, aber je genauer ich nachschaue, desto rechenaufwändiger wird mein Programm. Statt eines Punkterasters möchte ich nun einfach nur ein Viereck benutzen, das wäre ja nur eine einzige Berechnung, statt bisher etwa 50x50 oder sowas. Aber ich suche nun eine Formel, die mir sagen kann, ob die beiden irgendwie übereinanderliegen oder nicht. Danke schonmal!

sind auch schnittgeraden wichtig oder nur schnittflächen ?
wenn zweiteres, dann kannst du erstmal schauen, ob die Normalen identisch sind (vorher normalisieren) denn nur dann kann überhaupt eine schnittfläche vorhanden sein
wie man dann am besten überprüft, ob eine überschneidung vorliegt kann ich auch nciht sagen...
du könntest die kanten dann auf einen schnittpunkt untersuchen :-/

EDIT: hatte überlsen, dass es sich um 2D handelt... daher ist die überprüfung der Normalen hinfällig ^^

_________________
. . .

Unten siehst Du eine Skizze, welche Fälle möglich sind. Ich hab zuwenig Ahnung davon, als dass ich Deine Eingangsfrage beantworten könnte. Eigentlich sollte es um Flächen gehen. Ich muss nur irgendwie das Viereck als eine Art "Scanner" ansehen, das nach einem Dreieck sucht.

Du kannst das Dreieck ja auch um die Breite des Vierecks nach außen hin vergrößern. Dann mußt du nur für den Mittelpunkt des Vierecks prüfen ob er im Dreieck liegt.

Vorschlag:
1.) Du schreibst die drei Kanten des Dreiecks als Geradengleichungen. (f1(x), f2(x), f3(x))
2.) Du nimmst einen Punkt (i, j) der garantiert im Dreieck liegt und bestimmst für jede Geradengleichung ob j größer oder kleiner f(i) ist.
3.) Ein Punkt (a, b) liegt im Dreick wenn gilt:
((f1(a) > b) = (f1(i) > j)) AND ((f2(a) > b) = (f2(i) > j)) AND ((f3(a) > b) = (f3(i) > j))
sprich, wenn er bei jeder Kante auf der selben seite wie der Referenzpunkt liegt!

Das machst du einfach für jeden Eckpunkt des Quads. Natürlich könnte immernoch ein Punkt des Quads im Dreieck sein obwohl die Ecken allesamt nicht drinn sind.

(hoffe das macht sinn)

_________________
Selber Denken macht klug!

ich würds auf ne menge von 1D prüfungen zurückführen, wenns wirklich nur 2D ist, also die beiden primitiven auf einer ebene liegen, damit wäre das releativ einfach gelöst. ich weiss das das ne die effetivste und schönste variante ist, aber helfen sollte es, damit könnte man auch fälle wie DREIECK UMFASST VIERECK und ANDERSRUM abfange ...

rswm

_________________
Aktuelles Projekt :
www.PicPlace.de

Möchtest du das vorm Zeichnen wissen oder während? Weil wenns während is, dann müsstest du nur gucken, ob an der Stelle im Framebuffer wo du dein Dreieck/Viereck is schon was steht. Wie das genau geht wissen die Gurus hier... (ich net )

_________________
Blog: kevin-fleischer.de und fbaingermany.com

@lithander: Genau das ist meine aktuelle Strategie. Aber wie gesagt, ich will weg von Punkten und hin zu Flächen, da ich zur Zeit einfach zuviele Punkte durchrechnen muss, um möglichst effektiv zu berechnen.

Ich erläutere mal besser den Hintergrund meines Programms: Es hat erstmal nichts mit OpenGL direkt zutun. Ich schreibe gerade ein Programm, dass ein 3ds-Modell in eine 3D-Matrix überträgt. Diese Matrix hat eine variable Auflösung, etwa 100x100x100 Blöcke. Ich schaue also Block für Block durch, ob dort das 3ds-Modell liegt und schreibe in diesen Block eine 1, sonst eine 0. Um das ganze zu beschleunigen schaue ich nicht alle 1.000.000 Blöcke sturr durch, sondern übertrage die einzelnen Faces (das sind bekanntlich meine Dreiecke) in diese Blöcke. Ein Face kann 4 Fälle haben: alle x-Koords sind gleich, alle y oder alle z-Koords. Hier habe ich nämlich meine 2D-Darstellungen. Der Vierte Fall ist der aufwändigste: Das Face liegt schief. Hier habe ich mir einen Algorithmus zusammengebastelt, den ich erstmal so lassen werde. Später in der OpenGL-Darstellung brauche ich dann nur noch maximal 100x100x100 Quadrate zeichnen und fertig. Wenn mein Rechner am Arbeitsplatz jetzt noch schnell genug wäre, könnte er diese Menge an Quadraten auch rotieren etc