marching squares algorithm?

Topics: Developer Forum
Developer
Dec 21, 2010 at 3:25 PM

Hi,

I was wondering where I could find the algorithm you are talking about here (scroll down to Texture to polygon) and I found out that you are talking about the code I submitted (as I saw my name here and the note that I'm using marching squares).

Well, I'm using an algorithm that I developed on my own and it feels not right to let the missinformation there :P ... I didn't just implement an existing idea, I spent quite some time on this :).

 

I'm afraid a simple message to genbox will go under in the amount of messages he probably gets, so I'm posting it here.

 

What might have led to this missinformation is that there was a user who told me about the marching squares algorithm and I tried it out. However, my implementation of that algorithm was slower then what I had created, so I dropped it and never released it ...

Coordinator
Dec 21, 2010 at 11:57 PM

That is my fault David. I must have misread the discussion way back when you developed the code. I'll be sure to remove the misinformation right away.

Now that I have you here (again...), do you think you can improve the implementation a bit with some changes I have in mind?

Developer
Dec 22, 2010 at 7:28 PM
Edited Dec 22, 2010 at 7:29 PM

Thanks :).

Well, I have got to work the next week, but the week after I should be able to find a day or two.

So, what can I do for us?

Coordinator
Dec 22, 2010 at 11:13 PM

Well, I was thinking we could improve the hole support a bit. Nothing fancy really, the algorithm should return the holes it finds as simple polygons with a clockwise winding. This way we could use the holes in triangulation algorithms such as constrained delaunay that support holes.

Another thing is that the algorithm works with pixels and it returns the vertices as it found them in the texture. As seen in AdvancedSamples Demo1 (from the source control - inside the yet to be released FPE 3.2) you have to translate the vertices by the centroid - I'm wondering if this could be done inside the algorithm itself or would that be stupid?

You also have a TODO in there that should be looked at or removed. And I guess if you took an extra look at the algorithm, you could probably find a couple of improvements your self.

Developer
Dec 23, 2010 at 4:13 PM

... the algorithm should return the holes it finds as simple polygons with a clockwise winding.

Sounds simple.

 

(...) the algorithm works with pixels and it returns the vertices as it found them in the texture. (...) you have to translate the vertices by the centroid - I'm wondering if this could be done inside the algorithm itself or would that be stupid?

The Reason for that was that I wanted to generate polygons from huge textures and I didn't want to lose the position of the found polygons. I also didn't want them to become just one body.

However, I can put a flag into the creation parameters class and let the user decide what he wants.

 

You also have a TODO in there (...)

I'll take a look at that. I thought a few times about asking you to grant me svn developer rights so I could work on the alorithm whenever I'd like to... ? I thouth about creating a new decomposer or changing the algorithm so it doesn't need a decomposer anymore ... ... but I don't know if I can find that much time. What do you think?

Coordinator
Dec 23, 2010 at 5:07 PM

It is fine with me. You are welcome to do some work on the algorithm - my experience tells me that it is pretty stable and works in most cases.. If you make any major changes or change the API, be sure to let me know. I'll add you as a developer, if you have any questions, let me know.

Developer
Dec 25, 2010 at 10:43 AM

This way we could use the holes in triangulation algorithms such as constrained delaunay that support holes.

Is this already supported?

Coordinator
Dec 25, 2010 at 11:10 AM

Yes, the CDT algorithm in FPE already support holes. However, the API for holes is not yet exposed.

At the moment I'm trying to keep any changes out of the engine that is not related to the FPE 3.2 release (I've sent you an e-mail, not sure if you got it since you have 2 emails in my contacts) but if you take a look at the CDTDecomposer, you will see that the Polygon object have an AddHoles() or similar method.

Developer
Dec 25, 2010 at 11:29 AM
Edited Dec 26, 2010 at 11:31 AM

I got your email and I'm sure you have my @t-online and @sickbattery email addresses. I use both, so it doesn't matter which one you use.

I will tak a look at the CDTDecomposer. Thanks.

Update:
Ok, I've analysed my code and have decided to remove the PolygonCreationParameters class, also TextureConverter won't be static anymore (don't worry, I will do my best to keep the static interface intact). The return values will have to change (or I'll have to create new functions with new return values) because of the holes change request.

The functions will return something like:

    public class PolygonWithHoles
    {
        public Vertices Polygon;
        public List<Vertices> HolePolygons;
    }

Any objections?

Since it's x-mas I don't have that much time today. I'll work on it tomorrow (for two or three hours) and then in the new year again (I have to go to work between the holidays, sorry).

Update2:
It won't be that easy to keep the static intarface intact, since I have to return something more complex then List<Vertices> ...