(editor crashed, new post…)
I use this data structure as well, and i like it. But it's a lot of work to implement, getting used to it, and then implement mesh editing operations like edge split, flip, etc. Multiple weeks of work, depending on what you need. The linked library is free IIRC, and it should have all this functionality already. Maybe worth to consider. There are more such libraries, e.g. CGAL which also has boolean mesh operations. https://www.cgal.org/ No idea about license. To deal with floating point issues CGAL uses some extended precision representation of numbers. (Your use of epsilon will still leave you with some very close vertices which should be merged, and this is where the rabbit hole opens up.)
2. Let's assume you want to keep things simple: ‘Mesh adjacency should not be necessary - just cut those polygons along the intersections. Should not be that hard, and if there are some errors in the result it does not matter.’
Not sure if this can work because i've never done it. But i'm optimistic and would do it like this:
Find intersection polygons, split them so the new edges are added to both meshes. (As you currently do, i guess)
After that, determinate which polygons should be deleted.
The second step is maybe harder than you think. But i know of a very robust method, which is also easy to implement. I use it to voxelize non manifold meshes with holes, or confusing ‘inside / outside’ situations.
(E.g. think of a column on a planar floor. The modeler guy will not cut out a hole into the floor where the column is. He will just place a cylinder (column) on a big quad (floor). This gives us a problem, because inside the column we see front faces of the floor but back faces of the column. So we do not know if we are in solid or empty space - only human intelligence creates this information for us, but writing an algorithm becomes hard. )
So, the method i propose does something that i call ‘solid angle integration’. It basically gives you the best guess we can do without requiring a form of intelligence. (A very similar method has been described in papers of Alec Jacobson https://www.dgp.toronto.edu/projects/fast-winding-numbers/ but they somehow did it more complicated than necessary)
Here is the code where i figured it out:
static bool visInsideOutsideTest = 0; ImGui::Checkbox("visInsideOutsideTest", &visInsideOutsideTest);
if (visInsideOutsideTest)
{
static int init = 1;
static HEMesh mesh;
if (init)
{
//MeshConverter::TestTrianglesToHE (mesh, mesh);
//((HEMesh_Serialization&)mesh).AutoLoadModel ("C:\\dev\\pengII\\mod\\bunny closed.lxo"); // hangs on tessellation (delauney)
((HEMesh_Serialization&)mesh).AutoLoadModel ("C:\\dev\\pengII\\mod\\Armadillo_input.obj");
//((HEMesh_Serialization&)mesh).AutoLoadModel ("C:\\dev\\pengII\\mod\\Gear.lxo");
//((HEMesh_Serialization&)mesh).AutoLoadModel ("C:\\dev\\pengII\\mod\\MaxPlanck_input.obj");
//((HEMesh_Serialization&)mesh).AutoLoadModel ("C:\\dev\\pengII\\mod\\Beetle_input.obj"); // hangs on tessellation (delauney)
//((HEMesh_Serialization&)mesh).AutoLoadModel ("C:\\dev\\pengII\\mod\\Buddha_input.obj"); // hangs on tessellation (delauney)
}
static vec query(0.46f, 0, 0);
ImGui::DragFloat3("query", (float*)&query, 0.001f);
static bool surfels = 0; ImGui::Checkbox("surfels", &surfels);
float integral = 0;
if (surfels) for (int i=0; i<mesh.GetPolyCount(); i++) // surfels
{
float area;
vec center = mesh.CalcPolyCenterAndArea(area, i);
vec norm = mesh.CalcPolyNormal(i);
vec diff = query - center;
float sql = diff.SqL(); // SqL is just dot(diff,diff)
if (sql > FP_EPSILON2)
{
float solidAngle = diff.Dot(norm * area) / (sqrt(sql) * sql);
integral += solidAngle;
}
}
if (!surfels) for (int i=0; i<mesh.GetPolyCount(); i++) // triangles
{
vec triVD[3];
bool onSurface = false;
int eI = mesh.GetPolyEdge(i);
for (int j=0; j<3; j++)
{
vec diff = mesh.GetEdgeVertexPos(eI) - query;
float dist = diff.Length();
if (dist < FP_EPSILON2)
{
onSurface = true;
break;
}
triVD[j] = diff / dist;
eI = mesh.GetEdgeNext(eI);
}
if (!onSurface)
{
float numer = triVD[0].Dot(
vec(triVD[1]-triVD[0]).Cross(triVD[2]-triVD[0]));
float denom = 1 +
triVD[0].Dot(triVD[1]) +
triVD[0].Dot(triVD[2]) +
triVD[1].Dot(triVD[2]);
float solidAngle = 2 * atan2(numer, denom);
integral += solidAngle;
}
}
float winding = 1 / float(4*PI) * integral;
bool inside = winding > 0.5f;
RenderCircle(0.01f, query, vec(0), !inside, inside, 0);
ImGui::Text("winding %f", winding);
((HEMesh_Vis&)mesh).RenderMesh(0,0,0);
init = 0;
}
We can use a query point, e.g. the center of a triangle from mesh A, and see if it is inside or outside of mesh B. Then delete accordingly.
Then i have two options. First option is fast by approximating each triangle with a disc ('surfel'). So i precompute those surfels to be on the triangle center, having equal normal and area. This gives approximate results, but good enough if the triangles are not close to each other.
Second option is exact by using triangles instead surfels.
This works pretty well, but i still need some further heuristices to get a solid voxelization of the Sponza model, for example. For some meshes which are even worse, user interaction is necessary to decide which parts should be removed.
