Zufällige 3D Vektoren innerhalb einer Kugel

314159265358979

Huhu,

Für das Spiel, an dem ich gerade arbeite, benötige ich zufällige Vektoren. Der Spieler bewegt sich innerhalb einer Kugel mit dem Radius 500.f. Man denke sich eine weitere Kugel mit dem Radius 1000.f und dem selben Zentrum. Nun benötige ich Zufallszahlen, die genau zwischen diesen beiden Kugeln liegen. Kann ich sowas irgendwie mit C++11 Mitteln erzeugen?

Grüße,
PI

CStoll

Du wählst drei Zahlen r zwischen 500 und 1000, alpha (0 bis 2*pi) und beta (0 bis pi/2) und verwendest sie als Kugelkoordinaten für deine Zielposition. Alternativ kannst du auch solange je drei Werte x, y, z (je -1000 bis 1000) ziehen, bis der gefundene Punkt im erlaubten Bereich liegt.

otze

oder, um mal den Finger in die Wunde zu legen:

Für manche Dinge braucht e snicht C++11 sondern einfache Mathematik.

314159265358979

Man müsste halt wissen, wie man sowas tut.

brotbernd

std::uniform_real<float> radiusDistribution(innerRadius, outerRadius);
std::uniform_real<float> alphaDistribution(0, 2*PI);
std::uniform_real<float> betaDistribution(0, 0.5*PI);

Die Methode mit Polarkoordinaten erzeugt auf den ersten Blick aber wohl auf kleineren Radien mehr Punkte. Oder?
Die zweite Methode hat sicher eine Gleichverteilung.

std::uniform_real<float> distribution(-outerRadius, outerRadius);

Vector test = RandomVector(sphere.Center, distribution, engine); 
float distance = Norm(sphere.Center - test);
if (distance < outerRadius && distance > innerRadius)
  AddPoint(test);

template<typename Dist, typename Engine>
Vector RandomVector(Vector v, Dist distribution, Engine eng)
{
  v.x += distribution(eng);
  v.y += distribution(eng);
  v.z += distribution(eng);
  return v;
}

SeppJ

@brotbernd, CStoll: Eure Methoden erzeugen beide keine Normalverteilungen. brotbernd ist da schon auf der richtigen Spur, aber deine Methode kann ich überhaupt nicht nachvollziehen. Schreibfehler oder übersehe ich da Sachen?

Man muss da drauf achten, dass die Anzahl möglicher Punkte mit dem Radius quadratisch zunimmt. Ich habe gerade keine Zeit, um das in Code zu gießen, aber ihr bekommt das bestimmt auch alleine hin.

CStoll

SeppJ schrieb:

@brotbernd, CStoll: Eure Methoden erzeugen beide keine Normalverteilungen.

Pi sagte etwas von "zufällig", nicht von "normalverteilt"

brotbernd ist da schon auf der richtigen Spur, aber deine Methode kann ich überhaupt nicht nachvollziehen. Schreibfehler oder übersehe ich da Sachen?

Das dürfte auf den Ansatz "wähle einen Punkt im umgebenden Würfel und prüfe, ob er gültig ist" hinauslaufen.

314159265358979

Ich brauche die Punkte ungefähr gleichverteilt. Aber natürlich sind Abweichungen okay, rand()-like Zufallszahlen wären gut genug.

Die Zahlen sollen als Positionen für kleine Kugeln genommen werden, die Sterne in meinem Weltraum darstellen.

Bashar

otze schrieb:

Für manche Dinge braucht e snicht C++11 sondern einfache Mathematik.

"einfache"? Ich hab grad keine Ahnung, wie das mathematisch gehen könnte.

SeppJ

Bashar schrieb:

otze schrieb:

Für manche Dinge braucht e snicht C++11 sondern einfache Mathematik.

"einfache"? Ich hab grad keine Ahnung, wie das mathematisch gehen könnte.

