commit dfa491bea05931c905973f3a5590146c6d324600
parent af469d3e1a376b7c0ee5ea8d810d42bc38447fb1
Author: Mikolaj Lenczewski <33129490+EnderRifter@users.noreply.github.com>
Date: Mon, 8 Jul 2019 12:36:21 +0100
completely fixed barnes-hut bug
Diffstat:
6 files changed, 31 insertions(+), 107 deletions(-)
diff --git a/StarSim/StarSim/Program.cs b/StarSim/StarSim/Program.cs
@@ -104,8 +104,6 @@ namespace StarSim
bodyDrawer.DrawBodies();
- ulong frameCounter = 0;
-
while (window.IsOpen)
{
window.Clear();
@@ -114,14 +112,11 @@ namespace StarSim
if (!inputHandler.IsSimulationPaused)
{
bodyPositionUpdater(bodies, Constants.TimeStep);
- Console.WriteLine($"Finished physics frame: {frameCounter++}");
}
bodyDrawer.DrawBodies();
window.Display();
-
- //Console.Read();
}
Console.WriteLine("Goodbye, World!");
diff --git a/StarSim/StarSimLib/Constants.cs b/StarSim/StarSimLib/Constants.cs
@@ -13,7 +13,7 @@ namespace StarSimLib
/// <summary>
/// The amount of bodies that are rendered by default.
/// </summary>
- public const int BodyCount = 10;
+ public const int BodyCount = 100;
/// <summary>
/// The mass of the central body, if it is included.
diff --git a/StarSim/StarSimLib/Data Structures/Octant.cs b/StarSim/StarSimLib/Data Structures/Octant.cs
@@ -188,42 +188,42 @@ namespace StarSimLib.Data_Structures
{
case PositionSpecifier.TopNorthWest:
return GetOrSetChildOctant(ref childOctants, 0,
- midpoint + new Vector4(-halfSideLength, +halfSideLength, +halfSideLength),
+ midpoint + new Vector4(-quarterSideLength, +quarterSideLength, +quarterSideLength),
halfSideLength);
case PositionSpecifier.TopNorthEast:
return GetOrSetChildOctant(ref childOctants, 1,
- midpoint + new Vector4(+halfSideLength, +halfSideLength, +halfSideLength),
+ midpoint + new Vector4(+quarterSideLength, +quarterSideLength, +quarterSideLength),
halfSideLength);
case PositionSpecifier.TopSouthEast:
return GetOrSetChildOctant(ref childOctants, 2,
- midpoint + new Vector4(+halfSideLength, +halfSideLength, -halfSideLength),
+ midpoint + new Vector4(+quarterSideLength, +quarterSideLength, -quarterSideLength),
halfSideLength);
case PositionSpecifier.TopSouthWest:
return GetOrSetChildOctant(ref childOctants, 3,
- midpoint + new Vector4(-halfSideLength, +halfSideLength, -halfSideLength),
+ midpoint + new Vector4(-quarterSideLength, +quarterSideLength, -quarterSideLength),
halfSideLength);
case PositionSpecifier.BottomNorthWest:
return GetOrSetChildOctant(ref childOctants, 4,
- midpoint + new Vector4(-halfSideLength, -halfSideLength, +halfSideLength),
+ midpoint + new Vector4(-quarterSideLength, -quarterSideLength, +quarterSideLength),
halfSideLength);
case PositionSpecifier.BottomNorthEast:
return GetOrSetChildOctant(ref childOctants, 5,
- midpoint + new Vector4(+halfSideLength, -halfSideLength, +halfSideLength),
+ midpoint + new Vector4(+quarterSideLength, -quarterSideLength, +quarterSideLength),
halfSideLength);
case PositionSpecifier.BottomSouthEast:
return GetOrSetChildOctant(ref childOctants, 6,
- midpoint + new Vector4(+halfSideLength, -halfSideLength, -halfSideLength),
+ midpoint + new Vector4(+quarterSideLength, -quarterSideLength, -quarterSideLength),
halfSideLength);
case PositionSpecifier.BottomSouthWest:
return GetOrSetChildOctant(ref childOctants, 7,
- midpoint + new Vector4(-halfSideLength, -halfSideLength, -halfSideLength),
+ midpoint + new Vector4(-quarterSideLength, -quarterSideLength, -quarterSideLength),
halfSideLength);
default:
diff --git a/StarSim/StarSimLib/Data Structures/OctantTree.cs b/StarSim/StarSimLib/Data Structures/OctantTree.cs
@@ -24,11 +24,6 @@ namespace StarSimLib.Data_Structures
private Body body;
/// <summary>
- /// The total number of bodies held in this instance.
- /// </summary>
- private int bodyCount;
-
- /// <summary>
/// The point at which all the mass seems to be concentrated.
/// </summary>
private Vector4 centreOfAggregateMass;
@@ -45,11 +40,6 @@ namespace StarSimLib.Data_Structures
public OctantTree(Octant octant)
{
this.octant = octant;
- body = null;
-
- bodyCount = 0;
- aggregateMass = 0;
- centreOfAggregateMass = new Vector4();
childTrees = new OctantTree[8];
}
@@ -76,20 +66,21 @@ namespace StarSimLib.Data_Structures
private void AddToChildTree(Body newBody)
{
- for (int subTreeIndex = 0; subTreeIndex < 8; subTreeIndex++)
+ // don't create subtrees if it violates the minimum width limit, to prevent infinitely deep trees and thus
+ // preventing excessive resource allocation
+ if (octant.Length / 2 < Constants.MinimumTreeWidth)
{
- Vector4 subtreeLocation = octant[subTreeIndex].Midpoint;
+ return;
+ }
+
+ for (int childTreeIndex = 0; childTreeIndex < 8; childTreeIndex++)
+ {
+ OctantTree childTree = SubTree(childTreeIndex);
- // determine if the body is contained within the bounds of the subtree under
- // consideration
- if (Math.Abs(subtreeLocation.X - newBody.Position.X) <= octant.Length / 2
- && Math.Abs(subtreeLocation.Y - newBody.Position.Y) <= octant.Length / 2
- && Math.Abs(subtreeLocation.Z - newBody.Position.Z) <= octant.Length / 2)
+ // if the child tree under consideration contains the given body, then add it to that tree
+ if (childTree.octant.ContainsPoint(newBody.Position))
{
- if (childTrees[subTreeIndex] == null)
- childTrees[subTreeIndex] =
- new OctantTree(octant[subTreeIndex]);
- childTrees[subTreeIndex].AddBody(newBody);
+ childTree.AddBody(newBody);
return;
}
}
@@ -125,23 +116,12 @@ namespace StarSimLib.Data_Structures
{
centreOfAggregateMass = (aggregateMass * centreOfAggregateMass + newBody.Mass * newBody.Position) / (aggregateMass + newBody.Mass);
aggregateMass += newBody.Mass;
- bodyCount++;
- if (bodyCount == 1)
+ if (body == null)
{
// this is an empty instance that has not yet had any bodies added to it.
body = newBody;
}
- else
- {
- AddToChildTree(newBody);
-
- if (bodyCount == 2)
- {
- AddToChildTree(body);
- }
- }
- /*
else if (IsExternal())
{
// this instance is 'external' and contains another body. figure out where the new body should go and
@@ -156,14 +136,13 @@ namespace StarSimLib.Data_Structures
// any further child nodes
AddToChildTree(newBody);
}
- */
}
/// <summary>
/// Whether this instance does not have any child instances and is thus an 'external' octant tree, or not.
/// </summary>
/// <returns>Whether this instance has no non-null child instance.</returns>
- public bool IsExternal() => childTrees.All(tree => tree == null);
+ public bool IsExternal() => childTrees.All(tree => tree == null) && body != null;
/// <summary>
/// Returns the specified child octant tree instance.
@@ -224,62 +203,23 @@ namespace StarSimLib.Data_Structures
/// <param name="referenceBody">The body instance against which force updates are made.</param>
public void UpdateForces(Body referenceBody)
{
- /*
- if (IsExternal())
- {
- // since this tree instance is 'external' it has no children. we can treat it as a single body
- if (body != null && body != referenceBody)
- {
- referenceBody?.AddForce(body);
- }
- }
- else if (octant.Length / body.DistanceTo(referenceBody, out _) < Constants.TreeTheta)
- {
- // otherwise if the octant length divided by the distance to the body (the width to distance ratio) is
- // within a defined tolerance, we consider the tree to be effectively a single massive body
- if (body != null)
- {
- referenceBody?.AddForce(body);
- }
- }
- else
- {
- for (int i = 0; i < childTrees.Length; i++)
- {
- OctantTree tree = SubTree(i);
-
- if (body != null)
- {
- tree.UpdateForces(referenceBody);
- break;
- }
- }
-
- foreach (OctantTree subtree in childTrees)
- {
- subtree?.UpdateForces(referenceBody);
- }
- }
- */
-
+ // cache the distance between the centre of mass of this tree instance and the reference body
double dx = centreOfAggregateMass.X - referenceBody.Position.X;
double dy = centreOfAggregateMass.Y - referenceBody.Position.Y;
double dz = centreOfAggregateMass.Z - referenceBody.Position.Z;
double distance2 = dx * dx + dy * dy + dz * dz;
- // Case 1. The tree contains only one body and it is not the one in the
- // tree so we can perform the acceleration.
- //
- // Case 2. The width to distance ratio is within the defined tolerance so
- // we consider the tree to be effectively a single massive body and
- // perform the acceleration.
- if (bodyCount == 1 && referenceBody != body || octant.Length * octant.Length < Constants.TreeTheta * Constants.TreeTheta * distance2)
+ if (IsExternal() && referenceBody != body || octant.Length * octant.Length < Constants.TreeTheta * Constants.TreeTheta * distance2)
{
+ // since this tree instance is 'external' it has no children, we can treat it as a single body
+ // we can also treat it as a single body if the width of the octant squared is less that the predefined
+ // 'theta' (grouping tolerance) value times the distance between the centre of mass and the reference body
referenceBody.AddForce(Body.GetForceBetween(referenceBody, centreOfAggregateMass, aggregateMass));
}
- // Case 3. More granularity is needed so we accelerate at the subtrees.
else if (childTrees != null)
{
+ // otherwise we need to fall back to a more 'granular' approach, and get the force between individual
+ // child trees, as they are not far enough away to be considered as a single body
foreach (OctantTree subtree in childTrees)
{
subtree?.UpdateForces(referenceBody);
@@ -292,7 +232,7 @@ namespace StarSimLib.Data_Structures
/// <inheritdoc />
public override string ToString()
{
- return $"Tree - Octant: {octant?.ToString() ?? "null"}, Body: {body?.ToString() ?? "null"}, " +
+ return $"Tree - Octant: {octant?.ToString() ?? "null"}, " +
$"TNW: {childTrees[0]?.ToString() ?? "null"}, TNE: {childTrees[1]?.ToString() ?? "null"}, " +
$"TSE: {childTrees[2]?.ToString() ?? "null"}, TSW: {childTrees[3]?.ToString() ?? "null"}, " +
$"BNW: {childTrees[4]?.ToString() ?? "null"}, BNE: {childTrees[5]?.ToString() ?? "null"}, " +
diff --git a/StarSim/StarSimLib/Physics/BodyUpdater.cs b/StarSim/StarSimLib/Physics/BodyUpdater.cs
@@ -36,8 +36,6 @@ namespace StarSimLib.Physics
{
if (body.IsInOctant(universeOctant))
{
- Console.WriteLine($"Body (during tree construction): {body}");
-
// only update a body's position if it is within the bounds of the universe
barnesHutTree.AddBody(body);
}
@@ -46,8 +44,6 @@ namespace StarSimLib.Physics
// we update the positions of the bodies in the populated tree
foreach (Body body in bodyEnumerable)
{
- Console.WriteLine($"Body (before position update): {body}");
-
if (body == null)
{
continue;
@@ -61,8 +57,6 @@ namespace StarSimLib.Physics
body.Update(deltaTime);
}
-
- Console.WriteLine($"Body (after position update): {body}");
}
}
diff --git a/StarSim/StarSimLib/StarSimLib.xml b/StarSim/StarSimLib/StarSimLib.xml
@@ -586,11 +586,6 @@
The <see cref="T:StarSimLib.Data_Structures.Body"/> instance that is held in this instance, be it real or an aggregate.
</summary>
</member>
- <member name="F:StarSimLib.Data_Structures.OctantTree.bodyCount">
- <summary>
- The total number of bodies held in this instance.
- </summary>
- </member>
<member name="F:StarSimLib.Data_Structures.OctantTree.centreOfAggregateMass">
<summary>
The point at which all the mass seems to be concentrated.
