View Full Version : Level Set Fluid Simulation

 merlin7410-18-2006, 06:33 AMIt seems several people are interested in fluid simulation using level set methods, as described in a series of papers by Fedkiw et al. Well, I am one of them. Basically, I am following "Practical Animation of Liquids" by Foster and Fedkiw. I have only achived the first stage, setting up the grids, placing particles in some grid cells, obtaining the implicit function phi(x) based on the expression from the paper (phi(x)=phi_p(x)=distance(x,p)-r, where p is the closest particle to x) , a fast marching procedure to make phi(x) signed distance, and a reinitialization procedure to smooth phi(x). Before proceeding to the next stage, I want to make sure what I have done is right. There several things I am not quite sure. 1. If we follow the paper strictly, the initial implicit function phi(x) defined on all particles are going to be all positive except near the interface where phi(x) is small but with both positive and negative signs. The paper didn't mention what r (radius of particels) should be, but I assume it is within a grid cell size. So the phi_p(x) is going to be always positive if x is farther way from p beyond r. my question is: Shouldn't phi(x) be negative when x is in the liquid volume and positive when it is outside the volume? But I don't see the paper mentioning distinguishing the point inside and outside the liquid when defining the implicit function. So I did it myself, by multiplying -1 to phi(x) when x is inside the liquid. Am I doing it right here? Or fast marching methods could make phi(x) have correct sign according to the position of x? However, both Fedkiw and Sethian's books talk about doing fast marching on positive and negative grid points seperately, which means phi(x) already has its sign correct based on where x is. 2. The paper said doing a few relaxation steps using Equation(5.1) will smooth phi(x). However, I couldn't find what the time step going to be when solving Equation(5.1) using Runge-Kutta methods. Anyone has an idea about this? Thanks, Merlin
HollyWoodland
10-18-2006, 11:38 AM
Hi Merlin

