Texture to vertices question

Topics: Developer Forum, User Forum
Feb 1, 2009 at 2:47 AM
I just noticed that farseer has a Texture to Vertices function, which I find very interesting. But before I attempt to use it I had 2 quick questions.

1. Is the  Geom built only from the non-alpha portions of the image? I assume so, but I wanted to make sure.
2. Does the algorithm account for multiple polygons within the image? For example, if you had an image with 3 shapes, and an alpha background, and then ran the Texture to Vertices function against the image, would it produce 3 polygons within the geom, or would it attempt to merge them all into one polygon?

Thank you.
Coordinator
Feb 1, 2009 at 12:35 PM
1. It does account for the alpha in the image. You can set the tolerance in the methods.

2. It does only support one geometry at the moment. It returns a vertices array that contains the outline of your texture. Sickbattery is the one who made the extension to the Vertices class, he also made a multipolygon method if I remember correctly. I will talk to him about including such features in FP 2.1.
Feb 1, 2009 at 1:22 PM
Ok, that's excellent news. Any sort of ETA for when the multipolygon method will be accessible, cause that is exactly what I need. I was just going to write it myself, but if its going to be integrated into the engine itself, then no sense in reinventing the wheel. BTW, thanks for the quick response.
Coordinator
Feb 1, 2009 at 4:46 PM
I've just sent an email to Sickbattery. Our 2.1 version will take some time before it comes out, but I'll notify you when I have implemented the multipolygon functionality. You will be able to download it from our source control.
Feb 1, 2009 at 5:55 PM
Thank  you
Feb 5, 2009 at 12:22 AM
Do you know if Sickbattery's algorithm is based on the "marching squares" algorithm?
Developer
Feb 5, 2009 at 1:53 PM
Edited Feb 5, 2009 at 1:55 PM
Boy, I don't even know what "marching squares" are. *googles it*

Hey, this looks interesting but I guess it's slower then my version. "marching squares" checks all pixels in a texture. My code looks for an solid pixel and from that point on it moves along the edge. I have some ideas to speed it up even further with some direction expectation code. This would lower the pixel checks even more (but I'll scratch that idea if it's more time consuming then five pixel checks).

... but thanks for the idea. Who knows, maybe I'll come to a point where I could use it.
Thanks!
Developer
Feb 5, 2009 at 2:03 PM
Edited Feb 5, 2009 at 2:05 PM
Oh boy -.- ... I'd like to kill myself.
I didn't read it carefully enough. I'm at work.

Will read it at home and post again if it's faster or not and it might very well be. I'm about to change polygon from texture anyway ...
Developer
Feb 5, 2009 at 2:25 PM
... I thought about something like this a time ago, but I was thinking about a compression method of the uint array I get in polygon from texture. I had quite some problems figuring out what happens if I hit on the middle right most combinations. ... but in my head I was checking 2x2 pixels and also moving 2x2 pixels because I tried to quad the speed of detection and that's not possible because then I can't say in which direction to go and I scratched that idea.

... moving one pixel at a time solves the problem.

This is getting very very interesting ... and it's faster for sure. (Yeah I'm still at work but this doesn't leave me alone now.)
Feb 5, 2009 at 3:17 PM
Yeah, I am at work as well. In fact I was in a meeting with one of my larger customers discussing a firewall replacment when my leg started vibrating from all the emails. I thought another customer was down, or a server blew up, and got nervous. Man I was glad it was just graphics brain candy. :-)

A few years ago I used a variation of the marching cubes (3D version, of marching squares, obviously) in an experimental game engine I was creating, but never did much with it due to the Patent on the algorithm at that time. However, since then the patent has lapsed, so game on! So if you need any help, let me know. The only difficult part I see, is detecting a shape totaly encompassed by another hollow shape. For example, a hollow square with a solid circle in the middle, that dont touch at all. Being that the algorithm marches around the outside of the shape, in its current form it would never detect the inner circle, unless every pixel of the texture was checked..... However, detecting multiple solid shapes that dont touch within a texture wouldnt be that hard. You just march around the first object, note which pixels are checked, and which pixels are contained, then continue checking the rest of the non marked pixels looking for the next object, march around it, etc.

Let me know your thoughts. Thanks.
Developer
Feb 5, 2009 at 4:59 PM
Edited Feb 5, 2009 at 5:14 PM
A shape in a shape, huh :) ?

