My current project of the day is sitting down with pen and paper and drawing some polygon simplification and rendering algorithmns.
Those of you who have followed my work in the past may remember "Flake Engine" my little c++ spin off designed to render a SRF file in Direct3D.
The problem with YSF SRF files is that polygons can be much larger than 3 verticies that OpenGL/Direct3D etc. draw in.
So how to simplify these polygons and draw correctly?
"Just trace from vertex 0, to 1, to 2... then do 2 to 3 to 0..." This is the FAN technique, which works for an ordered list.
Problem is what if you get a complex polygon where the edges intercept each other and draw holes?
So now it gets much harder to render a polygon.
I have read of the "ear lobe" technique and also the "odds/even" technique. I've written my own solution, which is similar to Soji's YSClass's YSSword function as well.
The algorithm is simple actually: Simplify the edges, then cut off the lob ears until no polygons can be drawn.
I will now apply this algorithm to this complex polygon:
Step One: Simplify the edges.
Start by checking if any edges intersect each other, as viewed from the polygons normal axis. All the intersections will need to have a vertex added.
The vertex is added and the polygon definition is updated to put the vertex in between the two affected edges. This will increase the polygons vertex count.
The edges are simplified until there are no more intersections.
Step Two: Start Ear Lobing.
Trace from the current vertex root (starts at 0) to it's next linked vertex (vertex 1), and then to the one after that (vertex 2). If any edge, especially the end vertex to the root intersects another edge, the polygon is no good (overflow) and iteration will restart from the next highest vertex root (vertex 1). Once a successful preliminary match is found, Find the center of the polygon that could be drawn by these 3 vertices and make that the polygon center for testing.
Draw an infinite ray from the calculated polygon center and count how many edges it intersects with. If the number of edges is ODD, it is INSIDE the final polygon, and will need to be drawn. If it is EVEN, then the polygon would be OUTSIDE the final polygon and should not be drawn. In this case, the root number of the vertices should be increased by one, and Step Two will re-iterate, testing and drawing new polygons based off the defined order.
Step Three: Breakdown of Ear Lobing
As each successful polygon is calculated, it is added to a completed list, and the polygon definition is updated.
Step Two is resumed on the new polygon definition, finding Ear Lobes and testing them to see if they are in the polygon and do not cross any other edges.
Step Four: Repeat
The process is repeated until no more edge conflicts are found, no more polygons can be created, or the working polygon definition (the one we keep breaking down as we break off ear lobes) is reduced to 3 vetecies or less.
The complex polygon is now drawn.
Some examples rendered with this method:
This method works for all polygons I can think of in my mind at the moment. Problem is that it is not very efficient.
This style of solving triangulation has existed for many years (at least 10?) now, but it's a slow approach. It'll get the polygons right every time, but it WILL take time to calculate. In fact the exact same lag problem exists in the real YSFlight executables, in YSClass (Soji explained this to me, he has a few methods, and he tries them all from fastest to slowest based on some binary tests).
So if I go back to my rendering engine code and re-write it, I should be able to FINALLY draw polygons completely correctly.
I will use this algorithmn to load SRF and eventually DNM models into my own programs when I finally get that far in coding.