Hi Leute, ich habe hier eine eher geometrische Frage. Da ich gerade sowas wie eine Editor-Engine versuche, die ich nach und nach ausbauen kann bin ich irgendwann auch zu der Frage gekommen wie ich wohl herausfinden kann welches Objekt ich angeklickt habe.
Bevor jetzt jemand sagt, das geht mit OpenGL ganz einfach:
- Ich will jede beliebige API benutzen können, meintwegen auch mal Glide
- Objekte sollen auch selektiert werden, wenn ich leicht daneben klicke; bei Punkten fundamental wichtig
- Hintereinanderliegende Objekte sollen auch der Reihe nach 'durchgeklickt' werden können, wofür ich eine Liste aller, nicht nur des nächsten Objekts brauche

Ich habe mich also für bounding spheres entschieden, weil sie wenig Speicher brauchen (4 floats) und leicht zu prüfen sind (Distanz zum Mittelpunkt < Radius). Nun musste ich feststellen, dass es nicht gerade trivial ist die kleinste Kugel um eine bliebige Zahl von Eckpunkten zu finden, habe aber jetzt einen funktionierenden Ansatz.

Meine Frage an euch:
Habt ihr schon Erfahrungen damit? Sei es für Selektionen oder zur Sichtbarkeitsberechnung. Soll ich den Ansatz weiter verfolgen oder lohnen sich bounding boxes mehr, die ja schneller berechnet werden, aber m.M.n. länger zum Prüfen brauchen?
Ich ziehe auch eine Näherung an die optimale bounding sphere in Betracht, um den Overhead beim Erstellen/Modifizieren von Objekten zu verringern.

du willst die kleinste kugel um ein vertex bestimmen ?

du berechnest den schwerpunkt des objektes oder des vertex und gehst dann alle punkte durch, du nimmst dann den punkt mit dem größten abstand zum schwerpunkt und subtrahierst diesen vom mittelpunkt, die länge des resultierenden vektors ist dein radius und der schwerpunkt der mittepunkt deiner kugel.

wenn es net explizit um opengl geht, warum postest du dann in der opengl sparte ?

mfg

Warum ich hier poste? Weil darunter steht: "Bitte nur Fragen zur Programmierung von OpenGL, Effekten oder 3D-Techniken im allgemeinen posten."

Danke, das du mir geantwortet hast, aber der Schwerpunkt ist nicht der Mittelpunkt der Kugel! Wenn es doch so einfach wäre.
Beim Schwerpunkt zählen alle Punkte, bei der kleinsten Kugel nur die (maximal) vier äußersten Punkte, die die Kugel aufspannen. Das Paradox: Diese Punkte kann ich erst bestimmen, wenn ich das Zentrum der Kugel habe für das ich aber freilich die vier Punkte brauche für die ich das Zentrum brauche, um festzustellen, dass sie die vier äußeren Punkte sind... usw. Also bleibt nur Trial&Error mit ein paar Optimierungen.

P.S.: Wenn jemand einen Algorithmus hat, der aus 4 Eckpunkten den Umkreismittelpunkt errechnet - immer her damit!

mag sein, dass man noch eine kleinere kugel finden kann, bin mir jetzt aber nicht sicher, aber ist die methode nicht ausreichend ?

Hey, DU hast gesagt, das sei der Algorithmus für die kleinste Kugel. Ob der Algo ausreichend für meine Zwecke ist, ist eine andere Frage. Hmm, wenn ich mir so verschiedene 3D-Objekte ausdenke finde ich kaum was, was einen besonders ungünstigen Schwerpunkt hat, also vermutlich hast du Recht.
Nichts desto trotz fände ich eine exakte Berechnung nützlich, also guck ich mal ob noch jemand was schreibt. Thx erstmal.

Ich hab das mal ausprogrammiert, allerdings habe ich da auch einen Sourcecode von irgendwo verwendet und nur an meine Bedürfnisse angepasst und auch nicht so 100% verstanden :-). Die Quelle die ich verwendet habe, wo das etwas besser erklärt war, finde ich nicht mehr (ich glaube die ist mittlerweile gar nicht mehr Open Source), aber eine ganz ähnliche Implementierung findest du hier: http://magnum.dimajix.de/source/geometry/geometry.spherelimiter.inl

Mit den Templates wohl teilweise etwas ungut zum lesen, aber zumindest das Teil mit den 4 gegebenen Punkten solltest du halbwegs übernehmen können. Die Funktion nennt sich dort exactSphere4.

