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:39] – [Auftrag A - Teil II] scatalit:fluid_simulation [2025-11-16 19:27] (aktuell) – sca
Zeile 425: Zeile 425:
    * Brute Force: $4-5$ FPS    * Brute Force: $4-5$ FPS
    * Spatial Hashing: knapp $60$ 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.1763285972.txt.gz
  • Zuletzt geändert: 2025-11-16 09:39
  • von sca