Quote: btw, funneling is not a replacement for string pulling? (or what ever it's called) It's rather an extra step.

I'm not sure what the 'real' definition of string-pulling is, so I'm just going to avoid using that term. As for the funnel algorithm, yeah, it's an extra (post-processing) step applied after the (rough) path has been built.

Quote: One thing i noticed from the links tough was that they placed the points/nodes on each edge rather than the center of each triangle.

That's how I do it as well, and I think it probably works out better that way overall. (For one thing, even though it's unlikely to happen in practice, you can run into situations where the straight path between the centers of two mesh polygons actually goes through an obstacle, but this won't happen when the nodes lie on the polygon edges.)

Is there any example how to perform the funnel search once you got all the triangles?

basically what I got is the start/end point and all the triangles that form the "channel".

what's left is to build all possible paths and select the shortest one. Iv'e never even seen pseudo code for this in any article.

I don't know of pseudocode, but the code follows directly from the description of the funnel algorithm. Basically, to expand the right hand side of the funnel, walk down the right side of the funnel from the mouth towards the neck to find a point to put the new point after, such that the side of the funnel won't become concave. If you don't find it by the time you get to the neck, walk back up the left side of the funnel, collapsing it, until the point is on the right of one of the line segments on the left side. For expanding the left hand side, just do that in reverse. Draw out a funnel and some example expansion points and you'll see the pattern. Just remember: Walk down the extended side to the neck, then back up the other side to the mouth.

Quote: Is there any example how to perform the funnel search once you got all the triangles?

basically what I got is the start/end point and all the triangles that form the "channel".

what's left is to build all possible paths and select the shortest one. Iv'e never even seen pseudo code for this in any article.

Well, you don't actually build all possible paths and select the shortest one (that would take forever - literally!). Rather, the algorithm incrementally builds a path that is guaranteed to be no longer than any other path through the channel.

This was all discussed recently in some detail here. I'll repeat a couple of things I said in that thread. First of all, the paper I linked to in my first reply in that thread is the best reference I know of on the subject. (Unfortunately, it's not perfect - there seem to be some errors and ommisions in the article and the included pseudocode.)

I'll also make the same offer I made in the other thread: if you get really stuck, I'd be happy to share my code. The only caveat is that the code is somewhat application-specific, and so would probably take some work to adapt.

wow..141 pages! :P

thanks.

Quote: wow..141 pages! :P

Well, if it helps at all, the section on the funnel algorithm itself is only a few pages long :)

Well, I've read and searched about the funnel algorithm now and I get the concepts, now I need an "attack" plan. I got the triangles for the channel.

Should I merge the triangles to a polygon? eg:


so I get a list of points making up the edges. In this case 6 points.

Now it's time to do the funnel search, like Sneftel described.

[Edited by - HermanssoN on September 14, 2009 3:00:13 PM]

I too want to give the funnel algorithm a try but I am having a really hard time understanding the algorithm's details beyond the path, apex and funnel definitions, much more the pseudocode included in the paper mentioned earlier(http://www.cs.ualberta.ca/~mburo/ps/thesis_demyen_2006.pdf). Could someone please elaborate?