give me a week or 2 to catch up with you then i'll get back to you properly
(i've been getting distracted with daytime TV recently!)

but I would have to agree about the sign problems - I thought the whole point was that the interface was defined where phi(x) = 0 so negative values of phi would be inside and positive outside

ok i'll have a more detailed look asap (well as soon as i stop watching tv and get on with it)

some questions for you:
are you just working on liquids or are you planning on using it for fire as well?
also are you writing this as a plugin or a separate app to spit out the data?
how are you going to render it - convert to mesh or custom render of the interface?

let me know how you get on

Holly

darktding
10-18-2006, 03:03 PM
I am curious to what you guys are doing so please do discuss... I might get that level set yellow book and might join you all if I have the time...
I have a quick question, how are you going to implement the solver?
Thanks

HollyWoodland
10-18-2006, 03:46 PM
I am curious to what you guys are doing so please do discuss... I might get that level set yellow book and might join you all if I have the time...
I have a quick question, how are you going to implement the solver?
Thanks

have a look at this http://graphics.stanford.edu/~fedkiw/papers/stanford2001-02.pdf

check out his site in general http://graphics.stanford.edu/~fedkiw to see the sort of things we are looking at doing

merlin74
10-18-2006, 05:27 PM
Despite those things I am not sure, I got some images rendered.

1. http://www.cnblogs.com/images/cnblogs_com/bssrdf/73176/r_particle.jpg

This image shows the zero isosurface of the implicit function, as defined using particles placed in the grid cells near the interface.

2. http://www.cnblogs.com/images/cnblogs_com/bssrdf/73176/r_fm.jpg

This image shows the same zero isosurface of the implicit function as above, but after a fast marching procedure is applied to the function.

3. http://www.cnblogs.com/images/cnblogs_com/bssrdf/73176/r_reinit.jpg (http://www.cnblogs.com/images/cnblogs_com/bssrdf/73176/r_reinit.jpgv)

This image shows the same zero isosurface of the implicit function as 2, but after a reinitialzation is applied to the function. I use 5 steps.

You can see there is not much difference between 2 and 3. I am not sure whether it's because my reinitialzation routine is not right, or the implicit function phi(x) feeding into my reinitialzation routine from 2 (fast marching) is already smooth enough.

But certainly the surface is not flat. In these images, I only placed 4 particles in each grid cell. Do more particle are needed to get a flat water surface? I don't know.

Nervertheless, it's not hard to get a initial flat surface. In the following images, the surfaces are flat.

4. http://www.cnblogs.com/images/cnblogs_com/bssrdf/73176/r_fm1.jpg
This one is after fast marching.

5. http://www.cnblogs.com/images/cnblogs_com/bssrdf/73176/r_reinit1.jpg
This one is after fast marching and reinitialization.

I changed the definition of the implicit function in image 4 and 5 compared to 1, 2 and 3.
Now, I only calculate phi(x) at grid points close to interface. I use phi(x)=-0.5 for all points near interface, which I intend to put at half a grid size away. Other grid points get their implicit function values via fast marching. But this is not what is done in Foster and Fedkiw's paper.

To HollyWoodland:
I plan to start on fluid first. When I get a decent fluid simulation system, I may touch fire and smoke.
I am writing it as a seperate program which outputs implicit function on the grids. Then a Monte carlo ray tracer reads in this data and directly render the surface. I am using pbrt for which somebody wrote a nice shape plugin for grid-based implicit function.

djwarder
10-30-2006, 05:55 PM
Hi Merlin

merlin74
10-30-2006, 06:23 PM
Hi Merlin

I am writing code for Stam's N-S solver and advecting level set using Fedkiw's method.

Boundary conditions really gave me a headache.

Stay tuned...

darktding
10-30-2006, 06:52 PM
stupid question: what algorithm are you guys using to mesh the fluid? I know you guys are using implicit functions any good place to read up on it? I know googles a good place to start but if you know of any other good websites please do tell...
Thanks

djwarder
10-30-2006, 06:55 PM
Will do! Looking into this field myself, but is a major headache. Have had a look at the Osher/Fedkiw book, but too hardcore at the moment. Will probably buy Sethian's book instead ...

merlin74
10-30-2006, 07:14 PM
stupid question: what algorithm are you guys using to mesh the fluid? I know you guys are using implicit functions any good place to read up on it? I know googles a good place to start but if you know of any other good websites please do tell...
Thanks

I did not extract a mesh from implicit function. Instead, there are existing methods to directly ray trace it.

djwarder
10-30-2006, 07:19 PM
Direct raytracing is much better than meshing (i.e marching cubes). Get better resolution, plus low on memory requirements ...

HollyWoodland
11-02-2006, 12:05 PM
ditto to the ray tracing the implicit surface

the only benefit of meshing is if you want to be able to adjust the results after the simulation

merlin/djwarder - are you guys writing yours as standalone apps or plugins? i'm starting off with writing the maths/algorithms in C++ and using python for all I/O but i ultimately want to make it into a Maya plugin.
Any idea how I would implement the implicit surface ray tracer in Maya? (I have lots of developing experience for standalone apps but not so much with plugins)

HollyWoodland
11-02-2006, 12:09 PM
just saw merlin's earlier post and realised half my questions were duplicates - sorry :-)

djwarder
11-02-2006, 02:18 PM
Well, me personally, I'm just looking into the subject as an interest, but would prefer to make a plugin rather than standalone app. I've used RealFlow in the past and I don't like the feel on an external app. I'd much rather have something inside of Maya to make me feel 'at home'. Also, Maya offers a lot of powerful features that you'd have to create in your own application if you started from scratch.

As for ray tracer implementation I'd probably right a shader/DSO for Renderman/MentalRay rather trying to interupt the internal renderer. Not such exactly how to do this tho, I'll have to look into it ...

DIMO
11-21-2006, 09:58 AM
Hi,

Although I don't have a fluid simulation I wrote a direct raytracing routine for implicit surfaces for VRay/3dsmax. You can visit my blog to see my results. I am very interested in plugging a fluid solver into this. That would be cool.
I have a feature that allows to multiply a 3D procedural to the implicit function. This allows to generate coral like objects. It plugs nicely into VRay and supports all types of lighting. I don't have UVs.

If anyone of you wants to cooperate that would be cool. I contribute the Raytracing for VRay and you the fluid engine?

Best regards,

Dieter

Benr
11-21-2006, 02:40 PM
And I wrote a raymarcher plugin (http://www.xsibase.com/forum/index.php?board=6;action=display;threadid=20262) for direct volume rendering for Mental Ray / XSI. I assume it would be simple to convert to Maya. It would be fun to plug in grid data generated by a fluid sim.

yarniso
12-07-2006, 03:45 PM
Hi guys,

I don't mean to unnecessarily bump this thread, but I'm also very interested in fluids simulation. I'm reading a lot about it now and I'm planning to implement either a LBM or SPH based fluid simulation using Level Sets for surface generation.
Is there any place besides this thread where I can follow your progress? Personal websites or blogs or something like that?

Greets

yarniso
12-07-2006, 04:02 PM
Sorry, made a mistake. This post can be removed if possible

djwarder
12-13-2006, 10:42 AM
Ummm, nothing to show at the mo, still trying to get my head round the maths at present!! Might set up a blog if I get anything cool happening ...

yarniso
12-13-2006, 10:59 AM
Hi,

okay, cool. I know what you mean about the math. I'm diving into it as well, trying to overcome the occasional "where the hell did this equation come from? and what does it mean?" moment. :)
But we'll get there in the end. ;)

Greets, Bart

djwarder
12-13-2006, 11:58 AM
Hopefully!! :D Going thru implicit surface stuff at the mo, reading Osher/Fedkiw's book when I get a chance and still deciding which type of solver is best. I'd like to use LBM due to its simplicity, but it just seems to need way more memory that any other technique and there's very little literature on it compared to conventional finite difference methods. Will have to do some testing and see what works best ...

DIMO
12-30-2006, 09:33 AM
@djwarder:

How did you like Fedkiw's book? I bought it and was very disappointed. There's no source code in there, and no practical examples. The section about fluid sims are only a few pages, the rest is rubbish one doesn't need for fluid solving. Is there any other good book about fluid simulation there, with code examples like in Physically Based Rendering, From Theory to Implementation Matt Pharr (http://www.amazon.de/exec/obidos/search-handle-url/303-7677819-7847460?%5Fencoding=UTF8&search-type=ss&index=books-de-intl-us&field-author=Matt%20Pharr), Greg Humphreys (http://www.amazon.de/exec/obidos/search-handle-url/303-7677819-7847460?%5Fencoding=UTF8&search-type=ss&index=books-de-intl-us&field-author=Greg%20Humphreys) ?
That would be cool.

Best regards,
Dieter

djwarder
12-30-2006, 03:45 PM
Hi DIMO

Know what you mean about the Fedkiw/Osher book. I've looked at a copy from a workmate and didn't find anything that I couldn't really find online!

As for books on fluid simulation, apart from CFD books with an engineering bent, there's not much else I know of. I bought the 'Physics-Based Animation' book from Charles River and it gives a good introduction to simulation coding, but not much of fluids apart from SPH. There's quite a good bit on finite elements and finite differencing tho ...

yarniso
01-03-2007, 10:55 AM
Hi guys,

I know what you mean by your disappointment with the Osher/Fedkiw book. But then again it is supposed to be a mostly mathematical book. So I guess it was kind of to be expected and I still like the book. It would certainly be nice to have at least some information on actual implementation though. I had hoped this year's SIGGRAPH course would give that, but for as far as I could see it doesn't either. Let's see if something will appear soon, because more and more people start to work with level sets. And perhaps once we get some things up and running we could exchange thoughts/ideas as well.

Greets and good luck.

yarniso
05-08-2007, 09:16 PM
Hi guys,

are you still working on your respective implementations? I have been silently busy in the background and I soon hope to have something presentable.
I stumbled upon something interesting. http://www.magix.ucla.edu/software/levelSetLibrary/
A small particle level set library to pull some ideas from. There also is a small document with some nice explanation. Just thought I should mention it.

Good luck.

DIMO
05-09-2007, 06:27 PM

If I had knew this earlier, I would have used it for my project. Now I have my own fast marching implementation. But at least I understood it now:)

Best regards,

Dieter

djwarder
05-13-2007, 11:51 AM
Hey! Still working on it, but having trouble finding time, deadlines and all! Have seen that library before, looks interesting. Might focus more on getting the actual simulation part up and running and get it looking good with marker particles before tackling level-sets bigtime!

DIMO
07-10-2007, 07:36 AM
Hi there,

I had some time to look into the Level Set Library mentioned above. Did anyone try it? Because here both 2D and 3D project crash right away. But It looks promising.

Best regards,

Dieter

yarniso
07-12-2007, 08:18 AM
Hmm, strange. They ran just fine on my comp a while ago. Both 2D and 3D. I haven't used it in my own code though. I'm coding up my own lib because I want to learn a bit more about that stuff myself.

djwarder
07-12-2007, 10:06 AM
Hey DIMO! Just been to your site, looks like you've got some cool stuff on there. Sounds cool that you met Stephan, creator of 'Flowline', and that he was interested in your isosurface plugin. I think they started off with a similar plugin before they went fully into the full hardcore CFD stuff (http://www.chaosgroup.com/news/20040604-01.html)

As for levelset work, not really been looking into that at the moment, been looking more into the simulation side of things and trying to understand & code a 'conjugate gradient' solver. Its doing my head in!! :scream:

DIMO
07-13-2007, 07:16 PM
Yes, that's the page that got me started. And seeing their progress on "300"and poseidon is a good motivation. But I can't catch up with their development doing a little coding in my spare time. But I am having fun. No deadlines here:)
I wrote an email to the guy who wrote the level set library, but didn't get an answer yet. I am compiling with VS2005. Perhaps this is the problem. Was this meant for VS2003?

