Markov-Chains in VoroX

For VoroX.jl Benoît build a system that is similar to Google’s PageRank that uses Markov Chains, where web-crawlers are released onto the internet to measure the connections and generate rating of sites.

In his system there's an amount of traffic released into the Voronoi-edges of the foam, these pulses move from the edges to the junctions and check if the gates are open or closed. 

When a gate is open a pulse moves on to the next gate and so forth. These ‘ratings' correspond to the current in each edge between the cells and define if a cells shrinks or expands. The particles move until they reach a Steady-State, as in Nick’s 2D Dynamic Foam model:

If you’re not familiar with Markov-Chains, this video from Khan academy explain it in 3 minutes:

https://www.khanacademy.org/college-careers-more/bjc/2018-challenge/2018-challenge-mathematics/v/markov-chains-breakthrough-junior-challenge-2018

So in VoroX.jl dogs/pulses/web-crawlers move to other rooms/edges/websites when there’s an open-door/gate//link. 

After a couple of iterations a Steady-State is reached and we can count the dogs/flow/connections.

These values lets us know how much ‘erosion' the flow in an edge (a-c) has caused to its neighboring cells A and D, and as such the contraction-value for its dual edge A-D.

---

Details from the control panels of the 2D Dynamic-Foam

https://github.com/weigert/DynamicFoam

 that might make more sense now:

https://youtu.be/X-KytAnr1rg

https://youtu.be/wR3JgunXDdU

• Energy, Scale and Critically 

This refers to the number of particles/pulses are put into the system and their size.

 • Circumcenter / Barycenter / Incenter 

Refers to the method used to create the dual Voronoi Mesh on top of the Delaunay Mesh.

• Expansive Flow / Contractive Flow

Particles in Voronoi-edges (a-c) expand OR contract Delaunay-edges (AB).

Details from theVoroX.jl control panels of the 3D/2D Dynamic-Foam program where the particles are replaced by a Markov-Chain value system:

https://youtu.be/0UTzeL0uesY

https://youtu.be/sTa5utH-8Uc

Height: 

set size of the Area

Point size, Center size, Edge width, Circuit width: 

visualisation properties

Decay:

time a current in edges stays highlighted

Shading for the faces.

3D 

Processing Schemes & Diagrams

Intro

There’s a foam where flow runs through the edges, the angles of the junctions regulate if flow can pass or is not, the amount of current in an edge defines if its neighboring cells grow or shrink, like a river sedimentation vs erosion. 

Scheme I : Technical setup

1. Random Poisson distribution (or Blue Noise) of points that fills the area.

2. Build the Delaunay Triangular Mesh with these points (see ref. Alterntives for Voronoi Diagrams)

3. Calculate the Barycenters/Centroids.

4. Build the Dual Voronoi Mesh.

5.a. Send pulses from the edges of the Voronoi Mesh in both directions.

5.b. Calculate from the triangles which Angles/Gates/Connections are:  Open (I) > 90° or Close (0) < 90°

5.a./5.d. Keep forwarding the pulses through the edges so we get a current-value for each edge (until we reach a Steady-State).

6. The results of (5.a.) gives us the value of how much the Delaunay-edges should contract or expand (similar to a Mass-Spring system).

-> Now we are full-circle and we have new positions for (1.) and (2.), and we can draw a new set of (3.) Centroids and redo the whole process.

Scheme 2 : Divide Large Mesh in Small Blocks

Maybe we can cut up the ‘Global Mesh' in smaller blocks that can be easily parallel computing on the GPU, where the a edges fo the Global Grid/Mesh are separated into small blocks that have a Local ‘virtual’ Grid and are easy to process individually to be send back to the Global Mesh.

Scheme 3 : Iteration of Global Backbone and Local Blocks

The mesh could be divided into one Global horizontal strip with small Local blocks:

Y0 / Y1 / Y2 / Y3 / …

At each iteration there’s a vertical process where each block can figure out it’s local connectivity status, the results are fed into a Global graph that uses a Morkov-Chain process to figure out the connectivity ‘flow’ state of each connection, just like how Google’s Page-Rank works, and the results are fed back into the Global mesh.

Step 1 / Step 2 / Step 3 / ...

OpenAI / Chat GPT Spiralled Torus as logo

 Cool to see that the hottest and most advanced company at the moment is using 'our' spiralled torus for their logo.

3D *Simi* Dual Mesh with Compute Shader in Unity

Last year we got somewhat stuck with the upgrade of the 3D Dynamic Foam program in Julia (Voro-X) to a more performant 2.0 version. The reason is that there is no CGAL version (yet) for Julia to use as the backbone. 

So I decided to explore if a Compute Shader might be an option, because shaders use the full power of GPU's and can significantly increase the speed of simulations.

As such I got in touch with Polish developer Przemyslaw Zaworski to see if it was possible to get the Dynamic Foam model running with a Compute Shader in Unity.

The result is a *semi* 3D Dual Mesh simulator with a Delaunay Triangles/Tetrahedrons basis out of which a Semi-Voronoi-Mesh is distilled using the Jump Flooding Algorithm (JFA):

https://github.com/przemyslawzaworski/Unity-GPU-Based-Tetrahedralization

It is a *Semi* mesh because the Voronoi mesh is only a pixel/voxel-mesh and not a 'real' mesh made out of a conglomerate of points, edges and faces. As such it cannot be used to setup the interaction model between the two complimentary dual meshes (Delaunay/Voronoi). Perhaps in the future an actual Voronoi mesh can be extrapolated from the semi-Voronoi-mesh.

Here's a compilation video with more examples of the simulator:

An other option worth exploring might be Mesh-shaders …