Hallo,

Diese Frage bezieht sich auf Bounding Boxes... Mir ist klar wie ich eine netzparallele* BoundingBox ermitteln/errechnen/erstellen kann. Mich würde aber die "kleinstmögliche Bounding Box" interessieren, die ja nicht immer netzparallel ist.
Bei meinen google und foren Recherchen fand ich nichts, das ich direkt einbauen könnte, hier ein paar Treffer:

Eine Patentinformation... (da hat hoffentlich niemand das, was ich brauche patentiert?)
http://www.freepatentsonline.com/7218331.html
Eine ausführliche theoretische Abhandlung inclusive Source Code in C:
http://valis.cs.uiuc.edu/~sariel/papers/98/bbox.html

Naja meine Hoffnung liegt jetzt darin, das jemand von euch vielleicht den obigen source code in delphi gesehen hat oder halt einen delphi code mit dem sich das errechnen lässt
Um nochmal auf mein ursprüngliches "Problem" zu kommen: ich hätte gern die kleinstmögliche, rechtwinklige bounding box um eine geometrie aus vertices.

* Mit netzparallel meine ich parallel zum absoluten Koordinatensystem also über die min/max x,y und z werte aller punkte.

Gruß und danke schonmal

Wölfchen

PS: allen einen guten Rutsch!

Also bist du sicher das du dies wirklich benötigst? Es dürfte wesentlich einfacher sein eine entsprechende Box von Hand zu generieren.
Schau dir beispielsweise den Aufwand für den einfachen Approximationsalgorithmus im Paper an: O(n log n + n / µ^3)
Angenommen du willst eine Lösung die nicht mehr als 5% von der optimalen Lösung abweicht berechnen, dann ist µ = 0.05. Bei einem Mesh mit sagen wir n=1000 Vertices wird dann n / µ^3 plötzlich zu 8.000.000. Das ganze ist nur deshalb "effizient", weil der Faktor 8000 nicht von der Anzahl der Vertices abhängt. In der Informatik ist alles "effizient" solange nur die Laufzeit noch als Polynom ausgedrückt werden kann

Vorschlag:
Generiere dir eine "netzparallele BoundingBox" für dein Mesh. Ich nenne die mal AABB (AxisAlignedBoundingBox). In den vielen Fällen ist das bereits die optimale Box, da die Objekte im Modelingprogramm normalerweise bereits nach den Achsen ausgerichtet sind. Passt sicher nicht bei jedem Objekt, aber für Autos, Personen und Keksdosen sollte das z.B. passen.
Wenn du nun dein Mesh transformierst (z.B. rotierst) müsstest du normalerweise eine neue AABB berechnen. Diese wird dann üblicherweise unnötig groß, zumindest wenn nur du eine AABB der transformierten Eckpunkte der ursprüngliche AABB generierst.
Stattdessen könntest du aber die ursprüngliche AABB mit der Transformationsmatrix deines Meshes kombinieren und so eine OBB (OrientatedBoundingBox) erhalten. Damit hast du einen Mittelweg aus schneller Berechnung und optimalem Volumen.

Übrigens kannst du eine OBB wie eine AABB behandeln, wenn du einfach die Welt mit der inversen Transformationsmatrix der OBB transformierst. Also nicht die BoundingBox drehen, sondern die Welt.

_________________
Yeah!

Danke erstmal für die Antwort.
Warum ich nach der "kleinstmöglichen" Box frage hat einen eher wirtschaftlichen Aspekt, der Gedanke geht in die Richtung für beliebig komplexe Bauteile und Baugruppen die kleinstmögliche Verpackung zu ermitteln. Ich komme aus der Maschinenbau Konstruktion und da interessiert es die Kalkulatoren und Logistiker öfter einmal wieviele Bauteile sie in eine Box bekommen, wie große die zu wählende Transportbox zu sein hat, und damit dann wieviele davon in einen LKW passen. Daher meine Frage. Über die erforderliche Genauigkeit der Box kann man sicher nachdenken, sie darf meinetwegen bis zu 15% zu groß sein, aber niemals zu klein. Mit einem entsprechenden Algorythmus könnte man dann auch für bewegliche Baugruppen den idealen Anlieferzustand errechnen, der zwar oft, aber eben nicht immer offensichtlich ist.

Gut, in der Logistik geht es natürlich um Geld...da lohnt es sich immer etwas Gehirnschmalz und Rechenleistung zu invertieren. Der normale Hobby-Computergrafiker im Einsteiger-Forum braucht sich damit aber üblicherweise nicht auseinandersetzen

Also mir ist da kein Algorithmus bekannt und mir fällt auch Anhieb keine sinnvollere Methode als BruteForce ein. Also BruteForce heißt einfach alle mögliche Rotationen in Schritten von sagen wir 5 Grad ausprobieren: Jeweils das Mesh rotieren und die AABB berechnen. Am Ende nimmst du die Rotation mit dem kleinsten Volumen. Du kannst natürlich dann beim kleinsten Volumen nochmal die Umgebung in kleineren Schritten absuchen um das Ergebnis zu verbessern.

Wahrscheinlich ist es aber das beste einfach den Algorithmus aus dem Paper zu implementieren. (Wobei ich das Paper nicht gelesen habe.)

_________________
Yeah!

