What is the technology/algorithm behind Auto Geometry?

Discuss new features and future development.
Joseph39
Posts: 10
Joined: Mon Dec 07, 2015 1:50 am
Contact:

What is the technology/algorithm behind Auto Geometry?

Post by 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.
User avatar
slembcke
Site Admin
Posts: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

Re: What is the technology/algorithm behind Auto Geometry?

Post by 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
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
Joseph39
Posts: 10
Joined: Mon Dec 07, 2015 1:50 am
Contact:

Re: What is the technology/algorithm behind Auto Geometry?

Post by 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.
User avatar
slembcke
Site Admin
Posts: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

Re: What is the technology/algorithm behind Auto Geometry?

Post by 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.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
Joseph39
Posts: 10
Joined: Mon Dec 07, 2015 1:50 am
Contact:

Re: What is the technology/algorithm behind Auto Geometry?

Post by 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!!
User avatar
slembcke
Site Admin
Posts: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

Re: What is the technology/algorithm behind Auto Geometry?

Post by 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
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
Joseph39
Posts: 10
Joined: Mon Dec 07, 2015 1:50 am
Contact:

Re: What is the technology/algorithm behind Auto Geometry?

Post by 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
Posts: 10
Joined: Mon Dec 07, 2015 1:50 am
Contact:

Re: What is the technology/algorithm behind Auto Geometry?

Post by 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.
User avatar
slembcke
Site Admin
Posts: 4166
Joined: Tue Aug 14, 2007 7:13 pm
Contact:

Re: What is the technology/algorithm behind Auto Geometry?

Post by 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.
Can't sleep... Chipmunks will eat me...
Check out our latest projects! -> http://howlingmoonsoftware.com/wordpress/
Joseph39
Posts: 10
Joined: Mon Dec 07, 2015 1:50 am
Contact:

Re: What is the technology/algorithm behind Auto Geometry?

Post by 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++.
Post Reply

Who is online

Users browsing this forum: No registered users and 4 guests