ZDoom

by **Graf Zahl** » Sun Jan 03, 2010 1:58 am

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

by **randi** » Sat Jan 02, 2010 5:26 pm

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.

by **Graf Zahl** » Fri Jan 01, 2010 4:20 am

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.

by **Graf Zahl** » Fri Dec 25, 2009 5:10 pm

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.

by **Graf Zahl** » Fri Dec 25, 2009 4:13 pm

randy wrote:
Graf Zahl wrote: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.

randy wrote:
Graf Zahl wrote: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.

Graf Zahl wrote: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.

by **randi** » Fri Dec 25, 2009 3:25 pm

Graf Zahl wrote: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.

Graf Zahl wrote: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.

Graf Zahl wrote: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.

by **Graf Zahl** » Fri Dec 25, 2009 9:38 am

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.

by **Graf Zahl** » Fri Dec 25, 2009 7:40 am

This seems to be caused by the SplitCost setting. If it's at 8 the nodes for this map are broken.
However, if I set it to 4 they build correctly.

But what I don't know is how this can be handled dynamically on a case-by-case basis if some map does not build anymore with the higher setting.

At least it's good to know that it's not a floating point precision issue because then we would have had a real problem.

by **Graf Zahl** » Fri Dec 25, 2009 7:16 am

I activated the internal node builder's debug output and here's where it seems to lose it:

Code: Select all

Seg   186, ld 116 ( -704,-1248)-( -704,-1223) scores 0
Seg   241, ld 158 ( -704,-1248)-( -720,-1259) scores -32454
Seg   256, ld 172 ( -752,-1280)-( -757,-1275) scores -293753
Seg   341, ld 235 ( -976,-1328)-( -839,-1299) scores 0
Seg   343, ld 236 ( -839,-1299)-( -752,-1280) scores 0
Seg   344, ld 237 ( -839,-1299)-( -844,-1296) scores -458298
Seg   346, ld 238 ( -976,-1328)-( -844,-1296) scores -45700
Seg   348, ld 239 ( -844,-1296)-( -757,-1275) scores -113682
Seg   350, ld 240 ( -757,-1275)-( -736,-1270) scores -1109
Seg   352, ld 241 ( -844,-1296)-( -848,-1294) scores -1262964
Seg   354, ld 242 ( -736,-1270)-( -752,-1280) scores -21715
Seg   355, ld 243 ( -757,-1275)-( -762,-1270) scores -309330
Seg   362, ld 247 ( -976,-1328)-( -848,-1294) scores -28216
Seg   364, ld 248 ( -848,-1294)-( -762,-1270) scores -67784
Seg   366, ld 249 ( -762,-1270)-( -720,-1259) scores -1171
Seg   369, ld 251 ( -848,-1294)-( -852,-1292) scores -896411
Seg   371, ld 252 ( -762,-1270)-( -765,-1266) scores -99045
Seg   386, ld 260 ( -976,-1328)-( -852,-1292) scores -18213
Seg   388, ld 261 ( -852,-1292)-( -765,-1266) scores -30403
Seg   390, ld 262 ( -765,-1266)-( -704,-1248) scores -7082
Seg   392, ld 263 ( -852,-1292)-( -864,-1285) scores -358301
Seg   394, ld 264 ( -765,-1266)-( -779,-1252) scores -393698
Seg   408, ld 271 ( -976,-1328)-( -864,-1285) scores -256353
Seg   410, ld 272 ( -864,-1285)-( -779,-1252) scores -235772
Seg   421, ld 278 ( -864,-1285)-( -881,-1276) scores -709541
Seg   423, ld 279 ( -779,-1252)-( -798,-1230) scores -354531
Seg   437, ld 286 ( -976,-1328)-( -881,-1276) scores 0
Seg   441, ld 288 ( -798,-1230)-( -704,-1177) scores 0
set 186, step 0, nosplit 1 has no good splitter (1)
Seg   186, ld 116 ( -704,-1248)-( -704,-1223) scores 0
Seg   241, ld 158 ( -704,-1248)-( -720,-1259) scores -32454
Seg   256, ld 172 ( -752,-1280)-( -757,-1275) scores -293753
Seg   341, ld 235 ( -976,-1328)-( -839,-1299) scores 0
Seg   343, ld 236 ( -839,-1299)-( -752,-1280) scores 0
Seg   344, ld 237 ( -839,-1299)-( -844,-1296) scores -458298
Seg   346, ld 238 ( -976,-1328)-( -844,-1296) scores -45700
Seg   348, ld 239 ( -844,-1296)-( -757,-1275) scores -113682
Seg   350, ld 240 ( -757,-1275)-( -736,-1270) scores -1109
Seg   352, ld 241 ( -844,-1296)-( -848,-1294) scores -1262964
Seg   354, ld 242 ( -736,-1270)-( -752,-1280) scores -21715
Seg   355, ld 243 ( -757,-1275)-( -762,-1270) scores -309330
Seg   362, ld 247 ( -976,-1328)-( -848,-1294) scores -28216
Seg   364, ld 248 ( -848,-1294)-( -762,-1270) scores -67784
Seg   366, ld 249 ( -762,-1270)-( -720,-1259) scores -1171
Seg   369, ld 251 ( -848,-1294)-( -852,-1292) scores -896411
Seg   371, ld 252 ( -762,-1270)-( -765,-1266) scores -99045
Seg   386, ld 260 ( -976,-1328)-( -852,-1292) scores -18213
Seg   388, ld 261 ( -852,-1292)-( -765,-1266) scores -30403
Seg   390, ld 262 ( -765,-1266)-( -704,-1248) scores -7082
Seg   392, ld 263 ( -852,-1292)-( -864,-1285) scores -358301
Seg   394, ld 264 ( -765,-1266)-( -779,-1252) scores -393698
Seg   408, ld 271 ( -976,-1328)-( -864,-1285) scores -256353
Seg   410, ld 272 ( -864,-1285)-( -779,-1252) scores -235772
Seg   421, ld 278 ( -864,-1285)-( -881,-1276) scores -709541
Seg   423, ld 279 ( -779,-1252)-( -798,-1230) scores -354531
Seg   437, ld 286 ( -976,-1328)-( -881,-1276) scores 0
Seg   441, ld 288 ( -798,-1230)-( -704,-1177) scores 0
set 186, step 0, nosplit 0 has no good splitter (1)
 - seg 186(-704,-1223)-(-704,-1248) line 116 front 74305984 back 74306356
 - seg 241(-704,-1248)-(-720,-1259) line 158 front 74303752 back 0