That's pretty easy. Look. All you have to do is create the first line around the outer shape. Then you take the most outstanding vertices of top and bottom. Now you iterate throu top to bottom Y-coords and check which edges of the polygon cut the horizontal line of the Y-coord. You save these cut points in a list and it's obvious what they are for:

outside | inside | outside

Now you iterate between the inside bounds to find the hole edge. If you find one then you do what you did last time and create a polygon following that line. Then you have to insert this line into the other polygon. Ready is the polygon with a fake hole (because it all has to be a single continuos line).

outside | inside | outside | inside | outside

Then run the hole searching code again to find all the other holes. If no holes are found then you save that polygon and restart the search for new polygons but(!) this time you always check if you are in a saved polygon. If yes then search on and don't care about the edge you just found. If it's a new edge then start from the very beginning.


I have the find hole in polygon code nearly ready to use. It's already creating fake holes. All I have to do is the part -> Search other shapes :).
And uhm ... I thought there is no such thing as a software patent oO?

Whatever ... I'll try to push "marching squares" to the max ;D. Shouldn't be a problem to implement it because it's just the search for the next pixel. The code to compress a bunch of vertices into a line will stay the same.
Developer
Feb 5, 2009 at 5:19 PM
Edited Feb 5, 2009 at 5:22 PM
Hehe ... ok, there is a little bit more to it but I don't want to go too much into the details ;).
(The code has to be fast and in order to be fast you need to compress many vertices on the fly into less and that's making it a bit more complicated to search for holes because the polygon edges aren't exactly on the texture's edge ... but like I said: It's already working here ;). ...)
Developer
Feb 5, 2009 at 5:50 PM
Ok oO. I'll get myself some snackfood and continue the work :).
I really hope that I can release a first beta this weekend.
Feb 5, 2009 at 6:49 PM
Excellent. Can I make a feature request?

I would really love to be able to pass rectangular / square chunks of the texture to the algorithm, not just the entire texture each time. This way you could make an updateable / destructible landscape by simply creating a large "terrain" texture, breaking the terrain into even chunks, then passing each chunk to the algorithm. Then whenever you need to change a piece of the landscape you simply determine which chunk has changed, dispose the geoms that are associated with it, pass the chunk back to the algorithm, and save the new geoms to your array of chunks.
Developer
Feb 5, 2009 at 8:29 PM
Edited Feb 5, 2009 at 8:58 PM
<strike>You'll have to split up your textures anyway. ... or are you planning on drawing 1024² textures :) ?
Since you'll have to splitt them you will probably have to update only 256² textures and that shouldn't take long.

I mean, I also like to create levels on one large png ... but I have code which splitts this large texture into smaller parts.
I can share it with you, if you want :).
</strike>
Developer
Feb 5, 2009 at 8:51 PM
Edited Feb 5, 2009 at 8:53 PM
Ok I was chatting with my gf and was busy and obviously stupid as f*** again -,- ... girls downgrade my brain somehow.

... ignore my post above please. It's just embarrassing. I know (now) that you just said that ... and yes I'll do my best to make it possible.
Feb 9, 2009 at 6:19 PM
So how goes the progress?
Developer
Feb 10, 2009 at 4:36 AM
Edited Feb 10, 2009 at 4:52 AM
At the moment I have a problem with marching squares. It ends up in an infinite loop because of the two middle right most cases. Somehow I knew these cases would make problems ;D ... remember me writing this ^^ ? Just scroll up, hehe. .. and here is what happens (the algorithm is moving around a barely transparent black pixel).

... but I won't throw it away. Don't worry. I already have an idea to fix that ;).

I'm a bit late. I know, I tried to finish sunday but then ... I had a choice oO. Go to my girlfriend or code like every other day at work. ...there was no possible way to stay home. I mean I knew I would have to go to her but I wasn't finished and ...

Today I got up really early. It's now 6.25 and I got up at 3.55 to work on this again. So you stil have to thank me for my effort and shouldn't ask me for the progress xD (the last part, just joking).

