## #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: #mesh #vectors Application of parallel transport in computer graphics and mesh processing

### Bounty: 150

Does anyone know what applications has the computation of a parallel transport on a mesh?

I’m talking about methods such as this one

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!!!