OpenGL boolesche operation auf Rechtecke

[gerdgerdgerd]

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

 

[Evil-Devil]

Zb. mittels CSG: Constructive Solid Geometry ? Wikipedia

Jedenfalls musst du das zu Fuß machen. Mir fällt keine Lib ein die einem das in JOGL abnimmt.

 

[Spacerat]

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]

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

 

[Steev]

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:

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]

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

 

[gerdgerdgerd]

was hällt ihr von so einer lösung:

Region Quadtree Demo

einzigste negative sind keine genauen double (float) angaben.

 

[Marco13]

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 😀 ) Lösung...

 

[Steev]

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]

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).

 

[Evil-Devil]

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]

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.

 

[gerdgerdgerd]

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 🙂

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]

Hab's jetzt (mangels KSKB und so) nicht getestet, aber dieses

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

        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]

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.

 

[Marco13]

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.