Best regards,
Dieter

merlin74
09-10-2007, 11:27 PM
guys, wondering what 's the progress you have been made.

Here is my attempt.

Sorry, the quality is poor (using only 40x40x40 grids). Also I don't know how to make a water material. Anyone got an idea? I use pbrt for rendering, BTW.

Fixed a stupid bug. Now looks much better. But particles seem to have problems in falling down once hitting the ceiling :)

yarniso
09-12-2007, 10:57 AM
Hey, nice progress. Looks quite good already.
As for myself development has come to a halt. Just have been too busy at work lately, couple of weeks of vacation and at the moment programmers-block. :) But I hope to get at it again soon. I'm planning to focus on some good level set code first, since I can use that in some of my work as well.
As for the water material, couldn't you just use a glass material and tweak the Fresnel parameters a bit if it doesn't look as you would like.
By the way, what do you use as a programming environment? All code of your own, or do you use any libraries? I find myself spending too much time on writing all kind of utility code.

Good luck and keep us up to date

merlin74
09-13-2007, 06:01 AM
Hey, nice progress. Looks quite good already.
As for myself development has come to a halt. Just have been too busy at work lately, couple of weeks of vacation and at the moment programmers-block. :) But I hope to get at it again soon. I'm planning to focus on some good level set code first, since I can use that in some of my work as well.
As for the water material, couldn't you just use a glass material and tweak the Fresnel parameters a bit if it doesn't look as you would like.
By the way, what do you use as a programming environment? All code of your own, or do you use any libraries? I find myself spending too much time on writing all kind of utility code.

Good luck and keep us up to date

yarniso, I coded most part of the program myself. I didn't build my own PCG solver but used Brison's code, which is very easy to incoporate.

I think you only need some basic tools. The only significant infrastructure is the fast marching method. I did spend a lot of time on it.

As to my current implementation, I only used liquid particles, similar to Foster and Fedkiw (2001). Will add air particles later.

Happy coding....

DIMO
09-13-2007, 08:27 AM
Hi,
good test. Do you have a link for brison's code?

Dieter

yarniso
09-13-2007, 11:00 AM
Correct me if I'm wrong, but I think it's this one:

http://www.cs.ubc.ca/~rbridson/fluidsimulation/

Greets.

djwarder
09-13-2007, 11:45 AM
Yep, that's the one I've looked at before.

