find all the miminum local in a 3D model

Question

I am working on a project where I need to find locals mimimum points on the Z plane.

With an image it would be easier to understand my need :

http://s28.postimg.org/5y60b3asd/local_minimum.png

The view is z up aligned and I want to automatically find points showed by arrows, but I haven't got any idea about how to proceed...

It seems that i need to cut my model in several sub-model to find their zMin, but how to do this...

Could you pleaze give me some advices about existing algorithm to do that ?

Thank you !

Answer 1

If you have only your mesh data it's not so easy but it can be done.

By rendering:

Render your mesh from bottom to depth buffer, using orthogonal camera. Then run a shader on a resulting depth image and for each pixel compare its depth with depth of neighboring pixels.

If all neighbors are further than you current pixel - it's the local minimum. The precision of this method will depend on your rendering resolution, you may also get some rasterization artifacts, all depends on your mesh.

By mesh analyze: - the better one

You need to compute vertex neighbors, and store them per-vertex maybe like this: (this pseudo-code assumes the mesh is indexed)

for each triangle:
    for each vertex:
        add two another vertices to this vertex neighbours

Then looking for your minimums is quite simple:

for each vertex:
    var z = vertex.z;
    for each vertex neighbor:
        if neighbor.z < z:
            not a local minimum!