Make vertices at intersections of two overlapping polygons

Let us know if you have a nice R.U.B.E script to share!
bvargish
Posts: 26
Joined: Fri Oct 02, 2015 4:17 pm

Make vertices at intersections of two overlapping polygons

Post by bvargish » Wed Oct 21, 2015 6:50 pm

I'm working on a rubescript that will make vertices at the intersections of two overlapping polygons, with the ultimate goal of making a script that will merge two overlapping polygons. Just getting the vertices so I can create a new shape using their info will suffice for now, though.

Before I post my code so far, how can I get the world position of a vertex? getVertices() gets the local positions.

Is there a way to keep the script from breaking if there is a divide by zero error? This happens when my lines have no slope.

bvargish
Posts: 26
Joined: Fri Oct 02, 2015 4:17 pm

Re: Make vertices at intersections of two overlapping polygo

Post by bvargish » Wed Oct 21, 2015 8:49 pm

I'm so close! For some reason my intersection points are slightly off. The body2 dotted line is pointing to a line that contains the intersection points on each end. They should be up and to the left where the two shapes overlap. Any ideas why this might be? Here's my code and an image.

Code: Select all

fixture f1 = sf()[0];
fixture f2 = sf()[1];
vertex[] v1 = f1.getVertices();
vertex[] v2 = f2.getVertices();
for (uint i = 0; i < v1.length; i++) {
	float x1 = v1[i].wpos.x;
	float y1 = v1[i].wpos.y;
	float x2 = v1[(i + 1) % v1.length].wpos.x;
	float y2 = v1[(i + 1) % v1.length].wpos.y;
	for (uint j = 0; j < v2.length; j++) {
		float x3 = v2[j].wpos.x;
		float y3 = v2[j].wpos.y;
		float x4 = v2[(j + 1) % v2.length].wpos.x;
		float y4 = v2[(j + 1) % v2.length].wpos.y;
		//print("l1p1: " + x1 + ", " + y1 + "  l1p2: " + x2 + ", " + y2);
		//print("l2p1: " + x3 + ", " + y3 + "  l2p2: " + x4 + ", " + y4);

		// adapted from http://processingjs.org/learning/custom/intersect/
		bool intersection = true;
		float a1, a2, b1, b2, c1, c2;
		float r1, r2, r3, r4;
		float denom, offset, num;
		float x, y;

		// Compute a1, b1, c1, where line joining points 1 and 2
		// is "a1 x + b1 y + c1 = 0".
		a1 = y2 - y1;
		b1 = x1 - x2;
		c1 = (x2 * y1) - (x1 * y2);

		// Compute r3 and r4.
		r3 = ((a1 * x3) + (b1 * y3) + c1);
		r4 = ((a1 * x4) + (b1 * y4) + c1);

		// Check signs of r3 and r4. If both point 3 and point 4 lie on
		// same side of line 1, the line segments do not intersect.
		if ((r3 != 0) && (r4 != 0) && r3 * r4 >= 0) {
			intersection = false;
		}

		// Compute a2, b2, c2
		a2 = y4 - y3;
		b2 = x3 - x4;
		c2 = (x4 * y3) - (x3 * y4);

		// Compute r1 and r2
		r1 = (a2 * x1) + (b2 * y1) + c2;
		r2 = (a2 * x2) + (b2 * y2) + c2;

		// Check signs of r1 and r2. If both point 1 and point 2 lie
		// on same side of second line segment, the line segments do
		// not intersect.
		if ((r1 != 0) && (r2 != 0) && r1 * r2 >= 0) {
			intersection = false;
		}

		//Line segments intersect: compute intersection point.
		denom = (a1 * b2) - (a2 * b1);

		if (denom == 0) {
			intersection = false;
		}

		if (intersection) {
			if (denom < 0) {
				offset = -denom / 2;
			} else {
				offset = denom / 2;
			}

			// The denom/2 is to get rounding instead of truncating. It
			// is added or subtracted to the numerator, depending upon the
			// sign of the numerator.
			num = (b1 * c2) - (b2 * c1);
			if (num < 0) {
				x = (num - offset) / denom;
			} else {
				x = (num + offset) / denom;
			}

			num = (a2 * c1) - (a1 * c2);
			if (num < 0) {
				y = (num - offset) / denom;
			} else {
				y = (num + offset) / denom;
			}

			// lines_intersect
			print("intersection: " + x + ", " + y);
		}

	}
}
Attachments
Capture2.JPG
Capture2.JPG (21.93 KiB) Viewed 20137 times

