Quesiton about the NODES lump (and subsectors)

[Watermelon]

I'm trying to understand how to find the sides on a subsector using information from segs/ssectors/nodes.


1) I'm unsure what some of the node values are with respect to how it can tell me the line splitting info. In vanilla doom we have:

0 	2 	Partition line x coordinate
2 	2 	Partition line y coordinate
4 	2 	Change in x to end of partition line
6 	2 	Change in y to end of partition line 

from ( http://doomwiki.org/wiki/Node )

What does the partition line x/y coordinate tell me? I thought it has to be a line that slices the remaining areas? Unless the latter two pieces are dx/dy from that reference point and I can go from there.



2) When trying to construct subsectors, should each node split result in a 'line' I should add, and use that in the final construction?



3) I'm also trying to understand the image for the node splitting. When the level is cut at a diagonal:
http://img3.wikia.nocookie.net/__cb20051107002221/doom/images/f/fb/FirstLeftNodeE1M1.png
Does the node builder or something in the doom engine store all the lines/segs as its rendering above and below the line?




4) Fixed point inconsistencies: Should there be some kind of range of error I allow if a cut is done at an angle that cuts it into what should be a decimal number rather than a whole number?
If so, is a good buffer ~1.0? (or 65535 / 65536)?



I'm doing my best to attempt to understand it, sorry if I'm a bit of a newbie at this.

[Foxpup]

Watermelon said:

What does the partition line x/y coordinate tell me?

It tells you the start of the line. In geometry, a line is defined by two points, and extends infinitely in each direction.

Watermelon said:

2) When trying to construct subsectors, should each node split result in a 'line' I should add, and use that in the final construction?

No. Subsectors are constructed from segs, which in turn are constructed from linedefs which may or may not have been split by partition lines. Lines that are not part of linedefs do not become segs, resulting in an open subsector (which is not a problem as long as its neighbouring subsector is part of the same sector, which it should be unless the map geometry is invalid).

Consider the following sector, which has been divided by a partition line:

   f   a
  +--+------+
  |   .     |     +  vertex
e |    .    | b   -| linedef
  |     .   |     .. partition line 
  +------+--+
    d      c

Segs a and f are part of the same linedef, as are segs c and d. The two subsectors are constructed from segs abc, and segs def. The partition line in not part of either subsector.

Watermelon said:

3) I'm also trying to understand the image for the node splitting. When the level is cut at a diagonal:
http://img3.wikia.nocookie.net/__cb20051107002221/doom/images/f/fb/FirstLeftNodeE1M1.png
Does the node builder or something in the doom engine store all the lines/segs as its rendering above and below the line?

I don't understand the question.

Watermelon said:

4) Fixed point inconsistencies: Should there be some kind of range of error I allow if a cut is done at an angle that cuts it into what should be a decimal number rather than a whole number?
If so, is a good buffer ~1.0? (or 65535 / 65536)?

Be aware that there will be cases (especially if the map contains lines at many different angles) where there is always an unacceptable rounding error. Node builders that take this into consideration do so by selecting the solution with the lowest error, rather than eliminating solutions that don't meet an arbitrary level of accuracy, since there may be no solutions left.

I don't see how any of this is really relevant to the problem of "finding the sides on a subsector". The SSECTORS lump tells you which segs compose each subsector, and the SEGS lump tells you which vertices mark the start and end of each seg. The coordinates of the vertices are in the VERTEXES lump, obviously. Isn't that what you're looking for?

[Watermelon]

I don't see how any of this is really relevant to the problem of "finding the sides on a subsector". The SSECTORS lump tells you which segs compose each subsector, and the SEGS lump tells you which vertices mark the start and end of each seg. The coordinates of the vertices are in the VERTEXES lump, obviously. Isn't that what you're looking for?

Since this may possibly solve my question without me worrying about the nodes and all:

If I want to find a subsectors bounds (all the sides), I would iterate through SSECTORS by extracting the number of segs used, and then the segs that make it up, and piece them together head to tail?

