Project

General

Profile

Bug #1591

[BSP] Fully overlapped map geometry is not always split

Added by skyjake about 8 years ago. Updated about 2 years ago.

Status:
Progressed
Priority:
Low
Assignee:
-
Category:
Defect
Target version:
Start date:
2013-10-18
% Done:

50%

Tags:

Description

Fully overlapped map geometry is not always split when building the BSP (partial overlaps are split correctly).

extrasegs.wad (2.57 KB) extrasegs.wad danij, 2014-10-27 15:25

Related issues

Copied to Bug #2046: [BSP] Space partitioning results in superfluous line segmentsClosed2015-05-12

Associated revisions

Revision 6c6241f4 (diff)
Added by danij about 7 years ago

Fixed|World|bsp::Partitioner: Space partitioning results in superfluous line segments

An overly conservative epsilon used when searching for existing line
segments in the map would sometimes lead to the creation of additional
line segments unnecessarily.

IssueID #1591

History

#1 Updated by skyjake about 8 years ago

  • Description updated (diff)

#2 Updated by skyjake about 8 years ago

  • Category set to Defect

#3 Updated by skyjake about 8 years ago

  • Target version changed from 1.12.1 to 1.13

#4 Updated by skyjake almost 8 years ago

  • Target version changed from 1.13 to 1.14

#5 Updated by danij over 7 years ago

  • Target version changed from 1.14 to 1.15

#6 Updated by danij about 7 years ago

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.

#7 Updated by danij about 7 years ago

  • Status changed from New to In Progress

#8 Updated by danij about 7 years ago

#9 Updated by danij about 7 years ago

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.

#10 Updated by skyjake over 6 years ago

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.

#11 Updated by danij over 6 years ago

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.

#12 Updated by danij over 6 years ago

  • Target version deleted (1.15)

#13 Updated by skyjake over 6 years ago

  • Copied to Bug #2046: [BSP] Space partitioning results in superfluous line segments added

#14 Updated by skyjake over 6 years ago

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

#15 Updated by skyjake over 5 years ago

  • Status changed from In Progress to Progressed

#16 Updated by skyjake over 4 years ago

  • Target version set to Modding

#17 Updated by skyjake about 2 years ago

  • Assignee deleted (danij)

#18 Updated by skyjake about 2 years ago

  • Priority changed from Normal to Low

Also available in: Atom PDF