Womit wir wieder bei den Einsteigerthemen wären *gg*
a) weiss ich net wie ich was drehe, so das sich auch wirklich die Koordinaten ändern.... (ich müsste ja nach jeder drehung neue min maxes ermitteln)
b) kann ich C noch weniger als Delphi also überhaupt nicht

aber neues Jahr, neues Glück, werde mir irgendwas basteln...

Hey,

du hast doch noch die glSupport-Unit von mir, damut kannst du deine Vertecs um ne Achse drehen. mach das einfach so wie ich mit den Achsen in dem Prog, bloß halt mit dn Vertecs...

MfG Bergmann

_________________
Aktuelle Projekte: BumpMapGenerator, Massive Universe Online
Auf meiner Homepage gibt auch noch paar Projekte und Infos von mir.

Kann es sein, dass bei einem Polygon-Model immer eine Fläche parallel zu einer Seite der minimalen Boundingbox ist?
Wenn das so wäre bräuchte man die Lage nur für nur alle Flächen testen. Also man wählt eine Fläche, dann berechnet man den Abstand aller Punkte zu der Ebene auf der das Dreieck (oder allgemein Vieleck) liegt. Dadurch hab man dann schon eine Abmessung der Box. Dann macht man das ähnlich für die Kanten, die man bekommt wenn man das Model auf die Ebene projiziert. Und die dritte Ausdehnung der "Schachtel" ergibt sich dann zwangsweise. Aus allen möglichen Kombinationen wählt man dann einfach das Minimum der Produkte.
Das funktioniert natürlich nur für konvexe Modelle. Man müsste also Konkave erst umwandeln. Logischerweise ändert das Umwandeln, was das Volumen des Models größer werden lässt, aber nichts an der kleinst möglichen BoundingBox, weil diese selbst konvex ist.

Hey,

hab grad noch ne andere Idee. Alle Abstände zwischen den Punkten berechnen, un den größsten als Achse betrachten. Dann die Orthogonale zu der Achse berechnen und wieder das Paar suchen was parallel zu der Achse ist und einen Maximalen Abstand hat. Das ganze dann noch für die 3. Achse und man sollte die minimale Box haben...

MfG

p.s.: Frohes Neues...

_________________
Aktuelle Projekte: BumpMapGenerator, Massive Universe Online
Auf meiner Homepage gibt auch noch paar Projekte und Infos von mir.

Ein gang in die Bibliothek dürfte beim OBB Problem helfen . Code konnte ich auch keinen finden.

Ich glaub nicht das es so einfach ist. Immer den größsten Abstand nehmen ist auch irgendwie komisch, wenn man eine minimale Box sucht. Für das Trapez im Anhang funktioniert das zB nicht.

Stimmt, aber ich denke des Ansatz über die Achsen/Vectoren is nich schlecht, oder?

_________________
Aktuelle Projekte: BumpMapGenerator, Massive Universe Online
Auf meiner Homepage gibt auch noch paar Projekte und Infos von mir.

1. Aus der Menge der Punkte muss man das ideal konvexe Polygon ermitteln und sich die einzelnen Dreiecksflächen davon merken (als Ebene in Form von Stützvektor und Normale).

2. Für die erste Kante reicht es alle Punkte auf die Normale der aktuell betrachteten Ebene zu projezieren und sich den Punkt mit der größten projektionsdistanz zu merken. Die Normale ist die Kante und die Projektionsdistanz seine Länge.

3. Man projeziert die Punkte auf die aktuell betrachtete Ebenen und ermittelt den Punkt mit der größten Distanz. Dieser Vektor ist die zweite gesuchte Kante der Boundingbox. Um die Länge der Kante zu ermitteln müssen jetzt wieder alle Punkt auf die frisch ermittelte Kante projeziert werden. man sucht hierbei die größt mögliche Distanz zwischen dem Punkt der die Kante erzeugt und den restlichen Punkten.

4. Für die Dritte Kante wird das Kreuzprodukt der ersten beiden Kanten berechnet (normieren nicht vergessen). Auf diesen Vektor werden alle Punkte projeziert und wieder kleinster und größter ermittelt. die Distanz zwischen den beiden stellt die Länge der letzten Kante dar.
Aus den drei Kanten, ihrer Längen und dem alten Mittelpunkt kann man jetzt den tatsächlichen BoundingBoxmittelpunkt errechnen. Das Produkt der Kantenlängen ist das Volumen der Boundingbox (da seine Kanten orthogonal sind).

Diesen Vorgang wiederholt man für jede Ebene der idealkonvexen Polygonhülle. Ist das Volumen der aktuellen Boundingbox kleiner als das der vorherigen, dann wird die alte Boundingbox mit der neuen überschrieben, ansonsten passiert nichts. am Ende sollte die kleinste Boundingbox als Resultat bereitstehen.

_________________
Klar Soweit?

Das ist genau das was ich ansatzweise oben beschrieben habe. Heißt das jetzt, dass meine Vermutung von oben stimmt? So wie du das beschreibst klingt das jedenfalls so als wäre das bewiesen.

ja das stimmt. Es ist der gleiche Ansatz, nur etwas ausführlicher. Mir steckt wohl das Neujahr noch in den Knochen.
Bewiesen ist die Idee nicht, allerdings macht es in meinem Kopf Sinn das Problem so zu lösen.

Falsch wird es wohl nicht sein...

_________________
Klar Soweit?