
[Sponsors] 
August 22, 2005, 09:22 
Tracking particles

#1 
Guest
Posts: n/a

Does anyone know where I can find an efficient algorithm to locate which computational cell a particle is in for tracking particles through a simulated flow field on an unstructured mesh?
Thanks, Karl Kevala 

August 22, 2005, 23:27 
Re: Tracking particles

#2 
Guest
Posts: n/a

You can judiciouly design a hash function that maps into the corresponding unstructure cell where the particle is dwelling. Alternatively you can have a data structure where you maintain a list of all cells surrounding every cell (you do it only once!). Subsequently, the particle and initial cell location can be tied into one single struct variable. Pl. feel free to express, if it sounds too cryptic.


August 23, 2005, 05:00 
Re: Tracking particles

#3 
Guest
Posts: n/a

hi,pfzczc pngnzik. if the geometry is changed, does the hash function need to be designed again? I prefer to the second method. But It seems I haven't understand the idea, can you detail it or provide me some reference papers or books. Thanks in advance.


August 23, 2005, 10:35 
Re: Tracking particles

#4 
Guest
Posts: n/a

I was thinking to start from the second approach. That is, I have an array of cell structures, with a field containing cell centroid coordinates, a field with pointers to all neighboring cells, and a field with a pointer to the (8) cell nodal coordinates.
Thus, after updating a particle position, I look at the distance of the particle from the centroid of the cell that it was in (before updating), and compare that with the particle distance from each of the neighboring cell centroids. Then, assume that the particle is in the cell for which the computed distance is smallest. I don't like this method because it is not rigorous. With hexahedral cells, that can have arbitrary nonorthogonal faces, the above method will give only an approximation to the "correct" cell location. After locating the "closest" centroid, there must be some type of fast algorithm to check if the particle is really in the volume bounded by the faces. Is there some paper on this problem that you know a ref. for? Karl 

August 23, 2005, 16:15 
Re: Tracking particles

#5 
Guest
Posts: n/a

A simple way to check if a particle P is within an arbitrary cell i is the following IF the outward normal to and the centroid of each face of cell i is either already known or easily calculated:
1) create vector pointing FROM particle P to the centroid of face k of cell i x = xface(k)  xpart(P) y = yface(k)  ypart(P) z = zface(k)  zpart(P) where xface(k),yface(k),zface(k) = centroid of face k xpart(P),ypart(P),zpart(P) = particle location 2) if particle P is inside cell i, then the dot product (x,y,z) dot (nx(k),ny(k),nz(k)) for ALL faces k=1,nfaces(i) of cell i should be positive, otherwise particle P is not within cell i, where nx(k), ny(k), nz(k) = outward normal to face k (ie, out of cell i) 

August 23, 2005, 20:57 
Re: Tracking particles

#6 
Guest
Posts: n/a

If combining karl and jeff moder's idea. it seems the particle can be tracked. but this method is timeconsuming. I mean each cell have 8 neighbours for 2d griddings, and 26 for 3d griddings. if time step is small and the number of particle is big, only the time to locate particle position is amazing, but to detect the interaction between particle is most timeconsuming. Just in this morning I get a new idea, I am not sure it is feasible. We can use a series of boxes to divide the whole computational domain. often to locate a particle in a group of boxes is very easy. at the beginning ,we need to find which box all the volume cell belong to(do it only one). During the simulation, we just locate particle in boxes,then the volume cell. if a boxes include more than one cell, we can calculate the distance between particle and centroid of cell, and find the minimum (like karl's) or just follow Jeff Moder's idea. Hope the discussion can move on


August 24, 2005, 13:01 
Re: Tracking particles

#7 
Guest
Posts: n/a

My previous post was only about how to determine if a particle was in a particular cell. Efficient coding to decide which new cells (if any) to check for containing a particular particle has many possibilities and can be very dependent of data structure, parallel processing, particle solver timestepping, etc... Some of this may come down to a choice between how much precomputed data you want to store (memory) versus how much data you want to recalculate each particle seach (CPU time), and possibly how much message passing you want to do (if running parallel).


August 24, 2005, 18:58 
Re: Tracking particles

#8 
Guest
Posts: n/a

to Jeff Moder. Yes, I support your idea.Now I am having a headache on how to track particle in a complex geometry reasonably. Would you show me how to handle with a usual condition? that is, a structure grid in CFD is adapted, there is no parrallel. when calculate the particle trajeroy at any time step, the previous position of particle is known, how can I decide which cell the particle locate in. I will appreciate you can help to describe the process comprehensively. Thanks in advance.


