#StackBounty: #3d #computational-geometry #mesh #geometry #cad Algorithm to select regions based on curvature on a mesh

Bounty: 50

I’m trying to understand how to implement an algorithm similar to the one used by Magics’ mark surface tool, you can see such behaviour on this video.

Quoting the video: "Basically with this tool you’re able to select surfaces, which unlike planes, surfaces take curvature into account."

The first idea that come to my mind to implement something similar was starting by considering the adjacency information of the mesh and consider on the computation the angle adjacent triangle normals. My idea was that if such an angle wasn’t on the range [pi/2-tol, pi/2+tol] two adjacent triangles would be "smooth". This thought was too naive and the idea would just work for a very limited of cases and it’d start fail for many of them.

After that, I’ve spent a little bit of time reading some papers talking about mesh segmentation and it seems this has been an area of research for many years… But before even considering implementing any of these one I’d like to ask here if you knew some basic&good enough algorithm I could implement that could behave in a similar fashion to Magic’s.

So yeah, that’s my question basically, assuming a triangular mesh that has adjacency information built (ie: you can check adjacent triangles from any given face) and a starting selected triangle, how would you detect the "surface" region associated to it?

Thanks in advance.


Get this bounty!!!

#StackBounty: #computational-geometry #geometry #mesh #data-structure Smart half edge iteration?

Bounty: 50

In my HE implementation, half edges are stored in an array. When I iterate over the edges, I color all the HE black, and when I do an operation on an edge (e.g edge splitting) I mark both the current half edge and its pair blue. And in the loop I skip blue edges.

This essentially stops me from applying the same operation to an edge twice.
This however requires O(n) additional memory and iterating over every edge twice (once for each of the HE that compose the edge.)

    for(uint i=0; i < edge_num; i++)
    {
        if(mesh.edges[i].color != BLUE)
        {
            /*Do stuff*/
           mesh.edges[i].color = BLUE;
           mesh.edges[i].pair.color = BLUE;
        }
    }

I am wondering if there is a smarter way. In particular, a way that avoids branching. I know I could do something like depth first search or breath first search, but that’s likely to be slower than just skipping over edges.


Get this bounty!!!

#StackBounty: #algorithm #c++ #computational-geometry #mesh HalfEdge data structure in openmesh, create_face function explanation

Bounty: 50

Does anyone have experience with open-mesh or computational geometry and can kindly explain what exactly happens in the function below?