Also, it seems that using 'conjuate gradient' for the pressure solve is the most usual algorithm, but recently have seen people using Jacobi & multigrid techniques (esp. on the GPU), what does everyone think about that? Which way is the best to go, as for me the Jacobi iterative solver looks the simplest and fastest, but maybe not the most accurate? But for computer fx, it doesn't really need to be 100% accurate, just look good right?

DIMO
09-13-2007, 11:54 AM
I even was at the fluid course at siggraph, but overlooked the source code on his page.
Anyone thought about a SPH based fluid solver?

Best regards,
Dieter

djwarder
09-13-2007, 01:45 PM
Anyone thought about a SPH based fluid solver?

Yep, been looking at all possibilities. Could be faster than a grid-based solver, but not sure how good it would be for getting a free-surface to render. I've also been wondering if using an LBM algoritm (like the sim in Blender) could be useful, but its more memory hungry than anything else, plus there isn't that much literature on it. Any ideas?

yarniso
09-13-2007, 02:28 PM
As far as SPH goes, the SIGGRAPH 2007 paper "Adaptively Sampled Particle Fluids" got me quite interested. SPH in general seems to be quite a nice approach, although I've not read nor experimented enough to give any well thought out views. In the paper they have a nice section on their surface model as well, avoiding the blobbiness found in earlier methods. I might dive into this at one point, but first want to get the level set based method working.

DIMO
09-13-2007, 02:56 PM
Yes, I was in that talk, too. The results he showed were very nice. And you wouldn't be restricted by the bounding box size any more.

Dieter

merlin74
09-13-2007, 05:47 PM
Yep, that's the one I've looked at before.

Also, it seems that using 'conjuate gradient' for the pressure solve is the most usual algorithm, but recently have seen people using Jacobi & multigrid techniques (esp. on the GPU), what does everyone think about that? Which way is the best to go, as for me the Jacobi iterative solver looks the simplest and fastest, but maybe not the most accurate? But for computer fx, it doesn't really need to be 100% accurate, just look good right?

I think, for levelset-based method, the solvers for pressure equation have to be accurate. Otherwise, there will be significant mass(volume) loss even if particles are used. In my implementation, I had used Gauss-Seidel iterations and it turned out to be too inaccurate.

Just my 2 cents...

djwarder
09-14-2007, 10:49 AM
Ah ok. So PCG is the way to go then? For me thats probably the most complicated part of all the solver, which makes a lattice-boltzmann sim that much more tempting if I could only fully understand that as well!! :shrug:

yarniso
09-14-2007, 12:22 PM
I guess you already know this, but there is a very nice explanation that's quite easy to follow in this paper: www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf (http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf)
I've worked myself through it with pen and paper and it's not that hard at all. The magic now seems to lie in finding a good precoditioner for PCCG, but I've seen quite a lot of papers on that as well. I will stick to basic CG first though.

djwarder
09-14-2007, 01:52 PM
Cheers for the link, have read it before, but will have to study it again!

DIMO
09-15-2007, 03:46 PM
Hi,

I am currently bringing my math back in shape here:
http://ocw.mit.edu/OcwWeb/Mathematics/18-085Fall-2005/VideoLectures/index.htm (http://ocw.mit.edu/OcwWeb/Mathematics/index.htm)