iforce2d
Site Admin
Posts: 860
Joined: Sat Dec 22, 2012 7:20 pm

Re: Make vertices at intersections of two overlapping polygo

Post by iforce2d » Thu Oct 22, 2015 1:44 am

The 'vertex' script class has these two properties:
vec2 pos
The position of this vertex in body-coordinates.
vec2 wpos
The position of this vertex in world coordinates.

When you say 'breaking' do you mean RUBE crashes? That would be a bug. If it just stops script execution then that is what we would expect - you would need to avoid divbyzero by checking if the denominator is zero.

Here is a C++ function I use in RUBE and many other projects for detecting if two lines cross and finding the intersection point if they do:

Code: Select all

bool linesCross(b2Vec2 v0, b2Vec2 v1, b2Vec2 t0, b2Vec2 t1, b2Vec2 &intersectionPoint)
{
    if ( areVecsEqual(v1,t0) ||
         areVecsEqual(v0,t0) ||
         areVecsEqual(v1,t1) ||
         areVecsEqual(v0,t1) )
        return false;

    b2Vec2 vnormal = v1 - v0;
    vnormal = b2Cross(1.0f, vnormal);
    float v0d = b2Dot(vnormal, v0);
    float t0d = b2Dot(vnormal, t0);
    float t1d = b2Dot(vnormal, t1);
    if ( t0d > v0d && t1d > v0d )
        return false;
    if ( t0d < v0d && t1d < v0d )
        return false;

    b2Vec2 tnormal = t1 - t0;
    tnormal = b2Cross(1.0f, tnormal);
    t0d = b2Dot(tnormal, t0);
    v0d = b2Dot(tnormal, v0);
    float v1d = b2Dot(tnormal, v1);
    if ( v0d > t0d && v1d > t0d )
        return false;
    if ( v0d < t0d && v1d < t0d )
        return false;

    intersectionPoint = v0 + ((t0d-v0d)/(v1d-v0d)) * (v1-v0);

    return true;
}
I'll convert this to rubescript in my next post (unless you beat me to it!)

iforce2d
Site Admin
Posts: 860
Joined: Sat Dec 22, 2012 7:20 pm

Re: Make vertices at intersections of two overlapping polygo

Post by iforce2d » Thu Oct 22, 2015 2:23 am

Here is a rubescript version of the above, with an example usage. The script assumes the two selected fixtures both have at least two vertices, and will move the cursor to the intersection of their first edges, if their first edges actually intersect.

Code: Select all

bool areVecsEqual(vec2 a, vec2 b)
{
	return a == b;
}

 float b2Dot(vec2 a, vec2 b)
{
	return a.x * b.x + a.y * b.y;
}

vec2 b2Cross(float s, vec2 a)
{
	return mv(-s * a.y, s * a.x);
}

bool linesCross(vec2 v0, vec2 v1, vec2 t0, vec2 t1, vec2 &out intersectionPoint)
{
    if ( areVecsEqual(v1,t0) ||
         areVecsEqual(v0,t0) ||
         areVecsEqual(v1,t1) ||
         areVecsEqual(v0,t1) )
        return false;

    vec2 vnormal = v1 - v0;
    vnormal = b2Cross(1.0f, vnormal);
    float v0d = b2Dot(vnormal, v0);
    float t0d = b2Dot(vnormal, t0);
    float t1d = b2Dot(vnormal, t1);
    if ( t0d > v0d && t1d > v0d )
        return false;
    if ( t0d < v0d && t1d < v0d )
        return false;

    vec2 tnormal = t1 - t0;
    tnormal = b2Cross(1.0f, tnormal);
    t0d = b2Dot(tnormal, t0);
    v0d = b2Dot(tnormal, v0);
    float v1d = b2Dot(tnormal, v1);
    if ( v0d > t0d && v1d > t0d )
        return false;
    if ( v0d < t0d && v1d < t0d )
        return false;

    intersectionPoint = v0 + ((t0d-v0d)/(v1d-v0d)) * (v1-v0);

    return true;
}

