[Haskell-cafe] Re: [GSoC] A data parallel physics engine

[Sebastian Sylvan]

On Mon, Mar 10, 2008 at 11:48 PM, Manuel M T Chakravarty <
chak at cse.unsw.edu.au> wrote:

> Roman Cheplyaka:
> > I'm looking for interesting project to work on during Google Summer of
> > Code. So I found [1]"A data parallel physics engine" ticket and got
> > excited about it. I'd like to know interested mentors and community
> > opinion about the complexity of such project.
> >
> > I have not very deep knowledge about both NDP and physics engines. Is
> > it feasible to learn all the necessary stuff during these 2 month
> > before
> > SoC starts?
> >
> >  1. http://hackage.haskell.org/trac/summer-of-code/ticket/1535
>
> Using NDP is actually pretty easy, that is, for somebody who is
> already used to functional programming.  The idea is, for anything you
> want to have running in parallel, don't use explicit recursion, but
> use list comprehensions (well, array comprehensions, but it's the same
> idea) and combinators like mapP, foldP, scanP, etc (which are also
> like their list variants).  Here, for example, is quicksort:
>
> > qsort      :: Ord a => [:a:] -> [:a:]
> > qsort [::]  = [::]
> > qsort xs    = let
> >               m  = xs!:0
> >               ss = [:x | x <- xs, x <  m:]
> >               ms = [:x | x <- xs, x == m:]
> >               gs = [:x | x <- xs, x >  m:]
> >               qs = [:qsort ys | ys <- [:ss, gs:]:]
> >             in
> >             qs!:0 +:+ ms +:+ qs!:1
>
> where [:a:] is the type of arrays of as, [::] is an empty array, [: ..
> | .. :] are array comprehensions, (!:) is array indexing, and (+:+)
> array concatenation.  The only funny thing is the bindings of qs,
> where we put ss and gs into an array and apply qsort recursively
> *inside* an array comprehension.  This is so that the two recursive
> calls to qsort happen in parallel.
>
> Getting good parallel performance is the tricky bit, but in a project
> like the physics engine for GSoC, a basic parallelisation strategy is
> sufficient and performance can then be improved incrementally.  We
> don't expect anybody to implement a fully-fledged, fully parallelised,
> high-performance physics engine during GSoC.  It is rather about
> laying a solid foundation on which we can then build over time.  (GSoC
> is a lot about getting exciting open source projects of the ground,
> not about producing a polished product that doesn't change anymore
> after GSoC.)
>
> Besides, there is more to physics engines than just collision
> detection.  Another aspect is physical simulations of non-solid
> bodies, such as liquids and cloth - re the latter, see <
> http://graphics.snu.ac.kr/~kjchoi/publication/cloth.pdf<http://graphics.snu.ac.kr/%7Ekjchoi/publication/cloth.pdf>
>  > for an interesting SIGGRAPH paper.  What aspect we'd cover in the
> GSoC project would really be a matter of what you are most interested
> in.
>


There are a variety of approximate fluid simulation techniques (see
SIGGRAPH, GDC papers etc., for example you could do the heightfield based
approach, that simplifies the equations by working in 2D -- this runs in
realtime on most decent hardware!) that aren't too complicated to implement,
but looks really really cool. So I'd recommend doing something in that area
because it's a "high coolness factor per unit time spent coding" kind of
thing :-)


-- 
Sebastian Sylvan
+44(0)7857-300802
UIN: 44640862
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080311/15cd585f/attachment.htm