The video lectures 180805 Mathematical Methods for Engineers I (http://ocw.mit.edu/OcwWeb/Mathematics/18-085Fall-2005/CourseHome/index.htm) are a good alternativ to the TV in the evening :)

Dieter

yarniso
09-17-2007, 01:42 PM
Hi,
[/url]

The video lectures 180805 [u]Mathematical Methods for Engineers I (http://ocw.mit.edu/OcwWeb/Mathematics/index.htm) are a good alternativ to the TV in the evening :)

Dieter

Thanks for the link. Who says developers don't know how to have fun. ;)

DIMO
09-17-2007, 06:38 PM
Hi guys,

I am trying to implement the surface definition of this paper right now.
I am having a lot of artifacts with this. Two particles look like this:http://dimo3d.info/surfacedef.jpg
This is directly raytraced against the implicit surface function. There should be a smooth suface, but I always get those overshoot areas. And it doesn't get much better with more particles. The images in the paper show perfectly smooth surfaces. I have no idea why this is not working. That's what I am doing in pseudocode to calculate the field:
for (int i = 0; i<NumberofParticles;++i) //iterate through the particles nearby

{

d=Kernelfunction(Particles[i].center,Particles[i].radius,pp); //pp is the point that is evaluated

a+=Particles[i].center*d;

sum_d+=d;

sum_r= Particles[i].radius*d*0.5f; // I am using r/2 instead of the real distance to the surface. They mention this on p.5

}

if (sum_d==0)return 0.0f;

sum_r/=sum_d;

a/=sum_d;

return ( sum_r-(toVector(a)-pp).length());

The kernelfunction is :
float deltar = (pp-center).lengthSqr();

{

}

else u= 0;

return u;

Can anyone spot my error?

Dieter

yarniso
09-19-2007, 08:41 PM
Hmm, nasty little problem.

I didn't find anything wrong in your pseudo-code after a quick glance, although I do wonder about your r/2. Didn't they mention that using that transforms it into the Zhu/Bridson model? (Might have mis-read that, but I don't think it's the cause of your problem anyway). I'll have to look at it a bit closer and perhaps work it out for myself on paper, but based purely on the shape of your surface I have a feeling that there is a square somewhere that shouldn't be there or a multiplication where there should be a division.

Those are pure guesses though, but I thought I'd mention them anyway. Let me know if you make any advances and what the problem turns out to be. :) Good luck.

DIMO
09-19-2007, 09:32 PM
Hi,
thanks for the hints. I indeed turned it into the bridson/Zhu algorithm, because I don't have any of the fluid simulation stuff implemented yet. I thought I start with the surfacing.
I got a tip that this is what they say in the Sandfluid paper:

"
The most significant problem with this definition is artifacts in concave
regions: spurious blobs of surface can appear, since x may erroneously
end up outside the surface in concavities. However, since
these artifacts are significantly smaller than the particle radii we can
easily remove them without destroying true features by sampling
f (x) on a higher resolution grid and then doing a simple smoothing
pass.
"

So I guess I got it right but the algorithm is not suited for direct rendering :(

Best regards,

Dieter

crydalch
09-20-2007, 05:39 PM
Just wanted to chime in and gives kudos to seeing all of you work on this stuff. I don't understand 99.9% of it, but it's still interesting to see your thought processes.

Nice job.:thumbsup:

DIMO
10-17-2007, 12:05 PM
Hi,

I just wanted to show my progress.
I managed to get the bridson surfacing to work with direct raytracing. Additionally I wrote a connection to the SPH Solver from the Ageia PhysX Board. First tests are promising. You can have a look at my blog for more details.
http://labs.mackevision.de/labs/t_big.0016.jpg
http://labs.mackevision.de/labs/t_big.0041.jpg

Animation (http://labs.mackevision.de/labs/fluid3.mov)
Best regards,
Dieter

cbizz
10-18-2007, 04:22 AM
Amazing work...keep us posted as you make more progress :)

yarniso
10-18-2007, 08:05 AM
Nice progress. :thumbsup:
How did you solve the surfacing problem you were having before? I had started to write my own to see if I could verify your problem, but I'm too swamped in other duties at the moment to do any coding for myself.
Keep us posted on your progress. And great blog btw.

Greets

DIMO
10-18-2007, 11:14 AM
Hi,

the solution is to change the radius in regions of low density. I use a smoothstep funtion to bring the radius to zero when the density is low. There are still cases when the ghost particles cause artifacts but it's a lot better now. The advantage of having exact motionblur for the fluids now outweights the artifacts by far :)

Dieter

djwarder
10-24-2007, 09:46 AM
Cool, nice work Dieter! Considering its just using the standard AGEIA SPH code it looks great, tho I'm not sure if its me or not, but it looks like there may be some volume loss in the anim.

Have been looking a lot at Zhu & Bridson's paper you mentioned and really like the idea of a hybrid solver and am considering bypassing level sets all together and using a point-based rendering approach. Does this sound viable?

DIMO
10-25-2007, 06:58 PM
Hi,

I am a bit disappointed about the AGEIA SDK. There's a 32k particle count limit. I bought a PhysX card (it's only 100 bucks), because I thought that it might be software mode related, but it isn't. 32k particle is not enough for most fluid problems. The dev support from ageia hasn't replied to any of my questions yet. And it's very hard to find good fluid settings.
On the other hand with a PhysX Card in the machine it's quite interactive.
Might be a good addition to the pflow toolset for doing splashes etc. But it's not an option for complex fluid simulations :sad:
I just implemented it to see if I can do it anyway:)

I think in the end the ultimative fluid engine will have both - particles and levelsets. Perhaps levelset based solver for the main surface and SPH engine for the drops etc or something like that.
From the results I got I think that with newer surfacing algorithms it will be possible to get rid of the blobbiness that SPH simulations had. And take advantage of the better support for motionblur and volume preservation.
After having seen what the PhysX Card can do for performance I think I should definetly try to do something with CUDA or something like that. The fun begins when you can just press the play button...

Best regards,

Dieter

djwarder
10-26-2007, 12:26 PM
I am a bit disappointed about the AGEIA SDK. There's a 32k particle count limit.

32k? Would have thought you need 100,000s of particles to get any good results, tho I guess the SDK is for games use really. I think you're right tho, a pairing of a levelset engine and a particle system (SPH, MLS, etc) is a good combo. I think that's what FLOOD seems to do, although its not beta yet (and not sure when it will be!), so can't say for sure. Also, can't remember if this was mentioned before, but did you see the paper Pixar presented at Siggraph on getting surfaces from particles? Might be some use :

http://graphics.pixar.com/SurfacesFromParticles/paper.pdf

DIMO
10-26-2007, 03:37 PM
Hi,

from what I understand from the paper they use the Zhu/Bridson model as well. I think they need meshes that are continuous during one frame to tag certain properties to it because they rely on polygons for rendering and need motionblur.
My approach is to directly raytrace the surface without polygons. I do not need continous meshes.
Using meshes will probably render faster. I have a BVH for my particles to speed up rendering but it's still slower than meshes. But it's more effort to get proper motionblur with meshes.

Best regards,
Dieter

djwarder
10-26-2007, 03:54 PM
Yep, direct rendering is the way I'd like to go. Not sure about speed issues, but I would have thought the result would look better than meshing the surface. Also, for meshing I guess the quality depends on the tesselation of the mesh, whereas rendering it implicity is independent of this. What kind of rendertimes are you getting?

DIMO
10-26-2007, 04:36 PM
I have a big difference between "with refractions" and "without refractions".
Without refractions it's pretty fast and not much slower than with meshes. I do not have any mesh generation delays. It starts rendering immediately. If you just do testrendering without antialiasing it's even faster than mesh based rendering.
With refractions I have to step through the inner regions of the fluids, which means rayintersections with a lot of particles. It gets really slow then.
Perhaps I can post some renderings with timings.

I do not have any comparisons regarding motion blur, because I think there is no way to motionblur blobmeshes in 3dsmax right now:)