Need to synthesize a splitter for set 186 on seg 241
Subsector from set 186

After that last line this set is never being looked at again even though it still contains lots of lines that most definitely do not form a convex region.

by **Kappes Buur** » Mon Oct 05, 2009 6:14 pm

Ceeb wrote:Well, I did away with the stairs and made it a regular hallway, kept the light diffusion, now it works.

Thanks for trying to help, y'all.

You could have kept the stairs. Just get rid of unnecessary detail in the lighting aspect and all is fine.

Spoiler:

Especially, when the detail isn't really visible

Spoiler:

It's the tiny, intricate sectors that screw things up, ... most of the time.
Sonnyboy was on the right track.

by **Graf Zahl** » Sat Oct 03, 2009 5:23 am

Project Dark Fox wrote: I think you broke ZDBSP dude.

That would be my guess, too.

by **Enjay** » Sat Oct 03, 2009 4:01 am

I'm not to familiar with DB2 error checking and so on but, yeah, it certainly gave the area a clean bill of health. I then copied the map to ZdoomHexen format and the problem vanished. I was also able to check the map using deePsea in that format and although the map did have errors, none of them should obviously have been affecting that particular area.

Given that the area worked in ZdoomHexen format and not in UDMF, it might well be a bug either with UDMF or Zdoom's implementation of it so I think it would be worth flagging up for checking by Graf/Randy.

by **Ceeb** » Fri Oct 02, 2009 7:41 pm

Well, I did away with the stairs and made it a regular hallway, kept the light diffusion, now it works.

Thanks for trying to help, y'all.

by **Sonnyboy** » Fri Oct 02, 2009 6:46 pm

Perhaps not...

I was able to get rid of a lot of it by deleting some unneccesary vertices.
Curious...

by **Ceeb** » Fri Oct 02, 2009 6:37 pm

I guess I just need to tone down the light diffusion a bit.

ZDoom

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

Post a reply

Expand view Topic review: [ ZDBSP] UDMF maps keep doing this to me...

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

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

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

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

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

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

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

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

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

Re: UDMF maps keep doing this to me...

Re: UDMF maps keep doing this to me...

Re: UDMF maps keep doing this to me...

Re: UDMF maps keep doing this to me...

Re: UDMF maps keep doing this to me...

Re: UDMF maps keep doing this to me...