1
$\begingroup$

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 vertex\n";
      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 edge\n";
      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 failed\n";
          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 failed\n";
          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).

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.