Best regards,
Dieter

DIMO
12-06-2007, 06:11 PM
Hi there,

I for all who have missed it. The new CUDA SDK from NVidia is out. It has sample code for Particle interaction and for eulerian fluids. It is so f---ing fast that I had tears in my eyes :). And it has no limitation like the PhsysX SDK has for the particle count. I already simulated 2 Mio particles with 3 fps with it. But it's just collisions for now. No SPH stuff yet. But that can be changed....:)

Best regards,

Dieter

yarniso
12-06-2007, 06:31 PM
It is absolutely great stuff.
At the moment I'm using CUDA for my work trying to implement some cloth and softbody simulations. When I installed the 1.1 SDK and ran the n-body simulation I noticed myself staring at the screen for several minutes. So much power. And especially problems like fluid simulations and particles systems are ideally suitable for the hardware.
Now let's see if I can do something cool with it for a problem which is slightly less ideal for the platform.

DIMO
12-07-2007, 08:16 AM
Same here,
we were just staring at the demos. Currently trying to implement the adaptive sampled SPH particles on it...

Best regards,

Dieter

skydave
12-07-2007, 11:35 AM
Hi guys,

I currently try to implement surface construction from a given set of particles based
on the Bridson/Zhou paper from 2005.

I build a triangle mesh instead of rendering the implicit surface. But maybe you can
help me anyway. I have the following questions:

1. what values for phi(x) are assigned to gridpoints which dont have
any particles within their range?
As far as I see phi(x) can only be computed if there is at least one
point in its neighbourhood. What must be done
if there is none?

2. How exactly is the smoothing pass done? Currently I assign a
weighted average of all gridpoints within a 3x3 (edit: 3x3x3) range matrix to each
gridpoint. The results from smoothed phi are not satisfying (means: they are shit).
What exactly is meant with "[...] grid smoothing, restricted to decreasing phi [...]" ?

Any help would be appreciated.
Thanks,
David.

DIMO
12-07-2007, 08:29 PM
Hi David,

I have also implemented a marching cubes algorithm for my plugin to have a viewport mesh representation.
You can initialize the values of the grid with with a high value, 1e16f or something like that. You should try to not visit cells with no particles nearby.
The smoothing is done to get rid of the "ghost" particles. Same problem I stated earlier in this thread. I think more important will be to smooth the resulting mesh.
For what application are you developing? I would be interested in your calculation time.
Have you planned something like multithreading?

Best regards,

Dieter

merlin74
12-10-2007, 06:56 PM
It seems all you guys are moving towards the particle-based methods. Has anybody tried particle-levelset-set method? I am still struggling in the fighting with the boundary conditions.

