Pic & Flip

Na onze presentatie zijn we begonnen met onderzoek naar de pic en flip methode. Na een kleine poging tot implementatie ontdekten we toch wat moeilijkheden die eerst aangepakt moesten worden. Concreet ontbraken we een manier om parallel cellwaarden up te daten zonder synchronisatie conflicten en hadden we nood aan een efficiënte interpolatiemethode.

In de pic en flip methode moeten we eigenschappen van onze deeltjes overzetten naar een gridstructuur. Cellen uit dit grid krijgen een bijdrage per deeltje, waardoor ze simultaan geupdate moeten worden (bij niet CUDA implementaties wordt hier texture splatting voor gebruikt, maar dit is in CUDA niet mogelijk). Gelukkig voorziet CUDA atomische operaties, maar jammer genoeg alleen met integers (wij gebruiken floats). In een eerste poging gebruiken we een conversion factor om floats om te zetten in integers en weer terug. De resultaten waren bruikbaar, we kunnen een factor bepalen die voor een aantal optellingen een zekere nauwkeurigheid garandeert.

Dit leek ons eerder een omslachtige methode (die niet altijd even nauwkeurig gaat werken) dus probeerden we met een soort locking systeem de synchronisatie te garanderen. Al snel bleek de atomische "compare and store" (CAS) functie het nuttigst en we vonden een werkende implementatie van atomicFloatAdd op de NVIDIA forums. In onze testsituatie bleek deze manier van werken wel 100 keer trager, maar er is natuurlijk geen verlies aan nauwkeurigheid. Er zal moeten getest worden met beide mogelijkheden om uit te maken welke de beste resultaten zal opleveren.

Als tweede puntje werd de interpolatiemethode bekeken. We kunnen op 3 manieren interpoleren:

• lineair
• met behulp van de kernel functions
• 3D Texture interpolatie van CUDA

We implementeerde reeds de eerste twee methodes en kwamen tot de conclusie dat er geen verschil is tussen beide, althans niet in nauwkeurigheid. De nauwkeurigheid hangt wel sterk af van het aantal gridcellen en de smoothing length van de deeltjes. Bij een dubbel zo kleine smoothing length heb je ongeveer dubbel zoveel gridcellen nodig, zoals je kan zien in deze grafiek:

De 3DTexture interpolatie hebben we nog niet uitgeprobeerd. Deze gaat minder nauwkeurige resultaten geven (er wordt niet exact geïnterpoleerd), maar wel sneller werken.

Met deze resultaten kunnen we verder met de implementatie van pic & flip. Deze taak zal ik op mij nemen, terwijl Daniel een uniform grid implementeert. Dit grid kent dan wel de beperking dat er af en toe deeltjes niet in gaan passen, waardoor de simulatie minder goed gaat zijn. We nemen een harde deadline: volgende week vrijdag moeten de implementaties af zijn zodat we kunnen vergelijken welke methode de beste resultaten geeft.

Als extraatje heb ik nog een linkje naar gratis Microsoft software voor studenten, bijvoorbeeld Visual Studio 2008 professional. (wie weet kan iemand dit goed gebruiken, wij blijven verder werken met kate en linux)

Eerste thesispresentatie

Vorige week zijn we vooral bezig geweest met onze tussentijdsepresentatie. Deze is hier terug te vinden. Buiten enkele nieuwe ideeën die we kunnen gebruiken in de thesis zelf kregen we nog wat tips om de presentatie te verbeteren:

• een betere aansluiting tussen de verschillende delen voorzien
• tijdens het presenteren niet naar de slides kijken
• onze grafiekjes beter verzorgen en hiermee proberen aan te tonen wat de schaalbaarheid nu net is (dit is belangrijk voor het interactieve aspect)

Vermits de grafiek met resultaten niet zo duidelijk was, geven we hier een tabel met de berekende waarden. De timestep bepaald hoe lang we moeten simuleren in een seconde en hebben we niet constant genomen, wat voor een bespreking van de schaalbaarheid eigenlijk wel zou moeten. (de reden dat we de timestep lieten variëren is natuurlijk de performantie: hoe groter we de timestep krijgen, hoe meer frames per seconde we zullen halen)


We hebben ook nog de bug uit onze CPU implementatie gehaald en het programma op de grafische kaart werkend gekregen (zonder optimisaties). Tenslotte hebben we ook een mogelijke visualisatie techniek uitgeprobeerd, namelijk blobs. Hierbij laten we de deeltjes samensmelten, zodat ze samen een volume vormen. Deze techniek is niet real time maar geeft wel meer de illusie van water weer:

PIC and FLIP

We hebben deze week een drukke week gehad, met onder andere de presentaties van CG-thesissen. Interessant was om feedback te krijgen na de presentatie zelf: De gegeven suggesties geven ons nieuw inzicht over de toekomst van onze thesis.

Zo was er een voorstel om de PIC and FLIP methode te overwegen bij het berekenen van de buren van alle particles. We hebben vandaag afgesproken met Toon, die ons een paper heeft voorgesteld waarbij dat PIC & FLIP worden gebruikt om de neighbour search algoritme te omzeilen. (Animating Sand as Fluid, Zhu & Bridson (2005))

De Particle in Cell methode (PIC) maakt gebruik van een grid om benaderde waarden bij te houden. Ik heb hier een tekening van gemaakt om te illustreren:

Figuur 1: Particle in Cell methode

Wat men normaal gezien verwacht in een SPH implementatie is dat men op zoek gaat naar buren van alle particles, om zo de krachten tussen de particles onderling te bepalen. Met de PIC methode gaat men anders redeneren. Men maakt gebruik van het feit dat het in SPH mogelijk is om op elk puntje van uw volume te gaan evalueren aan de hand van de kernel functies, zelfs al valt dat puntje dus niet op een particle.

Om hier gebruik van te maken stelt men een uniforme grid op, en gaat men in die grid op welbepaalde punten de druk, dichtheid etc... analyseren. Elke particle heeft invloed op alle gridcellen die binnen zijn kernel straal liggen. Zo kan men dus bijvoorbeeld de dichtheid bepalen van elke gridcel door alle particles exact één keer te overlopen. In de volgende stap gaat men dan de gevonden waarden terug mappen op de particles, door opnieuw gebruik te maken van de kernels.

In figuur 1 is geillustreerd hoe dat een particle invloed heeft op naburige gridcellen. De paarse cirkel stelt een kernel straal voor, en de kruisjes zijn gridcellen. De groene gridcellen zijn degene die binnen de straal vallen, en die dus zullen worden geincrementeerd door de desbetreffende particle. Het geheel kan geparalleliseerd worden in cuda, aangezien men voor alle particles tegelijk de gridcellen kan gaan uitrekenen.

Het stukje FLIP moet er dan weer voor zorgen dat kleine details zo goed mogelijk bewaard blijven tijdens de PIC methode. Het probleem met de PIC methode is dat de eigenschappen van de particles heel hard uitgemiddeld worden. De details zijn voorlopig nog niet duidelijk, maar met FLIP gaat men er voor zorgen dat men de berekeningen incrementeel toevoegt aan de particles aan de hand van de vorige berekeningen, in plaats van het volledig absoluut te bepalen. Deze methode schijnt veel beter te werken om kleinschalige effecten te bereiken.

Alleszins, we gaan het nu onderzoeken in hoeverre dat het de moeite is om deze methode te gebruiken in onze SPH implementatie.