As you may know, currently there're two tools I made are available in this forum that come with a quadrify feature. You can find them in the following posts in case you're interested in an attempt:
GSTDQuadifyer
A9Tool
Both of the quadrify method in these tools are based on a simple fact: the meshes they're dealing with have amost ideal face buffers, where almost every two triangles that should form a quadrilateral are placed in the buffer continuously. So there's even no need for a second thought about how to perform the quadrify process.
For those game models where mostly every two of these triangles are separated in discrete positions in the buffer, I came up with this 'unreliable' idea which was described in this post.
This method requires you to first manually find some quads with your judgement on its topology and figure out the 'filter rules' they followed. Then try to quadrify them with these found rlues through programing. It sounds logically unreliable but it does work for some cases as shown here and there. Maybe there do exist some kind of regular patterns if the original quads are simply split into triangles based on the orientation of the faces' vertex indices. But I can't imagine a way to mathematically prove it.
So, I've been working on a more universal method that's built upon some actually practical rules ever since: uniform and good topology. It's a dynamic and flexible system that allows you to specify how you want these rules to be applied. By changing the available parameters it can produce different results, and so as the side effects.
I'm not going to explain it in depth but merely to give an overall idea here.
The main idea of this method is to quadrify starting from those triangles which are known in certain ways to form quads with their neighboring triangles. I defined 3 types of such triangles and for properly referring I'll name them as pointcut type 1, 2 and 3. All these pointcuts are chosen from the border of the mesh, as it's easier to distinguish. The quadrify process is then performed outwards the two sides of these pointcuts along the border. When the first round is done, the new border is created by ignoring the triangles that have been processed. And so on all triangles should be handled since this process is theoretically convergent. Of course the settings of the parameters could result in termination before all triangles are processed, as that's what it is capable of at its best.
To demonstrate this algorithm here's a test I've done on a head mesh from RE7. For easier observation I replaced its UVs with the positions.
First image will be the original mesh:
zoom in:
Here's the result of quadrifying with pointcut type 1 only:
The white areas are the pointcuts, which were handled firstly. The green and red areas are staggered after them. The black areas are what havn't been covered yet.
zoom in:
Here's the result of quadrifying with pointcut type 2 only:
zoom in:
And here's the result of quadrifying with pointcut type 1 mixed with type 2 at the same time for each round:
zoom in:
Here's the result of quadrifying with pointcut type 1 first, and with type 2 when no pointcuts of type 1 can be found in current state, and with type 1 again when no pointcuts of type 2 can be found an so on:
zoom in:
Here's the result of quadrifying with previous method but with also pointcut type 3 in the switching list:
The blue areas are pointcuts of type 2, and the yellow areas are pointcuts of type 3.
zoom in:
Here's the result of the quadrify option of 3DS Max:
zoom in:
To further compare the previous result with it, here's the comparison under the wireframe view (2nd image for 3DS Max):
- overall:
- zoom in:
As you can see, this new algorithm has better performance than the Quadrify option in 3DS Max in terms of these areas it has covered. Currently its parameters control how you find these pointcuts, when you use them, how you switch between different types of pointcuts, and how you determine a quad to be a 'correct' one. By changing these values, this algorithm can accordingly change its behavior, so as to produce different results. Of course there're still some issues which might be possible to be fixed later.
For instance, there're some dis-located quads that result in those red triangles which were supposed to be treated as two quads.
One possible way to fix this issue is by providing a mechanism to check all the remaining triangles after the process is finished and determine if they're supposed to be handled as quads instead of triangles, and do some patching procedure like this:
That's still just an idea and a TODO thing in the future though.
when you get helped.
