OpenGL boolesche operation auf Rechtecke

Status
Nicht offen für weitere Antworten.

gerdgerdgerd

Aktives Mitglied
Hallo zusammen,

ich möchte eine Rechteck mit boolesche operation realisieren. D.h. es können z.B.

- 2 Rechtecke zusammengefügt werden
- ein Rechteck von einem anderen abziehen
- Teile von einem Rechteck ausschneiden
- ...

Hier ist ein Beispiel Bild:



Wie kann ich da mathematisch vorgehen?
Das ganze soll in OpenGL (JOGL) realisiert werden.

Danke
 
S

Spacerat

Gast
Ne Lib fällt mir da auch nicht ein...
Aber wie wäre es mit ein paar Stichworten, für die "zu Fuss"-Lösung...
- <Rectanlge>.intersects();
- GeneralPath
- GLU Tesselation
 

gerdgerdgerd

Aktives Mitglied
danke für die stichworte.

ich bin jetzt folgendermaße vorgegangen:


jetzt fehlt mir noch die differenz und vorallem optimierung. da ich den letzten schritt im bild auch mit 3 rechtecken hinbekommen könnte. wenn jemand ne idee hat wie man das umsetzen kann :)

ich merke gerade das ich voll die performance probleme bekomme, da ich im 3 Schritt jedes erstellte temporäre rechteck gegen alle aus schritt 1 existierenden rechtecke prüfen muss. da nur ein rechteck erstellt wird wenn es die fläche auch vorher schon gab.

wäre sehr froh, wenn ihr eure ansätze schreiben könntet, da ich evtl. zu kompliziert denke :autsch: :)

danke
 
Zuletzt bearbeitet:

Steev

Bekanntes Mitglied
Ich würde durch die einzelnen Nodes des Pfades iterieren und prüfen, ob diese innerhalb oder Auserhalb des jeweils anderen Objektes liegen.

Etwa so:
cuts.png


Interessant wird es dann, wenn die Punkte so weit auseinanderliegen, dass kein Punkt eines Objektes, innerhalb des anderen Objektes liegt. In dieser Situation würde ich dann mithilfe einer Formel berechnen, an welcher Position, oder ob überhaupt, sich die Linien schneiden.
 

Marco13

Top Contributor
Der "interessante" Fall tritt ja schon bei so vermeintlich einfachen Beispielen wie dem oben rechts auf. Man sollte IMHO unbedingt die Schnittpunkte berücksichtigen.
 

Marco13

Top Contributor
Komt drauf an... wenn du nur ein Bitmap haben willst, kannst du gleich den Pixel-Array speichern und mit dem rumhantieren ... ich dachte, es geht um eine mathematische (und keine informatische :D ) Lösung...
 

Steev

Bekanntes Mitglied
Na ja, ich weis nicht. Ich finde es besser, wenn man sowieso schon vektorbasierte geometrische Objekte hat, dass man auch mit diesen arbeitet. Das ist schneller, weil auch bei komplexen Objekten ja nur die Eckpunkte und die Strecken zwischen den Eckpunkten geprüft werden.
 

gerdgerdgerd

Aktives Mitglied
ja, das stimmt, aber der nächste schritt nachdem die geometrischen objekte gezeichnet wurden, wäre das rastern. d.h. ich würde die erhaltene geometrie im späteren verlaufen mit einem gleichmäßigen raster rastern.

ps: ich merke eh gerade das die performance bei einer feinen auflösung ziemlich in die knie geht (quadtree).
 
Zuletzt bearbeitet:

Evil-Devil

Top Contributor
Was ist eigentlich dein Endziel? Denn Quadtrees werden zumeist zur Bereichseinteilung genutzt und Editoren die CSG nicht gerade fürs Raytracing nutzen erzeugen daraus später einen BSP-Tree.
 

gerdgerdgerd

Aktives Mitglied
Mein Endziel ist eine Rasterung von einem Model. Mit den geometrischen Flächen will ich nur sagen wo er das Model rastern soll, da ich nicht das komplette Model rastern muss, sondern nur Teilbereiche.

Jedoch komme ich mit den Quadtrees schnell an das Limit, wenn das Raster ziemlich genau sein soll.
Quadtree = o(2^n) wobei n die Genaugkeit ist.
 
Zuletzt bearbeitet:

gerdgerdgerd

Aktives Mitglied
Hier ist meine aktuelle Lösung. Ich muss dazusagen, dass ich wie in meinem 2 Beitrag vorgegangen bin. Ich berechne (recalculateArea) die Flächen nur neu, wenn ich eine Fläche abziehe. Es gibt mit Sicherheit eine bessere Lösung, aber diese scheint vorerst zu funktionieren. Falls jemand doch einen Verbesserungsvorschlag hat, bin ich natürlich ganz offen.

