[ ZDBSP] UDMF maps keep doing this to me...

[Graf Zahl]

I think I found it but I'm not feeling comfortable fixing this for real. This code:

Code: Select all

			// Splitters that are too close to a vertex are bad.
			frac = InterceptVector (node, *test);
			if (frac < 0.001 || frac > 0.999)
			{
				score -= int(1 / frac);
			}

adds a huge negative bias to the score. For the set in question it effectively invalidates every single potential candidate for use as a splitter.

Since this was added to avoid a crash in another map I did some analysis of that map and found the actual problem that wasn't really fixed by the addition of the code above:

When splitting a seg the node builder does not select an exact vertex but allows some tolerance. In the case of cata.wad it just happens that the selected vertex is one of the ending vertices of the seg to be split. But the code in SplitSeg doesn't even check this case and just goes on assuming everything is fine which results in the generated sub-set being identical to the parent and the node builder being stuck in an endless loop. I think if this is properly taken care of in the splitting code the problem will go away and the fudging code posted above can be removed.

[randi]

For the set in question it effectively invalidates every single potential candidate for use as a splitter.

I think it should still be able to pick something, though. That's why the score is modified rather than rejected outright.

node builder does not select an exact vertex but allows some tolerance

Necessary because of floating point, and because the final vertex is fixed point with only 16 bits of fractional precision.

and the fudging code posted above can be removed

I don't think that's a good idea. If the segment is too short, it won't be well-represented by fixed point coordinates, and if it's especially short, it could even degenerate to a single vertex when converted to fixed point.

Am I right in assuming this only happens with UDMF maps because they allow fractional coordinates? It might be a good idea to restrict the amount of fractional precision allowed for them.

[Graf Zahl]

For the set in question it effectively invalidates every single potential candidate for use as a splitter.

I think it should still be able to pick something, though. That's why the score is modified rather than rejected outright.

Sure. But it is modified in a way that invalidates every single candidate. If you look at the list everything got a negative score.

node builder does not select an exact vertex but allows some tolerance

Necessary because of floating point, and because the final vertex is fixed point with only 16 bits of fractional precision.

That part in itself is ok. But with cata.wad what happens if the fudging code is removed (or the score altered to always be positive) the splitter vertex would not be the real ending vertex but it's close enough to get mapped to it (The distance is 5/65536 map units.) That also wouldn't be a problem if the code that divides a set of segs would deal with such a case. But it doesn't. It just goes along assuming that everything can be properly divided.
Instead the code should check if the seg splitting is successful and not just assume that it will always succeed. It can deal with an undividable set after this check and not preemptively mess around with the score to make it less likely. The UDMF map clearly shows that that doesn't work.

and the fudging code posted above can be removed

I don't think that's a good idea. If the segment is too short, it won't be well-represented by fixed point coordinates, and if it's especially short, it could even degenerate to a single vertex when converted to fixed point.

Am I right in assuming this only happens with UDMF maps because they allow fractional coordinates? It might be a good idea to restrict the amount of fractional precision allowed for them.[/quote]

Only partially. In this map some things come together to create this mess. First, due to the high tendency to avoid splits the map gets reduced to a section that only contains high precision vertices and second, this section contains lines which are almost colinear but not quite. As a result every single splitter candidate comes too close to another vertex. In the end the precision of the vertices was not too high but not high enough so fudging around here will only create more problems.

I think if you fix the splitting code to check its results and deal with failure cases properly the problems will go away.

[Graf Zahl]

This is the real problem. It's in the 'default' case of SplitSegs:

Code: Select all

			frac = InterceptVector (node, *seg);
			newvert.x = Vertices[seg->v1].x;
			newvert.y = Vertices[seg->v1].y;
			newvert.x += fixed_t(frac * double(Vertices[seg->v2].x - newvert.x));
			newvert.y += fixed_t(frac * double(Vertices[seg->v2].y - newvert.y));
			vertnum = VertexMap->SelectVertexClose (newvert); //  --------------> this will pick the starting vertex of the seg to be split.

And now the code just goes on without ever checking the vertex so the seg that should be split ends up completely on one side of the splitter with the other side having just an empty point. But nowhere in here is a check for this and if everything from this set ends up on the same side the child is identical to its parent and the node builder ends up in an endless loop:

Code: Select all

			seg2 = SplitSeg (set, vertnum, sidev1);

			Segs[seg2].next = outset0;
			outset0 = seg2;
			Segs[set].next = outset1;
			outset1 = set;

This is the reason why cata.wad crashes with a stack overflow if the fudging is not done. With the fudging this set will be determined not to be splittable any further but this can also be done by checking the results here and acting accordingly if the situation as described above happens. Then the scoring can be redesigned to give such segs a low score but still make it positive. It would decrease the likelihood of them being picked as splitter but it wouldn't outright prevent it. I think with that done both cata.wad and this demo map will build proper nodes.

[Graf Zahl]

I attempted a fix myself.

Randy, can you please verify?

The current ZDoom revision builds working nodes for both the demo map and cata.wad but for cata.wad it produces one malformed subsector that has no valid sidedef reference. I had to add some additional checking code to P_GroupLines to address this case. With this in place it also loads the GL nodes without problems.

I hope it's all ok now but I can't be sure that I didn't overlook something.

[randi]

I think you are on the right track. However, I believe the proper fix is to still penalize splitters that come near vertices while outright rejecting ones that cannot possibly produce a unique vertex when splitting a seg. Doing it like that produces working nodes for both the attached map4.wad as well as cata.wad without producing nodes that violate the GL nodes spec.

[Graf Zahl]

Since the latest revision builds proper nodes for this and cata.wad I think this can be closed now.