Any cheap route to find the elemet located at some xyz coordinate?

Any cheap route to find the element located at some xyz coordinate?

Thomas Driesner 09 Oct 2010 18:33

I wondered if one could use a 3D finite element mesh to handle our H₂O-NaCl phase diagram and fluid properties. An ignorant question in that context: is there a computationally fast and cheap way to find out which element is located at a given xyz coordinate in a 3D mesh of tetrahedra? If this is available in CS(M)P, it'd be fine (although I only detected iteration over potentially all elements), if there is any not-too-esoteric other way or even an open source library with that functionality, please let me know.

Last edited on 09 Oct 2010 20:04 by Thomas Driesner Show more

Re: Any cheap route to find the elemet located at some xyz coordinate?

apaluszn 14 Oct 2010 11:26

There are methods that can be used to speed up the search of an xyz coordinate in a 3D mesh. I am not aware of any methods implemented into the CSP core for this. Do you have any hints as of where your xyz coord might be? Like an original location? I have some methods implemented for my variable mapping that might be of use. How variable is your mesh? Is it static, dynamic? How many points do you need to search for? How many nodes does your mesh have (approx, millions, tens of millions)? Is your mesh hybrid 2D/3D?

Re: Any cheap route to find the elemet located at some xyz coordinate?

Thomas Driesner 15 Oct 2010 05:50

Hi Adriana

The idea would be to create a hybrid mesh 3D/2D of the phase diagram of H2O-NaCl. Phase boundaries would be represented by surfaces of, e.g., of triangles, the regions inbetween by volume elements like tetrahedra. I guess it'll be in the order of 10^5-10^6 elements to have sufficient resolution.

I'd need to pseudo-randomly access ANY xyz coordinate (BUT: for a given node in the simulation domain (not the lookup mesh) I'd probably have a good guess from the last time step in what region I should be).

As always, there is a trade-off to be considered: Currently, my 3D-lookup is a cartesian grid with variable resolution in certain regions. From given xyz (which are temperature-pressure-composition) I can jump to the correct position with one very quick operation and linearly interpolate in that rectangual cell.

This works fine, fast and cheap unless I am in a situation where a phase boundary (e.g. liquid/vapor) lies within that cell. Then there is a plethora of possible topologies how exactly that boundary lies in the cell (and whether there are one, two, or three boundaries). Figuring them out is possible but I'd like to avoid going through that pain. Up to now, I extrapolated across the boundary but this is probably not accurate enough for our upcoming strict transport CVFEM scheme (flow gets potentially unstable if fluid properties are even slightly inconsistent with each other).

So, creating an FE-based lookup table looked attractive as it (a) would give a very good geometric representation and (b) has intrisically consistent interpolation routines. The unattractive side would be the cost of finding the right element for interpolation.

One possibility I thought of is creating the mesh such that it'd essentially consist of a series of long prisms which have there long axis strictly parallel to one of the axes (in my case y) and are themselves then subdivided into smaller prism or tretrahedral elements. This would allow to quickly find the right "long" prism first and then loop within it to find the right spot along the y-axis. However, this is not well thought through yet.

Re: Any cheap route to find the elemet located at some xyz coordinate?

sebgei 27 Oct 2010 12:08

Did you get anywhere with Stephan's/Julian's suggestion to evaluate the shape functions at point XYZ and test if they sum up to 1? Otherwise I have some code that I can dig out. Not sure though if it is fast enough for your frequent applications (but a good search structure in a stl map may help).