What is the technology/algorithm behind Auto Geometry?

[Joseph39]

What kind of algorithm or technology that is being used to trace the outlines of the image? ... is it marching squares? if it is then how are they using it?

i wanna know what it is so i can use it in my c++ project if possible and i cant use chipmunk objective c version and i don't wanna use an external library right now.

[slembcke]

It's marching squares, and it's included as part of the free/open source part of Chipmunk now:
https://github.com/slembcke/Chipmunk2D/ ... /cpMarch.h
https://github.com/slembcke/Chipmunk2D/ ... Polyline.h

[Joseph39]

So it is marching squares.
but how are they proceeding to the next contour once they finished tracing the outlines of the first one?

because i have the marching squares algo and it stops once it traced the first contour and i don't know how to make it proceed to the next one.
that's the mystery that i wanna Solve.

i just need this little push to be done with my project.
and i just want the concept the idea that makes this algorithm work on multiple shapes.

and even though the source is in front of me and i still dont know how are they proceeding to the next shape once done with the first.

P.S 1: i have the marching squares algo and it works perfectly fin and i used it many times on images with only one shape in theme and when i use it on multiple shapes it only traces the first shape.

P.S 2: i'm starting to think about contacting with one of the developers so i can get this resolved but i just dont know if they will respond back to me or not?

and thanks in advance.

[slembcke]

It doesn't trace each contour individually. It processes the image left to right, top to bottom. For each square with a segment in it cpMarch*() calls a callback function. cpPolylineSetCollectSegment() is provided as a default callback to use. It builds a set of polylines one segment at a time. Each segment added either starts a new polyline, is added to the front of back of an existing one, or joins two ends (either causing a loop or joining two existing lines).

Iterating the image one row at a time is very cache friendly, and there are usually very few polyline ends to search through to find where to insert a segment.

[Joseph39]

but this doesn't seem like marching squares at all?
and what do you mean by "For each square"? do you mean for each pixel?

and please bear with me here i still have a lot of questions!!

[slembcke]

A common algorithm is to follow a contour through the image. AFAIK this is not marching squares at all, but it's a good shortcut if you only need a single contour. I often see people call this marching squares though.

In marching squares you make a grid where each pixel is a corner on the grid instead of cells (squares) in the grid. Each cell in the grid is processed independently into a chunk of geometry, then all of the geometry is combined somehow. In my case, each cell produces 0, 1 or 2 line segments and those are combined together into polylines.

Thi wikipedia article for marching squares is pretty good:
https://en.wikipedia.org/wiki/Marching_squares

[Joseph39]

do you know any implementation of it that operates on a raw image data because i searched and i found a lot of implementations But sadly none of them operates on a raw image data(unsigned char*).

and i know am going too far asking you for this but pls bear with me.

[Joseph39]

the closest thing to what has been mentioned on the wiki article that i have found is this implantation which doesn't even take an image to process it as input and extract its geometry not to mention that there are some errors in IslandVoxelSpaceAdapter class constructor and in another method with this signature :

float value In( int x, int y ) const.

i just dont understand how is he using it??? ... where is the image that is supposed to be processed? .. its no where to be found in the source code??

source code:
http://www.idevgames.com/forums/thread-8761.html

could you take a look at it please.

P.S: i replaced each Vec2i , Vec2f types with my Point struct which contains x and y properties as the author said and corrected all the errors except the errors in the IslandVoxelSpaceAdapter class.

[slembcke]

The following is the extra simple example for Chipmunk 6.x. The API changed a little in 7.x, I don't quite remember if I checked it since then... It might require a couple of simple tweaks.
http://chipmunk-physics.net/tutorials/C ... Tracer.tgz

Chipmunk's autogeometry can work on any data source though the use of a callback. All you need to do to make it work with raw image data is to make a basic getPixel() function. It looks like that example is the same, you give it a function that takes an x/y and you return a float between 0 and 1.

[Joseph39]

this library is built on top of each other so its not going to be easy to extract any
functionality from it without almost dragging the whole library with it.

how can i decouple the functionality that i just need from this library.
what approach do you suggest?

and one more thing what about the source code above .... did you took a look at it!!

P.S: dont forget that my main goal in here is bringing this functionality to c++.