Jo danke! Echt super, genau sowas habe ich gesucht. Ich habe gestern Kopfschmerzen bekommen beim Matrizen invertieren und Determinanten berechnen ^^. Templates hab ich auch im Code ... nur heißen die $IFDEF SINGLE_PRECISION und $IFDEF DOUBLE_PRECISION
Der Algorithmus für 3 Punkte ist ja auch dabei. Umso besser, dann habe ich auch einen Rückfallmechanismus wenn die 4 Punkte auf einer Ebene liegen.

So Leute, ich habe nicht locker gelassen und lange verschiedene Algorithmen entwickelt und ausprobiert. Darunter auch ein Iterationsverfahren und eine Brute-Force Lösung. Letztere war bei 100 Punkten schon mit 1/4 Sekunde dabei, weil sie vier verschachtelte Schleifen verwendete. Laufzeit also O(n^4). Das Iterationsverfahren lief wesentlich schneller und das tolle: Man kann bei Iterationsverfahren immer selbst bestimmen, wie genau man es braucht. Interessanter weise lief dieses jedoch bei akzeptabler Genauigkeit wesentlich langsamer wie das was ich jetzt verwenden werde.
Das Grundgerüst hat eine O(n)-Laufzeit. Unter gewissen Umständen muss jedoch ein Codeteil wiederholt werden, weshalb der Graph nicht gerade verläuft.

Im Moment habe ich noch Probleme mit Rundungsungenauigkeiten, die oft dazu führen, dass ungültige Zustände erreicht werden, deshalb veröffentliche ich den Source hier nicht.

Hallo NerdIII,

eine sehr einfaches Verfahren zur Berechnung einer Bounding Sphere findest du hier : http://wiki.delphigl.com/index.php/Bounding_Sphere.
Es reicht aus die Bounding Box deines Objektes zu berechnen und den Mittelpunkt als Mittelpunkt der Bounding Sphere zu verwenden (mit der halben Raumdiagonalen als Radius).

Viele Grüße
dj3hut1

Das ist aber nicht notwendigerweise die kleinste Umkugel

@the-winner

du hast natürlich Recht, aber dieses Verfahren liefert in den meisten Fällen eine gute und schnelle Lösung.

Ich denke, dass es für eine Echtzeitandwendung wie z.B. einem Editor nicht unbedingt nötig ist, eine absolut perfekte Bounding Sphere zu berechnen, um einen "Klickradius" zu bestimmen, sondern dass es eher darauf ankommt, eine gute Näherungslösung in effizienter Zeit zu berechnen.

Viele Grüße
dj3hut1

Nun um die Beste Boundingsphere zu finden sollte man etwa so vorgehen (Denk ich zumindest):

Als erstes werden die 2 Punkte gesucht, die am weitesten von einander entfernt sind. Diese liegen auf der Kugeloberfläche (zumindest kann ich mir nicht vorstellen wie ich pukte so verteilen kann das die mit dem größtem Abstand nicht auf dem kleinstmöglichen Kreis oder Kugel befinden.)

Nun müssen alle Punkte verworfen werden, die innerhalb der kleinstmöglichen Kugel zu finden sind. Von dene die überbleiden wird der mit dem gößtem Abstand zu den bekannten gesucht. Mit diesn 3 Punkten wird eine neue Sphere erzeugt (Kleinste Kugel aus 3 Punkten. Die Sphere kann dabei nur in eine richtung verößert werden, da sonst zwei treffer in diesem durchgang einengrößeren abstand hätten als im erstem durchgang)

Da nun zwar 3 Punkte bekannt sind, bleiben nurn noch ein freiheisgrad zu viel: Wieder wird aus der Punkt ausgesucht der von allen andern am weitesten entfernt ist. DIeser ist dann der 4. un d letzte Punkt reicht aus um eine enin deutige Sphere zu konstruieren, Allderding kann es beim 3. oder 4. Punkt passieren dass keiner mehr außerhalb der aktuellen sphere zu finden ist, dann kann der algoritmus früher abgebrochen werden....

Allein das würde aber bereits eine O(n²) Laufzeit bedeuten, obwohl man das sicherlich auch etwas optimieren könnte. Vielleicht kann ja NerdIII noch ein paar Worte über seinen Algorithmus verlieren und uns die Weisheit für einen Algorithmus mit durchschnittlicher Laufzeit von O(n) mitteilen :-).

Soweit ich das damals mit bekommen habe ging es bei dem Algorithmus den ich verwendet habe etwa so:
Nimm 2 zufällig ausgewählte Punkte und mach die minimale Bounding Sphere.
Hol einen 3ten Punkt herein (den du noch nicht betrachtet hast), schau ob er innerhalb oder ausserhalb der Kugel liegt.
Ausserhalb => Verwende den 3ten Punkt ebenfalls als Stützpunkt
Innerhalb => nächster Punkt

