New GL-Nodes spec (V5)

[andrewj]

Hi, I'm Andrew Apted, author of glBSP.

A new version of the GL-Nodes specification has been prepared and can be found at the following URL:

http://glbsp.sourceforge.net/specs.php

This is a draft version, and I'm looking for feedback, like ways the specs could be improved, mistakes to fix, better ways to do things. Also feel free to ask any questions. I plan to freeze the specs after 3 weeks or so, and update glBSP to generate the new formats.

Summary of the changes:

- V5 GL-Nodes, which removes all the limits. V3 removed the segs and vertex limits, but V5 also prevents overflowing the number of nodes/subsectors. The other versions (V1, V3, V4) are now deprecated, only V2 and V5 need to be supported.

- support for storing information in the GL level marker lump (GL_MAP01 etc). The format is a text file with KEYWORD=VALUE pairs. Currently there are keywords for a timestamp, a level checksum, and the name of the node-builder.

- support for level names longer than 5 letters. When this happens, the GL level marker becomes "GL_LEVEL", and the name of the normal level is stored inside this lump using the "LEVEL" keyword.

- a standard way of creating Extension lumps.

You can email me at: <ajapted@users.sourceforge.net>

[Graf Zahl]

The one thing I am not sure about are the unaligned subsectors. I wonder if it is really necessary to introduce such a potentially hazardous element into the spec. (Of course it all depends how the data is read. It's only a danger if the lump is loaded into memory at once.)

If you are concerned about saving space I think the best place to do it is the end vertex of the segs. After all a subsector is formed by a sorted group of segs so the end vertex is always the same as the starting vertex of the next seg with the exception of the last one. Its end vertex ist the start vertex of the subsector's first seg. But all end vertices can be easily retrieved from the rest of the data.

[andrewj]

Graf Zahl said:

The one thing I am not sure about are the unaligned subsectors. I wonder if it is really necessary to introduce such a potentially hazardous element into the spec. (Of course it all depends how the data is read. It's only a danger if the lump is loaded into memory at once.)

This format is the same as Jack's V4, which (I'm told) has been implemented in 3 or 4 ports already, so while I agree it is not ideal, I doubt there'll be any problems in practice.

[Graf Zahl]

Ajapted said:

This format is the same as Jack's V4, which (I'm told) has been implemented in 3 or 4 ports already, so while I agree it is not ideal, I doubt there'll be any problems in practice.

On x86 systems there won't ever be alignment problems (and which is the main reason why so many software is so hard to port.) Those will only show with CPU's that can't do unaligned accesses.

[andrewj]

Graf Zahl said:

Those will only show with CPU's that can't do unaligned accesses.

I'll be testing it with PowerPC (my main machine is an iBook). What other CPU types may be affected?

[Graf Zahl]

It's not about testing it. With the right code that avoids unaligned access it will never be a real problem. And of course if someone implements this wrong he will get an immediate crash anyway. ;)

Maybe I was just worrying too much when I first saw it. After all ZDoom's compressed node format is completely unaligned but since it is read per element and not as a whole it won't ever become an issue.

[deep]

Graf Zahl said:

It's not about testing it. With the right code that avoids unaligned access it will never be a real problem. And of course if someone implements this wrong he will get an immediate crash anyway. ;)

Exactly. Has nothing to do with "right code" it has to do with the "right" coder instead. There are only a few processors that can't do unaligned access. HP had one for example.

Maybe I was just worrying too much when I first saw it. After all ZDoom's compressed node format is completely unaligned but since it is read per element and not as a whole it won't ever become an issue.

Yeah, I thought that was an odd comment to make. As you note, it's easy to avoid any problem by merely "reading" each part.

This is no different from any data access that addresses the externally saved world and translated to the internal world that the code works with. For example database access code.

The coder should always make the translation efficient for that particular processor. For example the use of byte and short is recommended to be made int for intel machines. Some coders get all freaked out over this as if we are still living in a 640kb world.

[andrewj]

Version 5 of the GL-Nodes specification has been updated. Draft #2 makes the following changes:

1. The GL_SSECT structure has been changed to prevent possible problems with mis-alignment. The 'count' field is now 4-bytes long, as in V3. It was noted that some processors (Alpha, and SH-4 used in the Dreamcast) cannot handle mis-aligned longs, and some processors (x86-64) incur a large speed penalty.