BTW, just noticed that Frank Losasso had another paper (http://physbam.stanford.edu/~fedkiw/papers/stanford2007-05.pdf) on PLS. This time coupling SPH with PLS. Seems generating good results with sprays now.

Cheers,

merlin74
01-16-2008, 09:03 PM
Hi all,

I got questions about Error Correction in Particle Level Set method.

I am struggling in implementing the particle level set methods as
described in "Enright, D., Marschner, S. and Fedkiw, R., "Animation
and Rendering of Complex Water Surfaces", SIGGRAPH 2002, ACM TOG 21,
736-744 (2002)."

As to the error correction using escaped particles, the paper states
" ... The reconstruction of the
implicit surface occurs locally within the cell that each escaped
particles currently occupies. Using equation 3, the phi_p values of
escaped particles are calculated for the eight grid points on the
boundary of the cell containing the particle. ....". I don't
understand which these "eight grid points" refer to. I am using the
staggered MAC grid with level set function stored at cell center and
velocities on the cell face. I searched almost all papers related to
this method and couldn't find any information to clarify this issue.

One possibility I think is the 8 corner points of the cell containing the particle. But then, after level set function values at these corner points are corrected, how can they merge back to the center where it is defined? Simple linear interpolation wouldn't work because the characteristic information is lost.

In another paper "Real-time Particle Level Sets with Applications to Flow Visualization", it is stated that "... Each escaped particle p contributes to the eight surrounding grid voxels through ....". This seems suggesting the particle-defined level set function phi_p should be evaluated at the cell center, not the corners.

I am really confused here.

Has anybody got an idea about which grid points shall be?

Thanks,

merlin

yarniso
01-18-2008, 04:40 PM
Hmm, I might be wrong here (I just confused myself) but aren't the levelset values stored at the corners of each voxel in stead of at the center? And therefore you would figure out the level set value for each of these eight corners by this relation between particle position and corner location (i.e. the distance between the two)?

As I say I might be wrong here because I answered without checking, but that's how I always saw it. let me know if it makes any sense to you.

merlin74
01-18-2008, 09:19 PM

I am pretty sure level set function values are stored at the cell center if a staggered MAC grid is used (just like in two Enright et al. papers in 2002 and 2003), before Lassaso et al.(2004) implemented PLS on an octree structure.

Of course now storing them on corners of the cell makes more sense to me, in terms of error corrections using particles. But I don't want to change my grid structure at least for now.

Another difficulty associated with my grid is that I don't know how to treat levelset values at velocity points. I interpolated cell centered levelset functions, which have been reinitialized and corrected, onto the velocity grid points which are on the face center of the cell. Then do I need to reinitialize them before I can extrapolated velocities into the air region? Or these values are already signed distances?

merlin

Hmm, I might be wrong here (I just confused myself) but aren't the levelset values stored at the corners of each voxel in stead of at the center? And therefore you would figure out the level set value for each of these eight corners by this relation between particle position and corner location (i.e. the distance between the two)?

As I say I might be wrong here because I answered without checking, but that's how I always saw it. let me know if it makes any sense to you.

skydave
03-11-2008, 05:26 PM
Hi,

thank you Dieter for your helpfull comment. At the end I got the best smoothing results
when I did a signed distance computation on those gridpoints which dont have any
particles in their neighbourhood...

Anyway, I finally got it working and together with the developed fluidsimulator I could
produce the following result:

http://web.inf.tu-dresden.de/%7Edk402538/msc/water50024.png

Here you can see the animation which was rendered in 3dsmax:
Here are 10% of the particles in action:

I also tried to implement the Mohr-Coloumb friction model which was proposed in the
Zhou/Bridson paper to model sand:

I had a very very hard time getting the sand-stuff to work and still I am not happy with it.
Currently I'm desperately looking for someone who has successfull implemented sand-
simulation using this method or who at least tried it. So if you know somebody...

Does anybody know a good forum, mailing list, google-group etc. for physical based
animation topics in the cg-field? I still havent found the right place in the internet
to ask and discuss such problems.

David

cbizz
03-11-2008, 10:28 PM
David and Dieter,
amazing results you guys. All the animations/stills I have seen here have been very impressive. I have been reading about all this CFD stuff, and hope on writing a working simulator this summer once I finally have time for a project like this.

Anyway, great work, and don't hesitate to post any other images/videos you have produced, I'd like to see anything else you have created.

DIMO
03-14-2008, 05:02 PM
Hi David,
great results! I wish I had more time to work on the fluid stuff, but I didn't have time to code anything at all the last few month. Busy earning money... :)
But I am not yet tired of the fluid stuff.
There is still more to come.

Best regards,
Dieter

merlin74
05-05-2008, 04:46 PM
Hello, you guys' amazing work really makes me feel I should catch on.

Just don't have much spare time to work on it. But still I have made some progress on my particle levelset implementation.

There still are various issues, e.g., a small pocket of water close to the ceiling won't fall off.

Cheers,

Bin

Phibmobil
05-05-2008, 10:32 PM
Good job !! very exciting, these fluid sims are beautifull, keep it up.

yarniso
05-06-2008, 08:21 AM
Damn, you guys are all producing nice results. A shame that work has become increasingly busy over here. So unfortunately no fluids for me at the moment. (Not even my own research at all at the moment. Deadlines force me to work on ActiveX controls and web services. :shrug: ) I hope to get back to all of this though.
Keep up the good work!!

merlin74
06-02-2008, 05:46 PM
Just made a test animation with curved boundaries (a sphere).

Now I am much more interested in coupling SPH to PLS to have sprays accurately simulated.

skydave
06-03-2008, 08:51 AM
Hey Merlin,

great work! It seems PLS are quite demanding.

Do you use a MAC-Based approach for your simulation? And can you tell what gridsizes do you use?
As far as I see there is a trade-off between using SPH and MAC.
MAC suffers from volume-loss while SPH makes it harder to capture the high-details.

merlin74
06-04-2008, 06:21 AM
Hey Merlin,

great work! It seems PLS are quite demanding.

Do you use a MAC-Based approach for your simulation? And can you tell what gridsizes do you use?
As far as I see there is a trade-off between using SPH and MAC.
MAC suffers from volume-loss while SPH makes it harder to capture the high-details.

skydave, I am using staggered MAC grid. The resolution is 120x60x80. The actual grid for fluid is 110x50x70 (5 cell thickness at each boundary).

I just found out there are still some errors in that simulation. I am fixing it now.

I think SPH is suitable for details too fine to be resolved by the underlying grid. Indeed, using PLS only still loses some volume inevitably.

yarniso
09-10-2008, 02:26 PM
Perhaps interesting to some of you (if you haven't already seen it), Robert Bridson has published a book called "Fluid Simulation for Computer Graphics". Take a look at http://www.cs.ubc.ca/~rbridson/fluidbook/

I liked his SIGGRAPH course, so perhaps the book will be nice to. He also links to quite a nice thesis by one of his master students on surface reconstruction from particles.

Just though I'd mention it.
Greets.

djwarder
09-11-2008, 09:32 AM
Yay, can't wait for this book. But when's it out? Some sites say this september, some say last month and Foyles told me august last year!! :argh:

yarniso
09-11-2008, 09:52 AM
The publisher's site says this september, so I guess that one is the most reliable.

merlin74
09-11-2008, 04:25 PM
Already ordered one at Amazon. Hopefully it will provide enough details on particle levelset method. At least according to Bridson's website, this books is very PLS oriented.

It is to be released on 09/18. I expect to receive it by the end of this month.

DIMO
09-14-2008, 08:23 AM
Thanks for the info. Order placed :)

Dieter

djwarder
09-17-2008, 09:19 AM
Just spoke to the publisher, looks like won't be out in the UK til late October! :sad: I can't wait that long!!

startnow
10-06-2008, 08:10 AM
I am also working on level set fluid. I implemented level set advection using semilagrangian
advection, but its not working. If I use constant velocity, then the surface advects properly.
But when I apply external velocity field(computed by Navier stokes), the surface breaks into pieces. So My questions are

1. Should I use HJ-ENO or HJ-WENO for the level set advection?
2. For solving the pressure of fluid, I did not use PCG, is it the reason?

Would anyone plz suggest? Thanks in advance.

djwarder
10-29-2008, 10:29 AM
Anyone managed to get a hold of a copy of Rob Bridson's book at all? Still not out here in the UK! :banghead:

yarniso
10-29-2008, 10:33 AM
Nope. Here in Switzerland they tell me it will become available in December (through amazon.de). :(
I hate being patient. :D

Dubbie
11-10-2008, 11:25 PM
My copy came in the mail a few days ago.

Good book - have to say it's a lot easier to understand than the Fedkiw one.

Benr
11-11-2008, 05:24 PM
Oddly I just got a cheap copy at a local used book store. Found it on Amazon and then realized the seller was in my town.

JohnDes
11-21-2008, 04:23 PM
Great work....great discussion...and great that you are all sharing the progression with those of us wanting to get started in this field to build and app or other...

I am interested in try to do some simple fluid sim/interaction in realtime engines...I know ambitious and crazy but hey...thats what makes this fun.

Anyway, besides all the links given in this thread ...what do you all think about deconstructing the source code for Blender's fluid solvers? Would that maybe be another good place to learn some tricks etc?

Thanks...and keep it coming...

yarniso
11-22-2008, 05:07 PM
Hi,

well, you can of course learn from the work of others. That's always a good idea. But I would not just take the source and try to figure things out from there. If you're interested in the Lattice Boltzman approach, which is the approach taken by Blender's fluid solver if I'm not mistaken, then you might want to look at the excellent papers and thesis of Nils Thürey (the author of Blender's fluid simulator) first for some explanation. http://graphics.ethz.ch/~thuereyn/ntoken3/index.html

I don't know what kind of fluids you exactly are thinking of for real-time interaction (full fluids, surfaces, sprays,...) but the most common choice would be a particle solution (although I can easily contradict myself here by citing numerous links of people trying all kinds of real time fluids using stable-fluids-like approaches and many others).
To get started take a look at some of the work here: http://graphics.ethz.ch/research/physics/fluids.php

Another interesting (fluid-like) approach are the wave particles of Cem Yuksel:
http://www.cemyuksel.com/research/waveparticles/

Good luck and let us know when you've got something to show. :)

JohnDes
11-25-2008, 03:33 PM
Thanks very much for the links and encouragement...I will definitely post something once Ive got something to show.

Also I am glad you mentioned who was the author(s) of the Blender solvers....that was one reason to look at the source was to get a basic "works cited" as well.

Thanks again very much for the wonderful links...

olson
11-25-2008, 07:27 PM
Anyone managed to get a hold of a copy of Rob Bridson's book at all? Still not out here in the UK! :banghead:

I received my copy directly from AK Peters last week. They might have international shipping if the book is not available at any distributors in the UK. Cheers!

merlin74
12-24-2008, 01:58 AM
Hi Guys,

I think it's time to summarize the implementation of my particle level set fluid simulator and plan for future development.

It started off by combining Stam's stable fluid solver and Foster and Fedkiw's particle enhanced level set approach. Then I immediately jumped to some recent developments such as, vortex particles, MacCormack Method, and divergence free velocity extrapolation. Some of these extensions are successful, and some not. During the whole process, the foundational method for levelset has been fast marching method (FMM) for reinitialization and semi-lagrangian method for advection. Helped by the particles, this has been what Enright et al. (2004) advocated and a series of other authors used (Losasso's octree method, Gundelman's coupling to thin shells, and Losasso's multiple level sets and melting solids into liquids). Octree is great, but its implementation is too complex. Without it, however, the results look very bad unless a high resolution grid is used. But the original paper by Enight et al. (2002) produced highly realistic result. How can that be?

In recent months, I have been modifying the code to replace FMM with solving reinitialization equation with 5th order WENO and 3rd order Runge-Kutta. Futhermore, level set advection has also been done by the 5th order WENO and 3rd order Runge-Kutta. Particles are advected with 3rd order Runge-Kutta. Essentially I have turned the code into Enright's 2002 incarnation. The disadvantage is the performance hit. But there is advantage too. Now the code is readily parallelized for multi-threading and multi-processors.

Here is the present status, although it's 6 years behind the front of the current research.
You may notice all those mass loss when liquid sheets thin out. This is the best I can do on this grid resolution.

What's about next? Clearly octree is an ideal candidate, as it can resolve those thin sheets the underlying grid is missing. But it requires some major data structure changes in the code. In addition, for any decent production simulation, even an octree couldn't handle all the details on a single processor. So that leaves the only option: parallel execution. Fortunately, my previous code changes make the task relatively easy.

startnow
12-27-2008, 08:49 AM
Hi Marlin,

Congrats that you became successful in level set fluid simulation. I have just started working on it. I have a number of questions but found no body to answer. Hope you will help me.

1.Did you consider the signed distance value "phi" as the density of fluid?
2. How did you implement the velocity extrapolation?
3. Did you consider the level set updating step as a subcycle of
semilagrangian update?

ViCoX
01-05-2009, 11:13 PM
YYYber cool thread! Keep it comming guys!
Pffttt.. Makes my brain hurt to see so smart people here. : )

CGTalk Moderation
01-05-2009, 11:13 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.

1