2
$\begingroup$

I need a program or an algorithm that computes the intersection of a mesh and a boundary.

The mesh is structured orthogonal in nature and the boundary is a circle (for example). This will be used for solving Poisson's equation using finite difference technique with 5 point unequal spacing stencil.

Improve this question
$\endgroup$
1
$\begingroup$

I would suggest (in case you are coding in C++), the CGAL library, which allows you to compute the intersection lists between axis aligned bounding boxes (AABBs, in your case, the mesh cells) and geometric primitives, assembled in queries (or even surface meshes, polyhedra, etc):

Intersecting sequences in CGAL

This would give you labeling information on the cells that are cut... there are algorithms for computing the intersections if you need them, as well, which return actual geometrical constructs as intersection results.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the reply, but I am new to c++ programming as CGAL is confusing for me but this idea is good to pursue. $\endgroup$ – goutham Feb 19 '12 at 15:35
  • $\begingroup$ If you are new to C++, your development will be determined by the time you will be able to invest in order to learn it. I would pick up C++ Primer from Stanley Lippman, go over it "quickly" and move on to Josuttis' book on STL (CGAL is architected using STD approach of separating data structures from algorithms, and going even to further abstractions such as concepts). Good luck! $\endgroup$ – tmaric Feb 20 '12 at 13:33
0
$\begingroup$

If you describe the boundary via the zero-line of a signed distance function, then you can determine whether a boundary intersects a cell by testing whether all vertices of the cell have the same sign of the distance function (no intersection) or different signs (intersection). I believe that that's the usual algorithm.

Improve this answer
$\endgroup$
2
  • $\begingroup$ if the boundary is complicated(meaning mix and match of different splines). then it will be harder for computing the signed distance function. $\endgroup$ – goutham Feb 19 '12 at 15:37
  • $\begingroup$ Not all that much: If you have multiple splines, then the distance to any of them is the minimum over the distances to each one. And a cell is intersected if it is intersected by at least one of them, so you can check them individually. But yes, it clearly is more difficult in general. $\endgroup$ – Wolfgang Bangerth Feb 20 '12 at 7:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.