PS: Meine Java Doc ist nicht der Burner :)

Java:
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import javax.media.opengl.GLAutoDrawable;

import Vertex;
import Facade;
import Quad;

public class Grid2DArea {

	private List<Quad> quads;

	public Grid2DArea() {
		quads = new ArrayList<Quad>();
	}

	public void addQuad(Quad addQuad) {
		if (addQuad != null) {
			quads.add(addQuad);
		}
	}

	public void difference(Quad diffQuad) {
		if (diffQuad != null) {
			List<Quad> containQuads = new ArrayList<Quad>();
			for (Quad currentQuad : quads) {
				if (currentQuad.contain(diffQuad)) {
					containQuads.add(currentQuad);
				}
			}

			recalculateArea(containQuads, diffQuad);
		}
	}

	/**
	 * Berechnet die Rechtecke um eine Geometry darzustellen
	 * 
	 * @param containQuads
	 * @param diffQuad
	 */
	public void recalculateArea(List<Quad> containQuads, Quad diffQuad) {
		float[] dimension = Facade.getSceneDimension();

		List<Float> xCoords = new ArrayList<Float>();
		List<Float> yCoords = new ArrayList<Float>();

		List<Quad> tempQuads = new ArrayList<Quad>();
		tempQuads.addAll(containQuads);
		tempQuads.add(diffQuad);

		for (Quad currentQuad : tempQuads) {
			Vertex leftTopCorner = currentQuad.getLeftTopCorner();
			Vertex rightBottomCorner = currentQuad.getRightBottomCorner();

			if (!xCoords.contains(leftTopCorner.getX())) {
				xCoords.add(leftTopCorner.getX());
			}
			if (!xCoords.contains(rightBottomCorner.getX())) {
				xCoords.add(rightBottomCorner.getX());
			}

			if (!yCoords.contains(leftTopCorner.getZ())) {
				yCoords.add(leftTopCorner.getZ());
			}
			if (!yCoords.contains(rightBottomCorner.getZ())) {
				yCoords.add(rightBottomCorner.getZ());
			}
		}

		Collections.sort(xCoords);
		Collections.sort(yCoords);

		remove(containQuads);

		// Neue Rechtecke hinzufuegen
		for (int x = 1; x < xCoords.size(); x++) {
			for (int y = 1; y < yCoords.size(); y++) {
				Quad addQuad = new Quad(new Vertex(xCoords.get(x - 1), dimension[4] + 0.5f, yCoords.get(y - 1)),
						new Vertex(xCoords.get(x), dimension[4] + 0.5f, yCoords.get(y)));

				for (Quad currentQuad : containQuads) {
					if (currentQuad.contain(addQuad) && !diffQuad.contain(addQuad)) {
						quads.add(addQuad);
					}
				}
			}
		}
	}

	/**
	 * Entfernt alle Rechtecke von der Grundflaeche
	 */
	public void removeAll() {
		quads.clear();
		quads = new ArrayList<Quad>();
	}

	/**
	 * Entfernt alle uebergebenen Quads
	 * 
	 * @param containQuad
	 *            Zu entfernenden Rechtecke
	 */
	public void remove(List<Quad> containQuad) {
		for (Quad currentQuad : containQuad) {
			quads.remove(currentQuad);
		}
	}

	/**
	 * Zeigt alle Rechtecke an
	 * 
	 * @param drawable
	 */
	public void display(GLAutoDrawable drawable) {
		for (Quad currentQuad : quads) {
			currentQuad.display(drawable);
		}
	}
}
 

Marco13

Top Contributor
Hab's jetzt (mangels KSKB und so) nicht getestet, aber dieses
Code:
for (many things)
{
    if (!someList.contains(thing)) list.add(thing);
}
sort(list);
ist wohl inhärent ineffizient. Floats auf diese Weise zu behandeln ist wegen der Rechenungenauigkeit außerdem recht heikel, aber das nur nebenbei.

Statt der Sache mit dem contains/add könnte man ein sortiertes Einfügen machen - das ist ein bißchen mehr zu tippen, aber könnte sich lohnen.

Wobei ich jetzt nicht nachvollzogen habe, OB (oder WOFÜR) du die Sortierung unbedingt brauchst.

Als ... "Mittelding" oder ersten Schritt könnte man sowas machen wie
Code:
        Set<Float> xCoordsSet = new HashSet<Float>();
... 
        for (Quad currentQuad : tempQuads) {
            Vertex leftTopCorner = currentQuad.getLeftTopCorner();
 
            xCoordsSet.add(leftTopCorner.getX()); // Einfach einfügen, ohne contains-abfrage
...
        }
 

        // Wenn du sie dann unbedingt als sortierte Liste brauchst:
        List<Float> xCoords = new ArrayList<Float>(xCoordsSet);
        Collections.sort(xCoords);
