look for a geometry in a cartesian grid
 

Hi everyone.

I'm looking for an algorithm that detects solid bodies inside a cartesian grid. Any suggestions? Does someone have a source code or know about a library that implements this technique?

Thanks in advance.

That really depends on how you store your geometry, what is it made of (triangles, points, etc) and what you want to search for (nearest element, elements in a region, etc.).

Take a look at:

Christer Ericson - Real-time collision detection

However, it can be very simple actually

At the moment I have a geometry specified by coordinates (x, y, z) and I have to find the grid cells that are inside and outside the geometry.

Ok, that's quite a whole different business, mostly because it involves the geometry reconstruction from a point cloud.

I can suggest few more books (useful as references to actual methods you need to know):

Zhang - Geometric Modeling and Mesh Generation from Scanned Images
Botsch - Polygon Mesh Processing
O'Rourke - Computational geometry in C

And Meshlab to actually reconstruct the surface from the points:

http://fabacademy.org/archives/2014/...loudToSTL.html
http://gmv.cast.uark.edu/scanning/po...sh-in-meshlab/
http://meshlabstuff.blogspot.it/2009...nt-clouds.html

Or, maybe, you can try to use this:
https://conself.com/blog/from-point-...lated-surface/

Once you have your geometry as a triangulated surface, you can loop over the triangles and determine which of your grid cells are intersected and tag them (for a given triangle, first take its bounding box and determine a minimum subset of your grid cells to investigate, than test each of them for intersection with the triangle).

At the end of this process you end up with a grid whose cells intersected by your reconstructed geometry are tagged. Then you can pick up a point for each zone you would conisder outside, determine the cell containing it, tag it as outside, loop over its neighbor, tag them as outside, etc. etc. When you hit a cell previously tagged as intersected, you don't consider it of course, nor its neighbors. The whole process is known as advancing wave front algorithm or something like that.

Note that the first step in the algorithm above is only approximate. A triangle might intersect one of your grid cells whose center is actually outside the geometry. One way to correct this is to do the subsequent tagging in reverse. Pick up a point surely inside the geometry, and only tag inside cells. All the remaining ones will be surely outside. At this point you only need to check again the cells tagged as intersected that potentially need to be switched to outside (otherwise they are inside).

First of all thanks a lot Paolo.

I'm afraid this is a little too complicated for me (and maybe too general!). I'll explain my problem. I need to calculate a "set-level" function of some arbitrary solid contours within a grid; I need a function that is 1 in the solid and 0 in the liquid domain (or true / false). But I do not know if there is an algorithms that do this, and especially if there is a numerical library that can apply this technique.

P.S. I'm coding in Fortran90, able to read C/C++ codes

Francesco

My suggestion is to never tag anything related to computational geometry as too general. At some point you will surely find yourself lacking in generality, no matter what. The goal is to have that point very far in time.

Now, I have no idea of any library out there, even if, probably, there might be several.

But I think that the level at which you are looking for a library is too deep or application specific. You can really find stuff only for more general tasks. And these do not usually involve things like uniform grid searches because they are usually easy to implement.

The only libraries I know of in Fortran are kdtree2 (https://github.com/jmhodges/kdtree2) and adt_utilities from nasa (https://sourceforge.net/projects/cfd...ies/files/adt/), used respectively to search for nearest points and triangles to a given point. But you need to somehow build your application around them... and I'm not even sure you actually need them.

Otherwise you can give a look to this (but looks like an overkill to me):
http://ktchu.serendipityresearch.org/software/lsmlib/
https://github.com/ktchu/LSMLIB