commit 73d0407a413799f3075c25516674e761756ba5d0
parent a9eb778eabc5ee1d86d2ee041dd706f01c632ae8
Author: Mikolaj Lenczewski <33129490+EnderRifter@users.noreply.github.com>
Date: Wed, 3 Jul 2019 23:19:49 +0100
Started on implementation of barnes hut algorithm.
Diffstat:
3 files changed, 337 insertions(+), 3 deletions(-)
diff --git a/StarSim/StarSimLib/Data Structures/Body.cs b/StarSim/StarSimLib/Data Structures/Body.cs
@@ -182,6 +182,16 @@ namespace StarSimLib.Data_Structures
}
/// <summary>
+ /// Whether this instance is currently inside the bounds of the given <see cref="Octant"/> instance.
+ /// </summary>
+ /// <param name="octant">The octant to check.</param>
+ /// <returns>Whether this <see cref="Body"/> instance is inside the given <see cref="Octant"/> instance.</returns>
+ public bool InOctant(Octant octant)
+ {
+ return octant.ContainsPoint(position);
+ }
+
+ /// <summary>
/// Resets the internal force vector.
/// </summary>
public void ResetForce()
diff --git a/StarSim/StarSimLib/Data Structures/Octant.cs b/StarSim/StarSimLib/Data Structures/Octant.cs
@@ -1,10 +1,205 @@
-namespace StarSimLib.Data_Structures
+using System;
+using System.Diagnostics;
+
+namespace StarSimLib.Data_Structures
{
/// <summary>
+ /// Enumerates the possible sub-octants positions.
+ /// </summary>
+ public enum PositionSpecifier
+ {
+ /// <summary>
+ /// The child octant in the top layer, north west corner.
+ /// </summary>
+ TopNorthWest,
+
+ /// <summary>
+ /// The child octant in the top layer, north east corner.
+ /// </summary>
+ TopNorthEast,
+
+ /// <summary>
+ /// The child octant in the top layer, south east corner.
+ /// </summary>
+ TopSouthEast,
+
+ /// <summary>
+ /// The child octant in the top layer, south west corner.
+ /// </summary>
+ TopSouthWest,
+
+ /// <summary>
+ /// The child octant in the bottom layer, north west corner.
+ /// </summary>
+ BottomNorthWest,
+
+ /// <summary>
+ /// The child octant in the bottom layer, north east corner.
+ /// </summary>
+ BottomNorthEast,
+
+ /// <summary>
+ /// The child octant in the bottom layer, south east corner.
+ /// </summary>
+ BottomSouthEast,
+
+ /// <summary>
+ /// The child octant in the bottom layer, south west corner.
+ /// </summary>
+ BottomSouthWest,
+ }
+
+ /// <summary>
/// Represents an octant of 3D space.
/// </summary>
public class Octant
{
- Vector4
+ /// <summary>
+ /// The length of a half of 1 side of this instance, used to provide the side length of child instances.
+ /// </summary>
+ private readonly double halfSideLength;
+
+ /// <summary>
+ /// The centre of this instance.
+ /// </summary>
+ private readonly Vector4 midpoint;
+
+ /// <summary>
+ /// The length of a quarter of 1 side of this instance, used to provide the midpoint of child instances.
+ /// </summary>
+ private readonly double quarterSideLength;
+
+ /// <summary>
+ /// The length of 1 side of this instance.
+ /// </summary>
+ private readonly double sideLength;
+
+ /// <summary>
+ /// The child octant instances of this instance.
+ /// </summary>
+ private Octant[] childOctants;
+
+ /// <summary>
+ /// Initialises a new instance of the <see cref="Octant"/> class.
+ /// </summary>
+ /// <param name="midpoint">The central midpoint of this instance.</param>
+ /// <param name="length">The length of 1 complete side of this instance.</param>
+ public Octant(Vector4 midpoint, double length)
+ {
+ this.midpoint = midpoint;
+ sideLength = length;
+ halfSideLength = length / 2;
+ quarterSideLength = length / 4;
+
+ childOctants = new Octant[8];
+ }
+
+ /// <summary>
+ /// The length of 1 complete side of this instance.
+ /// </summary>
+ public double Length
+ {
+ get { return sideLength; }
+ }
+
+ /// <summary>
+ /// Indexes this instance, shorthand for <see cref="SubOctant(PositionSpecifier)"/>.
+ /// </summary>
+ /// <param name="specifier">Which child octant instance to return.</param>
+ /// <returns>The specified child octant instance.</returns>
+ public Octant this[PositionSpecifier specifier]
+ {
+ get { return SubOctant(specifier); }
+ }
+
+ /// <summary>
+ /// Returns the specified child octant instance, or instantiates a new octant if the specified child instance
+ /// is <c>null</c>. The newly constructed instance will then be returned.
+ /// </summary>
+ /// <param name="octants">
+ /// A reference to the <see cref="Octant"/> array from which to get the specified instance.
+ /// </param>
+ /// <param name="index">The index in the array whose held instance to get or set.</param>
+ /// <param name="newMidpoint">The midpoint of the new child instance, if necessary.</param>
+ /// <param name="newSideLength">The side length of the new child instance, if necessary.</param>
+ /// <returns>The instance held at the specified index, or the newly created instance.</returns>
+ private static Octant GetOrSetChildOctant(ref Octant[] octants, int index, Vector4 newMidpoint, double newSideLength)
+ {
+ if (octants != null && octants?[index] == null)
+ {
+ octants[index] = new Octant(newMidpoint, newSideLength);
+ }
+
+ return octants?[index];
+ }
+
+ /// <summary>
+ /// Whether the given point is within the bounds of this instance.
+ /// </summary>
+ /// <param name="point">
+ /// The point whose position to check. Only the first 3 dimensions are used, the 4th is ignored.
+ /// </param>
+ /// <returns>Whether the given point is within the bounds of this instance.</returns>
+ public bool ContainsPoint(Vector4 point)
+ {
+ return point.X <= midpoint.X + halfSideLength && point.X >= midpoint.X - halfSideLength &&
+ point.Y <= midpoint.Y + halfSideLength && point.Y >= midpoint.Y - halfSideLength &&
+ point.Z <= midpoint.Z + halfSideLength && point.Z >= midpoint.Z - halfSideLength;
+ }
+
+ /// <summary>
+ /// Returns the specified child octant instance.
+ /// </summary>
+ /// <param name="specifier">Which child octant instance to return.</param>
+ /// <returns>The specified child octant instance.</returns>
+ public Octant SubOctant(PositionSpecifier specifier)
+ {
+ switch (specifier)
+ {
+ case PositionSpecifier.TopNorthWest:
+ return GetOrSetChildOctant(ref childOctants, 0,
+ midpoint + new Vector4(-quarterSideLength, +quarterSideLength, +quarterSideLength),
+ halfSideLength);
+
+ case PositionSpecifier.TopNorthEast:
+ return GetOrSetChildOctant(ref childOctants, 1,
+ midpoint + new Vector4(+quarterSideLength, +quarterSideLength, +quarterSideLength),
+ halfSideLength);
+
+ case PositionSpecifier.TopSouthEast:
+ return GetOrSetChildOctant(ref childOctants, 2,
+ midpoint + new Vector4(+quarterSideLength, +quarterSideLength, -quarterSideLength),
+ halfSideLength);
+
+ case PositionSpecifier.TopSouthWest:
+ return GetOrSetChildOctant(ref childOctants, 3,
+ midpoint + new Vector4(-quarterSideLength, +quarterSideLength, -quarterSideLength),
+ halfSideLength);
+
+ case PositionSpecifier.BottomNorthWest:
+ return GetOrSetChildOctant(ref childOctants, 4,
+ midpoint + new Vector4(-quarterSideLength, -quarterSideLength, +quarterSideLength),
+ halfSideLength);
+
+ case PositionSpecifier.BottomNorthEast:
+ return GetOrSetChildOctant(ref childOctants, 5,
+ midpoint + new Vector4(+quarterSideLength, -quarterSideLength, +quarterSideLength),
+ halfSideLength);
+
+ case PositionSpecifier.BottomSouthEast:
+ return GetOrSetChildOctant(ref childOctants, 6,
+ midpoint + new Vector4(+quarterSideLength, -quarterSideLength, -quarterSideLength),
+ halfSideLength);
+
+ case PositionSpecifier.BottomSouthWest:
+ return GetOrSetChildOctant(ref childOctants, 7,
+ midpoint + new Vector4(-quarterSideLength, -quarterSideLength, -quarterSideLength),
+ halfSideLength);
+
+ default:
+ throw new ArgumentOutOfRangeException(nameof(specifier), specifier,
+ "The given specifier is outside of the valid range.");
+ }
+ }
}
}
\ No newline at end of file
diff --git a/StarSim/StarSimLib/Data Structures/OctantTree.cs b/StarSim/StarSimLib/Data Structures/OctantTree.cs
@@ -1,9 +1,138 @@
-namespace StarSimLib.Data_Structures
+using System;
+using System.Linq;
+
+namespace StarSimLib.Data_Structures
{
/// <summary>
/// A tree of <see cref="Octant"/> instances, where each node has 8 children.
/// </summary>
public class OctantTree
{
+ /// <summary>
+ /// The <see cref="Octant"/> of space managed by this instance.
+ /// </summary>
+ private readonly Octant octant;
+
+ /// <summary>
+ /// The <see cref="Body"/> instance that is held in this instance, be it real or an aggregate.
+ /// </summary>
+ private Body body;
+
+ /// <summary>
+ /// The child octant tree instances of this instance.
+ /// </summary>
+ private OctantTree[] childTrees;
+
+ /// <summary>
+ /// Initialises a new instance of the <see cref="OctantTree"/> class.
+ /// </summary>
+ /// <param name="octant">The <see cref="Octant"/> instance representing the space managed by this instance.</param>
+ public OctantTree(Octant octant)
+ {
+ this.octant = octant;
+
+ childTrees = new OctantTree[8];
+ }
+
+ /// <summary>
+ /// Indexes this instance, shorthand for <see cref="SubTree(PositionSpecifier)"/>.
+ /// </summary>
+ /// <param name="specifier">Which child octant tree instance to return.</param>
+ /// <returns>The specified child octant tree instance.</returns>
+ public OctantTree this[PositionSpecifier specifier]
+ {
+ get { return SubTree(specifier); }
+ }
+
+ /// <summary>
+ /// Returns the specified child octant tree instance, or instantiates a new octant tree if the specified child
+ /// instance is <c>null</c>. The newly constructed instance will then be returned.
+ /// </summary>
+ /// <param name="trees">
+ /// A reference to the <see cref="OctantTree"/> array from which to get the specified instance.
+ /// </param>
+ /// <param name="index">The index in the array whose held instance to get or set.</param>
+ /// <param name="newOctant">
+ /// The octant instance representing the space managed by the new child tree instance, if necessary.
+ /// </param>
+ /// <returns>The instance held at the specified index, or the newly created instance.</returns>
+ public static OctantTree GetOrSetSubTree(ref OctantTree[] trees, int index, Octant newOctant)
+ {
+ if (trees != null && trees?[index] == null)
+ {
+ trees[index] = new OctantTree(newOctant);
+ }
+
+ return trees?[index];
+ }
+
+ /// <summary>
+ /// Adds the given <see cref="Body"/> instance to this tree instance or a child tree instance.
+ /// </summary>
+ /// <param name="newBody">The <see cref="Body"/> instance to add.</param>
+ public void AddBody(Body newBody)
+ {
+ if (body == null)
+ {
+ // this is an empty instance that has not yet had any bodies added to it.
+ body = newBody;
+ }
+ else if (!IsExternal())
+ {
+ // this instance already has a body to represent it, and it is not an 'external' tree instance, that is
+ // it has child trees of its own. figure out in which child tree the new body should be stored and update
+ // any further child nodes with recursion
+ }
+ else if (IsExternal())
+ {
+ // this instance is 'external' and contains another body. figure out where the new body should go and
+ // create a new octant tree instance to hold the new body. no recursion is necessary
+ }
+ }
+
+ /// <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);
+
+ /// <summary>
+ /// Returns the specified child octant tree instance.
+ /// </summary>
+ /// <param name="specifier">Which child octant tree instance to return.</param>
+ /// <returns>The specified child octant tree instance.</returns>
+ public OctantTree SubTree(PositionSpecifier specifier)
+ {
+ switch (specifier)
+ {
+ case PositionSpecifier.TopNorthWest:
+ return GetOrSetSubTree(ref childTrees, 0, octant?[specifier]);
+
+ case PositionSpecifier.TopNorthEast:
+ return GetOrSetSubTree(ref childTrees, 1, octant?[specifier]);
+
+ case PositionSpecifier.TopSouthEast:
+ return GetOrSetSubTree(ref childTrees, 2, octant?[specifier]);
+
+ case PositionSpecifier.TopSouthWest:
+ return GetOrSetSubTree(ref childTrees, 3, octant?[specifier]);
+
+ case PositionSpecifier.BottomNorthWest:
+ return GetOrSetSubTree(ref childTrees, 4, octant?[specifier]);
+
+ case PositionSpecifier.BottomNorthEast:
+ return GetOrSetSubTree(ref childTrees, 5, octant?[specifier]);
+
+ case PositionSpecifier.BottomSouthEast:
+ return GetOrSetSubTree(ref childTrees, 6, octant?[specifier]);
+
+ case PositionSpecifier.BottomSouthWest:
+ return GetOrSetSubTree(ref childTrees, 7, octant?[specifier]);
+
+ default:
+ throw new ArgumentOutOfRangeException(nameof(specifier), specifier,
+ "The given specifier was outside of the valid range.");
+ }
+ }
}
}
\ No newline at end of file