void main() 
{
	if ( sf().length < 2 ) {
		print("Please select two fixtures");
		return;
	}

	vec2 p0 = sf()[0].getVertex(0).wpos;
	vec2 p1 = sf()[0].getVertex(1).wpos;
	vec2 q0 = sf()[1].getVertex(0).wpos;
	vec2 q1 = sf()[1].getVertex(1).wpos;

	vec2 intersection;
	if ( linesCross( p0, p1, q0, q1, intersection ) )
		setCursor( intersection );
}
For example, before and after:
intersection.png
intersection.png (5.77 KiB) Viewed 20135 times
I think what you are doing is a worthwhile enough feature to be added to the default action menu in the next release, so I'll work on it myself too. Finding the intersection points is only a small part of the job though, there is a fair bit more to it yet...

First you need to make sure the edge you start with is on the outer edge of selected fixtures, then you need to make sure you have the windings correct when you intersect, and make sure the intersection point is the closest among what could be multiple intersections, and you need to make sure the next edge you follow is also an exterior edge, and you need to be careful about inserted vertex indices, and you need to decide how you're going to arrange the merge (does one fixture remain and absorb the other? are they both discarded and a new one created? which body should the merged fixture be attached to? etc etc). There are likely a few more tricky points I haven't even thought of too.

And that's only when you're considering just two fixtures... if you want to be able to select a big bunch of fixtures and have them all merged into each other as much as possible, you will also need to detect islands in the group as well.

All in all it's not surprising this hasn't been done yet :) If you feel like waiting a bit I will give it a go, but could be a day or two before a good solution is ready.

bvargish
Posts: 26
Joined: Fri Oct 02, 2015 4:17 pm

Re: Make vertices at intersections of two overlapping polygo

Post by bvargish » Thu Oct 22, 2015 9:06 pm

Thanks so much! And sorry, I meant that the script stopped executing, not that the program crashed.

There must have been something funky with the math code I snagged off the web because yours works fine. I updated your code to check every side of a fixture and log all intersection points, which is sufficient for me for now. Now I can get all of the coordinates needed to create a single line edge fixture instead of having a bunch of overlapping polygons. I'm guessing that would improve performance (otherwise I'm wasting my time!).

It would be really cool to have a merge shapes feature much like Adobe Illustrator's Pathfinder unite function (which is definitely over my head!). I'm only needing it to simplify something already created with a simpler Box2D tool, but arranging simple shapes then combining them would be helpful in creating complex polygons rather than drawing them point by point in some cases.

Code: Select all

bool areVecsEqual(vec2 a, vec2 b) {
	return a == b;
}

float b2Dot(vec2 a, vec2 b) {
	return a.x * b.x + a.y * b.y;
}

vec2 b2Cross(float s, vec2 a) {
	return mv(-s * a.y, s * a.x);
}

bool linesCross(vec2 v0, vec2 v1, vec2 t0, vec2 t1, vec2 & out intersectionPoint) {
	if (areVecsEqual(v1, t0) ||
		areVecsEqual(v0, t0) ||
		areVecsEqual(v1, t1) ||
		areVecsEqual(v0, t1))
		return false;

	vec2 vnormal = v1 - v0;
	vnormal = b2Cross(1.0f, vnormal);
	float v0d = b2Dot(vnormal, v0);
	float t0d = b2Dot(vnormal, t0);
	float t1d = b2Dot(vnormal, t1);
	if (t0d > v0d && t1d > v0d)
		return false;
	if (t0d < v0d && t1d < v0d)
		return false;

	vec2 tnormal = t1 - t0;
	tnormal = b2Cross(1.0f, tnormal);
	t0d = b2Dot(tnormal, t0);
	v0d = b2Dot(tnormal, v0);
	float v1d = b2Dot(tnormal, v1);
	if (v0d > t0d && v1d > t0d)
		return false;
	if (v0d < t0d && v1d < t0d)
		return false;

	intersectionPoint = v0 + ((t0d - v0d) / (v1d - v0d)) * (v1 - v0);

	return true;
}

