Within the last 5 days I was able to generate a block structured Cartesian grid generation system with a combination of Fortran,C++ and Python.

I am running intersection tests of the imported geometry with the bounding box it is surrounded by and if the intersection test succeeds then I am subdividing the parent bounding box into 4 children boundary box.

As it can be understood for this 2D case, I am using Quad Tree decomposition.

And now I am planning to code a FVM / FEM solver for it.


However, I am unable to think of an algorithm that would help me identify cells which are SOLID (i.e inside the body) and FLUID ( i.e outside the body) at a fast speed.

I can run a double ray intersection test by casting two opposite rays out of all the cells and see if both of the rays intersect with the boundary of the geometry or not to identify the solid domain. However such a test will be computationally very expensive to run after we have decomposed the quad tree to a certain mesh level.

The figure given below has 40,577 quad elements, so it is not very high. But future meshes will have more elements. And hence this particular problem can become a performance bottleneck.

FIG 1 : NACA 2412 Aerofoil meshed Cartesian grid for a NACA 2412 aerofoil

FIG 2 : Zoomed view of trailing edge demonstrating mesh distribution Zoomed view of trailing edge


i) Can I perform any kind of initial tests to reduce my computational load ?

ii) Is there any other algorithm that would be more suited for this problem ?

  • $\begingroup$ What about running the double-ray test during the construction of the tree for blocks (not individual cells)? $\endgroup$ – Anton Menshov May 21 '18 at 19:19
  • 1
    $\begingroup$ Yes , that is the solution I am going to use. This will significantly reduce the complexity. And also, the double ray intersection test will prove to be very heavy for this. So I will be using "An incremental angle point in polygon test " by Weller Kelvin (1994) from Graphics Gems IV. Thanks for your help. $\endgroup$ – SYN Jun 25 '18 at 16:54
  • $\begingroup$ Glad to help! Thanks a lot for letting me know, that's very valuable. BTW, you can convert your comment into an answer to your own question and accept it. $\endgroup$ – Anton Menshov Jun 25 '18 at 17:52
  • $\begingroup$ Yes, sure. I will explain in detail. $\endgroup$ – SYN Jun 27 '18 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.