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

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.

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.

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 non-orthogonal 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

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)

If combining karl and jeff moder's idea. it seems the particle can be tracked. but this method is time-consuming. 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 time-consuming. 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

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 time-stepping, 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).

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.

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 2-d or 3-d) (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).

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 3-d. 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.

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?

The idea of binary or quad-tree (2D) (oct-tree 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 (particle-based) computational methods. The application of this method directly to the problem of particle tracking in a traditional finite-volume 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, FEDSM2005-77042, June 19-23, 2005, Houston, Texas USA

Adrin Gharakhani

Our problem is how to locate particle in volume cell, not to detect particle collision. For particle collision detection, quad-tree (2D) (oct-tree 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".

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 quad-tree. For a second pass (which may be necessary for anisotropic elements) one can then use the divergence theorem as proposed earlier...

Adrin Gharakhani