HI,
I have a 3D object whose shape is irregular. Shape of object can be both convex or non convex type. The shape of object is defined by triangulated mesh. So, I have the vertex and edge information of the triangle from marching cube. I can also get the axis aligned bounding box of this object. Now I have to generate random points inside this object.
People suggested a technique called ray intersect triangle where a ray has to pass through in space and then find whether it intersect with triangle or not.
I have around 200,000 number of triangles and around 8 billion grid points at grid spacing of 1.
So if i go for all grid points to check whether grid points inside or outside then I need to do 200,000 x 8 billion number of operations.
Which is very lengthy to do.
What is your suggestion for me? How to check efficient and optimise way to whether any grid point is inside or outside of an object.
Thanks. Any suggestion are welcome.
I think that this problem occurs also in the problem of intersecting tetrahedras: a first step is to find where are the vertices of a tetahedra within (if any) an other one (so a search on mesh intersection would be useful).
To avoid a too large increase in computational cost, I guess there is a coarse search step, used to eliminate the nodes that are "clearly" outside the element. This may be done for instance by using bounding boxes for the elements (a cartesian box aligned with the axis coordinates so that if any node coordinate is outside the associated min and max coordinate of the box, we are sure that the node is outside, so it is no more a candidate for a more exact and costly search).
Hope this helps.
Dear Ankit,
in fact a brute force search over 200000 triangles per each grid point cannot be done in reasonable time.
I suggest you to exploit the same optimization ideas that are used in the community that works on collision detection algorithms. The ray-triangle test is a special case of ray-casting collision test.
Many collision algorithms bypass the complexity by implementing smart "narrow phase" algorithms that allow you to run the ray/triangle test only on the small number of triangles that are within a specific sub-volume, ex. the thin box that contains the ray that you test.
Examples:
One option is that you run a test per each grid point where you exploit the SAP (Sweep and Prune) algorithm. It requires handling lists of axially-aligned-bounding boxes extremas of the triangles.
Other ideas for narrow phase accelerations are octrees, hash maps, etc.
Hoping this helps.
A.T.
MC produces an iso-surface, say at value A. It is not guaranteed that you will end-up with a closed manifold. You may end-up also with several objects or objects with internal holes. This makes your task difficult as you first need to decide what inside means.
If you are sure that the objects will be closed manifolds (which is, however, something rare to obtain from MC), you know A and the original volumetric data is available, you can simply take all the voxels with values greater than A and you will get a set of points that are guaranteed to be on the same side of the surface. All you need to do, is to determine, if the set is inside or outside but this is easy to do, and then sample (randomly) the points.
If all you have is the triangular surface mesh and this mesh is a closed manifold without holes, you could generate random points in a bounding box of this mesh and use Mean Value Coordinates interpolant (or similar) to check, if all the MVC coordinates of this point are positive (point is inside). This would be 200,000 * M operations, where M is the number of your points. Should run in seconds.
Thanks a lot Josef Kohout , Alessandro Tasora and David Dureisseix . Your answers are really helpful for my research. I will read in details about mean value coordinates method. It looks interesting. Thanks.
- Badges
- Science topic
- Similar topics
- Engineering
- Modeling