Then I have some (let's say minor) code design problems, you know this code evolved, I didn't plan anything and now I'm getting the bill for this.

I'll try to get it done next week end; I don't promisse but I'd like to have this functionallity, too. So belive me, I'm trying.
Coordinator
Feb 10, 2009 at 1:40 PM
You are such a chaotic man sickbattery :D Have you ever considered multitasking? you know, working while your gf..... nevermind.

Anyway, you are doing a great job and a real effort. Thanks a lot!
Feb 11, 2009 at 2:31 AM

Well, consider you efforts official applauded.

I appreciate what your doing, and wasnt trying to rush you. Was just curious about how things were progressing, and if you wanted any help.

And dont worry... 20 years from now you will look back on this time and think man... I totally should have spent more time coding, and less time with her...... BTW: That is basically how I ended up with my first ex wife.... If only I had spent more time coding, and less time with her, I wouldnt be out thousands and thousands of dollars in legal fees. LOL ;-)

Keep me posted, and left me know if I can help.

Feb 16, 2009 at 4:45 PM
So Sickbattery long time no chat, how was the weekend? Get a chance to dive further into the algorithm? Need any help?
Developer
Feb 17, 2009 at 6:53 PM
Edited Feb 17, 2009 at 7:05 PM
@genbox
Yeah oO. I'm very chaotic. Wanna see my brain? Click here. I forget everything -.- ...

@gamebeavis
I forgot about valentine's day. So she was here the whole weekend and before that I sew a pillow for her oO. Yeah, lol me out, I don't care xD ...
Oh and I can't say that I'm angry at her ... I'm just sorry for you guys oO.

Also, my last week was awful stressing because of my job. I worked from 6am to 6pm every day.

I didn't want to post until I've got it done -.- ... It's depressing if you have to post, that you still are working on something and you kinda said you'd be ready a week or two ago oO.

However. I'm having troubles with marching squares. It's somehow ... slower then my old code and that's odd.
I have fixed the infinite loop problem ... and I don't know.

I have a new class: PolygonCreationAssistance
It holds the texture data and performs checks and makes sure the data is valid. I don't know if this brakes everything down oO ? But it's still slower ... both versions use it.


I did some more testing and ... my code is twice as fast as marching squares oO. I don't get it! marching squares is just a select case!! -.- ... ...


Ok I've debugged a bit more, lol. It's freaking awesome xD. My search checks less pixels then marching squares :).