2. The date and time format has been changed slightly to be compatible with the ISO standard. The '-' character is now used as the separator in the date (instead of '/'), and the fraction of a second is respresented with '.' followed by four digits (instead of ':' followed by two digits).

>> Example: 2005-04-30 15:49:40.1234

This is still a draft, and further suggestions and/or corrections are welcome. The full specifications can be found here:

http://glbsp.sourceforge.net/specs.php

Cheers,
Andrew Apted <ajapted@users.sourceforge.net>

[deep]

You do not have to worry about aligment in the stored structure .. period. If that was true a lot of database programs would be in a world of hurt.

This is a PURE CODING issue, not a format issue. What you do is READ each part and CONVERT to a properly aligned internal structure. Actually not all that different from reading older formats and converting short to int (which is what I do for example in R3Dedit).

That was explained in above by both Graf and I. Just reread what we wrote and see how it's done.

Plus this still does not account for regular nodes which HAS TO BE DONE otherwise the whole spec is almost as lacking as V3 in addressing large levels. When a person builds both regular and gl-nodes for a large level, it will go TU for normal nodes.

[andrewj]

deep said:

You do not have to worry about aligment in the stored structure .. period.

There were two programmers who raised this as a potential issue, which is significant. Of course any format can be read if you do it right, but I'm looking to keep it simple and allow the same method that regular Doom allows. This also avoids the complication where some compilers may need a special switch or declaration to enforce the packing to 6 bytes.

I can only think of two arguments for the 6-byte format:

1) smaller file size. Not a real problem: hard drives are big, and inside a ZIP the extra two zero bytes will be compressed away.

2) easing the transition from V4. I don't see any real problem, it's just cut-n-paste of the code and a tweak, like for the different seg format.

You'll need something more compelling than the above two arguments to convince me to change it back.

Plus this still does not account for regular nodes which HAS TO BE DONE otherwise the whole spec is almost as lacking as V3 in addressing large levels. When a person builds both regular and gl-nodes for a large level, it will go TU for normal nodes.

(What is TU ?)

It doesn't have to be done. When a port only needs GL nodes (e.g. EDGE), then it doesn't matter what the normal nodes are, since they are ignored.

But for ports which still use normal nodes, it would be good to do something. You started a discussion here on DW about a year ago, but nothing came of it. I see two possible solutions:

1) Use ZDoom's compressed format. It does remove all limits: segs, nodes/subsectors AND vertices.
2) Use another (uncompressed) format.

That's not something for me to decide, it needs consensus from all the port authors. Number 2 needs a clear proposal from someone. It could even be ZDoom format without the compression and fix the alignment.

[CodeImp]

I dont like it. Nothing wrong with the concept of storing GL nodes in a WAD file, but the level marker is a stupid idea. If you store the GL lumps after the other map lumps that should be sufficient. There is nothing the level marker adds in functionality for the Doom engine which cannot be done in any other way.

The level name is not needed at all when you can store the GL lumps after the map lumps. If you want to share information such as when the level was built or what builder you used, write it in the damn text file, thats what the text file is for. And who cares for a checksum? If my download is damaged I wouldnt even be able to unzip it anyway.

[Graf Zahl]

CodeImp said:

I dont like it. Nothing wrong with the concept of storing GL nodes in a WAD file, but the level marker is a stupid idea. If you store the GL lumps after the other map lumps that should be sufficient. There is nothing the level marker adds in functionality for the Doom engine which cannot be done in any other way.

Yes, it adds one important thing: Being able to store the GL nodes in a separate file and not altering the original. This is important for GL ports.

The level name is not needed at all when you can store the GL lumps after the map lumps. If you want to share information such as when the level was built or what builder you used, write it in the damn text file, thats what the text file is for. And who cares for a checksum? If my download is damaged I wouldnt even be able to unzip it anyway.

Again, that is only a vaild concern if the GL nodes are packaged with the level. For 99% of all levels that's not the case!

[CodeImp]

Then at least make it optional. When I read a map's lumps, as with all others, they are right after each other which makes it easier and with Doom this is the generic way to read all lumps associated with the map. I certainly wouldnt feel good when I would have to write code to hunt down GL node lumps around the WAD file :\

