Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- talit:fluid_simulation [2025-11-03 14:39] – [Fluid Simulation] sca
+++ talit:fluid_simulation [2025-11-16 19:27] (aktuell) – sca
@@ Zeile 29: / Zeile 29: @@
 . An den Wänden sollen sie ohne Energieverlust reflektiert werden.
 . Kollisionen zwischen Teilchen werden noch ignoriert, sie bewegen sich also einfach durch einander hindurch.\\ \\
-. **Collision Detection V1:**
+. **Collision Detection V1: Brute Force**
-. Implementiere nun eine erste Version der Collision Detection: Iteriere über alle Teilchen. Iteriere für jedes Teilchen über alle anderen Teilchen und schaue, ob sie kollidieren. Dafür benötigst du also zwei ineinander verschachtelte Schleifen.
+. Implementiere nun eine erste Version - Brute Force - der Collision Detection: Iteriere über alle Teilchen. Iteriere für jedes Teilchen über alle anderen Teilchen und schaue, ob sie kollidieren. Dafür benötigst du also zwei ineinander verschachtelte Schleifen.
-. Zwei Teilchen kollidieren dann, wenn deren Abstand kleiner ist als $2\times$ der Radius. Alle Teilchen sollen, während sie miteinander kollidieren, eine andere Farbe annehmen. Siehe Tipps unten.
+. Zwei Teilchen kollidieren dann, wenn deren Abstand kleiner ist als $2\times$ der Radius.
-. Für wie viele Teilchen kannst du deine Simulation flüssig laufen lassen? Warum geht nicht mehr? Was ist das Problem mit dieser Art von Collision Detection?
+. Alle Teilchen sollen, während sie miteinander kollidieren, eine **andere Farbe** annehmen. Siehe Tipps unten.
+. Für wie viele Teilchen kannst du deine Simulation flüssig laufen lassen? Warum geht nicht mehr? Was ist das Problem mit dieser Art von Collision Detection?\\ \\
 === Unity Tipps ===
@@ Zeile 50: / Zeile 51: @@
 . Der Code sollte nun wie folgt funktionieren: Führt man den Code aus, so erschein in der Mitte des Bildschirms ein farbige Kugel, die sich nach oben bewegt.
-++++Code|
+++++Code von Template|
 **MainScript:**
@@ Zeile 177: / Zeile 178: @@
 </code></WRAP>
    * Tipp 1: Damit man nicht für jedes Frame für jede particleView den `GetComponent()`-Befehl wiederholt aufrufen muss, lohnt es sich, ein Array `particleRenderers` zu erstellen, in dem man die spriteRenderer für die entsprechenden Particles speichert. \\ \\
-   * Tipp 2: Passe gegebenenfalls den Code so an, dass die Farbzuweisung `... = Color.blue` nur dann ausgeführt wird, wenn sich die Farbe des Teilchens auch ändert. Verwende dazu z.B. ein Flag (bool) `changeColor`.
+   * Tipp 2: Passe gegebenenfalls den Code so an, dass die Farbzuweisung `... = Color.blue` nur dann ausgeführt wird, wenn sich die Farbe des Teilchens auch *ändert*. Verwende dazu z.B. zwei Flags (bool) `wasColliding` (ob kollidierte im letzten Frame) und `isColliding`. Jetzt wird nur die Farbe neu gesetzt, falls sich der Zustand von `wasColliding` zu `isColliding` geändert hat.
 == Grösse von GameObject im Code ändern ==
@@ Zeile 417: / Zeile 418: @@
 ++++
 </nodisp>
