Sign in to follow this  
ViLiO

Eliminating t-junctions ..using Yann's method

Recommended Posts

Hi, I'm having some trouble fully implementing the method of getting rid of t-junctions that Yann describes here I have got most of it working, well up to the point where I can identify t-junctions that aren't open edges, but updating one of the polygons by inserting the vertex from the other edge is proving tricky. My implementation is as follows: I am not worrying about texture-coordinates at this stage, just geometry. I have an array of unique vertices and an array of polygons. Each polygon is convex and consists of an array of indices. This array can be any length really, and each polygon is drawn as a triangle fan. I have created a list of all edges, where an edge consists of 3 integers. These integers represent an index to the first vertex, an index to the second vertex and a pointer to the polygon the edge belongs too. Next I have sorted this list of edges using std::sort (bare with me here [grin]) and have managed to get like edges together (ie edge 0 1 0 is right beside edge 1 0 1 if you follow from what those 3 integers represent). Then I am able to loop through, find all lone edges and test them to see if they are really t-junctions. This is where my own implementational thoughts have come into play [smile] When a lone edge is found, I loop through all other edges to find ones that share a vertex (edges have one common index). Then I test that edge to see if it is parallel to the possible t-junction edge (this is done with a dot product). If they are parallel I try to insert the non-common index from edge 2, into edge1 at a location between edge1's two indices. It works some times, but fails most of the time [rolleyes] So can anyone give me some pointers? Code upon request [grin] Thanks, ViLiO

Share this post


Link to post
Share on other sites
I got it sorted all by my very own [grin]

Source below for the readers of tomorrow (bare in mind at this stage I was not concerned with texture coords, I will work on that next [smile])


bool fixTJunctions(std::vector<class Polygon *> &polys, Set<class vector3f> &verts)
{
bool foundOne = false;
unsigned int len = (unsigned int)polys.size();
std::vector<polyEdge> edges;
int prev, curr;
polyEdge edge;

for(unsigned int i=0; i<len; i++)
{
prev = verts.find(polys[i]->getLastVertex());
int pos1 = polys[i]->getnVertices() - 1;
for(unsigned int j=0; j<polys[i]->getnVertices(); j++)
{
curr = verts.find(polys[i]->getVertex(j));

// add prev and curr to edge list
edge.i1 = prev;
edge.i2 = curr;
edge.pos1 = pos1;
edge.pos2 = j;
edge.p_Face = i;
edge.ptj = false;
edges.push_back(edge);

pos1 = j;
prev = curr;
}
}
len = (unsigned int)edges.size();

std::stable_sort(edges.begin(),edges.end());

if(len > 0)
{
for(unsigned int i=0; i<len; ++i)
{
if(i==0)
{
if(edges.at(i) != edges.at(i+1))
edges.at(i).ptj = true;
}
else if(i==len-1)
{
if(edges.at(i-1) != edges.at(i))
edges.at(i).ptj = true;
}
else
{
if(edges.at(i-1) != edges.at(i) && edges.at(i) != edges.at(i+1))
edges.at(i).ptj = true;
}
}
vector3f edge1;
vector3f edge2;
for(unsigned int i=0; i<len; ++i)
{
if(edges.at(i).ptj)
{
for(unsigned int j=0; j<len; ++j)
{
if(i!=j)
{
if(edges.at(j).ptj)
{
if(edges.at(i) <= edges.at(j))
{
if(edges.at(i).i1 == edges.at(j).i1 || edges.at(i).i2 == edges.at(j).i2)
{
edge1 = (verts.at(edges.at(i).i1) - verts.at(edges.at(i).i2));
edge2 = (verts.at(edges.at(j).i1) - verts.at(edges.at(j).i2));
}
else
{
edge1 = (verts.at(edges.at(i).i1) - verts.at(edges.at(i).i2));
edge2 = (verts.at(edges.at(j).i2) - verts.at(edges.at(j).i1));
}
float e1Len = edge1.squaredLength();
float e2Len = edge2.squaredLength();
edge1.normalize();
edge2.normalize();

float diff = fabsf(dotProduct(edge1,edge2) -1.0f);
if(diff <= EPSILON)
{
if(e1Len > e2Len) //edge2 cuts edge1
{
int uncommonIndex;// = edges.at(j).i2;
if(edges.at(i).i1 == edges.at(j).i1)
uncommonIndex = edges.at(j).i2;
else if(edges.at(i).i2 == edges.at(j).i1)
uncommonIndex = edges.at(j).i2;
else
uncommonIndex = edges.at(j).i1;

foundOne = polys.at(edges.at(i).p_Face)->insertVertex(verts.at(uncommonIndex),edges.at(i).pos2);//+insertOffset);
if(foundOne)
edges.at(i).ptj = false;
}
}
}
}
}
}
}
}

}
edges.clear();
return foundOne;
}



The ccw ordering remains in tact if only inserting a single index into a polygon, but the ordering isn't guaranteed for more than 1 index insertion. So I sort the polygon's indices to get them into ccw order after mending all t-junctions if it is necessary.

Now my .t3d compiler tool is almost perfect [grin]

If anyone has any suggestions on how it could be improved or if i've been particularly messy with my code, then feel free to tell me off.

Regards,
ViLiO

Edit: Changed it to return a bool as not all t-junctions are found with one call of fixTJunctions().
This way you can use it as part of a ...
while(fixTJunctions())
{
...sort vertices as needed
}
It gets them all in the end [grin]

[Edited by - ViLiO on December 9, 2005 9:51:54 AM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this