Grobe Erklaerung: Du suchst Zufallszahlen mit einer Vertielung p(y), wobei das Integral ueber p(y)dy auf 1 normiert ist. Dann kommt man nach etwas Rechnung da drauf, dass man auf 0:1 gleichverteilte Zufallszahlen x durch Anwendung der Funktion P^(-1)(x) auf die gewuenschte Verteilung p(y) transformieren kann. Dabei ist P das unbestimmte Integral von p und P(-1) dessen Umkehrfunktion. Im Allgmeinen ist der Knackpunkt da dran, dass die Funktion sich nicht einfach umkehren laesst, hier ist das bei der parabelfoermigen Verteilung der r-Koordinate aber noch einfach. Uebrigens muss man bei den theta und phi Koordinaten auch noch aufpassen, da man sonst mehr Werte an den Polen bekommt. Ist aber auf die Gleiche Art und Weise zu loesen.
Ich bin sicher, die allgemeine Transformation steht irgendwo bei Wikipedia. Und wie man gleichverteilte Punkte auf einer Kugelschlae zieht ist ein Standardproblem, dass man ueberall findet. Dann muss man nur noch eine passend verteilte Laenge ziehen, dann hat man es.

pumuckl

Bashar schrieb:

otze schrieb:

Für manche Dinge braucht e snicht C++11 sondern einfache Mathematik.

"einfache"? Ich hab grad keine Ahnung, wie das mathematisch gehen könnte.

Die Wahrscheinlichkeiten in den drei Distributionen müssten gewichtet werden, und zwar mit den Faktoren des Volumenelements.
d.h.:
phi_distribution: [0..2π), uniforme Verteilung
radius_distribution: [r1..r2], Verteilung geht mit r²
theta_distribution: [0..π], Verteilung geht mit sinθ

brotbernd

SeppJ schrieb:

@brotbernd, CStoll: Eure Methoden erzeugen beide keine Normalverteilungen. brotbernd ist da schon auf der richtigen Spur, aber deine Methode kann ich überhaupt nicht nachvollziehen. Schreibfehler oder übersehe ich da Sachen?

Die 2.Methode ist beliebig simpel. Ein gleichverteilten Punkt in einem Würfel ist sehr einfach. Zu prüfen, ob dieser Punkt innerhalb der Kugel liegt, die gerade in diesen Würfel passt ist auch sehr einfach. Die Punkte die innerhalb liegen merke ich mir, die die außerhalb liegen schmeiß ich weg.
Vielleicht kann man sich etwas kompliziertes und effizienteres überlegen, aber ich würde erstmal damit anfangen.

pumuckl

brotbernd schrieb:

Die Punkte die innerhalb liegen merke ich mir, die die außerhalb liegen schmeiß ich weg.
Vielleicht kann man sich etwas kompliziertes und effizienteres überlegen, aber ich würde erstmal damit anfangen.

KLar, nur wirfst du beim vorliegenden Fall, wo der innenradius = 1/2 Außenradius der Kugelschale ist, knapp 46% der Ergebnisse weg

Ich habe jetzt nicht alle Post gelesen daher könnte es sein, dass mein Vorschlag schon gesagt wurde.

Man kann doch jedem Punkt in einer Kugel mit 2 Winkeln und einem Skalar genau beschreiben. Daher müsste man doch nur 2 Zufallszahlen zwischen 0 und 360 erstellen und eine Zufallszahl zwischen 0 und r und damit wäre man fertig.

Bashar

bliblablid schrieb:

Ich habe jetzt nicht alle Post gelesen daher könnte es sein, dass mein Vorschlag schon gesagt wurde.

Ja, gleich als erste Antwort.

314159265358979

Ich habe dein Verfahren, SeppJ, leider nicht verstanden, denn wir haben Integralrechnung in der Schule auch noch nicht gemacht. Es wäre schön, wenn mir das jemand programmieren könnte.

Grüße

brotbernd

pumuckl schrieb:

KLar, nur wirfst du beim vorliegenden Fall, wo der innenradius = 1/2 Außenradius der Kugelschale ist, knapp 46% der Ergebnisse weg

Richtig. Aber wer sagt, dass das schlimm ist? Wenn am Anfang zur Initialisierung die Kugel in 2,17 ms statt in 1 ms mit zufälligen Punkten gefüllt wird, wen interessiert das?
Wenn das zu langsam ist, kann man sich immer noch was besseres ausdenken.

dot

Muss es denn tatsächlich eine exakte Gleichverteilung in einer Kugel sein? Ich mein, die Sterne am Nachthimmel sind jetzt auch nicht wirklich gleichverteilt, sogar ziemlich weit davon entfernt...

314159265358979

Naja, es sollten zumindest nirgens Lücken zu sehen sein.

cooky451

Wie wär's mit nem Würfel + Sichtschutz?