Alright, time for introducing some main ideas of the algorithm.
To quadify a model, there could be a lot of potential methods, but a natural and simple one would be focusing on the face buffer.
Hence it comes the problem: how to determine which two triangles should form a new quadrangle? For convenience of explanation, let's discuss the problem with the aid of a simple image.
As you can see, in the following image, the triangle ABC (denoted by ΔABC, the same below) is surrounded by another 3 triangles:
ΔADB,
ΔBFC and
ΔACE. The cyclic arrows represent the orientation of each triangle.
Let's assume that
ΔABC and
ΔACE should form a quadrangle, and they share the same edge
AC. So for a given triangle
ΔABC, whose face indices would be "
a b c",
its adjacent triangle
ΔACE's face indices could be "
a c e", "
c e a", or "
e a c".
Therefore we have 3 combinations of the actual face indices for these two triangles:
Code:
|a b c| or |a b c| or |a b c|
|a c e| |c e a| |e a c|
Say
ΔACE's face indices are "
a c e" for example, then all you need to do is locate to these two triangles, the combination of who's face indices meets with the form of |a b c|a c e|, and create a new quadrangle by removing the shared edge
AC. Taking into account the orientations of both triangles, the indices of the quadrangle would be "
a b c e". Actually the indices are the same if
ΔACE's face indices are "
c e a" or "
e a c". These combinations are used only to filter the two trangles
ΔABC and
ΔACE from the face buffer, and they won't influence the orientation of the quadrangle unless they're not of the same vertex.
But what if
ΔABC should form a quadrangle with
ΔADB, or
ΔBFC? So in total we get 9 combinations, which I call the filter rules:
Code:
| abc | abc | abc | abc | abc | abc |
| adb | cbd | bdc | dcb | bad | cda |
-------------------------------------------------------------------------------
| abc | abc | abc |
| acd | dba | dac |
This is based on the conditions that you don't need to modify the face buffer, otherwise some of them can actually be regarded as the same rule, like |abc|adb| and |abc|acd| coz they're symmetric in the horizontal direction.
Luckily the game engines usually use only a few rules listed above to break a quadrangle into two triangles, which usually are stored adjacently.
For example, say there're two quadrangles:
Code:
f 1 2 3 4
f 2 5 6 3
its triangle face indices could be
Code:
f 1 2 3
f 3 4 1
f 2 5 6
f 6 3 2
That's what 3Ds Max usually do when you export to obj as triangles. Recreate the original quadrangles simply by dividing them into groups per two triangles in the order of how they're stored.
If the original model contains also triangles, so long as they're not inserted between the two triangles generated from a quadrangle, usually you can ignore the side effects.
Code:
f 1 2 3
f 3 4 1 --> f 1 2 3 4
f 1 4 5 --> f 1 4 5
f 7 5 6
f 6 8 7 --> f 7 5 6 8