[andrewj]

CodeImp said:

Then at least make it optional. When I read a map's lumps, as with all others, they are right after each other which makes it easier and with Doom this is the generic way to read all lumps associated with the map.

When GL nodes are in the same WAD, then they will be straight after the level lumps. So the GL level marker is straight after BLOCKMAP, or after BEHAVIOUR if it's a Hexen level, or after SCRIPTS if it's a Vavoom-specific level. If you don't handle GWA files, you don't need to do any searching.

The checksum (purely optional) is there to verify that the GL nodes (in a GWA file) match the level data they were built with.

[deep]

Ajapted said:

There were two programmers who raised this as a potential issue,which is significant.

Significant or meaningless? The processors mentioned (Alpha and Dreamcast) are going to be used like .0000001% of users. There are also other processors. Again they aren't used. Designs are done for the majority and current technology, not the minority and obsolete equipment.

Of course any format can be read if you do it right

Exactly - you have to do it right. That's like saying you should know how to code:) But again, for 99.999% of compilers, coders and machines this is brutally simple and requires minimum knowledge. It HAS TO BE THAT WAY since data base design requires this.

If a coder doesn't know how to do this, then he's just out of his league. This isn't introduction to programming

but I'm looking to keep it simple

It IS simple for 99.999 percent of cases. This "issue" is being blown up way beyond the real world. This is a purely academic argument.

I can only think of two arguments for the 6-byte format:

Why waste space when you don't have to? that's the issue here. Pushing the "hard drives are big" argument really has nothing to do with this - it's just a better design. The other is not relevant for obvious reasons.

(What is TU ?)

Tits Up. Imagine dead and lying on it's back :)

It doesn't have to be done. When a port only needs GL nodes (e.g. EDGE), then it doesn't matter what the normal nodes are, since they are ignored.

Ah, but it does have to be done. You assume that a person makes a level just for EDGE and only plays on EDGE. In fact, many levels are much more generic and designed for ANY port. So when that level is played on port Y, it's goes TU on port Y. Not a good thing. What exactly are you going to write for normal nodes when a user builds both and it exceed the stock format??

But for ports which still use normal nodes, it would be good to do something. You started a discussion here on DW about a year ago, but nothing came of it.

Actually something did come of it : V4 which does both extended normal and GL nodes as you know :) But since all the ports were in transition AND I wanted to get a hold of you last year before I discussed this some more, I just put it on hold (and I was modifying port code to see how it all worked). No port was in imminent danger since most of them couldn't support levels past 32k linedefs anyway. V4 is used in the R3D ports.

1) Use ZDoom's compressed format. It does remove all limits: segs, nodes/subsectors AND vertices.

Look closer. It has a 64k vertex limit. I have a test level that exceeds that. Need to ask Fredrick if I can post it since it's one of his levels pasted.

2) Use another (uncompressed) format.

That's counter to your argument above about both simplicity, alignment and drive size. But if it went that way, it should be a modified ZDOOM format so it truly is unlimited and at least conforms to a similar design. Don't need another totally different ZIP thingy. Alignment is a NON ISSUE.

That's not something for me to decide, it needs consensus from all the port authors.

Except for ZDOOM, not a problem. I'm curious why didn't you didn't do that for V3? The V3 spec is why I was trying to contact you last year to get to what is now the "5" spec.

[deep]

Ajapted said:

When GL nodes are in the same WAD, then they will be straight after the level lumps.

Actually that's not always the case. You can blame this on users merging stuff together and on tools that let you do that without warning. I've seen it more than once where the GL nodes are somewhere else - not after the level markers.

Some ports actually LOOK for the GL_MAPxx marker, not by specific offset. IOW, this supports the "anywhere" location in a PWAD.

These ports will have to both modify their code for the new marker name as well as support "anyname" which is what this is all about.

So it's not quite as simple as stated, but not all that hard either.

[Fredrik]

deep said:

It has a 64k vertex limit. I have a test level that exceeds that. Need to ask Fredrick if I can post it since it's one of his levels pasted.

Sure.

[Graf Zahl]

deep said:

Look closer. It has a 64k vertex limit. I have a test level that exceeds that. Need to ask Fredrick if I can post it since it's one of his levels pasted.

