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).