August 24, 2005, 23:24 
Re: Tracking particles

#9 
Guest
Posts: n/a

Looks like you have generated a good discussion. The key difficulty appears to be particle search step and not the verification step. When you have the updated particle position you would like to find out to which cell does this particle belong ? You can follow a simple rule (i) Check if it is with in the same particle (ii)then, check the first neighbors (8 or 26 cells depending on 2d or 3d) (iii) you can even recursively look for neighbors of neighbors etc... till you end up in a successful search. The idea putforward by Harry looks elegant (this is in the realm of hash function design with an appropriately coupled linked list between box and cells).


August 27, 2005, 16:26 
Re: Tracking particles

#10 
Guest
Posts: n/a

Thanks Jeff for that nice method of determining an interior point. I do not understand what a hash function is.
On the search algorithm of checking neighbors, in practical situations this may not be that time consuming even in 3d. That is, you don't have to do the "interior point" algorithm for all 26 neighbors. It seems reasonable to run a loop where you perform the check for the most likely neighbors as Prasad says. That is, assume the particle is in one of the 6 neighbors that actually share a face (not just a node). Compute these 6 squares of the distances, d^2. The most likely cell where the particle would be is that cell for which d^2 is min. You can perform the interior check for this cell only, chances are great that this will be the correct cell. If not, just loop over the other 5 candidates untill you find the cell. In general, the you will rarely have to check more than 1 or 2 cells. If by rare chance the particle is not in these six cells, you can move recursively (to ultimately cover all 26 neighbors) as suggested previously. 

August 28, 2005, 23:11 
Re: Tracking particles

#11 
Guest
Posts: n/a

Thanks Karl for detailing the algorithm of checking neighbours. But I have some queries on this approach. that is, For the simulation of a system containing a fluid and particles, we often calculate the fluid flow and particle trajectories respectively. when simulating the motion of particle, we need the fluid speed of volume cell where the particle locate. So the problem can be simplified that the position of particle is known, and we have the information of cells of fluid, How can we quickly find which cell the particle is about to locate, not the exact cell?


August 29, 2005, 13:57 
Re: Tracking particles

#12 
Guest
Posts: n/a

The idea of binary or quadtree (2D) (octtree in 3D) is used quite frequently for fast search (using the same "box" idea mentioned by Harry), and is indeed the cornerstone of most meshless (particlebased) computational methods. The application of this method directly to the problem of particle tracking in a traditional finitevolume type CFD was presented recently in:
Jens A. Melheim, Matteo Chiesa, and Anders Gjelsvik, "Formulation and Numerical Performance of an Adaptive Algorithm for Efficient Collision Detection," in 2005 ASME Fluids Engineering Division Summer Conference, FEDSM200577042, June 1923, 2005, Houston, Texas USA Adrin Gharakhani 

August 29, 2005, 19:26 
Re: Tracking particles

#13 
Guest
Posts: n/a

Our problem is how to locate particle in volume cell, not to detect particle collision. For particle collision detection, quadtree (2D) (octtree in 3D) should be very efficient. we can refer to MFIX code(www.mfix.org).a neigbour list combined with box approach is also very popular, and easy to implement,you can read this classical publication for the relevant idea, "B.N. Asmar , P.A. Langston , A.J. Matchettb, J.K. Walters. Validation tests on a distinct element model of vibrating cohesive particle systems,Computers and Chemical Engineering 26 (2002) 785â€"802".


August 29, 2005, 19:41 
Re: Tracking particles

#14 
Guest
Posts: n/a

Without having given it too much thought, the two problems seem to me to be very similar. A poor man's strategy (to get rid of most of the cells in the first pass) would be to assume the cell centroids are positions for a fictitious set of particles and do a "near particle search" on these new particles using the quadtree. For a second pass (which may be necessary for anisotropic elements) one can then use the divergence theorem as proposed earlier...
Adrin Gharakhani 

Thread Tools  
Display Modes  


Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
trying to simulate twophase jet flow with particles in surface injection  ajkratos  FLUENT  5  March 3, 2015 22:33 
Particle Tracking  Can't define water particles  CFDLife  CFX  2  October 3, 2008 06:12 
too many particles trapped on wall with tracking  Wouter  FLUENT  0  August 11, 2008 11:15 
Tracking fluid particles  Kristen  FLUENT  2  July 31, 2007 11:00 
Tracking particles backwards in time?  David  FLUENT  0  April 14, 2003 12:44 