<br><br><div class="gmail_quote">On Mon, Mar 10, 2008 at 11:48 PM, Manuel M T Chakravarty &lt;<a href="mailto:chak@cse.unsw.edu.au">chak@cse.unsw.edu.au</a>&gt; wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Roman Cheplyaka:<br>
<div class="Ih2E3d">&gt; I&#39;m looking for interesting project to work on during Google Summer of<br>
&gt; Code. So I found [1]&quot;A data parallel physics engine&quot; ticket and got<br>
&gt; excited about it. I&#39;d like to know interested mentors and community<br>
&gt; opinion about the complexity of such project.<br>
&gt;<br>
&gt; I have not very deep knowledge about both NDP and physics engines. Is<br>
&gt; it feasible to learn all the necessary stuff during these 2 month<br>
&gt; before<br>
&gt; SoC starts?<br>
&gt;<br>
&gt; &nbsp;1. <a href="http://hackage.haskell.org/trac/summer-of-code/ticket/1535" target="_blank">http://hackage.haskell.org/trac/summer-of-code/ticket/1535</a><br>
<br>
</div>Using NDP is actually pretty easy, that is, for somebody who is<br>
already used to functional programming. &nbsp;The idea is, for anything you<br>
want to have running in parallel, don&#39;t use explicit recursion, but<br>
use list comprehensions (well, array comprehensions, but it&#39;s the same<br>
idea) and combinators like mapP, foldP, scanP, etc (which are also<br>
like their list variants). &nbsp;Here, for example, is quicksort:<br>
<br>
&gt; qsort &nbsp; &nbsp; &nbsp;:: Ord a =&gt; [:a:] -&gt; [:a:]<br>
&gt; qsort [::] &nbsp;= [::]<br>
&gt; qsort xs &nbsp; &nbsp;= let<br>
&gt; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; m &nbsp;= xs!:0<br>
&gt; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ss = [:x | x &lt;- xs, x &lt; &nbsp;m:]<br>
&gt; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ms = [:x | x &lt;- xs, x == m:]<br>
&gt; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; gs = [:x | x &lt;- xs, x &gt; &nbsp;m:]<br>
&gt; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; qs = [:qsort ys | ys &lt;- [:ss, gs:]:]<br>
&gt; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; in<br>
&gt; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; qs!:0 +:+ ms +:+ qs!:1<br>
<br>
where [:a:] is the type of arrays of as, [::] is an empty array, [: ..<br>
| .. :] are array comprehensions, (!:) is array indexing, and (+:+)<br>
array concatenation. &nbsp;The only funny thing is the bindings of qs,<br>
where we put ss and gs into an array and apply qsort recursively<br>
*inside* an array comprehension. &nbsp;This is so that the two recursive<br>
calls to qsort happen in parallel.<br>
<br>
Getting good parallel performance is the tricky bit, but in a project<br>
like the physics engine for GSoC, a basic parallelisation strategy is<br>
sufficient and performance can then be improved incrementally. &nbsp;We<br>
don&#39;t expect anybody to implement a fully-fledged, fully parallelised,<br>
high-performance physics engine during GSoC. &nbsp;It is rather about<br>
laying a solid foundation on which we can then build over time. &nbsp;(GSoC<br>
is a lot about getting exciting open source projects of the ground,<br>
not about producing a polished product that doesn&#39;t change anymore<br>
after GSoC.)<br>
<br>
Besides, there is more to physics engines than just collision<br>
detection. &nbsp;Another aspect is physical simulations of non-solid<br>
bodies, such as liquids and cloth - re the latter, see &lt;<a href="http://graphics.snu.ac.kr/%7Ekjchoi/publication/cloth.pdf" target="_blank">http://graphics.snu.ac.kr/~kjchoi/publication/cloth.pdf</a><br>
&nbsp;&gt; for an interesting SIGGRAPH paper. &nbsp;What aspect we&#39;d cover in the<br>
GSoC project would really be a matter of what you are most interested<br>
in.<br>
</blockquote><div><br>&nbsp;</div>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&#39;t too complicated to implement, but looks really really cool. So I&#39;d recommend doing something in that area because it&#39;s a &quot;high coolness factor per unit time spent coding&quot; kind of thing :-)<br>
</div><br clear="all"><br>-- <br>Sebastian Sylvan<br>+44(0)7857-300802<br>UIN: 44640862