Jump to content
  • Advertisement
Sign in to follow this  
DividedByZero

Testing if a triangle is inside other groups of triangles

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

If you intended to correct an error in the post then please contact us.

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;

 

qjolI5Y.png

 

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.

 

Thanks in advance :)

Share this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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.

 

UB0LVMl.png

 

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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? ph34r.png

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!