Uniform grid met sorting

Het is hier even stil geweest maar ondertussen is er toch wat werk gebeurd. In de eerste plaats heb ik eens onderzocht hoe de particle demo van CUDA zijn uniform grid opstelt en dit ook geïmplementeerd.

Het uniform grid wordt bijgehouden met buckets. Elke bucket kan een onbeperkte grootte hebben. Het principe wordt hier duidelijk geïllustreerd:

Door de particles te sorteren per gridcell kunnen we ook terugvinden waar er net een nieuwe gridcell begint. Het sorteren verloopt volgens het parallelle algoritme "radix sort" dat door Scott Le Grand (NVIDIA Corporation) gebruikt wordt in "Broad-Phase Collision Detection with CUDA" voor GPU GEMS 3. Dit algoritme werd reeds geïmplementeerd in de CUDA SDK dus dat konden we gewoon hergebruiken.

De implementatie is efficiënter dan wat we al hadden met de techniek van Harada. We moeten minder geheugen gebruiken, en als we geheugen uitlezen kan dit ook 1D gecached worden vermits de particles gesorteerd voorkomen (met andere woorden, buren liggen ook naast elkaar in het geheugen). Een simulatie van 65k particles loopt bijvoorbeeld aan 60 FPS op een GTX 260 waar we vroeger 50 FPS haalden op de GTX 280. Een vergelijking van beide methodes op de benchmark machine volgt nog ten gepaste tijden.

Ik heb ook nog naar de pic&flip implementatie gekeken. Door deze radix sort techniek met buckets zou de eerste stap van het algoritme geen synchronisatie problemen meer hebben en dus veel sneller zijn.
Maar de pic&flip methode zelf blijkt toch onstabiel. Wanneer de viscositeit te laag is bewegen de deeltjes gewoon de hele tijd door elkaar, wanneer de viscositeit hoger is dan aligneren de particles zich tussen gridcellen en vertonen ze hoge affiniteit voor cellen aan de rand van het oppervlak. Deze cellen hebben een lage snelheid en de viscositeit zorgt ervoor dat naburige cellen ook meer aan deze valse snelheid gaan bewegen. We kunnen cellen met lage eigenschappen filteren, maar een onderscheid maken tussen cellen met artificiële eigenschappen en cellen met echte eigenschappen is niet evident.

Van mijn CUDA uniform grid implementatie heb ik ook nog een filmpje gemaakt:

In de helft van het filmpje laat ik de zwaartekracht meebewegen met mijn view rotatie waardoor het water naar de zijkant stroomt. Dit zorgt voor een mooie golf.