+==== Auftrag A - Teil II ====
+Wahrscheinlich hast du gemerkt, dass die Brute Force Methode für die Particle Collision Detection nicht sehr effizient ist, da man den Abstand von jedem Teilchen zu jedem anderen Teilchen berechnet, selbst wenn diese Teilchen sehr weit auseinander liegen. Hat man beispielsweise $1000$ Teilchen, so sind für diese Methode Rechenschritte in der Grössenordnung von $1000^2 =1’000’000$ notwendig. Dies wollen wir drastisch verbessern, indem wir **Spatial Hashing** für die Collision Detection verwenden. Auf dem MacBook eures Lehrers läuft die Simulation mit $5000$ Teilchens wie folgt:
+   * Brute Force: $4-5$ FPS
+   * Spatial Hashing: knapp $60$ FPS
+Implementiere nun **Spatial Hashing**, um die Collision Detection zu optimieren:
+. Der Bildschirm wird gleichmässig **unterteilt in Zellen**. Als Zellenbreite eignet sich der Teilchenradius.
+. Jeder Zelle wird ein (möglichst) **eindeutiger Hash** (key) zugewiesen.
+. Es wird ein **Dictionary** angelegt. Die Hashes dienen als key. Die Values sind Listen, die alle Particles beinhalten, die in der entsprechenden Zelle liegen.
+. Anstelle dass man ein bestimmtes Particle mit allen anderen vergleicht, vergleicht man es nur mit denjenigen in der gleichen und **angrenzenden Zellen**. Dadurch skaliert der Code nur noch mit $O(n)$!
+. Dazu ermittelt man zuerst die Hashes dieser (insg. $9$) Zellen.
+. Dann liest man die entsprechenden Particles aus dem Dictionary aus.
+. Nachdem man alle Zellen updated hat, **aktualisiert** man das Dictionary.
+=== Unity Tipps ===
+== Dictionaries ==
+<code csharp>
+using System.Collections.Generic; // required for dictionary
+Dictionary<int, List<someDataType>> myDict = new Dictionary<int, List<someDataType>>(); // create empty dict
+myDict.clear(); // clear the dictionary
+myDict.Add(someObject); // add something to dict
+myDict.ContainsKey(someKey); // checks if myDict contains a certain key
+</code>
+<nodisp 2>
+++++Lösungen|
+<code csharp>
+// using static Unity.Mathematics.math;
+using UnityEngine;
+using System.Collections.Generic; // required for dictionary
+public enum CollisionDetectionType{
+    BruteForce,
+    SpatialHashingDict
+}
+public class MainScript : MonoBehaviour
+{
+    [Header("Simulation settings")] // creates header in Unity Inspector
+    public GameObject prefabParticle; // drag particle prefab on this field in Inspector
+    // and all other game settings
+    // PRIVARTE FIELDS
+    // screen boarders
+    private float xMin = -9;
+    private float xMax = 9;
+    private float yMin = -5;
+    private float yMax = 5;
+    // particles
+    private bool giveParticlesInitVel = true;
+    private float vCompMax = 2.5f;
+    private float particleDiameter = 0.05f; // 0.05f
+    private float particleInitSep = 0.01f; // 0.01f
+    private int particleCount = 5000; // 500, make public later s.t. can adjust in Inspector
+    private float widthToHeightRatioInitState = 2.0f; // radio of rectangle in which particles are placed initially
+    private float particleInitSepRandRange = 0.0f; // should be smaller than particleInitSep / 2 to avoid overlap
+    // spatial hashing stuff
+    private CollisionDetectionType collisionDetectionType = CollisionDetectionType.SpatialHashingDict;
+    Dictionary<int, List<ParticleModel>> particleModelDict = new Dictionary<int, List<ParticleModel>>();
+    private float gridSize; // should equal diameter of largest particle
+    // fields used in code below
+    private ParticleModel[] particleModels;
+    private ParticleView[] particleViews;
+    private SpriteRenderer[] particleRenderers;
+    float minDistanceSquared;
+    private float particleRadius;
+    private Color colorNoCollision = Color.green;
+    private Color colorCollision = Color.red;
+    void Start()
+    {
+        UnityEngine.Random.InitState(42); // with seed
+        InitParticles(); // create particles
+    }
+    void InitParticles()
+    {
+        Debug.Log("Instantiate Particles");
+        Debug.Log("Collision Detection Type: " + collisionDetectionType);
+        // some calcs
+        minDistanceSquared = particleDiameter * particleDiameter;
+        particleRadius = particleDiameter / 2;
+        gridSize = particleDiameter; // for spatial hashing
+        // Check if prefab is assigned
+        if (prefabParticle == null)
+        {
+            Debug.LogError("prefabParticle is not assigned! Please assign a prefab in the Inspector.");
+            return;
+        }
+        // Create new arrays for particle models and views
+        particleModels = new ParticleModel[particleCount];
+        particleViews = new ParticleView[particleCount];
+        particleRenderers = new SpriteRenderer[particleCount];
+        // Setup stuff for inital positions
+        int nx = Mathf.FloorToInt(Mathf.Sqrt((float)particleCount) * Mathf.Sqrt((float)widthToHeightRatioInitState));
+        int ny = Mathf.CeilToInt(Mathf.Sqrt((float)particleCount) / Mathf.Sqrt((float)widthToHeightRatioInitState));
+        if (nx * ny < particleCount)
+        {
+            Debug.Log("initial positions wrongly calculated!");
+            // throw; // new Exception("initial positions wrongly calculated!");
+        }
+        // CREATE A PARTICLE AND ITS VIEW, THEN ASSIGN TO ARRAY
+        for (int i = 0; i < particleCount; i++)
+        {
+            // create model for particle
+            int ix = i % nx;
+            int iy = i / nx;
+            float x = -nx / 2 * (particleRadius + particleInitSep) + ix * (particleRadius + particleInitSep);
+            float y = ny / 2 * (particleRadius + particleInitSep) - iy * (particleRadius + particleInitSep);
+            Vector2 position = new Vector2(UnityEngine.Random.Range(x - particleInitSepRandRange, x + particleInitSepRandRange),UnityEngine.Random.Range(y - particleInitSepRandRange, y + particleInitSepRandRange));
+            Vector2 velocity;
+            // initial velocity
+            if (giveParticlesInitVel)
+            {
+                velocity = new Vector2(UnityEngine.Random.Range(-vCompMax, vCompMax), UnityEngine.Random.Range(-vCompMax, vCompMax));
+            }
+            else
+            {
+                velocity = new Vector2(0, 0);
+            }
+            ParticleModel particleModel = new ParticleModel(position, velocity, 1.0f);
+            // create game object for particle with prefab as image, will be added to Unity Hierarchy:
+            GameObject particleGameObject = Instantiate(prefabParticle, particleModel.position, Quaternion.identity);
+            particleGameObject.transform.localScale = Vector3.one * particleDiameter;
+            if (particleGameObject != null)
+            {
+                // Try to get ParticleView component, if not found, add it
+                ParticleView particleView = particleGameObject.GetComponent<ParticleView>();
+                if (particleView == null)
+                {
+                    particleView = particleGameObject.AddComponent<ParticleView>();
+                    Debug.LogWarning("ParticleView component was missing on prefab, automatically added for particle");
+                }
+                particleView.Bind(particleModel);
+                // assign particle model, view and renderer to array
+                particleModels[i] = particleModel;
+                particleViews[i] = particleView;
+                particleRenderers[i] = particleView.GetComponent<SpriteRenderer>();
+            }
+            else
+            {
+                Debug.LogError("Failed to instantiate prefab for particle! Make sure prefabParticle is assigned in Inspector.");
+            }
+        }
+        // Set correct color
+        for (int i = 0; i < particleCount; i++)
+        {
+            particleRenderers[i].color = colorNoCollision;
+        }
+    }
+    void Update()
+    {
+        Step(); // one simulation step
+    }
+    void CollisionDetectionBruteForce()
+    {
+        for (int i = 0; i < particleCount; i++)
+        {
+            ParticleModel particleModel1 = particleModels[i];
+            for (int j = i + 1; j < particleCount; j++)
+            {
+                if (i == j) continue;
+                ParticleModel particleModel2 = particleModels[j];
+                Vector2 delta = particleModel1.position - particleModel2.position;
+                float distSq = delta.sqrMagnitude;
+                if (distSq < minDistanceSquared)
+                {
+                    particleModel1.isColliding = true;
+                    particleModel2.isColliding = true;
+                }
+            }
+        }
+    }
+    // SPATIAL HASING METHODS
+    int GetGridCellCoord(float x)
+    {
+        return Mathf.FloorToInt(x / gridSize);
+    }
+    int CalculateCellHash(int xCell, int yCell)
+    {
+        return xCell * 73856093 ^ yCell * 19349663;
+    }
+    void CollisionDetectionHashTableDict(){
+        // BUILD PARTICLE DICT
+        // clear dict
+        particleModelDict.Clear();
+        // iterate over all particles, determine hash and add to dict
+        foreach (var particleModel in particleModels)
+        {
+            int xCell = GetGridCellCoord(particleModel.position.x);
+            int yCell = GetGridCellCoord(particleModel.position.y);
+            int hash = CalculateCellHash(xCell, yCell);
+            if (!particleModelDict.ContainsKey(hash))
+            {
+                particleModelDict[hash] = new List<ParticleModel>();
+            }
+            particleModelDict[hash].Add(particleModel);
+        }
+        // CHECK FOR COLLISIONS
+        foreach (var particleModel in particleModels)
+        {
+            foreach (var neighbour in GetNeighbors(particleModel.position))
+            {
+                if (particleModel == neighbour) continue;
+                float distanceSquared = (particleModel.position - neighbour.position).sqrMagnitude;
+                if(distanceSquared < minDistanceSquared)
+                {
+                    particleModel.isColliding = true;
+                    neighbour.isColliding = true;
+                }
+            }
+        }
+    }
+    // get all particles in same and eight neighboring cells
+    // two options: same method once as IEnumerable and once returning a list. Same performance.
+    IEnumerable<ParticleModel> GetNeighbors(Vector2 position)
+    {
+        int xCell = GetGridCellCoord(position.x);
+        int yCell = GetGridCellCoord(position.y);
+        for (int dx = -1; dx <= 1; dx++)
+        {
+            int x = xCell + dx;
+            for (int dy = -1; dy <= 1; dy++)
+            {
+                int y = yCell + dy;
+                int hash = CalculateCellHash(x, y);
+                if (!particleModelDict.ContainsKey(hash)) continue;
+                foreach (var particle in particleModelDict[hash])
+                {
+                    yield return particle;
+                }
+            }
+        }
+    }
+    List<ParticleModel> GetNeighborsList(Vector2 position)
+    {
+        List<ParticleModel> neigbours = new List<ParticleModel>();
+        int xCell = GetGridCellCoord(position.x);
+        int yCell = GetGridCellCoord(position.y);
+        for (int dx = -1; dx <= 1; dx++)
+        {
+            int x = xCell + dx;
+            for (int dy = -1; dy <= 1; dy++)
+            {
+                int y = yCell + dy;
+                int hash = CalculateCellHash(x, y);
+                if (!particleModelDict.ContainsKey(hash)) continue;
+                foreach (var particle in particleModelDict[hash])
+                {
+                    neigbours.Add(particle);
+                }
+            }
+        }
+        return neigbours;
+    }
+    void Step()
+    {
+        // UPDATE POSITION
+        float dt = Time.deltaTime; // ensures that velocity is independent of frame-rate
+        foreach (var particleModel in particleModels)
+        {
+            particleModel.position += particleModel.velocity * dt;
+        }
+        for (int i = 0; i < particleCount; i++)
+        {
+            particleModels[i].wasColliding = particleModels[i].isColliding;
+            particleModels[i].isColliding = false;
+        }
+        // COLLISION DETECTION
+        if (collisionDetectionType == CollisionDetectionType.BruteForce){
+            CollisionDetectionBruteForce();
+        }
+        else if (collisionDetectionType == CollisionDetectionType.SpatialHashingDict)
+        {
+            CollisionDetectionHashTableDict();
+        }
+        else{
+            Debug.Log("ERROR no valid collision detection selected");
+        }
+        // CHANGE COLOR IF COLLIDE
+        for (int i = 0; i < particleCount; i++)
+        {
+            if (particleModels[i].isColliding && !particleModels[i].wasColliding)
+            {
+                particleRenderers[i].color = colorCollision;
+            }
+            else if (!particleModels[i].isColliding && particleModels[i].wasColliding)
+            {
+                particleRenderers[i].color = colorNoCollision;
+            }
+        }
+        // COLLISION HANDLING: WALLS ONLY
+        for (int i = 0; i < particleCount; i++)
+        {
+            ParticleModel particle = particleModels[i];
+            if (particle.position.x < xMin + particleRadius)
+            {
+                particle.position.x = xMin + particleRadius;
+                particle.velocity.x = -particle.velocity.x;
+            }
+            else if (particle.position.x > xMax - particleRadius)
+            {
+                particle.position.x = xMax - particleRadius;
+                particle.velocity.x = -particle.velocity.x;
+            }
+            if (particle.position.y < yMin + particleRadius)
+            {
+                particle.position.y = yMin + particleRadius;
+                particle.velocity.y = -particle.velocity.y;
+            }
+            else if (particle.position.y > yMax - particleRadius)
+            {
+                particle.position.y = yMax - particleRadius;
+                particle.velocity.y = -particle.velocity.y;
+            }
+        }
+    }
+}
+</code>
+++++
+</nodisp>
+==== Auftrag A - Teil III ====
+Formel für elastischen Stoss in 2D:
+[[https://sca.ksr.ch/lib/exe/fetch.php?media=talit:collisions.pdf|Slides Collision]]