luciusDXL
Fuel Station sectors 376, 377 and 388 have strange contours that are specified out of order.
Fuel Station sectors 376, 377 and 388 have strange contours that are specified out of order. This causes the resulting polygons to be incorrect. Robust handling of walls being out of order and not identifying the contours in an easy to deal with way.
Note this does not impact 2.5D rendering using the software renderer but makes the resulting polygons incorrect for true 3d rendering.
One way to solve this is keeping a list of visited walls. Start with an unvisited wall. Add its start vertex to the contour list and mark the wall visited. The next wall to visit will be the wall that starts with the current wall's ending vertex. When the first starting vertex is seen again as an ending vertex, the contour is complete. Keep searching for contours while you have walls to visit.
Another way to solve this is treating it like a graph problem. The contours of a sector are the cycles of its vertices. This may be overkill, but using a graph could allow you to detect other problems with the sector geometry.
Unfortunately, it seems the data is even more difficult than just being out-of-order.
Sector 388, vertex seven has two incoming edges and two outgoing edges.
Any algorithm is going to need to decide what outgoing edge to follow when making a contour.
In this example, going down the list of walls follows the correct outgoing wall (7->8), but there could be a situation where that is not the case (instead erroneously choosing 7->10).
Additionally, even when specifying the contours in the proper order, this is a problem for poly2tri. A vertex cannot be referenced twice, otherwise an assert will occur.
TheForceEngine\TFE_Polygon\MPE_fastpoly2tri.h
MPE_EdgeEventPoints()
Line 1714
MPE_Assert(Triangle->Points[PointIndex] == Point);
Edit: This assert can be mitigated by keeping a list of visited vertices, and avoiding adding duplicate vertices for the sake of creating a contour. The result is an improvement for 388's hole triangulation, but it is still imperfect.
This is definitely a difficult problem to handle robustly.
Also while looking at this I found another example sector with issues. Sector 324 has two separate disconnected walls, walls zero and one.
Actually, it seems sector 388 is three contours. 7->8->9->7 is a zero area contour. The only valid interior contour is supposed to follow 7->10 not 7->8.
I had some additional time to look at this and may have a working proof of concept algorithm. The Python source and the result are attached. The sectors mentioned in this issue were targeted for testing.
It is currently recursive, so it would likely need to be made iterative.
Thanks for taking a look at this @njankowski. Honestly, I'm going to rewrite the tessellation algorithm, I'm not really happy with the related code currently in the project. But right now I am focused on the reverse-engineering effort and getting the base game playable, which is why I haven't been responsive to this issue. But I do appreciate the thought and effort on your part. 👍
In other words, this issue is low priority for now.