Je nachdem, wie viele Zahlen das sind und so, könnte es auch effizienter sein, statt der HashSet eine TreeSet zu verwenden: Die ist automatisch sortiert, d.h. man kann sich am Ende das Sortieren der Liste sparen - aber das muss man ausprobieren/abschätzen.
 

gerdgerdgerd

Aktives Mitglied


im Schritt 2 siehst du warum ich sortieren muss, da ich die neuen (im Beispiel 9 Rechtecke) von oben links nach unten rechts aufbaue und darstelle.

Wenn ich nicht abfrage ob bereits ein Wert in der Liste steht, steht z.b. 3 mal der gleiche Wert drin. Was letztendlich dazu führt das ein Rechteck mehrmals gezeichnet wird.

Aber ich schau mal och ich es mit einer sortierten Liste versuche. So dass ich den Schritt mit dem Sortieren weglassen kann.

Wenn ich es als HashSet mache, muss ich es erstmal als Array konvertieren, da ich auf den index x - 1 und x zugreifen muss, was mit einem iterator schlecht zu realisieren ist.
 
Zuletzt bearbeitet:

Marco13

Top Contributor
Di Konvertierung in eine Liste wird - wie angedeutet - mit

List<Float> xCoords = new ArrayList<Float>(xCoordsSet);

gemacht - das ist sowas wie

List<Float> xCoords = new ArrayList<Float>();
xCoords.addAll(xCoordsSet);

