Doomsday Engine

Closer inspection reveals there are actually two underlying issues here that result in geometry being split incorrectly. In addition to the known issue with partially overlapped line segments, somehow the partitioner is dividing space in such a way as to induce the creation of the odd superfluous line segment long before overlap-splitting begins.

Edit: Logic of divideSegments() and splitLineSegment() appears fine. Following a split the new segments are inserted back into the blockmap and are processed again during the same divideSegments() call.

Edit2: Evidently addPartitionLineSegments() is erroneously creating a new segment on top of one that already exists in the map. Therefore this must be either an "edge tip" or an intercept management issue.

Edit3: Yes, clearly this is an intercept problem. The requisite vertex edge tips for the soon-to-be overlapped geometry are present and correct. Seemingly the problem lies with lineSegAtAngle()

Edit4: The logic of lineSegAtAngle() is fine, the issue is that epsilons aren't large enough for the segments to be detected (and thus affect the outcome of the later addPartitionLineSegments()). As yet it is not clear whether simply relaxing the epsilon (say, 1.f / 128) is a suitable fix.

Answer: Yes, this is a suitable short-term fix within the design of the current addPartitionLineSegments() algorithm. The existing tolerance is overly conservative. This algorithm is however fundamentally flawed in that a fixed tolerance is applied regardless of the distance between a pair of intercepts. A mathematically and geometrically proper fix would require a complete redesign of this algorithm.

The issue with the creation of superfluous line segments has now been addressed for 1.15

The second issue concerning splitting of overlapped line segments wrt support of maphacks (such as those seen in the attached extrasegs.wad) remains, however.

danij wrote:

The second issue concerning splitting of overlapped line segments wrt support of maphacks (such as those seen in the attached extrasegs.wad) remains, however.

Are you planning to fix the second issue also for 1.15, or was the target version only for the first part? I'm not seeing how this is important enough to hold the 1.15.0 release.

The 1.15 release target was indeed set because of the first part of this issue. As that is now addressed there is no reason to hold up the release because the second part only affects a tiny percentage of user-made maps.

Ok good. For bookkeeping I created a separate issue for the fix so it's included in 1.15.