PolyConnectivity::FaceHandle
PolyConnectivity::add_face(const VertexHandle* _vertex_handles, size_t _vhs_size)
{
  VertexHandle                   vh;
  size_t                         i, ii, n(_vhs_size);
  HalfedgeHandle                 inner_next, inner_prev,
                                 outer_next, outer_prev,
                                 boundary_next, boundary_prev,
                                 patch_start, patch_end;


  // Check sufficient working storage available
  if (edgeData_.size() < n)
  {
    edgeData_.resize(n);
    next_cache_.resize(6*n);
  }

  size_t next_cache_count = 0;

  // don't allow degenerated faces
  assert (n > 2);

  // test for topological errors
  for (i=0, ii=1; i<n; ++i, ++ii, ii%=n)
  {
    if ( !is_boundary(_vertex_handles[i]) )
    {
      omerr() << "PolyMeshT::add_face: complex vertexn";
      return InvalidFaceHandle;
    }

    // Initialise edge attributes
    edgeData_[i].halfedge_handle = find_halfedge(_vertex_handles[i],
                                                 _vertex_handles[ii]);
    edgeData_[i].is_new = !edgeData_[i].halfedge_handle.is_valid();
    edgeData_[i].needs_adjust = false;

    if (!edgeData_[i].is_new && !is_boundary(edgeData_[i].halfedge_handle))
    {
      omerr() << "PolyMeshT::add_face: complex edgen";
      return InvalidFaceHandle;
    }
  }

  // re-link patches if necessary
  for (i=0, ii=1; i<n; ++i, ++ii, ii%=n)
  {
    if (!edgeData_[i].is_new && !edgeData_[ii].is_new)
    {
      inner_prev = edgeData_[i].halfedge_handle;
      inner_next = edgeData_[ii].halfedge_handle;


      if (next_halfedge_handle(inner_prev) != inner_next)
      {
        // here comes the ugly part... we have to relink a whole patch

        // search a free gap
        // free gap will be between boundary_prev and boundary_next
        outer_prev = opposite_halfedge_handle(inner_next);
        outer_next = opposite_halfedge_handle(inner_prev);
        boundary_prev = outer_prev;
        do
          boundary_prev =
            opposite_halfedge_handle(next_halfedge_handle(boundary_prev));
        while (!is_boundary(boundary_prev));
        boundary_next = next_halfedge_handle(boundary_prev);

        // ok ?
        if (boundary_prev == inner_prev)
        {
          omerr() << "PolyMeshT::add_face: patch re-linking failedn";
          return InvalidFaceHandle;
        }

        assert(is_boundary(boundary_prev));
        assert(is_boundary(boundary_next));

        // other halfedges' handles
        patch_start = next_halfedge_handle(inner_prev);
        patch_end   = prev_halfedge_handle(inner_next);

        assert(boundary_prev.is_valid());
        assert(patch_start.is_valid());
        assert(patch_end.is_valid());
        assert(boundary_next.is_valid());
        assert(inner_prev.is_valid());
        assert(inner_next.is_valid());

        // relink
        next_cache_[next_cache_count++] = std::make_pair(boundary_prev, patch_start);
        next_cache_[next_cache_count++] = std::make_pair(patch_end, boundary_next);
        next_cache_[next_cache_count++] = std::make_pair(inner_prev, inner_next);
      }
    }
  }

  // create missing edges
  for (i=0, ii=1; i<n; ++i, ++ii, ii%=n)
    if (edgeData_[i].is_new)
      edgeData_[i].halfedge_handle = new_edge(_vertex_handles[i], _vertex_handles[ii]);

  // create the face
  FaceHandle fh(new_face());
  set_halfedge_handle(fh, edgeData_[n-1].halfedge_handle);

  // setup halfedges
  for (i=0, ii=1; i<n; ++i, ++ii, ii%=n)
  {
    vh         = _vertex_handles[ii];

    inner_prev = edgeData_[i].halfedge_handle;
    inner_next = edgeData_[ii].halfedge_handle;
    assert(inner_prev.is_valid());
    assert(inner_next.is_valid());

    size_t id = 0;
    if (edgeData_[i].is_new)  id |= 1;
    if (edgeData_[ii].is_new) id |= 2;


    if (id)
    {
      outer_prev = opposite_halfedge_handle(inner_next);
      outer_next = opposite_halfedge_handle(inner_prev);
      assert(outer_prev.is_valid());
      assert(outer_next.is_valid());

      // set outer links
      switch (id)
      {
        case 1: // prev is new, next is old
          boundary_prev = prev_halfedge_handle(inner_next);
          assert(boundary_prev.is_valid());
          next_cache_[next_cache_count++] = std::make_pair(boundary_prev, outer_next);
          set_halfedge_handle(vh, outer_next);
          break;

        case 2: // next is new, prev is old
          boundary_next = next_halfedge_handle(inner_prev);
          assert(boundary_next.is_valid());
          next_cache_[next_cache_count++] = std::make_pair(outer_prev, boundary_next);
          set_halfedge_handle(vh, boundary_next);
          break;

        case 3: // both are new
          if (!halfedge_handle(vh).is_valid())
          {
            set_halfedge_handle(vh, outer_next);
            next_cache_[next_cache_count++] = std::make_pair(outer_prev, outer_next);
          }
          else
          {
            boundary_next = halfedge_handle(vh);
            boundary_prev = prev_halfedge_handle(boundary_next);
            assert(boundary_prev.is_valid());
            assert(boundary_next.is_valid());
            next_cache_[next_cache_count++] = std::make_pair(boundary_prev, outer_next);
            next_cache_[next_cache_count++] = std::make_pair(outer_prev, boundary_next);
          }
          break;
      }

      // set inner link
      next_cache_[next_cache_count++] = std::make_pair(inner_prev, inner_next);
    }
    else edgeData_[ii].needs_adjust = (halfedge_handle(vh) == inner_next);


    // set face handle
    set_face_handle(edgeData_[i].halfedge_handle, fh);
  }

  // process next halfedge cache
  for (i = 0; i < next_cache_count; ++i)
    set_next_halfedge_handle(next_cache_[i].first, next_cache_[i].second);


  // adjust vertices' halfedge handle
  for (i=0; i<n; ++i)
    if (edgeData_[i].needs_adjust)
      adjust_outgoing_halfedge(_vertex_handles[i]);

  return fh;
}

More specifically, at the moment, I’d like to understand what exactly happens in the for loop below:

// re-link patches if necessary
  for (i=0, ii=1; i<n; ++i, ++ii, ii%=n)
  {
    if (!edgeData_[i].is_new && !edgeData_[ii].is_new)
    {
      inner_prev = edgeData_[i].halfedge_handle;
      inner_next = edgeData_[ii].halfedge_handle;


      if (next_halfedge_handle(inner_prev) != inner_next)
      {
        // here comes the ugly part... we have to relink a whole patch

        // search a free gap
        // free gap will be between boundary_prev and boundary_next
        outer_prev = opposite_halfedge_handle(inner_next);
        outer_next = opposite_halfedge_handle(inner_prev);
        boundary_prev = outer_prev;
        do
          boundary_prev =
            opposite_halfedge_handle(next_halfedge_handle(boundary_prev));
        while (!is_boundary(boundary_prev));
        boundary_next = next_halfedge_handle(boundary_prev);

        // ok ?
        if (boundary_prev == inner_prev)
        {
          omerr() << "PolyMeshT::add_face: patch re-linking failedn";
          return InvalidFaceHandle;
        }

        assert(is_boundary(boundary_prev));
        assert(is_boundary(boundary_next));

        // other halfedges' handles
        patch_start = next_halfedge_handle(inner_prev);
        patch_end   = prev_halfedge_handle(inner_next);

        assert(boundary_prev.is_valid());
        assert(patch_start.is_valid());
        assert(patch_end.is_valid());
        assert(boundary_next.is_valid());
        assert(inner_prev.is_valid());
        assert(inner_next.is_valid());

        // relink
        next_cache_[next_cache_count++] = std::make_pair(boundary_prev, patch_start);
        next_cache_[next_cache_count++] = std::make_pair(patch_end, boundary_next);
        next_cache_[next_cache_count++] = std::make_pair(inner_prev, inner_next);
      }
    }
  }

Just to give some context, the add_face (which is reused in other subclasses of PolyConnectivity) essentially creates a face given a set of vertices, the first part of the function, prior the for loop I’ve just mentioned, checks if the vertices are boundary vertices and if there’s a potential edge connecting two consecutive vertices.

The for loop I don’t understand is supposed to do something when three consecutive vertices v[i],v[i+1],v[i+2] are not connected (I think).


Get this bounty!!!