Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
talit:fluid_simulation [2025-11-16 09:20] – [Unity Tipps] scatalit:fluid_simulation [2025-11-16 19:27] (aktuell) – sca
Zeile 421: Zeile 421:
 ==== Auftrag A - Teil II ==== ==== 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:
 +
 +   1. Der Bildschirm wird gleichmässig **unterteilt in Zellen**. Als Zellenbreite eignet sich der Teilchenradius.
 +   1. Jeder Zelle wird ein (möglichst) **eindeutiger Hash** (key) zugewiesen.
 +   1. Es wird ein **Dictionary** angelegt. Die Hashes dienen als key. Die Values sind Listen, die alle Particles beinhalten, die in der entsprechenden Zelle liegen.
 +   1. 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)$!
 +   1. Dazu ermittelt man zuerst die Hashes dieser (insg. $9$) Zellen.
 +   1. Dann liest man die entsprechenden Particles aus dem Dictionary aus.
 +   1. 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]]
  
  • talit/fluid_simulation.1763284843.txt.gz
  • Zuletzt geändert: 2025-11-16 09:20
  • von sca