C ++ Vector is modified twice than required in computational geometry
I am trying to solve the following problem. I have 2 spherical polyhedrons as in the following image and I am trying to find the triangles of each model that are either inside the other model or intersect with it. For this I developed a geometric algorithm in which I start a ray at each vertex of the model and check how many times it intersects with another model. If the number is odd, then the vertex is inside another model, and if the number is even, it is outside.
The problem arises when I try to distinguish between triangles that are completely inside another model and intersecting ones. For this I use the following logic:
-
For every vertex that is inside another model, I check all triangles of the same model and try to find the triangles that this vertex belongs to.
-
When I find a triangle like this, I add 1 to the same index in the counter vector.
-
In the end, I want to check the number of vertices, each triangle of which has a different model. If it has 3, it is an inner triangle, if it has 1-2, it is intersecting, and if it has 0, it is outer.
The problem is that the following code, which seems to mimic this procedure, gets the counter values up to 6. This should not be the case, since each triangle can only have 3 vertices.
The image is in the format, counter value [ti] for ti.
I would be very grateful if someone could identify the problem for me! Also, any ideas to improve my code are welcome. Thank you in advance.
//create a vector to keep how many vertices are inside the other model for each triangle
std::vector<int> counter(triangles.size());
for (unsigned i = 0; i < counter.size(); i++){
counter[i] = 0;
}
//check for every vertex of the model whether it is inside the other model
for (unsigned vi = 0; vi < vertices.size(); vi++)
{
Vec3d &ver = vertices[vi];
vec myVec(ver.x, ver.y, ver.z);
Ray myRay(myVec, myVec.Normalized());
int interCount = 0;
for (unsigned ti = 0; ti < triangles2.size(); ti++){
vec v1, v2, v3;
v1.x = triangles2[ti].v1().x; v1.y = triangles2[ti].v1().y; v1.z = triangles2[ti].v1().z;
v2.x = triangles2[ti].v2().x; v2.y = triangles2[ti].v2().y; v2.z = triangles2[ti].v2().z;
v3.x = triangles2[ti].v3().x; v3.y = triangles2[ti].v3().y; v3.z = triangles2[ti].v3().z;
math::Triangle tri(v1,v2,v3);
if (myRay.Intersects(tri)){
interCount++;
}
}
//if it is inside, find the triangles that have this vertex
//and add 1 to the respective index in the counter
if (interCount%2!=0){
for (int ti = 0; ti < triangles.size(); ti++){
bool isOnTri = false;
vvr::Triangle &tri = triangles[ti];
if ((tri.v1().x == ver.x && tri.v1().y == ver.y && tri.v1().z == ver.z) && isOnTri == false){
isOnTri = true;
}
else if ((tri.v2().x == ver.x && tri.v2().y == ver.y && tri.v2().z == ver.z) && isOnTri == false){
isOnTri = true;
}
else if ((tri.v3().x == ver.x && tri.v3().y == ver.y && tri.v3().z == ver.z) && isOnTri == false){
isOnTri = true;
}
if (isOnTri){
counter[ti] ++;
}
isOnTri = false;
}
}
}
//put the triangles in the proper struct
cout << "\n";
for (int ti = 0; ti < triangles.size(); ti++){
cout << counter[ti] << " for " << ti << " ";
vvr::Triangle &tri = triangles[ti];
vvr::Triangle3D m_tri(tri.v1().x, tri.v1().y, tri.v1().z,
tri.v2().x, tri.v2().y, tri.v2().z,
tri.v3().x, tri.v3().y, tri.v3().z, Colour::blue);
m_tri.setSolidRender(true);
if (counter[ti]==5 || counter[ti] == 6){
m_tris_inner.push_back(m_tri);
}
else if (counter[ti]>0 && counter[ti]<5){
m_tris_intersect.push_back(m_tri);
}
else if (counter[ti]==0){
m_tris_outer.push_back(m_tri);
}
}
source to share
As mentioned in the comment, the likely reason your counter values are greater than 3 is because there are duplicate vertices in the vertex list, so the counter will update when both of them are processed. Since the counter for a triangle is incremented when any vertex equal to any of its vertices intersects the object, if there are two copies of each vertex with the same coordinates, then the counter will increment 6 times.
This could possibly happen if you create a model by starting with an icosahedron and recursively dividing its triangles using subdivision of the midpoint, without dividing the vertices of the midpoints of adjacent triangles.
The way to fix this would be to check for duplicates when generating vertices before adding a new list to the list, however there are a few optimizations you can make to your code that would make this irrelevant.
For starters, you can optimize your intersection tests by calculating a bounding box for all vertices in triangles2
before you start the outer loop. You can do this by simply iterating over all the vertices and finding the min and max of xy and z. Then, when you test each vertex in vertices
, first check if its xyz values are within the range given by the bounding rectangle for triangles2
, and if not, then it is not possible for intersection, and you can skip this loop:
for (unsigned ti = 0; ti < triangles2.size(); ti++)
Alternatively, you can compute the bounding sphere and perform a point-to-point test. It is also possible to do some special tests based on the spherical geometry of your objects - all triangles that partially intersect will lie on the plane. The bounding box, however, is a good general purpose optimization that works well for most freeform shapes. If you compute the bounding rectangle for both objects, then you can check if they overlap at the very beginning of your function, and if they don't, you know right away that neither of the vertices overlap.
The second change you can make is to store 3 indices in your array vertices
internally triangles
instead of storing 3 copies of the vertices. Don't intersect all the triangles after you find each intersecting vertex, but instead store interCount
in an array with one entry for each vertex. After you finish repeating all the vertices, iterate over the triangles in a separate loop:
for (int ti = 0; ti < triangles.size(); ti++)
and use the three indices of the vertices stored in each triangle to find 3 matching values in interCount
and count the number of odd values. If it is 0, then the triangle is completely outside the boundaries of another object. If it is 3, then it is completely inside. If it is 1 or 2, then it partially intersects the surface.
This way will be faster because you don't have to check every vertex for every triangle for every vertex, and you also don’t have to worry about counting more than three vertices because you only have 3 indices.
source to share