Aber du kannst natürlich auch toArray verwenden.
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
temi OpenGL: Eine Kugel Spiele- und Multimedia-Programmierung 7
P Audio Visualizer mit OpenGL in Java? Spiele- und Multimedia-Programmierung 4
Z Vlcj in OpenGL Spiele- und Multimedia-Programmierung 4
coolian opengl von scale in breite und höhe konvertieren Spiele- und Multimedia-Programmierung 23
F OpenGL (LWJGL) Shader Programmierung GLSL Spiele- und Multimedia-Programmierung 2
K Messdaten in Echtzeit darstellen in OpenGL Spiele- und Multimedia-Programmierung 4
J OpenGL Bild wird nicht richtig angezeigt Spiele- und Multimedia-Programmierung 2
B LWJGL OpenGL SIGSEGV auf Linux (Verzweiflung :/) Spiele- und Multimedia-Programmierung 8
KeexZDeveoper Fehler von OpenGL Spiele- und Multimedia-Programmierung 1
Kim_Dotcom libGDX - opengl Fehler Spiele- und Multimedia-Programmierung 5
Streeber Problem mit Transparenz/TextDrawing in LWJGL/Slick2d (OpenGL) Spiele- und Multimedia-Programmierung 1
RalleYTN OpenGL Context im JFrame? Spiele- und Multimedia-Programmierung 0
L OpenGL TransformationMatrix eines Flugzeugs Spiele- und Multimedia-Programmierung 2
F OpenGL - Transparenz mit Depth Peeling Spiele- und Multimedia-Programmierung 0
turing OpenGL / Jogle Code Reveiw zur Performance Verbesserung Spiele- und Multimedia-Programmierung 1
K LibGdx, Loadingscreen & Opengl context Spiele- und Multimedia-Programmierung 3
turing OpenGL VBO and Unfiform Handling Spiele- und Multimedia-Programmierung 1
B LWJGL / OPENGL Kriege Depth-Test nicht hin :( Spiele- und Multimedia-Programmierung 0
T opengl und Android.... Spiele- und Multimedia-Programmierung 3
D [OpenGL] Spiel in der Art von Age of Empires Spiele- und Multimedia-Programmierung 4
R LWJGL: OpenGL Fehler - weitere Informationen auslesen möglich? Spiele- und Multimedia-Programmierung 2
T Welche OpenGL-Version soll ich verwenden? Spiele- und Multimedia-Programmierung 2
O OpenGL - Texture falsch herum Spiele- und Multimedia-Programmierung 3
Gregorrr OpenGL & RCP/SWT Spiele- und Multimedia-Programmierung 3
P LWJGL oder OpenGL (C++) Spiele- und Multimedia-Programmierung 7
K Android: OpenGL render performance Tipps ? Spiele- und Multimedia-Programmierung 4
lumo opengl, sprites/tiles Spiele- und Multimedia-Programmierung 8
M OpenGL: Rectangle dort erstellen wo ich hintippe Spiele- und Multimedia-Programmierung 2
U OpenGl 1.1 (LWJGL GL11.*) und weiter? Spiele- und Multimedia-Programmierung 7
CookieSoft OpenGl Translatef Frage Spiele- und Multimedia-Programmierung 2
V Keine Ahnung von OpenGL! Hilfe wäre lieb! Spiele- und Multimedia-Programmierung 8
T 3D Stadtmodell mit OpenGL Spiele- und Multimedia-Programmierung 5
TheWhiteShadow OpenGL glDrawArrays Bufferfehler Spiele- und Multimedia-Programmierung 10
B LWJGL/OpenGL rendert manche Objekte nicht Spiele- und Multimedia-Programmierung 6
S OpenGL Textur unsauber Spiele- und Multimedia-Programmierung 2
T OpenGL ES verschwindene Vertices Spiele- und Multimedia-Programmierung 2
T Android OpenGL Bewegen Spiele- und Multimedia-Programmierung 5
R OpenGL Textur mit verschiedenen bit depths Spiele- und Multimedia-Programmierung 6
Helgon OpenGL Blend Frage Spiele- und Multimedia-Programmierung 18
A LWJGL/OpenGL und Text Spiele- und Multimedia-Programmierung 8
Helgon OpenGL vernünftige Tutorial? Spiele- und Multimedia-Programmierung 22
A OpenGL Textur und nicht Textur Spiele- und Multimedia-Programmierung 2
T Jmonkey opengl problem Spiele- und Multimedia-Programmierung 13
T Probleme mit Skysphere in Opengl Spiele- und Multimedia-Programmierung 4
M Problem mit Kamera (glMultMatrix (OpenGL/ LWJGL)/ Quaternionen) Spiele- und Multimedia-Programmierung 5
F Suche Tutorial zu "purem" OpenGL mit Java Spiele- und Multimedia-Programmierung 10
Kr0e OpenGL + glSubTexImage2D -> Bufferproblem Spiele- und Multimedia-Programmierung 3
F OpenGL Screenshot in iMove (als Greenscreen) => Farben invertiert? Spiele- und Multimedia-Programmierung 16
I Vergleich von Java3D und OpenGL Spiele- und Multimedia-Programmierung 17
F Mac: OpenGL Desktop-Screen aus Grafikkarte lesen Spiele- und Multimedia-Programmierung 2
F OpenGL 2D MouseClick/MouseMove Listener Spiele- und Multimedia-Programmierung 4
Kr0e Sehr schnelle Texturupdates (OpenGL) Spiele- und Multimedia-Programmierung 3
Kr0e OpenGL beliebige Texturgröße Spiele- und Multimedia-Programmierung 2
BattleMaster246 OpenGL - Transparenz Spiele- und Multimedia-Programmierung 10
Kr0e OpenGL .. Pixel Buffer Objekt oder Frame Buffer Object? Spiele- und Multimedia-Programmierung 2
Y JOGL / OPENGL in Frame Spiele- und Multimedia-Programmierung 11
A Problem openGL-Pipeline mit Win7? Spiele- und Multimedia-Programmierung 6
A JOGL / OpenGL Spiele- und Multimedia-Programmierung 7
G API für 3d-Programmierung? OpenGL? Spiele- und Multimedia-Programmierung 12
J OpenGL (JOGL) - Radial Blur Effekt (Glow) Spiele- und Multimedia-Programmierung 2
J Opengl Texture laden Null Pointer Exception Spiele- und Multimedia-Programmierung 6
J netbeans opengl keyPressed(KeyEvent evt) benutzen Spiele- und Multimedia-Programmierung 4
J netbeans opengl gluPerspective und gluLookAt Verständnis Spiele- und Multimedia-Programmierung 13
S glTexSubImage2D()-Fragen(Zerstörbares Terrain, OpenGL) Spiele- und Multimedia-Programmierung 3
Z Suche Tutorial zum Einstieg in OpenGl mit Java (JOGL) Spiele- und Multimedia-Programmierung 2
T Overlay in anderer OpenGL Anwendung Spiele- und Multimedia-Programmierung 4
egrath Vista OpenGL Performance Problem? Spiele- und Multimedia-Programmierung 3
Y OpenGL Spiele- und Multimedia-Programmierung 5
J opengl beispiele? Spiele- und Multimedia-Programmierung 10
D Java mit OpenGL - besser LWJGL oder JOGL? Spiele- und Multimedia-Programmierung 6
N OpenGL und DirectX - was genau ist das? Spiele- und Multimedia-Programmierung 5
C OpenGl Support für Applet (sun.java2d.opengl=True) Spiele- und Multimedia-Programmierung 3
B OpenGL oder Direct X Spiele- und Multimedia-Programmierung 9
P Invalid operation (1282) Spiele- und Multimedia-Programmierung 5

Ähnliche Java Themen

Neue Themen


Oben