Walking through an ofMesh

Hello OF people

I would like to write a little demo where I repeatedly step from one triangle to the next in an ofMesh instance. So, from any given triangle, pick an edge segment, and if that edge is also part of a neighbouring triangle, move to that triangle; then repeat…

Is there a smart way to do this using an ofMesh, i.e. without repeatedly having to cycle through all the triangles with a point in poly search? I was imagining that the edge segment selected might tell which is the next triangle number to access, and so on…

Can anyone suggest an approach, before I leap in at the deep end?

Thanks
S

Hi, it depends on how you build the mesh. There are several modes, explained here, all of which will define how the vertices are related and how these will build the triangles. All modes but OF_PRIMITIVE_TRIANGLES you’ll have adjacent triangles that share vertices, so it is quite easy to tell both, which vertices make the triangle and which is its adjacent triangle. Then if you use OF_PRIMITIVE_TRIANGLESyou’ll need to use the ofMesh indices to tell which vertices comprise each triangle. Actually this mode can be a bit more useful as you can use the indices to tell which triangles are sharing vertices and sides,

Thanks for the quick reply… I was planning on extracting the mesh shape from an ofPath object with fill, so a regular polygon with holes. Would this have the right structure?

Is there a demo or something of how I’d look up the adjacencies?

No prob.
you can check which mode the mesh is using by calling getMode() at the mesh object.
I dont think there is asuch a demo, as it is very specific. Yet, what are you trying to achieve? maybe there is another easier way to do such

Ultimately I want to try and build a version of the Bungui triangular expansion algorithm for visibility polygons/isovists: https://arxiv.org/pdf/1403.3905.pdf. I have a version of the Asano algorithm working since way back, and it performs really well, but by the looks of it the triangle expansion approach absolutely leaves it in the dust for speed.

I was thinking that extracting the mesh from an ofPath is a neat first step for getting the triangular solution of the space, and the technique after that seems to be a recursive ray walk across the mesh triangles. I thought if the mesh structure allows me to know which triangle is next each ray step, this makes for a real nice efficient search.

So I wanted to start simple, by making a quick proof test of walking a line across a triangular mesh, and pinging each triangle in turn (maybe turning it a different colour or something)…

S

update: from calling getMode() on the getTessellation() mesh result for some of my spaces, it looks like they are always mode 0 (OF_PRIMITIVE_TRIANGLES?), so I guess it might be a question of searching through the triangles after all.

So then I did this, to call out the indices, am I on the right track?

    vector<ofIndexType> catcher;
    catcher = accessibleMesh.getIndices();
    for(int i = 0; i<catcher.size(); i+=3) cout<<catcher[i]<<"-"<<catcher[i+1]<<"-"<<catcher[i+2]<<endl;

Seems to print a string of vertex ids, which is promising
S

More progress. I wrote the following, which searches through the indices lists, and builds a vector of triangle edge segments described by those indices. It includes a list of the neighbouring triangle segments that every segment can have (i.e. a max of four, and a min of two).

I’m imagining this gives me something to step from segment to segment… but have yet to check the result of what I get in the vector properly.

Any tips welcome

class segSearch : public glm::vec2{
public:
    int iD = -1;
    glm::vec2 neighbour_A = glm::vec2(-1,-1);
    glm::vec2 neighbour_B = glm::vec2(-1,-1);
};
   vector<ofIndexType> catcher;
    catcher = accessibleMesh.getIndices();
    vector<segSearch>segWeb;
    segWeb.clear();
    
    for(int i = 0; i<catcher.size(); i+=3){
        //this describes each triangle
        //first arrange each triangle into segments and organise those segments into a vector
        vector<segSearch>triangle;
        for(int j=0; j<3; j++){
            int k = j+1; if(k==3) k=0;
            segSearch segNew;
            segNew.x = catcher[i+j];
            segNew.y = catcher[i+k];
            for(int l = 0; l<segWeb.size(); l++){
                //if a match is found, record the iD no
                if(segWeb[l].x==segNew.x){
                   if(segWeb[l].y==segNew.y){
                       segNew.iD = l;
                       break;
                   }}
                else if(segWeb[l].x==segNew.y){
                    if(segWeb[l].y==segNew.x){
                        segNew.iD = l;
                        break;
                    }}}
            //if no segment match found, add to the web with a new iD
            if(segNew.iD < 0){
                segNew.iD = segWeb.size();
                segWeb.push_back(segNew);
            }
            triangle.push_back(segNew);
        }
        
        //next go through the vector of segments and record all triangle connections, i.e. the other segment ids
        for(int j=0; j<triangle.size(); j++){
            int k = j+1; if(k==3) k=0;
            int l = j-1; if(l<0) l=2;
            int iD = triangle[j].iD;
            //either record in set A
            if(segWeb[iD].neighbour_A.x == -1){
                segWeb[iD].neighbour_A.x = triangle[k].iD;
                segWeb[iD].neighbour_A.y = triangle[l].iD;
            }
            //or in set B if A is full
            else{
                segWeb[iD].neighbour_B.x = triangle[k].iD;
                segWeb[iD].neighbour_B.y = triangle[l].iD;
    }}}

Hi, with OF_PRIMITIVE_TRIANGLES you’ll need to use the indices. So, the idea is that you have a bunch of vertices, so in order to optimize the use of memory and duplicated vertices, indices are used. So every 3 indices make a triangle and these indices are the indices in the vertices of the mesh.
So it would be something like:

 auto indices = accessibleMesh.getIndices();
 auto vertices = accessibleMesh.getVertices();

    for(size_t i = 0; i<indices.size(); i+=3)
 {
//a triangle vertices would be 
vertices[i], vertices[i+1], vertices[i+2]
}

ofMesh also has a helper function getUniqueFaces() which returns a vector<ofMeshFace>, where esentially each face is a triangle with its vertices, normals, texCoords and colors. It might be easier to use such.

yip, got it, ta!

Will keep picking away at this one and post updates as I get there, but the last bit I did seems to give me the basic structure I need to search across. Fingers crossed

Thanks!
S

Hello,

Just in case: apart if your goal is to make your own implementation, you could probably use the CGAL library, mentionned in the pdf. CGAL now contains it. I’m far from an expert to link libraries to use them with OF, but I was successful with CGAL two years ago so you may do the same.

Hi, yeah I know the cgal has an implementation but I want to make my own. In part for the challenge but also because I want to play around with what it does a bit. Have sketched out a pseudo code, now I ‘just’ need to give it a try…