Physics sims: which structures to use (primitives versus vectors, `double` versus `long`, `volatile` versus `synchronized` versus `Atomic*`)

Most software engines (both for games, or physics sims) stick to float (or double) for position structures, but not much discussion exists on which structure to use.

[Version of this post is SusuPosts@cdbcad2. The most new version is on this GitHub preview branch.]

Intro

This document uses java syntax for data structures plus simple physics functions (which all have close-to-similar versions in most languages).

Most software engines (both for games, or physics sims) stick to float (or double) for position structures, but not much discussion exists on which structure to use.

Unless the sim is supposed to allow simple future changes of the structures used, the chore is often difficult:

• to switch from separate variables (such as double xPos, yPos;) to dim lists (such as double[] pos),

• to switch all positions + distances from double to long, or long to double.

---

Popular structures for sims

Examples below all assume the default is public class.

• types are primitives (such as double) or classes (such as java.lang.Integer).

  • Inheritance (”to inherit“) is for one class to have all which some (different) class (or interface) has. Non-primitive types in java all inherit from java.lang.Object: class Node : extends Object { double value; }; extends Object to include double value;.

  • interfaces are incomplete types, similar to pure virtual classes (classes which have unimplemented functions). For interfaces, use implements (not extends): interface RandomAccess { public double at(int index); }; class ImmutableList implements RandomAccess { protected double[] values; @Override public double at(int index) { return values[index]; } };

• Nodes (also known as elements) are types stored in lists (such as double[] arrayList or java.util.List<Integer> list), or stored in graphs.

  • Structures are nodes with some definition of usage (such as coordinates, vertices, meshes or textures).

  • Tensors are the superset of vectors (contiguous lists such as double[]) which can include numerous dimensions (Color[][] bitmap is an example of 2-dimensional tensor).

    • Resolution is most known to consumers as the .size() of tensors: Color[1000][2000] bitmap; gives 1000*2000 resolution to the tensor known as bitmap (resolution of monitors is the .size() of the bitmap of thus monitors).

      • Resolution has an overloaded definition: resolution also refers to the minimum step size (for Integer this is 1, for Double this changes with magnitude, but epsilon values (such as Double.MIN_NORMAL are popular minimum step sizes for Double, or you can use Math.nextAfter())). Most physics documents use the “minimum step size” definition of resolution (which the section double versus long uses).

• Indices are offsets from the first node of lists: class PrimitiveIndices { int[] index; }; class Index { Integer value; }; class Indices { List<Index> index; }; Indices stores a List of Indexes. With PrimitiveIndices, performance improves, but java‘s Generics can not use primitives.

  • Edges are tuples of indices into lists, for adjacent nodes: class Edge { Index source, dest; /* indices */}; class Edges { List<Edge> edge; };, Edges stores a List of Edges. The source, dest format supports directed edges (some graphs require directed edges), but also allows undirected edges (meshes use undirected edges).

    • Graphs are similar to lists but store connections (Edges).

      • Dense graphs are 2-dimensional lists of nodes (in meshes, thus nodes are vertices): Index[nTotalVertices][nMaxAdjacentVertices] adjacencyList; is a dense graph of Indexs (indices) to nodes.

      • Sparse graphs are the most popular graphs, which are similar to dense graphs except just edges are stored:

        • one form of sparse graphs is Edges, which stores unsorted Edges.

        • another form of sparse graphs is Map<Index, Indices> adjacencyList;, which is an associative list of Indexs (indices) of nodes to Lists of adjacent nodes. This uses more resources to store, but less resources fetch values.

• Pixels are 24-bit RGB (or 32-bit RGBA) components: class PrimitivePixel { int value; }; class PrimitivePixels { int[] value; }; class Pixel extends Integer {}; class Pixels { Pixel[] pixel; };, Pixels stores a simple list of Pixels.

  • Most languages will use 32-bit integers for bitmaps, but java has java.awt.Color for thus: class Pixel extends Color {};. Pros of Color: is standard, popular structure which stores RGBA values, with functions to access individual channels, plus does not require more overhead then Integer to implement.

  • Some architectures use other structures such as Y’UV (to improve performance for specific tasks).