Sorry. I'm scratching marching squares oO.
I hope no one is disappointed oO ?
Developer
Feb 17, 2009 at 7:16 PM
Edited Feb 17, 2009 at 7:28 PM
Here is my marching squares algorithm:
(But as I said. I'll use my algorithm instead. I post it for whoever wants it ...)

Ok first of all PolygonCreationAssistance.cs:

using System;
using System.Collections.Generic;
using System.Text;
using FarseerGames.FarseerPhysics.Mathematics;

#if (XNA)
using Microsoft.Xna.Framework;
#endif

namespace FarseerGames.FarseerPhysics.Collisions
{
    public class PolygonCreationAssistance
    {
        #region Attributes
        private uint[] _data;
        private int _width;
        private int _height;

        private Vector2 _relevantAreaStart;
        private Vector2 _relevantAreaEnd;

        private byte _alphaTolerance;
        private uint _alphaToleranceRealValue;

        private float _hullTolerance;
        #endregion

        #region Properties
        public uint[] Data
        {
            get { return _data; }
        }

        public int Width
        {
            get { return _width; }
        }

        public int Height
        {
            get { return _height; }
        }

        public Vector2 RelevantAreaStart
        {
            get { return _relevantAreaStart; }
            set
            {
                if (value.X < 0f)
                {
                    value.X = 0f;
                }

                if (value.Y < 0f)
                {
                    value.Y = 0f;
                }

                _relevantAreaStart = value;
            }
        }

        public Vector2 RelevantAreaEnd
        {
            get { return _relevantAreaEnd; }
            set
            {
                if (value.X > _width)
                {
                    value.X = _width;
                }

                if (value.Y < _height)
                {
                    value.Y = _height;
                }

                _relevantAreaEnd = value;
            }
        }

        public byte AlphaTolerance
        {
            get { return _alphaTolerance; }
            set
            {
                _alphaTolerance = value;
                _alphaToleranceRealValue = (uint)value << 24;
            }
        }

        public uint AlphaToleranceRealValue
        {
            get { return _alphaToleranceRealValue; }
            set
            {
                _alphaTolerance = (byte)(value >> 24);
                _alphaToleranceRealValue = value;
            }
        }

        public float HullTolerance
        {
            get { return _hullTolerance; }
            set
            {
                float hullTolerance = value;

                if (hullTolerance > 4f) hullTolerance = 4f;
                if (hullTolerance < -1f) hullTolerance = -1f;

                _hullTolerance = hullTolerance;
            }
        }
        #endregion

        public PolygonCreationAssistance(uint[] data, int width, int height)
        {
            _data = data;
            _width = width;
            _height = height;

            RelevantAreaStart = Vector2.Zero;
            RelevantAreaEnd = new Vector2((float)width, (float)height);

            AlphaTolerance = 225;
            HullTolerance = 2f;
        }

        public bool IsSolid(Vector2 pixel)
        {
            return IsSolid((int)pixel.X, (int)pixel.Y);
        }

        public bool IsSolid(int x, int y)
        {

            ///return false if out of bouds. that makes it a shape in infinite space ... oO makes one think ...
            if (x >= 0 && x < _width && y >= 0 && y < _height)
            {
                return ((_data[x + y * _width] & 0xFF000000) >= _alphaToleranceRealValue);
            }
            else
            {
                return false;
            }
        }

        public void PopulateSearchSquare(int x, int y, out SearchSquare searchSquare)
        {
            searchSquare = SearchSquare.None;

            if (IsSolid(x, y))
            {
                searchSquare |= SearchSquare.TopLeft;
            }

            if (IsSolid(x + 1, y))
            {
                searchSquare |= SearchSquare.TopRight;
            }

            if (IsSolid(x, y + 1))
            {
                searchSquare |= SearchSquare.BottomLeft;
            }

            if (IsSolid(x + 1, y + 1))
            {
                searchSquare |= SearchSquare.BottomRight;
            }
        }

        public bool IsValid()
        {
            return _data.Length == _width * _height;
        }

        ~PolygonCreationAssistance()
        {
            _data = null;
        }
    }
}



Here are some new Enums:

    public enum EdgeAlignment
    {
        Vertical    = 0,
        Horizontal  = 1
    }

    [Flags]
    public enum SearchSquare : byte  
    {
        TopLeft         = 0x01,
        TopRight        = 0x02,
        BottomLeft      = 0x04,
        BottomRight     = 0x08,

        None            = 0x00,

        MoveRightComb1  = TopRight,
        MoveRightComb2  = TopLeft | TopRight,
        MoveRightComb3  = TopLeft | TopRight | BottomLeft,
        MoveLeftComb1   = BottomLeft,
        MoveLeftComb2   = BottomLeft | BottomRight,
        MoveLeftComb3   = BottomLeft | BottomRight | TopRight,
        MoveUpComb1     = TopLeft,
        MoveUpComb2     = TopLeft | BottomLeft,
        MoveUpComb3     = TopLeft | BottomLeft | BottomRight,
        MoveDownComb1   = BottomRight,
        MoveDownComb2   = TopRight | BottomRight,
        MoveDownComb3   = TopLeft | TopRight | BottomRight,

        SpecialComb1    = BottomLeft | TopRight,
        SpecialComb2    = TopLeft | BottomRight,

        DeadLock        = TopLeft | TopRight | BottomLeft | BottomRight
    }




And here is the marching squares algorithm:
(Just add this to Vertices.cs)

        #region Sickbattery's Extension
        private int _sourceWidth;
        private int _sourceHeight;

        private static SearchSquare _lastMove;

        private int SourceWidth
        {
            get { return _sourceWidth; }
            set { _sourceWidth = value; }
        }

        private int SourceHeight
        {
            get { return _sourceHeight; }
            set { _sourceHeight = value; }
        }

        public static Vertices CreatePolygon(ref PolygonCreationAssistance pca)
        {
            Vertices polygon;
            Vertices holePolygon;

            Vector2? holeEntrance;

            // First of all: Check the array you just got.
            if (pca.IsValid())
            {
                polygon = CreateSimplePolygon(ref pca, Vector2.Zero);

                //if (polygon != null)
                //{
                //    polygon.SourceWidth = pca.Width;
                //    polygon.SourceHeight = pca.Height;

                //    if (polygon.Count > 2)
                //    {
                //        holeEntrance = GetHoleHullEntrance(ref pca, ref polygon);

                //        if (holeEntrance.HasValue && false)
                //        {
                //            holePolygon = CreateSimplePolygon(ref pca, holeEntrance.Value);
                //            polygon.AddRange(holePolygon);
                //        }
                //    }
                //}
            }
            else
            {
                throw new Exception("Sizes don't match: Color array must contain texture width * texture height elements.");
            }

            return polygon;
        }

        public bool Update(ref PolygonCreationAssistance pca)
        {
            if (pca.IsValid() && pca.Width == _sourceWidth && pca.Height == _sourceHeight)
            {

            }

            return true;
        }

        /// <summary>
        /// This function inserts the hole polygon into the main polygon.
        /// </summary>
        /// <param name="polygon">Main polygon (outer polygon).</param>
        /// <param name="polygonInjection">Vertices list to be added as inner polygon.</param>
        /// <returns>True if polygon was successfully added.</returns>
        private static bool InjectPolygon(ref Vertices polygon, ref Vertices polygonInjection)
        {
            List<float> crossingEdges;

            return true;
        }

        private bool SplitNearestEdge(ref Vertices polygon, EdgeAlignment edgeAlign, int checkLine, out int index1, out int index2)
        {
            //hole die edges, schaue welche edge es ist und füge dann zwei vertices ein

            index1 = 1;
            index2 = 2;
            return true;
        }

        private static Vector2? GetHoleHullEntrance(ref PolygonCreationAssistance pca, ref Vertices polygon)
        {
            List<float> edges = new List<float>();

            //int yDataPosition = 0;

            int startLine = 0;
            int endLine = 0;

            int lastSolid = 0;
            bool foundSolid = false;
            bool foundTransparent = false;

            if (polygon != null && polygon.Count > 0)
            {
                startLine = (int)GetTopMostVertex(ref polygon);
                endLine = (int)GetBottomMostVertex(ref polygon);

                if (startLine > 0 && startLine < pca.Height && endLine > 0 && endLine < pca.Height)
                {
                    for (int y = startLine; y <= endLine; y++)
                    {
                        edges = GetCrossingEdges(ref polygon, EdgeAlignment.Vertical, y);
                        //yDataPosition = y * pca.Width;

                        if (edges.Count > 1 && edges.Count % 2 == 0)
                        {
                            for (int i = 0; i < edges.Count; i += 2)
                            {
                                foundSolid = false;
                                foundTransparent = false;

                                for (int x = (int)edges[i]; x <= (int)edges[i + 1]; x++)
                                {
                                    //if ((pca.Data[x + yDataPosition] & 0xFF000000) >= pca.AlphaToleranceRealValue)
                                    if (pca.IsSolid(x, y))
                                    {
                                        if (!foundTransparent)
                                        {
                                            foundSolid = true;
                                            lastSolid = x;
                                        }

                                        if (foundSolid && foundTransparent)
                                        {
                                            return new Vector2(lastSolid, y);
                                        }
                                    }
                                    else
                                    {
                                        if (foundSolid)
                                        {
                                            foundTransparent = true;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }

            return null;
        }

        private static float GetTopMostVertex(ref Vertices vertices)
        {
            float returnValue = float.MaxValue;

            for (int i = 0; i < vertices.Count; i++)
            {
                if (returnValue > vertices[i].Y)
                {
                    returnValue = vertices[i].Y;
                }
            }

            return returnValue;
        }

        private static float GetBottomMostVertex(ref Vertices vertices)
        {
            float returnValue = float.MinValue;

            for (int i = 0; i < vertices.Count; i++)
            {
                if (returnValue < vertices[i].Y)
                {
                    returnValue = vertices[i].Y;
                }
            }

            return returnValue;
        }

        public static List<float> GetCrossingEdges(ref Vertices polygon, EdgeAlignment edgeAlign, int checkLine)
        {
            List<float> edges = new List<float>();

            Vector2 slope;
            Vector2 lineStart;
            Vector2 lineEnd;

            if (polygon.Count > 1)
            {
                lineEnd = polygon[polygon.Count - 1];

                switch (edgeAlign)
                {
                    case EdgeAlignment.Vertical:
                        for (int i = 0; i < polygon.Count - 1; i++)
                        {
                            lineStart = polygon[i];

                            if ((lineStart.Y >= checkLine && lineEnd.Y <= checkLine) || (lineStart.Y <= checkLine && lineEnd.Y >= checkLine))
                            {
                                if (lineStart.Y == lineEnd.Y)
                                {
                                    if (lineStart.X >= lineEnd.X)
                                    {
                                        edges.Add(lineStart.X);
                                    }
                                    else
                                    {
                                        edges.Add(lineEnd.X);
                                    }
                                }
                                else
                                {
                                    slope = lineEnd - lineStart;
                                    edges.Add((checkLine - lineStart.Y) / slope.Y * slope.X + lineStart.X);
                                }
                            }

                            lineEnd = polygon[i];
                        }
                        break;

                    case EdgeAlignment.Horizontal:
                        for (int i = 0; i < polygon.Count - 1; i++)
                        {
                            lineStart = polygon[i];

                            if ((lineStart.X >= checkLine && lineEnd.X <= checkLine) || (lineStart.X <= checkLine && lineEnd.X >= checkLine))
                            {
                                if (lineStart.X == lineEnd.X)
                                {
                                    if (lineStart.Y >= lineEnd.Y)
                                    {
                                        edges.Add(lineStart.Y);
                                    }
                                    else
                                    {
                                        edges.Add(lineEnd.Y);
                                    }
                                }
                                else
                                {
                                    slope = lineEnd - lineStart;
                                    edges.Add((checkLine - lineStart.X) / slope.Y * slope.X + lineStart.Y);
                                }
                            }

                            lineEnd = polygon[i];
                        }
                        break;
                }
            }

            edges.Sort();
            return edges;
        }

        private static Vertices CreateSimplePolygon(ref PolygonCreationAssistance pca, Vector2 searchPosition)
        {
            bool entranceFound = false;

            Vertices polygon = new Vertices();
            Vertices hullArea = new Vertices();

            SearchSquare searchSquare = SearchSquare.None;
            Vector2 hullPoint = new Vector2();
            Vector2 outstanding = new Vector2();

            // Get the entrance point.
            if (searchPosition == Vector2.Zero)
            {
                entranceFound = GetHullEntrance(ref pca, out searchPosition);
                
                if (pca.IsSolid(searchPosition))
                {
                    searchPosition.X -= 1;
                }
            }
            else
            {
                entranceFound = true;
            }

            if (entranceFound)
            {
                pca.PopulateSearchSquare((int)searchPosition.X, (int)searchPosition.Y, out searchSquare);

                _lastMove = SearchSquare.MoveRightComb1;
                if (GetNextHullPoint(ref pca, ref searchSquare, ref searchPosition, out hullPoint))
                {
                    polygon.Add(hullPoint);
                    hullArea.Add(hullPoint);

                    do
                    {
                        // Search in the pre vision list for an outstanding point.
                        if (SearchForOutstandingVertex(ref hullArea, pca.HullTolerance, out outstanding))
                        {
                            // Add it and remove all vertices that don't matter anymore
                            // (all the vertices before the outstanding).
                            polygon.Add(outstanding);
                            hullArea.RemoveRange(0, hullArea.IndexOf(outstanding));
                        }

                        // Get the next point on hull.
                        if (GetNextHullPoint(ref pca, ref searchSquare, ref searchPosition, out hullPoint))
                        {
                            if (polygon.Count > 0 && polygon[0] == hullPoint)
                            {
                                break;
                            }

                            hullArea.Add(hullPoint);
                        }
                        else
                        {
                            break;
                        }
                    }
                    while (true);
                }
            }

            // Return the heavy compresed polygon ;D.
            return polygon;
        }

        /// <summary>
        /// This function search for the first hull point.
        /// </summary>
        /// <param name="textureBits">A reference to your texture's data.</param>
        /// <param name="textureWidth">Width of your texture.</param>
        /// <param name="alphaTolerance">Alpha tolerance :). Value of 10 will include points with alpha of 11 and greater.</param>
        /// <param name="entrance">The entrance.</param>
        /// <returns>First hull point.</returns>
        private static bool GetHullEntrance(ref PolygonCreationAssistance pca, out Vector2 entrance)
        {
            // Search for first solid pixel.
            for (int y = (int)pca.RelevantAreaStart.Y; y <= (int)pca.RelevantAreaEnd.Y; y++)
            {
                for (int x = (int)pca.RelevantAreaStart.X; x <= (int)pca.RelevantAreaEnd.X; x++)
                {
                    if (pca.IsSolid(x, y))
                    {
                        entrance = new Vector2(x, y);
                        return true;
                    }
                }
            }

            // If there are no solid pixels.
            entrance = Vector2.Zero;
            return false;
        }

        /// <summary>
        /// This function searches for an outstanding pixel. When found it searches on for the most outstanding.
        /// </summary>
        /// <param name="hullArea">Put a peace of the hull in here.</param>
        /// <param name="hullTolerance">How much distance from the actual hull line is allowed? 1f to 2f are good values.</param>
        /// <param name="outstanding">This will give you the most outstanding point in the piece of hull you gave it.</param>
        /// <returns></returns>
        private static bool SearchForOutstandingVertex(ref Vertices hullArea, float hullTolerance, out Vector2 outstanding)
        {
            int hullAreaLastPoint = hullArea.Count - 1;

            float lastOutstandingDistance = 0f;
            bool searchMostOutstanding = false;

            Vector2 outstandingResult = Vector2.Zero;

            // Search between the first and last hull point.
            for (int i = 1; i < hullAreaLastPoint; i++)
            {
                // Get the distance of the outstanding point.
                float outstandingDistance = Calculator.DistanceBetweenPointAndLineSegment(hullArea[i], hullArea[0],
                                                                                          hullArea[hullAreaLastPoint]);

                if (!searchMostOutstanding)
                {
                    // Check if the distance is over the one that's tolerable.
                    if (outstandingDistance > hullTolerance)
                    {
                        // Ok, next time we search for the most outstanding.
                        searchMostOutstanding = true;
                        lastOutstandingDistance = outstandingDistance;
                        outstandingResult = hullArea[i];
                    }
                }
                else
                {
                    // Is it the most outstanding?
                    if (outstandingDistance > lastOutstandingDistance)
                    {
                        // Indeed :). But lets search to the end.
                        lastOutstandingDistance = outstandingDistance;
                        outstandingResult = hullArea[i];
                    }
                }
            }

            // Return the stuff...
            outstanding = outstandingResult;
            return searchMostOutstanding;
        }

        private static bool GetNextHullPoint(ref PolygonCreationAssistance pca, ref SearchSquare searchSquare, ref Vector2 searchPosition, out Vector2 hullPointToAdd)
        {
            hullPointToAdd = Vector2.Zero;

            switch (searchSquare)
            {
                /// x = hull point
                
                /// . .  / . o  / o o
                /// . x /  . x /  . x
                case SearchSquare.MoveDownComb1:
                case SearchSquare.MoveDownComb2:
                case SearchSquare.MoveDownComb3:
                    
                    hullPointToAdd = new Vector2(searchPosition.X + 1, searchPosition.Y + 1);
                    searchPosition.Y += 1;

                    _lastMove = SearchSquare.MoveDownComb1;
                    break;

                /// . x  / o x  / o x
                /// . . /  . . /  o .
                case SearchSquare.MoveRightComb1:
                case SearchSquare.MoveRightComb2:
                case SearchSquare.MoveRightComb3:
                    
                    searchPosition.X += 1;              // first move
                    hullPointToAdd = searchPosition;    // then add - saves an operation

                    _lastMove = SearchSquare.MoveRightComb1;
                    break;
                
                /// x .  / x .  / x .
                /// . . /  o . /  o o
                case SearchSquare.MoveUpComb1:
                case SearchSquare.MoveUpComb2:
                case SearchSquare.MoveUpComb3:
                    
                    hullPointToAdd = searchPosition;
                    searchPosition.Y -= 1;

                    _lastMove = SearchSquare.MoveUpComb1; // todo: recheck movement
                    break;

                /// . .  / . .  / . o
                /// x . /  x o /  x o
                case SearchSquare.MoveLeftComb1:
                case SearchSquare.MoveLeftComb2:
                case SearchSquare.MoveLeftComb3:
                    
                    hullPointToAdd = new Vector2(searchPosition.X, searchPosition.Y + 1);
                    searchPosition.X -= 1;

                    _lastMove = SearchSquare.MoveLeftComb1; // todo: recheck movement
                    break;
                
                /// . o
                /// o .
                case SearchSquare.SpecialComb1:
                    if (_lastMove == SearchSquare.MoveUpComb1)
                    {
                        goto case SearchSquare.MoveRightComb1;
                    }
                    else
                    {
                        goto case SearchSquare.MoveLeftComb1;
                    }

                /// o .
                /// . o
                case SearchSquare.SpecialComb2:
                    if (_lastMove == SearchSquare.MoveRightComb1)
                    {
                        goto case SearchSquare.MoveDownComb1;
                    }
                    else
                    {
                        goto case SearchSquare.MoveUpComb1;
                    }

                /// o o  / . .
                /// o o /  . .
                case SearchSquare.DeadLock:
                case SearchSquare.None:
                default:
                    _lastMove = SearchSquare.None;
                    return false;
            }

            // populate with new values
            pca.PopulateSearchSquare((int)searchPosition.X, (int)searchPosition.Y, out searchSquare);
            return true;
        }
        #endregion


Developer
Feb 17, 2009 at 7:33 PM
Ok, I've had enough for today oO. Will code on tomorrow ...
I have to play Burnout Paradise The Ultimate Box ^^ ...
Feb 18, 2009 at 12:38 AM
Sickbattery - I was just giving you crap about your girl. In truth I have a fiance and 9 month old son that takes up most of my coding time these days, and thats just fine with me.

I took a look over your code and it looks very nice. However if your new algorithm is really that much faster, integrates into farseer, allows for multiple polygons per texture, and hollow objects, then I will wait patiently for it. I cant believe that marching squares is really that much slower, but then again I dont know how your algorithm works, so I dont see why it wouldnt be. Good work so far sir, and I look forward to the rest.
Developer
Feb 18, 2009 at 7:12 AM
My algorithm is already in Farseer ;). ... but atm it's limited to one polygon (without holes) per texture.
I'll write some docs for it, so anyone can understand it without diving into the code.
Developer
Feb 18, 2009 at 7:09 PM
I didn't have much time today in the morning to answer ...

"I was just giving you crap about your girl. In truth I have a fiance and 9 month old son that takes up most of my coding time these days, and thats just fine with me."
Hehe. Great job ;). Maybe I can say the same one day.

Tomorrow will be great!
Work ends at 1pm and I should be at home at 2pm and then I'll code on and finish multi polygons per texture (hollow are already finished).
Developer
Feb 19, 2009 at 9:50 AM
Oh and ... drinking beer at work at 11am is kinda funny ^^ ... ...
http://en.wikipedia.org/wiki/Carnival#Rhineland

Kids! Don't do this at home.
Developer
Feb 19, 2009 at 8:44 PM
Edited Feb 19, 2009 at 8:48 PM
Ok, it's getting really complex oO.

First thing I did today was test the performance and while doing I messed up my code a little bit, but thanks to Subversion everything was fine after some merges. Then I experienced a heavy performance drop and searched for the reason for some hours -.- ...

This was the solution:
this.IsFixedTimeStep = false;

I don't know why I did this:
this.IsFixedTimeStep = true;
this.InactiveSleepTime = new TimeSpan(0, 0, 0, 0, 1);

... but it's possible it got in there after merging a few times. Maybe I used this a time ago to check ... something oO.

Anyway. There is a bug somwhere in my code. So ... you'll have to wait a little bit longer.


@ gamebeavis
You asked if you could help. Well, would you like to take a look at the code? I'll put comments into it and send it to you and give you my icq, msn or skype ID. Video call would be great.
Feb 20, 2009 at 1:11 PM
Excellent work thus far sickbattery. However, this weekend is no good for me (family plans), but you can send it to my email and I would be happy to take a look at it next week (monday / tuesday ish). Ofcourse if you fix it by then rock on.
Feb 26, 2009 at 5:10 PM
Hey sickbattery, long time no chat sir. Sorry, I have been a busy little beaver this week, and havent had a chance to check in. How is the code coming, still need a second pair of eyes. Let me know.
Developer
Feb 28, 2009 at 11:37 AM
I'm ill -.- ... not able to concentrate.
I've got a sick note and I'm almost all day in bed.

Sorry guys.
Mar 1, 2009 at 4:17 AM
Edited Mar 1, 2009 at 4:18 AM
That's ok! i hope you get better soon... i guess the first half of your nickname applies now huh? ;)
Developer
Mar 11, 2009 at 8:23 AM
Ok, I'm back to normal oO. I had an awful flu and couldn't take the antibiotics I got prescribed because I'm allergic against them. So another doc in a hospital prescribed me some other antibiotics with far greater side effects (and I mean far greater) and said I sould take them only if I really have to xD ... and I should let my immune system handle this and give myself a break, sleep more, drink much, avoid stress ...

So, I did and it's gone now.

I won't be able to code this weekend but I still want to have this feature in Farseer - badly - because I'm lazy and I won't get any game done if the collision data isn't calculated automatically Oo ...
Mar 11, 2009 at 9:59 PM
Glad to hear you're feeling better! it's fine that you won't have it done right away, its not like the next version is coming out this weekend (or is it? ;) )