void main() {
	if (sf().length < 2) {
		print("Please select two fixtures");
		return;
	}

	vertex[] v1 = sf()[0].getVertices();
	vertex[] v2 = sf()[1].getVertices();

	for (uint i = 0; i < v1.length; i++) {
		vec2 p0 = sf()[0].getVertex(i).wpos;
		vec2 p1 = sf()[0].getVertex((i + 1) % v1.length).wpos;
		for (uint j = 0; j < v2.length; j++) {
			vec2 q0 = sf()[1].getVertex(j).wpos;
			vec2 q1 = sf()[1].getVertex((j + 1) % v2.length).wpos;
			vec2 intersection;
			if (linesCross(p0, p1, q0, q1, intersection)) {
				print("intersection: " + intersection);
			}
		}
	}
}

iforce2d
Site Admin
Posts: 860
Joined: Sat Dec 22, 2012 7:20 pm

Re: Make vertices at intersections of two overlapping polygo

Post by iforce2d » Sat Oct 24, 2015 12:42 pm

I made a script that does the heavy-lifting part of this. It still needs some refinement before making it into the default menu, but I'll give you what I have for now since it should still save you a lot of time.

Before running the script, the expected starting state is:
- there must be a fixture named 'output' somewhere in the scene
- at least two polygon fixtures (excluding the 'output' fixture) should be selected
- the selected fixtures should all be wound the same way

The script will set the vertices of the 'output' fixture from the merged outline of the selected fixtures. It does this by starting with the left-most vertex of the selected fixtures and tracing around the outside looking for intersections with the other selected fixtures.

Here are some examples which will probably illustrate this more clearly. Between each of the following before and after shots, I have pressed F5 and then delete, to run the script and then delete the original fixtures for clarity. If your original fixtures are all on different bodies, you might want to delete those bodies instead of just their fixtures.

The square fixture on the right is the one called 'output' which will be reshaped, and remains as the merged result.

Basic example.
merge1.png
merge1.png (62.49 KiB) Viewed 20127 times
Example with hole - the interior outline will be ignored.
merge3.png
merge3.png (57.48 KiB) Viewed 20127 times
Example with two islands (note the removal of one small fixture near the bottom) - because the outline tracing starts with the leftmost vertex of the selection, the five fixtures in the bottom right have been completely missed out.
merge2.png
merge2.png (50.43 KiB) Viewed 20127 times
In cases where the resulting merge causes vertices to be within 0.005 units of each other, those vertices will be welded into a single vertex to avoid a decomposition with sliver triangles.

For your case, the outcome of this script will give you many more polygons than the original un-merged fixtures which will be a huge step backward from an efficiency point of view. I think I mentioned in our other discussion before, but you would only want to do this if you were going to make the ground a loop shape. The 'output' fixture can be a loop shape before running the script, since the only thing the script does is change the vertices of the output shape.

Rubescript first draft, a little rough but should work:

Code: Select all

vec2 cross(float s, vec2 a)
{
	return mv(-s * a.y, s * a.x);
}

bool linesCross(vec2 v0, vec2 v1, vec2 t0, vec2 t1, vec2 &out intersectionPoint, float &out f)
{
    if ( v1 == t0 || v0 == t0 || v1 == t1 || v0 == t1 )
        return false;

    vec2 vnormal = v1 - v0;
    vnormal = cross(1.0f, vnormal);
    float v0d = vnormal.dot(v0);
    float t0d = vnormal.dot(t0);
    float t1d = vnormal.dot(t1);
    if ( t0d > v0d && t1d > v0d )
        return false;
    if ( t0d < v0d && t1d < v0d )
        return false;

    vec2 tnormal = t1 - t0;
    tnormal = cross(1.0f, tnormal);
    t0d = tnormal.dot(t0);
    v0d = tnormal.dot(v0);
    float v1d = tnormal.dot(v1);
    if ( v0d > t0d && v1d > t0d )
        return false;
    if ( v0d < t0d && v1d < t0d )
        return false;

	if ( (v1d - v0d) == 0 )
		return false;

	f = (t0d-v0d) / (v1d-v0d);

    intersectionPoint = v0 + f * (v1-v0);

    return true;
}

bool fixtureIsPolygon(fixture f) {
	return f.getShape(0).type == 1;
}

