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?
In the above image, the triangle ABC is surrounded by another 3 triangles:
△ADB,
△BFC and
△ACE.
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:
Code:
|a b c| or |a b c| or |a b c|
|a c e| |c e a| |e a c|
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 condition that you don't need to change the face buffer.
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 3 6
its triangle face indices could be
Code:
f 1 2 3
f 3 4 1
f 2 5 3
f 3 6 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 7 2 --> f 1 7 2
f 2 5 3
f 3 6 2 --> f 2 5 3 6