I might be completely wrong here, but I thought (using your diagram for convenience) that line FC is not provided and has to be found out using the NODES lump by cutting up sectors. If it is provided, then problem solved because I can iterate through SSECTORS and all is well, if not... then how do you do it without using NODES?

[Foxpup]

Watermelon said:

then how do you do it without using NODES?

Just assume that if any seg has a start vertex that is not the same as the previous seg's end vertex, that a line can be drawn between those two vertices to close the subsector. This isn't strictly correct, but strictly speaking a subsector isn't bound by its segs in the first place.

[Watermelon]

Just assume that if any seg has a start vertex that is not the same as the previous seg's end vertex, that a line can be drawn between those two vertices to close the subsector. This isn't strictly correct, but strictly speaking a subsector isn't bound by its segs in the first place.

I'm confused now because you said a subsector isn't bound by its segs, but in your first post you said subsectors are constructed from segs. Also on the doom wiki it says "It is not uncommon for a subsector to consist of a single seg.", which means either another one has to be inferred from somewhere to make a triangle, or there has to be some other way of getting the partition line to get the entire subsector. Don't I therefore need to traverse the NODES lump to know what the partitioning line is? If not, then I should be able to stitch together segs that aren't head to tail without problem. But if this was the case, then this is impossible if the doom wiki is correct stating that a subsector can consist of a single seg.


Maybe I wasn't clear in what I said in the past: My goal (using your example) is to outline all the subsectors (so I'd want to say subsector 1 is made up of segs ABC + (partition line here), and subsector 2 is made up of DEF + (partition line here).


I need to explicitly know how they are joined since I'd like to render the flat inside the subsector in a 2D viewer.

[Foxpup]

Watermelon said:

I'm confused now because you said a subsector isn't bound by its segs, but in your first post you said subsectors are constructed from segs.

Well, the SSECTORS lump contains a list of segs, but it's perhaps better to say the segs are inside the subsector than that they compose it. To determine which subsector a given point is in*, and whether a subsector (and hence its segs) are visible at all, only the nodes are used.

*Note that points that are completely outside the map are still within one subsector or another.

Watermelon said:

Also on the doom wiki it says "It is not uncommon for a subsector to consist of a single seg.", which means either another one has to be inferred from somewhere to make a triangle, or there has to be some other way of getting the partition line to get the entire subsector.

When creating a new line to close a subsector, the back side of that line will close another subsector. Which subsector can be determined by taking the segs that connect to its vertices and sorting by angle.

Watermelon said:

I need to explicitly know how they are joined since I'd like to render the flat inside the subsector in a 2D viewer.

The technically correct way to do this is to just walk the nodes tree doing a floodfill at each partition line, though if you actually do this you'll immediately see what I mean when I say subsectors aren't bound by their segs. ;)

[DaniJ]

Foxpup said:

Watermelon said:

I need to explicitly know how they are joined since I'd like to render the flat inside the subsector in a 2D viewer.

The technically correct way to do this is to just walk the nodes tree doing a floodfill at each partition line, though if you actually do this you'll immediately see what I mean when I say subsectors aren't bound by their segs. ;)

And that is one of the reasons why this data is not suitable for what Watermelon is trying to do.

The node data generated by node builders for use with the software renderer is specifically intended for use by the vanilla software renderer's flood-fill algorithm for flat drawing.

I can tell you categorically that if the intention is to interpret the node data into a well-formed set of 2D polygons then you'll be entering a whole world of hurt trying to rationalize this. Do yourself a favour and use the data generated by a GL node builder instead. This is the reason why GL node builders exist in the first place.

[Graf Zahl]

Not only that - the nodes do not even have sufficient precision. You can see this in all its glorious ugliness, if you try to play a map with open sectors in PrBoom's GL renderer. In such a case it tries to create polygon data from the entirely insufficient nodes, resulting in a lot of gaps.