Teilweise kommt man dann (wie NerdIII bereits gesagt hat) auf bis zu 4 Stützpunkte. Wenn du alle Punkte durchlaufen hast, dann hast du höchst wahrscheinlich bereits eine sehr gut angenäherte Sphere. Danach zur Sicherheit noch mal alle Punkte überprüfen wenn mans genau wissen will und das war.

Um mit absoluter Sicherheit die minimale Bounding Sphere zu erhalten bedarf es aber wohl einen O(n^4) Algorithmus. Also der obere Algorithmus kann denke ich (nicht getestet) schon mal versagen wenn die Punkte halbwegs so wie die Oberfläche einer Kugel verteilt sind (mit kleinen Abweichungen). In diesem Fall rennt der obere Algorithmus entweder ziemlich lange wenn mans genau wissen will, oder aber man vergleicht wirklich jedes 4er Pärchen von Punkten (=> n^4). Ein anderer sehr unguter Fall für den oberen Algorithmus ist, wenn alle Vertices schön auf einem Haufen sind und nur 1 oder wenige extreme Ausreisser dabei sind ... das hab ich damals einige male am eigenen Leib zu spüren bekommen.

Wenn man 4 Punkte auf einer Kugeloberfläche gefunden hat und alle anderen drin sind, gibt es keine kleinere Kugel mehr.
Das Wichtigste wäre bei einem algoritmuss alle Punkte ausscheiden zu lassen, die garnatiert nicht auch der Oberfläche liegen. Denkbar wäre ein algoritmus der zuerst den Schwerpunkt berechnet und anschließend von innen heraus so viele Punkte wie möglich eleminiert. Hier wird nur O(2n) verbraucht. Auf jedenfall ist der Punkt, der am weitesten vom Schwerpunkt entfernt ist ein. Sehr guter Kandidat für einen Stützpunkt (eventuell könnte man beweisen, das er ein Stützpunkt ist), hat man diesen ersten punkt kann man nach dem zweiten suchen, dies kostet ebenfalls nur O(2n) für den 3. und 4 müsste man ebenfalls so handeln, so das der such aufwand nur proportional zu der anzahl der Punkte steigt. Prinzipell lässt sich das wieder an einem anderem algorimus zeigen:

alle Punkte werden wahlos in 4er gruppen aufgeteilt, welche eine Sphere erzeugen, nun werden immer Speheren durch eine gemeinsame Boundingsphere ersetzt (für 8 Punte ist der aufwand ja konstant, die 4 eingeschlossenen Punkte werden dabei verworfen) mit jedem Durchlauf halbiert sich die Anzahl der Spheren, so das der aufwand wohl mit O(log(n)) angegeben werden muss, was meiner Ansicht nach fast so gut wie O(n) ist.

Wie NerdIII ja gezeigt hat lässt sich offenbar im allgemeinen Fall ein durchschnittlicher Rechenaufwand von O(n) finden. Deinem Algorithmus im Sinne von zuerst Schwerpunkt finden, dann den am weitesten entfernten suchen und _hoffen_ dass es ein Stützpunkt ist wiederspreche ich mit dem Gegenbeispiel:
Viele viele Punkte auf einem Haufen. 1 Punkt am weitesten weg vom Haufen aus gesehen, 2 Punkte ziemlich weit weg, so das sie auf der minimalen Bounding Sphere liegen, jedoch vom Haufen aus gesehen weniger weit weg sind als der vorher genannte am weitesten entfernte Punkt.

Natürlich zielt ein Algoirthmus der die optimale minimale Bounding Sphere finden möchte erst mal darauf ab möglichst viele Vertices zu eliminieren. Warum tut er das? Weil es im durchschnittlichen Fall einfacher ist weniger Punkte prüfen zu müssen als mehr. Wenn man aber mit wenigen Punkten (zB 4) recht einfache Beispiele geben kann, wo man mit einem gegebenen Algorithmus alle Punkte mit allen vergleichen muss, so liegt die Annahme nicht allzu fern, dass es auch mit mehr Punkten Beispiele gibt wo der Aufwand enstprechend groß ist.

Ich will nicht behaupten, dass der Aufwand wirklich O(n^4) ist, weil ich mich diesbezüglich zu wenig auskenne. Aber bevor ich etwas anderes glaube muss mir jemand das Gegenteil beweisen.

Aus meinen vorigen Annahmen folgt auch mein obiges Beispiel wo alle Punkte annähernd auf einer Kugel liegen, ansonnsten sind meine Annahmen beispielsweise durch Punkt-Ausschluss-Algorithmen wie du einen genannt hast zu wiederlegen.