vertex findLeftmostVertex( fixture[] &fs ) {
	float lx  = 999999; // no FLT_MAX?
	vertex best;
	for (uint i = 0; i < fs.length; i++) {
		fixture f = fs[i];
		vertex[] vs = f.getVertices();
		for (uint k = 0; k < vs.length; k++) {
			if ( vs[k].wx < lx ) {
				best = vs[k];
				lx = best.wx;
			}
		}
	}
	return best;
}

float findFirstIntersection( vertex originVertex, vec2 startVec, vertex nextVertex, fixture[] fs, vec2[] &inout pts, vec2 &out intersection, vertex &out nextPt ) {
	//print("Finding:");
	//print( startVec );
	//print( nextVertex.wpos );

	float dist = 999999;

	if ( nextVertex == originVertex ) {
		//print("Found loop");
		return dist;
	}

	fixture thisFixture = nextVertex.getFixture();
	vec2 v0 = startVec;
	vec2 v1 = nextVertex.wpos;
	for (int c = 0; dist == 999999 && c < thisFixture.getNumVertices(); c++) {
		pts.insertLast(v0);
		for (uint i = 0; i < fs.length; i++) {
			fixture f = fs[i];
			if ( f == thisFixture )
				continue;
			vertex[] vs = f.getVertices();
			for (uint k = 0; k < vs.length; k++) {
				int nk = (k+1) % vs.length;
				vec2 q0 = vs[k].wpos;
				vec2 q1 = vs[nk].wpos;
				float tmpDist;
				vec2 tmpIntersection;
				if ( linesCross( v0, v1, q0, q1, tmpIntersection, tmpDist ) ) {
					//print("tmpDist");
					//print(tmpDist);
					if ( tmpDist > 0.005 && tmpDist < dist ) {
						intersection = tmpIntersection;
						nextPt = vs[nk];
						dist = tmpDist;
					}
				}
			}
		}

		if ( nextVertex == originVertex ) {
			//print("breaking");
			break;
		}

		nextVertex = nextVertex.next();
		v0 = v1;
		v1 = nextVertex.wpos;
	}
	//print("dist");
	//print(dist);
	return dist;
}

void main() 
{
	if ( sf().length < 2 ) {
		print("Need at least two polygon fixtures to merge");
		return;
	}

	// only handle polygons
	fixture[] fs = filterFixtures( sf(), fixtureIsPolygon );
	if ( fs.length < 2 ) {
		print("Need at least two polygon fixtures to merge");
		return;
	}

	vertex originVertex = findLeftmostVertex( fs );
	vertex nextVertex = originVertex.next();

	vec2 firstIntersection = originVertex.wpos;
	vec2[] pts;
	//vertex nextPt = nextVertex;
	int count = 0;

	// trace outline
	while ( findFirstIntersection( originVertex, firstIntersection, nextVertex, fs, pts, firstIntersection, nextVertex ) < 999999 ) {
		if ( count++ > 100 ) {
			print("Reached limit");
			break;
		}
	}

	// prevent consecutive vertices from being too close to each other
	for (uint i = 1; i < pts.length; i++) {
		if ( pts[i].distanceTo(pts[i-1]) < 0.005 ) {
			pts[i-1] = 0.5 * (pts[i] + pts[i-1]); // merge at midpoint
			pts.removeAt(i);
			i = 1; // start again
		}
	}

	// set the merged vertices for the fixture called 'output'
	fixture f = getFixture("output");
	f.setVertices(pts);

	// the vertices in the pts array are in world coordinates, 
	// need to shift the created fixture to where it should be
	vec2 offset = originVertex.wpos - f.getVertices()[0].wpos;
	translate( f, offset );
}

bvargish
Posts: 26
Joined: Fri Oct 02, 2015 4:17 pm

Re: Make vertices at intersections of two overlapping polygo

Post by bvargish » Tue Oct 27, 2015 7:16 pm

Wow! This is really cool! Thank you!

My end goal is indeed to make all the existing polygons into a handful of loop shapes, which I think Add body with edge fixture creates. Please correct me if I'm wrong! Basically what I'd be doing is keeping the top surface terrain points and deleting all the rest on the underside of the shapes. So the polygons above would wind up as a 4 or 5 point line (most of my cases are not this simple). Building a terrain like this wouldn't make sense if I was building from scratch where I'd just start with a line, but it does for my game conversion.

