Original Post
Hello, I'm new to this subject and i hope you can help me. I've seen this document: http://www.cs.ualberta.ca/~mburo/ps/thesis_demyen_2006.pdf (see pages 52 - 61) I'm interested in how Funnel Algorithm works and i'm trying to understand this. So far I've succesfuly implemented A* search on a nav-mesh (3D triangles) and the path generated is correctly found. So far the "monster" in my application walks thru' this path from one center to next triangle's center - until goal is reached. I have the Common Edges between adiacent triangles in the A* Path. I have also the Start and the Goal 3D points (i.e the monster start position and respectively the destination where the monster sould arrive). Now, i know that implementing Funnel Algorithm requires first to get 2 lists: - list 1 = list with ALL the vertices on the left of channel (in A* path). - list 2 = list with ALL the vertices on the right of channel (in A* path). So I build these lists (channel1 & channel2) like so : here are the results (screen-shoot): 
and the incorrect one (swiched vertices): 
I get messed up results i think because of the GetCommonEdge() function and i dont know how to do it correctly. How can i build left & right channels correctly ? (i.e the channel1 and channel2) What's the next step implementing Funnel Algorithm ?
// returns in "p1" & "p2" (two 3D points) => a common edge between two triangles (n1 & n2 are adiacent triangles in path)
void CFunnel::GetCommonEdge(CNavNode *n1, CNavNode *n2, CVector3 &p1, CVector3 &p2)
{
int index = -1;
CVector3 found[2];
// loop thru all vertices in triangle 1
for(int c2=0; c2<3; c2++)
{
// loop thru all vertices in triangle 2
for(int c1=0; c1<3; c1++)
{
// if common vertex is found then store it to "found" variable .
if(*n1->point[c2]==*n2->point[c1])
{
index++;
found[index] = *n1->point[c2];
}
}
}
// p1 = first common point, p2 = second common point.
p1 = found[0];
p2 = found[1];
}
//
void CFunnel::GetFunnel(CVector3 *start, CVector3 *goal)
{
// clear values in lists (channel1 & channel2 are lists of 3d points).
channel1.clear();
channel2.clear();
// get number of triangles found with A* (i.e no triangles in the path).
WORD size = AStar.m_ClosedList.size()-1;
// loop thru' all triangles.
for(unsigned short q=0; q<size; q++)
{
// get current triangle:
CNavNode* current = AStar.m_ClosedList[q];
// get current's adiacent triangle:
CNavNode* succesor = AStar.m_ClosedList[q+1];
// 2 vertices ( a common edge has 2 vertices)
CVector3 common[2];
//get common edge between current & succesor triangles and store found common points to common[0] & common[1]
// line from common[0] to common[1] define now the common edge between "current" and "succesor" triangles.
this->GetCommonEdge(current,succesor, common[0], common[1]);
// 2D Crossproduct = returns if common[0] is in clocwise order defined in respect to common[1]. (ignoring y axis)
float cross = common[0].x*common[1].z - common[0].z*common[1].x;
// if clockwise
if(cross>0)
{
// add common[0] to channel1
channel1.push_back(common[1]);
// add common[1] to channel2
channel2.push_back(common[0]);
}
else // else counterclokwise
{
// add common[1] to channel1
channel1.push_back(common[0]);
// add common[0] to channel2
channel2.push_back(common[1]);
}
}
}
