Path: utzoo!mnetor!uunet!husc6!bloom-beacon!tut.cis.ohio-state.edu!osu-cis!att-cb!att-ih!alberta!calgary!blob
From: blob@calgary.UUCP (Brian Wyvill)
Newsgroups: comp.graphics
Subject: Re: Particle systems and simulation
Message-ID: <1528@vaxb.calgary.UUCP>
Date: 6 Apr 88 02:06:33 GMT
References: <609@imagine.PAWL.RPI.EDU>
Organization: U. of Calgary, Calgary, Ab.
Lines: 21
Summary: Try space subdivision to reduce your O(n*n)

In article <609@imagine.PAWL.RPI.EDU>, kyriazis@pawl20.pawl.rpi.edu (George Kyriazis) writes:
> 
> 	Hello world.  I am about to start a project about simulating rigid
> bodies or fluids made out of particles, ........
> What is the problem is that the naive method is of O(n*n)
> (calculating n-1 forces exerted to every particle).  Since I am not into
> physics very much, what I'd like to find is any simplifications on that.

If you are worried about calculating the force exterted by every particle on
every other particle, try dividing the world uniformly into a 3D grid of
voxels.  (You may find octree subdivison useful too.)   Into each voxel
place a reference to all the particles that can affect that volume.   Now
you only have to consider how particles affect each other within a voxel.
Of course you may find that all the particles are placed in every voxel in
which case you are back where you started!



-- 
        Brian Wyvill
	..!{ubc-vision,ihnp4}!alberta!calgary!blob