Unfortunately, I must have done this part wrong - the selected fixtures should all be wound the same way - because with just two shapes the conversion fails. I think the script I'm using to generate the width and the height in meters based on the original pixel sizes is winding the shapes backwards or something (see code at https://www.iforce2d.net/forums/viewtopic.php?f=6&t=327). Maybe I could just reverse the vertices array to fix the glitch. I added my rube file for reference. I am aware that there are some gaps that I'd have to fill in order for this to fully work. Also, seems like I should probably just be using a single body with multiple fixtures rather than creating a bunch of bodies.
Capture.PNG
Capture.PNG (21.46 KiB) Viewed 20114 times
Attachments
level4_clone.rube
(35.64 KiB) Downloaded 750 times

iforce2d
Site Admin
Posts: 860
Joined: Sat Dec 22, 2012 7:20 pm

Re: Make vertices at intersections of two overlapping polygo

Post by iforce2d » Wed Oct 28, 2015 12:03 pm

Your fixtures are all wound correctly, it's a problem with the script. The fixed script (at least for these new cases) is below.

You can change the type of a fixture to 'loop' at any time in the properties panel. Probably the easiest thing to do is 'Add body with polygon fixture' and change it to a loop, or you could add your own menu entry pretty easily to have 'Add body with loop fixture' - see the built-in help under "Action menu" -> "Customizing the action menu" or this video for more details.

It may also be worth noting that the function used to find the 'output' fixture (getFixture()) will return the first fixture it finds in the scene with that name (typically the first created among them). So you could make one loop fixture called 'output' and duplicate it a dozen or so times, and at the end of the script where the new vertices are set you could give the newly re-shaped fixture a different name (setName()) - so that each time the script was executed it will use a different fixture. That should make the work a bit easier, because you would then just need to select the set of fixtures you want to merge and hit F5, delete, and repeat until done.

Code: Select all

vec2 cross(float s, vec2 a)
{
   return mv(-s * a.y, s * a.x);
}

bool linesCross(vec2 v0, vec2 v1, vec2 t0, vec2 t1, vec2 &out intersectionPoint, float &out f)
{
	if ( v1 == t0 || v0 == t0 || v1 == t1 || v0 == t1 )
        return false;

    vec2 vnormal = v1 - v0;
    vnormal = cross(1.0f, vnormal);
    float v0d = vnormal.dot(v0);
    float t0d = vnormal.dot(t0);
    float t1d = vnormal.dot(t1);
    if ( t0d > v0d && t1d > v0d )
        return false;
    if ( t0d < v0d && t1d < v0d )
        return false;

    vec2 tnormal = t1 - t0;
    tnormal = cross(1.0f, tnormal);
    t0d = tnormal.dot(t0);
    v0d = tnormal.dot(v0);
    float v1d = tnormal.dot(v1);
    if ( v0d > t0d && v1d > t0d )
        return false;
    if ( v0d < t0d && v1d < t0d )
        return false;

    if ( (v1d - v0d) == 0 )
        return false;

    f = (t0d-v0d) / (v1d-v0d);

    intersectionPoint = v0 + f * (v1-v0);

    return true;
}

bool fixtureIsPolygon(fixture f) {
   return f.getShape(0).type == 1;
}

vertex findLeftmostVertex( fixture[] &fs ) {
   float lx  = 999999; // no FLT_MAX?
   vertex best;
   for (uint i = 0; i < fs.length; i++) {
      fixture f = fs[i];
      vertex[] vs = f.getVertices();
      for (uint k = 0; k < vs.length; k++) {
         if ( vs[k].wx < lx ) {
            best = vs[k];
            lx = best.wx;
         }
      }
   }
   return best;
}