• Bitmaps are 2-dimensional tensors of pixels (most are supposed to show as sprites or as simple static images): class Bitmap { Pixel[xResolution][yResolution] pixel; }; class Bitmaps { Bitmap[] bitmap; };, Bitmaps stores a simple list of Bitmaps with similar resolutions.

  • Sprites are maps of directions to bitmaps which are used for simple 2-dimensional sims: enum Direction { North, South, East, West; }; class Sprite { Bitmap[Direction.values().length] avatar; }; class Sprites { Sprite[] sprite; };, Sprites stores a simple list of Sprites, which require geometric translation (vertical bounces) for motion. Some sims use .gifs (as opposed to Bitmaps) for more natural motion.

  • Textures are bitmaps which are supposed to transform onto (do complex geometric convolutions onto) meshes: class Texture extends Bitmap {}; class Textures { Texture[] tex; };, Textures stores a simple list of Textures with similar resolutions.

• Coordinates are offsets from the origin of Euclidean spaces: class PrimitiveCoordinate { double coord; }; class PrimitiveCoordinates { double[] coords; }; class Coordinate extends Double {}; class Coordinates { Coordinate[] coords; };, Coordinatess stores a simple list of Coordinate.

  • Positions are N-coordinates, for N-dimensional spaces: class Position { Coord[dim] coord; }; class Positions { Position[] pos; };, Positions stores a simple list of Positions. package susuwu.{Immutable,}Pos{2,} improves performance for popular position formulas. Most of thus also have uses for vertices.

    • Voxels [²] are Positions which represent cubes (or spheres) plus Color, for N-dimensional spaces: class Voxel { Position pos; Pixel pixel; }; class Voxels { Voxel[] voxel; double lengthOrRadius; }; Voxels stores a simple list of Voxels. Old-fashioned sims use Voxels.

    • Vertices are positions of corners of ngons (triangles are the simplest ngons): class Vertex extends Position {}; class Vertices { Vertex[] vertex; };, Vertices stores a simple list of Vertexes. New sims replace Voxels (with Vertices plus Textures).

      • Adjacent vertices are vertices attached with edges which form skeletons (or produce Ngons): class AdjacentVertices { Map<Index, Indices> map; /* Indexes of Vertexes */ }; is a simple “adjacency list“.

    • Surfaces are the flat geometric faces of Meshes: class Surface { Vertices vertices; }; class Surfaces { Surface[] surfaces; };, Surfaces stores a simple list of Surfaces, renderers set Textures onto thus Surfaces (or onto Ngons).

      • Ngons are the smallest groups of adjacent vertices which can produce faces, for N-dimensional spaces: class Ngon { Vertex[dim] vertex; }; class Ngons { Ngon[] ngons; };, Ngons stores a simple list of Ngons.

    • Skeletons are lists of vertices whose “joints” (connections) allow angular motions: class Skeleton { Vertex[] vertices; AdjacentVertices connections; }; class Skeletons { Skeleton[] skeleton; };, Skeletons stores a simple list of Skeletons.

      • Quarternions are trigonometric structures used for motion of joints in Skeletons.

    • Point clouds are lists of Positions of corners of processed surfaces: class PointCloud { Positions point; }; class PointClouds { PointCloud[] pointClouds; };, PointClouds stores a simple list of PointClouds. MiDaS (monocular depth estimation) processes individual Bitmaps into partial (just includes the surface) PointClouds (but is not accurate). cv2.calcOpticalFlowFarneback allows to produce whole (volumetric) Pointclouds, but requires motion images (lists of connected Bitmaps).

      • Textured point clouds are PointCloud which store Voxels (not just Positions): class TexturedPointCloud { Voxels voxel; double voxelDiameter; }; TexturedPointCloud[] texturedPointClouds;, TexturedPointClouds stores a simple list of TexturedPointClouds. Different formulas are used to produce thus, since the points are not infinitisimal corners of surfaces but are spheres (which all have similar circumfurence but different Colors)

      • Depth imagers (such as Microsoft Kinect 2) can produce whole connected point clouds (PointClouds which include Edges for adjacent Positions, which improves conversion into meshes): class ConnectedPointCloud { List<Position> point; Edges edges }; ConnectedPointCloud[] connectedPointClouds; stores a simple list of ConnectedPointClouds.

