Particle-Based Structure Formation
In order to build a complex and dynamic spatial system, there need be entities operating at multiple temporal and spatial scales. As mentioned in the previous post, the extremes of the spatial scale are local and global objects, which are typically particles and fields. It’s straightforward to build something where particles are affected by fields, but without intermediate structure formation, there is no opportunity for more complex dynamics to emerge. In morphogenetic processes, cells differentiate, cluster, striate, extend, etc. as interconnected and interwoven groups. Such patterns can be represented by meshes or networks of particles connected with edges that impart some form of behavioral change in the particles. The question is, how can the formation of such structures be described generally in terms of the patterns of formations but be given precise and specific behaviors that differentiate types? In other words, what are the primitive events and conditions that can describe the formation of a wide range of network structures?
The primitive operation here is that of connecting two particles together. (image) What is the condition that enables two particles to associate with each other? For simplicity, let’s assume that all particles are of the same kind and that particle can connect to every other particle under the proper conditions. Let’s further specify that the network structures that emerge should be surfaces and not volumetric in nature.
There isn’t much literature out there on how to connect particles together. Probably the best place to look is the point cloud research, which describes how data sets made up of particles in space can be turned into surfaces. The problem with a lot of the point cloud techniques is that they are often expensive and rely on optimization techniques that don’t map well to a real-time dynamic system. Typically, the first instinct when thinking about this problem is to make the capacity for particles to connect purely distance-based. The problem with this approach is that particles can easily crowd around each other, producing overlapping edges and degenerate mesh faces. Preferably, the particles would have a fairly regular spacing appropriate for the curvature of the surface.
To correct for this problem, a little bit of extra structure is needed to filter the conditions under which connections can be made. For the case of surfaces, what’s needed is some kind of device that tracks connection density and will only allow connections if the density criteria are met. This device could equally be called valency if it’s thought about like chemical bonds.
If we define the connection density as determining how many connections can be made within a given interval and set the number of 1, we can represent the connection criteria by a set of intervals around the particle in the particles’ plane. Each particle has a normal and two planar directions that uniquely determine its local coordinate system. If we say each particle can have up to 5 connections that sets a minimum spacing of 72 degrees between each connection. If a connection is attempted and it’s within 72 degrees of another connection, it will be rejected.
Once connections are made, the new properties and forces are applied to the particles. When a connection is formed, the particles on either end are likely not in the ideal locations to form a coherent surfaces, so we use the connections between particles to move them into some sort of optimized position and orientation. For example, in the simple case of forming a spherical shape, the particles will act on each other through the connections in order to form a surface of constant positive curvature.
Probably the most widespread technique for optimizing the structure of a mesh network is some form of spring or spring-electric simulation where each edge is a spring and in the spring-electric case each node applies a repulsive electric field to every other node. While this can give some interesting results, there is a certain uniformity to the shapes. Instead, each particle is given principle curvature values that define the local surface patch the particle represents. When particles are connected to each other, the attempt to place and orient the connected particle with the local surface patch.
The particles started out unconnected but connected themselves according to the connection filtering process described above. The light blue lines are the particle normals and the pink dots are the target locations the particles are trying to reach.
Since each particle in this simulation has a curvature of (1, 1), they will attempt curve into a sphere-like shape.
Currently, self-intersection is not prevented. When the edges come within range of each other, they form new connections as seen in the middle of this image.
The new connections further warp the form as it “inflates”.