float findFirstIntersection( vertex originVertex, vec2 startVec, vertex nextVertex, fixture[] fs, vec2[] &inout pts, vec2 &out intersection, vertex &out nextPt ) {

    float dist = 999999;

    if ( nextVertex == originVertex ) {
        pts.insertLast(startVec);
        return dist;
    }

    fixture thisFixture = nextVertex.getFixture();
    vec2 v0 = startVec;
    vec2 v1 = nextVertex.wpos;
    for (int c = 0; dist == 999999 && c < thisFixture.getNumVertices(); c++) {
      pts.insertLast(v0);
      for (uint i = 0; i < fs.length; i++) {
         fixture f = fs[i];
         if ( f == thisFixture )
            continue;
         vertex[] vs = f.getVertices();
         for (uint k = 0; k < vs.length; k++) {
            int nk = (k+1) % vs.length;
            vec2 q0 = vs[k].wpos;
            vec2 q1 = vs[nk].wpos;
            float tmpDist;
            vec2 tmpIntersection;
            if ( linesCross( v0, v1, q0, q1, tmpIntersection, tmpDist ) ) {
			if ( tmpDist < 0.00005 ) {
				c--;
			}
               else if ( tmpDist < dist ) {
                  intersection = tmpIntersection;
                  nextPt = vs[nk];
                  dist = tmpDist;
               }
            }
         }
      }

      if ( nextVertex == originVertex ) {
         break;
      }

      nextVertex = nextVertex.next();
      v0 = v1;
      v1 = nextVertex.wpos;
   }
   return dist;
}

void main() 
{
   if ( sf().length < 2 ) {
      print("Need at least two polygon fixtures to merge");
      return;
   }

   // only handle polygons
   fixture[] fs = filterFixtures( sf(), fixtureIsPolygon );
   if ( fs.length < 2 ) {
      print("Need at least two polygon fixtures to merge");
      return;
   }

   vertex originVertex = findLeftmostVertex( fs );
   vertex nextVertex = originVertex.next();

   vec2 firstIntersection = originVertex.wpos;
   vec2[] pts;
   int count = 0;

   // trace outline
   while ( findFirstIntersection( originVertex, firstIntersection, nextVertex, fs, pts, firstIntersection, nextVertex ) < 999999 ) {
      if ( count++ > 100 ) {
         print("Reached limit");
         break;
      }
   }

   // prevent consecutive vertices from being too close to each other
   for (uint i = 1; i < pts.length; i++) {
      if ( pts[i].distanceTo(pts[i-1]) < 0.005 ) {
         pts[i-1] = 0.5 * (pts[i] + pts[i-1]); // merge at midpoint
         pts.removeAt(i);
         i = 1; // start again
      }
   }

   // set the merged vertices for the fixture called 'output'
   fixture f = getFixture("output");
   f.setVertices(pts);

   // the vertices in the pts array are in world coordinates, 
   // need to shift the created fixture to where it should be
   vec2 offset = originVertex.wpos - f.getVertices()[0].wpos;
   translate( f, offset );
}

bvargish
Posts: 26
Joined: Fri Oct 02, 2015 4:17 pm

Re: Make vertices at intersections of two overlapping polygo

Post by bvargish » Wed Oct 28, 2015 6:41 pm

Awesome, thanks! Wouldn't I use a line rather than a loop in my case? Is a loop essentially just a closed line? If so, how is that any different from a polygon?

If I had a simpler shape like a plus sign, would I be better off welding two rectangles together (2 shapes) rather than merging them into a single shape (looks like 4 polygons are created within that fixture)?

iforce2d
Site Admin
Posts: 860
Joined: Sat Dec 22, 2012 7:20 pm

Re: Make vertices at intersections of two overlapping polygo

Post by iforce2d » Thu Oct 29, 2015 1:36 am

Yes, a loop is essentially just a closed line. I'm not quite sure why you wouldn't want it closed, but there is not much difference in behavior. The tricky thing is getting the open edge in the right place.

Depends what you mean by 'better off'. Presumably you mean performance, in which case generally you are better off with line/loop shapes than polygons. Line/loop shapes will also have ghost vertices set up for you, which avoids the 'sticking on invisible points in the ground' problem that is common with polygons. The drawback with line/loop is that the shape will not push other bodies out of it like polygons do - if some other body manages to get inside the loop it will stay there. For static shapes it is extremely unlikely that any other shapes will 'tunnel' through a line/loop edge especially if when continuous collision detection is enabled. For dynamic bodies it can quite easily happen though, so I would recommend any dynamic bodies you have don't use line/loop shapes. Collision detection is not done between line/loop shapes anyway, so you would not want to allow a static line/loop and a dynamic line/loop to collide.

Post Reply