|
[Sponsors] |
October 27, 2017, 12:04 |
look for a geometry in a cartesian grid
|
#1 |
New Member
Francesco De Vanna
Join Date: Jan 2017
Location: Venice, Italy
Posts: 8
Rep Power: 9 |
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. |
|
October 28, 2017, 03:57 |
|
#2 |
Senior Member
|
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 |
|
October 28, 2017, 04:28 |
|
#3 |
New Member
Francesco De Vanna
Join Date: Jan 2017
Location: Venice, Italy
Posts: 8
Rep Power: 9 |
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.
|
|
October 28, 2017, 06:47 |
|
#4 |
Senior Member
|
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. |
|
October 28, 2017, 06:56 |
|
#5 |
Senior Member
|
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).
|
|
October 28, 2017, 08:47 |
|
#6 |
New Member
Francesco De Vanna
Join Date: Jan 2017
Location: Venice, Italy
Posts: 8
Rep Power: 9 |
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 |
|
October 28, 2017, 13:47 |
|
#7 |
Senior Member
|
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 |
|
|
|
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Level set values for a cartesian grid | werder85 | Main CFD Forum | 0 | March 10, 2011 20:44 |
moving cylinder in a cartesian grid | yusun | Main CFD Forum | 1 | July 1, 2009 03:48 |
How to partition cartesian grid for MPI in fortran | CF | Main CFD Forum | 3 | January 17, 2008 04:38 |
Combustion Convergence problems | Art Stretton | Phoenics | 5 | April 2, 2002 05:59 |
Grid Independent Solution | Chuck Leakeas | Main CFD Forum | 2 | May 26, 2000 11:18 |