Splitting the polygon

Sep 24, 2009 at 5:55 AM
Edited Sep 24, 2009 at 7:14 AM

Yes, it's me again,

Trying to figure out the right way to split a polygon into sub-polygons. The thing that I am doing is this:

Using AABB, pick random point on each of two of its sides. Then I construct a line segment and use LineSegmentGeomIntersect to acquire intersection with the polygon. After all that, I would have an object and two points where it is intersected, and from here I classify polygon' points to either side of the line segment, thus having two polygons in result. Adding line segment points to start and end of each sub-polygon I, technically, should get two perfect polygons that, when summed, are parts of original polygon, but in reality I get jigged triangles that weakly resemble original polygon. I do not consider complex polygons that get more than two points of intersection here. Anyone knows what's the deal? Here's the code:

protected void Break(GameObject Object)
        {
            List<short> Numbers = new List<short>();
for (short iIndex = 0; iIndex < 4; iIndex++)
                Numbers.Add(iIndex);
// First, get object' AABB
            AABB Box = Object.Geometry.AABB;

            Random Rnd = new Random((int)System.DateTime.Now.Ticks);
int iLoc = Rnd.Next(4);
int iStartSide = Numbers[iLoc];
            Numbers.RemoveAt(iLoc);

            Rnd = new Random((int)System.DateTime.Now.Ticks);
            iLoc = Rnd.Next(3);
int iEndSide = Numbers[iLoc];
// Now, pick random point at each side
            Vector2 Pt1 = Side(iStartSide, Box.Min, Box.Max), Pt2 = Side(iEndSide, Box.Min, Box.Max);

            List<Vector2> Intersections = new List<Vector2>();
            CollisionHelper.LineSegmentGeomIntersect(ref Pt1, ref Pt2, Object.Geometry, true, ref Intersections);
            PartitionObject(Object, Intersections[0], Intersections[1]);
        }
protected Vector2 Side(int iSide, Vector2 Min, Vector2 Max)
        {
            Random Rnd = new Random((int)System.DateTime.Now.Ticks);
if (iSide == 0)
return new Vector2(Rnd.Next((int)Min.X, (int)Max.X), Min.Y);
else if (iSide == 1)
return new Vector2(Max.X, Rnd.Next((int)Min.Y, (int)Max.Y));
else if (iSide == 2)
return new Vector2(Rnd.Next((int)Min.X, (int)Max.X), Max.Y);
else if (iSide == 3)
return new Vector2(Min.X, Rnd.Next((int)Min.Y, (int)Max.Y));
return Vector2.Zero;
        }
protected void PartitionObject(GameObject ObjectToPartition, Vector2 SegmentStart, Vector2 SegmentEnd)
        {
            Vertices verts = ObjectToPartition.Geometry.WorldVertices;
            Vertices Part1 = new Vertices();
            Vertices Part2 = new Vertices();

            Part1.Add(SegmentStart);
            Part2.Add(SegmentStart);
foreach(Vector2 Vertex in verts)
            {
if (PointSide(SegmentStart, SegmentEnd, Vertex) >= 0)
                    Part1.Add(Vertex);
else
                    Part2.Add(Vertex);
            }

            Part1.Add(SegmentEnd);
            Part2.Add(SegmentEnd);
if (Part1.Count >= 3)
                AddPolygon(Part1);
if (Part2.Count >= 3)
                AddPolygon(Part2);
        }
int PointSide(Vector2 p1, Vector2 p2, Vector2 p)
        {
            Vector2 diff = p2 - p1;
            Vector2 perp = new Vector2(-diff.Y, diff.X);
float d = Vector2.Dot(p - p1, perp);
return Math.Sign(d);
        }
 

Coordinator
Oct 4, 2009 at 10:32 PM

What is the point of the polygon splitting? There are tons of decomposition algorithms avaliable in C# that works on everything from trapezoids to triangles. Some even decompose until they hit their limit (of # polygons).

Oct 5, 2009 at 3:09 AM

I need to simulate a breakdown of a piece of rock or dirt in my game. Guys at GameDev have suggested that I use  Voronoi partitioning with clipping, but I wonder are there any simplier ways to do it? As you mentioned "tons" of decomposition algorithms, can you suggest one that is most applicable for solving the problem?

Thanks.

Coordinator
Oct 5, 2009 at 12:51 PM

Voronoi partitioning creates sections around your points so you have to use clipping as they suggested. It will create a realistic breakdown of a rock in the sense that it does not just create 100 triangles.

We have a modified earclip algorithm inside our Vertices class. (Vertices.DecomposeGeom()) try it out and see if you can use it. (or have a look at the advanced samples - the one with SAT).