Jump to content
  • Advertisement
Sign in to follow this  
intransigent-seal

Automatically fixing vertex order for backface culling

This topic is 5405 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a set of models with pretty much random vertex order, and I want to write a tool to go through them and fix them all so that the vertex order is all clockwise (or counter-clockwise) so that I can turn on backface culling. But to do that I'll obviously need some algorithm for it. I've thought of one that I think should work, but I'm hoping there might be a better way (or maybe there's a standard algorithm for it that I don't know about). The way I've thought of so far is this: - Go through each triangle in the model. Calculate a face normal, and a triangle mid-point, and from those produce a ray from the centre of the triangle, and perpendicular to it. - Do an intersection test of that ray against every other triangle in the model. Count how many other triangles it intersects. - If the number is odd, then flip the vertex order. If it's 0 or even, then don't flip the vertex order. (The last point may be the wrong way round; ie, it may be flip if the count is even). However, as you can see, that's a fairly brute-force way of doing it. It would still be fast enough, since the models are low poly and there aren't too many of them, but even so I'd like to know if there's a better algorithm I could use. John B

Share this post


Link to post
Share on other sites
Advertisement
Ok here comes the pseudo code for something i wrote a while back...

what you need is the origin of the triangle / polygon so sum the vertecies and div by count


if (vertex count < 3)
return;

vector3 va = firstVertex;
vector3 vb = secondVertex;
vector3 vz = lastVertex; // of the triangle/polygon

vector3 ma = origin - va; // origin is the center/middle vec
vector3 mb = origin - va;
vector3 mz = origin - va;

vector3 crossAB = CrossProduct(ma, mb).Normalize();
vector3 crossAZ = CrossProduct(ma, mz).Normalize();

vector3 x = origin - crossAB;
vector3 z = origin - crossAZ;

if (Length(x) > Length(z))
{
// reorder them to CCW, were CW (I think, might be other way)
}


I hope thats correct, sorry for the short var names and little comments :D a bit short on time here


Hope that helped, if wrong(not understandable etc) pm me or reply, sorry gotta run

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!