• 11
• 27
• 9
• 20
• 31

Testing if a triangle is inside other groups of triangles

This topic is 815 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Hi Guys,

I have a large file (being used as a flat 2d model) that I want to discard unwanted triangles.

Is there a way to detect if a triangle resides within other triangles (or groups of triangles)?

Sort of like this;

I'd imagine there would have to be some serious loops and iterations involved with complex meshes.

But, any ideas on what sort of formula I could use would be awesome.

Share on other sites

If your group of triangles are convex, and there's no gap between the triangles, couldn't you just test the three corners of your test triangle against each triangle within the group?

If even a single corner is not colliding with any triangle within the group, then "keep", but if all three corners of the test triangle are within the group, then discard.

bool TriangleInsideGroup(Triangle testTriangle, const std::vector<Triangle> &triangleGroup)
{
bool cornerAInGroup = PointInsideGroup(testTriangle.cornerA, triangleGroup);
bool cornerBInGroup = PointInsideGroup(testTriangle.cornerB, triangleGroup);
bool cornerCInGroup = PointInsideGroup(testTriangle.cornerC, triangleGroup);

return (cornerAInGroup && cornerBInGroup && cornerCInGroup);
}

bool PointInsideGroup(Point point, const std::vector<Triangle> &triangleGroup)
{
for(Triangle triangle : triangleGroup)
{
if(IsWithinTriangle(point, triangle))
return true;
}

return false;
}

Share on other sites

Hi there, thanks for the reply.

The meshes are pretty complex, so there are plenty of concave, convex, and gaps in the geometry unfortunately.

This is a part close up of the geometry I have.

The entire model has 320K verts. Which I have exported to raw triangle data. As you can see there is a lot of wasted faces in there. The model (which happens to be grass in this case) is the combination of a bunch of other models. The original base models are clean and have no overlaps.

Edited by DarkRonin

Share on other sites
Servants suggestion would fail if the clip triangle is completely inside the test triangle -
no test points are inside the clip, so it would be accidently rejected.

In 3D one could solve this by convex polygon clipping:
For each edge of the clip poly, build a plane from poly normal and edge and clip all test polys against this plane (See code below).
Then clip the remainding polys by the next edge until all edges have been done.

In 2D instead of clipping against a plane, you need to clip against the infinite line of the edge.

That's complex and seems slow, but games like quake or any software renderer did it for exact frustum culling (in case you need it for realtime).

Finally you can retriangulate the remaining polys.

inline int ClipTexmapPolygon (const TexmapPolygon *pin, const vec &plane, TexmapPolygon *pout, const int space)
{
if (pout->numAvailableVertices < pin->numVertices + 1)
pout->Resize (pin->numVertices + 1);

int i, curin, nextin;
float curdot, nextdot, scale;
TexmapPolygon::Vertex *pinvert, *poutvert, *nextvert;

pinvert = pin->vertices;
poutvert = pout->vertices;
curdot = pinvert->puv[space].Dot (plane);
curin = (curdot >= plane[3]);

int ret = -1; // assume inside

for (i=0; i<pin->numVertices; i++)
{
nextvert = &pin->vertices[(i+1) % pin->numVertices];
// keep if inside
if (curin)
{
*poutvert++ = *pinvert;
}

nextdot = nextvert->puv[space].Dot (plane);
nextin = (nextdot >= plane[3]);

if (curin!=nextin) // add clipped vertex if plane splits edge
{

ret = 1; // clipped or outside
scale = (plane[3] - curdot) / (nextdot - curdot);

for (int c=0; c<3; c++)
poutvert->puv[c] = pinvert->puv[c] + (nextvert->puv[c] - pinvert->puv[c]) * scale;

poutvert++;
}

curdot = nextdot;
curin = nextin;
pinvert++;
}

pout->numVertices = poutvert - pout->vertices;
if (pout->numVertices < 3) return 0; // outside

return ret;
}

But... do you need this just to reduce overdraw of the grass? It might not be worth the affort. Edited by JoeJ

Share on other sites

Hi JoeJ,

This would all be a one off to re-calculate a the model(s). As it stands my project has 800 MB of vertex data. But I am sure I could drastically reduce this if I can clean up the redundant faces.

I'll re-read your suggestion a couple of times to see if it sinks in :)

Thanks again :)

Share on other sites

This would all be a one off to re-calculate a the model(s). As it stands my project has 800 MB of vertex data. But I am sure I could drastically reduce this if I can clean up the redundant faces.

Ok, but keep in mind that convex polygons would be better input data than triangles.
E. g. by triangulating a quad you add a additional edge, ending up with more vertices than necessary.
There area also algorithms for concave poly clipping.

It isn't as hard as it sounds, but look there first:

http://www.angusj.com/delphi/clipper.php
http://www.boost.org/doc/libs/1_60_0/libs/polygon/doc/index.htm
http://www.cs.man.ac.uk/~toby/gpc/

Share on other sites

Servants suggestion would fail if the clip triangle is completely inside the test triangle -
no test points are inside the clip, so it would be accidently rejected.

Unless I'm misunderstanding, if there are any points outside the clip, you don't want it to be culled.

This is not "triangle is overlapping", I think the criteria is "triangle is completely covered". If even one point is outside of any triangle (in a convex group), then we want it to return false. If the clip triangle is completely inside the test triangle, it should fail to be culled, because the clip triangle is not fully covering the test triangle. Right?

Share on other sites
Ah, ok - i get you now and agree, sorry.
For the picture in first post it would work your way (i've missunderstood the pictures as clip inside vs clip outside or something).

But for the grass you would find only a few triangles to discard, because it's not convex.
Using exact clipping you could find all triangles that are partially visible or completely occluded.

However - for the grass no method will reduce vertex count significantly.
Using clipped polys instead original polys could only reduce overdraw a lot.

Share on other sites

Using clipped polys instead original polys could only reduce overdraw a lot.

That's the big challenge though, trying to clip the polys. I am generating this in Maya and it seems there is no way to do it in Maya either.

What about adding verts at the intersection of the triangles? I know this will increase vertex count (initially), but I could then I would have a proper outline of the geometry and then could remove the internal verts in Maya and then re-triangulate the mesh. This would significantly reduce the triangle count to just a couple of thousand.

All good in theory, but I am racking my brain as to how to make it happen in practice.

Share on other sites

What about adding verts at the intersection of the triangles? I know this will increase vertex count (initially), but I could then I would have a proper outline of the geometry and then could remove the internal verts in Maya and then re-triangulate the mesh. This would significantly reduce the triangle count to just a couple of thousand.

You can achieve this by bolygon clipping - initially add all triangles to a active poly list, then:
1. Find front most polygon from list
2. Use polygon clipping as described above to cut front poly from all other polys (this adds vertices automatically)
3. Remove front poly from active list and go to 1