• Meshes are graphs of vertices: class Mesh { Vertex[] vertices; AdjacentVertices adjacentVertices; }; class Meshes { Mesh[] mesh; };, Meshes stores a simple list of Meshes (assumes vertices.size() > Index.intValue()).

• Motions are sequences of motion vectors (of derivatives of position), which are produced for specific meshes (”skeletons”) to move: one popular form of motions is .fbx Filmbox motions.

• Avatars (also known as models) are Meshes plus Texturees plus Skeletons: class Avatar { Skeleton skeleton; Mesh mesh; Texture texture; }; class Avatars { Avatar[] avatars; };, Avatars stores a simple list of Avatars.

  • Old-fashioned avatars use Voxels (not Meshes plus Textures): class OldFashionedAvatar { Skeleton skeleton; Voxels voxels; }; class OldFashionedAvatar { OldFashionedAvatar[] oldFashionedAvatar; };, OldFashionedAvatars stores a simple list of OldFashionedAvatars. Old-fashioned avatars are just used in old sims (such as DirectX 6 sims) or raytracers.

• Renderers load Avatars, process Meshes into surfaces attached to Skeletons, plus load “skins” (textures) onto thus surfaces.

  • Most popular renderers also use motions so Skeletons move, but some renderers just produce static images.

• tensorflow loads examples of {input, output} (which is {question, answer}) to produce connectomes (groups of synapses) which process future questions into new answers.

• Descriptions are char[]s or Strings, which store human-language versions of structures (such as of Meshes). Descriptions are used to document structures (for humans, or for tools such as tensorflow).

---

Separate variables versus dim lists

Pros of double xPos, yPos;:

• If stuck with source-code compilers (or script interpreters) which can not optimize static lists into constant access, this improves RAM plus CPU use.

  • If stuck with those which can not unroll loops (loops such as dimension-agnostic physics functions), this improves CPU use.

Pros of double[] pos;:

• Simple to switch to more (or less) dimensions: if loops are used for the physics functions (such as package susuwu does), allows to reuse dimension-agnostic source code.

• New compilers reduce those indirect accesses (the implicit pointer indirection) into constant accesses (hardcoded addresses).

---

double versus long

Some languages have long double (which gives nanometer resolution for all planets in our solar system), but:

• long double uses the FPU, so can not use vector improvements (such as SSE2, nor GPGPU).

• long double uses 80 bits (long or double use 64 bits).

• long double uses 80 bits (long or double use 64 bits).

Pros of double[] position;:

• double can store values in the range [(2-2⁵²)·2¹⁰²³, 2¹⁰⁷⁴] (inclusive), store NaN, or store Inf (although resolution is poor with large magnitudes, plus some functions can not use Double.NaN or Double.POSITIVE_INFINITY values).

• Since double[] includes variable exponents, double[] position;:

  • Is simple to use with formulas which involve squares (Math.pow()) or square roots (Math.sqrt()), such as Euclidean distance formulas (code which generalizes Math.hypot() to use more dimensions), which are common to physics sims.

  • double[] position = {0, 0, 0} with Sol (our sun)’s center-of-mass as the origin, can store positions as far as Pluto (but just with millimeter resolution).

Pros of long[] position;:

• long can store values in the range [-2⁶³, 2⁶³-1] (inclusive) (with similar resolution for all of those values).