Actually, the format itself stores vertex indices as 32 bit. If there are problems they come most likely from an improper implementation in ZDBSP but I have never checked that.

[andrewj]

deep said:
Ajapted said:2) Use another (uncompressed) format
That's counter to your argument above about both simplicity, alignment and drive size. But if it went that way, it should be a modified ZDOOM format so it truly is unlimited and at least conforms to a similar design. Don't need another totally different ZIP thingy. Alignment is a NON ISSUE.

Actually for 2) I was referring to your V4, but I thought you were still developing the extended normal node part of it. Do you have a link to the V4 specs?

So I was saying that the choice is between ZDOOM format and your V4 format. I'm glad to see you'll consider the ZDoom format (possibly modified).

deep said: (Re: GL lumps after level lumps)
Actually that's not always the case. You can blame this on users merging stuff together and on tools that let you do that without warning. I've seen it more than once where the GL nodes are somewhere else - not after the level markers.

Well that's unfortunate, since the specs are clear about this. glBSP does the right thing and writes them straight after the level lumps.

[deep]

Graf Zahl said:

Actually, the format itself stores vertex indices as 32 bit. If there are problems they come most likely from an improper implementation in ZDBSP but I have never checked that.

My mistake in assuming. I didn't look close enough, just knew that large levels past 32k lines/32k verts crash many times and wrongly assumed that the problem was in the format, but it could be basic loading code. ZDBSP appears to work for the huge level but ZDOOM blows up. Can't recall if all levels I tested worked ok for ZDBSP - too long ago - so it might be a ZDBSP issue too.

[deep]

Ajapted said:

Actually for 2) I was referring to your V4, but I thought you were still developing the extended normal node part of it. Do you have a link to the V4 specs?

I already gave them to you. It's not cast in concrete. I did have a working pre-alpha just for my own use since it's a natural byproduct of doing V4 GL nodes. The final depended a bit on getting a way to also verify that normal nodes matched the current level - just something that's always bugged me about both node formats. That's why I proposed those extensions.

In my original discussion last August 2004 or so, I had floating point coordinates, but JK pointed out that fixed_t technically had more precision in the ranges we work with. Plus it suits the port code better.

I was going to go back to those same ports that use the normal format and firm up the final spec after having time to play-test. That's what V5 needs to do - go to the ports. You may have to go to a port's forum (or email) though since posting in a generic area will not get their attention.

My point is that the whole spec is a packaged deal - normal + GL. You can't just ignore normal nodes as you did for both V3 and the proposed V5.

So I was saying that the choice is between ZDOOM format and your V4 format. I'm glad to see you'll consider the ZDoom format (possibly modified).

I never did not consider it :) It was a choice proposed in August to others - and later you when I finally was able to contact you.

Despite the argument that I somehow biased the question, all persons I asked (including you) did not like ZDOOM's complexity and that the storage issue is a non-issue. Both statements were repeated by you.

IOW, it has nothing to do with me and everything to do with other port authors to make adoption fast and easy to do. Taking a disagreement personal (as this was) is the other person's problem, not mine. I really don't care what the format is so long as the other ports agree and that it solves some GL issues as noted.

It has to be an open discussion without getting in a hissy fit. These are the issues started this whole debate: 1) keep it as simple as possible; 2) file size is not important today; 3) it has to address the issue of verifying node "freshness" as well as the GWA naming problem; 4) see #1.

If now you want to backtrack and say complexity doesn't matter and size (stored as an unzipped file - since zipped it's the same) matters then you better ask all the ports again. Who knows, maybe they changed their mind :)

The End

[DaniJ]

I must agree that having a compressed format for this simply isn't necessary. 99% of the time authors will be zipping their levels anyway or the port will be creating the nodes itself at runtime (in which case there is obviously no point in zipping them).

[andrewj]

deep said:

It has to be an open discussion without getting in a hissy fit. These are the issues started this whole debate: 1) keep it as simple as possible; 2) file size is not important today; 3) it has to address the issue of verifying node "freshness" as well as the GWA naming problem; 4) see #1.

Let's consider the ZDoom format for extended nodes in some detail:

1) vertices are 16.16 fixed point: good
2) no limits on segs/nodes/subectors/vertices: good
3) only changes a single lump: good (IMO)
4) compressed: bad
5) seg structures have odd size: bad (IMO)
6) length fields in-between data chunks: not ideal, but live-withable.

Now if (4) and (5) was fixed, I think the format would be acceptable to most port authors. For (3), my reasoning is that a single lump with a bunch of new formats is slightly better (certainly no worse) than each existing lump (SEGS, SUBSECTORS) getting new formats.

The new header of NODES might be "ZND2", followed by four zeros, followed by a four-byte level checksum (same algorithm as in GL-Nodes spec).

I haven't asked Randy about this yet, but what do people here think about this? Jack, would you support this format?

[deep]

Ajapted said:

only changes a single lump: good

BAD in terms of the work required to implement. That is the #2 criticism.

4) compressed: bad

That's the #1 criticism :)

5) seg structures have odd size: bad (IMO)

DOES NOT MATTER. How exactly is that a problem when it clearly has been demonstrated via implemented code to not be an issue in ZDOOM? It's not an opinion, but a fact. I have a feeling this non-issue isn't being understood and are designing to a phantom criteria.

You can make DATA fields in external storage any size and alignment you want. It has absolutely nothing to do with processor alignments and all that stuff. IOW, wasting space like that is not a good design. Even ZDBSP has wasteful space allocation for some parts - interesting only in how the rest is "unaligned" anyway?

So if 4 (not zipped) is "fixed" all you've done is made something simple (original spec) complicated for no good reason. As I went over before, once you establish the node ID in "nodes", the format is established. Leaving the parts in their respective areas (as originally done) makes decoding and debugging much simpler. No deblocking required.

ZDBSP had a somewhat different motivation for doing it the way it was done (size being #1) and #2 being lack of ability to store 16.16 coordinates. IOW the design has a reason for RH and one that I agree with in part.

As I discussed, for REGULAR nodes I'd have to make a similar embedded approach for exactly the same reason: to support 16.16 coordinates (otherwise n/a).

Which still begs the question: what is the spec for regular nodes. This can not be ignored. Z format covers it but not the others so far.

Now if (4) and (5) was fixed, I think the format would be acceptable to most port authors. For (3), my reasoning is that a single lump with a bunch of new formats is slightly better (certainly no worse) than each existing lump (SEGS, SUBSECTORS) getting new formats.

As I explained above, that reasoning doesn't make sense. Either you should literally copy ZDBSP layout and add the GWA extentions in the GL_LEVEL lump (probably possible - haven't really looked - but not the end of the world either since there are other ways to do this) or do it as ORIGINALLY outlined. Otherwise all you are doing is making yet another complicated system - Versus a cut/paste of V2 code

My argument is simple (the same as it's always been): The GOAL is to simplify and unite, not make yet another diversion in the port code.

The original #1 proposal (#2 too even with the added "size") is EASY to implement, satisfies ALL the criteria and has already been discussed with the other port authors.

Z format already exists and will probably still persist since I can't see any advantage over your changes, but instead just see more work with little to show for it.

So I'd rather support ZDBSP's layout given the 2 choices. However, this is rather premature to ask since you really need to contact the other port authors in their forums (including the ones that use regular nodes).

RH originally stated that he'd support "my" format if some port used it. That is now the case. Will he be true to his word and use yours? Either will present an interesting issue once you made the spec complete by finishing the regular node spec.

[Quasar]

Be sure to let me know if this limit-removing BSP format ever gets finished. I really want to widen level size limitations in Eternity. My main issue is this, however -- who's going to write a BSP builder that is of BSP or zennode quality and supports this new format? If the format exists but can't be used, it won't be much help.

[andrewj]

deep said:

Z format already exists and will probably still persist since I can't see any advantage over your changes, but instead just see more work with little to show for it.

Fair enough.

I'm now spent on this topic, and am too lazy and tired to go discuss it on all the other forums. Changing regular nodes is outside the scope of GL-nodes. The GL-node spec deals with the new lumps beginning with "GL_", period.

I will make glBSP generate some kind of extended nodes when the limits overflow. When I update glBSP for V5, I'll choose some format for this purpose, and I'm leaning towards ZDBSP format since I don't see an alternative that "covers it" (as you put it).