• Since long[] has fixed resolution:

  • The hardware (CPUs, GPGPUs, TPUs) plus software (the physics sim functions) is more simple.

  • All systems allow long bitshift (<<=, >>=) use (with java, double does not allow <<= nor >>=, but requires intrinsic functions such as Math.scalb). Versus division (also versus multiplication), bitshifts improve CPU use.

  • All positions have similar resolution (instead of femtometer resolution for Sol‘s core (millimeter resolution for Pluto‘s surface), the whole planet can have nanometer resolution).

  • long[] stores sufficient quantized positions to give nanometer resolution for the whole surface of the largest planet in our solar system (but with this resolution, the distance is limited to a single planet, such as Jupiter, with the planet’s center-of-mass as origin).

---

volatile versus synchronized versus Atomic* versus

Those are the most popular structures to ensure that multiple Threads (or other units of execution such as java.util.concurrent.ExecutorService) follow the spatiotemporal structure of the source code. More “explicit“ (granular) structures exist, which do not introduce as much blocks (as much “pauses“), but which are more difficult to use.

synchronized

If interpretation of so is true (am new to java, so asked Solar-Pro-2, which says is true), https://johanley.github.io/java-practices-snapshot/topic/TopicAction5ade.html?Id=35 says:

• class Foo { synchronized anInstanceFunction( { ... } }) causes such synchronized instance functions of class Foo to use an exclusive “instance lock” (not possible to choose which functions use which locks, except static versus not static).

• class Foo { synchronized static someStaticFunction( { ... } }) causes such synchronized static functions of class Foo to use an exclusive “static lock” (not possible to choose which functions use which locks, except static versus not static).

• synchronized(this) causes the current execution to block (to pause) unti no contexts of execution use the instance lock, irrespective of if the current function is set to synchronized.

• synchronized(this.getClass()) (which does what synchronized(Foo.class) does, if this.getClass() == Foo) causes the current execution to block (to pause) unti no contexts of execution use the static lock, irrespective of if the current function is set to synchronized.

java.util.concurrent.locks.ReentrantLock

If interpretation of this discussion with Solar-Pro-2 is true:

• java.util.concurrent.locks.ReentrantLock is the granular version of synchronized.

• The code must setup (plus store, plus acquire, plus release) separate ReentrantLock instances with explicit instructions, thus more difficult to use.

• Due to separate ReentrantLock instances, numerous units of execution can use 1 this, if those units of execution contest for separate ReentrantLocks. Thus more units of execution (versus synchronized, which limits all synchronized blocks of this to 1 unit of execution).

volatile primitive or AtomicPrimitive

If interpretation of so is true, this discussion with Solar-Pro-2 says:

• both ensure that java follows the explicit temporal precedence of the source code (without volatile or Atomic, java optimizes the execution such that race conditions are possible in executables which use multiple executors (such as thread pools or SMP).

• both ensure that stores whose size is more than the CPU architecture’s word size (thus, 64-bit primitives such as double or long) are stored whole. With no volatile or Atomic suffix, stores from one unit of execution can cause separate contexts of execution which access those addresses to process spliced versions (”tearing“: versions whose first 32-bits stores the new value but whose second 32-bits stores the old value).

  • Just AtomicPrimitive suits 64-bit CAS (volatile long foo = 42; if(42 < ++foo) is undefined, AtomicLong foo = 42; if(42 < foo.incrementAndGet()) is true).

Solar-Pro-2 says this is true, plus suggests the alternative java.util.concurrent.atomic.

---

Synopsis

This simple java fish sim still has much code churn around which position data structures to use.

./posts/GoogleStore_MicrosoftStore_Ubuntu_scripted_tool_sims.md lists numerous physics sims for school use.

Most search results for such discussions just show physics engines’ documents of float versus double:

• https://docs.godotengine.org/en/stable/tutorials/physics/large_world_coordinates.html

• https://godotengine.org/article/emulating-double-precision-gpu-render-large-worlds/

• https://developer.unigine.com/en/docs/future/code/double_precision/usage