Subsectors are not convex. How to draw them easily?

[entryway]

Is there an easy way to draw a subsector in OpenGL without tesselation? GL_TRIANGLE_FAN works fine with GL nodes, because in that case subsectors are convex. No easy way for normal nodes?

I asked this question in PM, but andrewj suggested me to ask it in public and he'll answer.

[CodeImp]

Subsectors should be convex. If not, that is a nodebuilder failure. I think GL nodes are sorted so that they are in clockwise order which just makes it easier to create a triangle fan.

Given that a subsector is convex, you can take any point and segment and make a triangle out of that without any other segment intersecting that area. You could make a triangle list from any given point and all subsector segments, but it would be less efficient than a triangle fan.

EDIT: Wait, not all segments are included in subsectors because Doom doesn't need them, only those along linedefs. That is what GL nodes added: segments for the entire subsector. It is possible to find all segments of a subsector without GL nodes, but it takes some work (Doom Builder 1 and some sourceports do this).

[entryway]

CodeImp said:

Doom Builder 1 and some sourceports do this

Can't find db1 sources on doombuilder.com

[CodeImp]

entryway said:

Can't find db1 sources on doombuilder.com

No? I think it is on this page, below the Doom Builder 2 SVN link ;)

[Quasar]

entryway said:

Can't find db1 sources on doombuilder.com

I think the general approach is to look for node lines that are coincident to any of the real segs' vertices, starting from the lowest node line on the tree and going back up. Then you can generate "minisegs" along the portion(s) of the node lines to close the subsector. I am probably leaving out some important details of course...

[entryway]

Looks like R_CreateFloorsAndCeilings from DoomsDay does this work.

[CodeImp]

The way DB 1 does it (I think I took this idea from Doomsday at that time) is by making a huge 65535 x 65535 square and start splitting it up with all the splits along the way to the subsector you need. With every split, the geometry on the side at which the subsector is (the side on which you continue recursively) is kept. Ofcourse this could be optimized by doing a breadth-first recursion and keeping a copy of the geometry for both sides on every split and generate the needed geometry for all subsectors that way.

[entryway]

Ok. All needed code already was in glboom.

[DaniJ]

Yeah, the prboom source borrows various stuff from Doomsday (tessellator, angle-clipper and other bits). I was wondering why you were asking :)

CodeImp said:

Subsectors should be convex. If not, that is a nodebuilder failure. I think GL nodes are sorted so that they are in clockwise order which just makes it easier to create a triangle fan.

FYI not all nodebuilders guarantee convexity (both migrant segs and degenerate subsectors can result) and many do not sort the segs into clockwise order. I certainly wouldn't rely on them being sorted put it that way ;)

[andrewj]

The following approach is what I'd try today if I were to make a OpenGL renderer from scratch:

The space covered by a subsector is just the intersection of all the halfplanes formed by the partition lines as you traverse the BSP tree from the root down to that particular subsector.

So you traverse the BSP tree and keep a list of all the partition lines visited, and when you reach a subsector you can then create the subsector polygon from that list. In other words, the list contains all the partitions from the parent node and its parent node (etc) upto the root.

The first caveat is that normal DOOM subsectors near the edge of the map are unbounded (the R_PointInSubsector always gives you a subsector, even when you are far off the map). Fixing that is easy, just add four extra halfplanes to the list, which correspond to the bounding box of the map.

The second caveat is that polygons generated this way will extend into void space. The OpenGL Z buffer will ensure correct rendering but there could be a lot more drawn than necessary, and hence it might be a large performance hit.

Trying to make the polygons smaller (by checking the segs) does NOT work in certain situations. Hmmmm... what may help is using the bounding box of the sector containing the subsector (instead of bbox of map), but that may have its own problems (like when a map contains self-referencing linedefs).

[DaniJ]

That only works if you have a guarantee of convexity from your nodes and no degenerate subsectors. Closing open leaves in that instance is trivial.

The main problem (as you noted) are self-referencing constructs which imo should have been extracted from the world prior to nodebuilding (except in cases where such a linedef shares an edge with 'normal' geometry, in which case you have more work to do).

[Gez]

You can always rebuild GL nodes during map load. That way, you can be sure to trust them, and if they're still wrong it's a bug you can (and need to) fix yourself.

You can even do like GZDoom does and keep the map's own nodes for the simulation, while still using the newly-built GL nodes for the renderer.

Both glBSP and ZDBSP are GPLv2.

[entryway]

I have small holes sometimes (normal nodes)

[Gez]

Is that a textured automap in the making?

[Graf Zahl]

You'll see the same effects in the game when rendering with normal nodes. I think it's caused by the node lines being full fixed point precision but the vertices generated by the node builder only being integer. Somehow these don't seem to match up.

This is one of the reasons why I never considered using normal nodes for the textured automap, btw. I have seen too many glitches with this algorithm in the past.

Gez said:

Is that a textured automap in the making?

Well, now that ZDoom got one, everybody needs it, right...? :P

[CodeImp]

Doom Builder 2 was first :P but I suppose map editors don't count in this fight.



By the way, Doom Builder 2 uses a more complex algorithm that creates triangles from complete sectors. But it does not work with software-rendering hacks such as deep water and it also does not work with broken sectors (such as unclosed sectors, which happens in some original maps). It does not suffer from map data inaccuracies though.

[4mer]

What Graf said is right.
There is a node partition line and a split seg that runs along it.
glBoom+ carves space to create flats using partition lines, then later using the segs.
(As noted by andrewj this could be slightly improved by starting with the map extents, glBoom+ starts with the largest square possible).
In this case they don't tie up due to the loss of precision introduced by the new vertex created at the seg split.

[Gez]

CodeImp said:

Doom Builder 2 was first :P but I suppose map editors don't count in this fight.

Shadowcaster was first! Though most people would rather associate it with DN3D. But as far as Doom ports go, ZDoomGL was the first, though it was glitchy.

[4mer]

How about using the line the seg runs along to clip the space instead of the seg?

[entryway]

Gez said:

Is that a textured automap in the making?

Yes, I did it today. Did not bother about software renderer though.

CodeImp said:

Doom Builder 2 was first :P but I suppose map editors don't count in this fight.

By the way, Doom Builder 2 uses a more complex algorithm that creates triangles from complete sectors.

I do not know what you mean with "Doom Builder 2 was first" and "more complex algorithm", but GLBoom has it about 10 years. It also creates triangles from complete sectors. GLBoom creates triangles for subsectors only if sector is not closed. I have no holes if I draw textured automap with sectors instead of subsectors (but I need subsectors for automap)

http://prboom-plus.sourceforge.net/glboom.png

Graf Zahl said:

Well, now that ZDoom got one, everybody needs it, right...? :P

Yeah, I noticed it yesterday and liked it.

[CodeImp]

entryway said:

I do not know what you mean with "Doom Builder 2 was first" and "more complex algorithm", but glboom has it about 10 years.

I don't know if I should spend time and energy to explain this, but the first thing is called intended pun and was in response to Graf mentioning ZDoom. Like I care who was first. It is more complex than making triangles from subsectors, because it deals with a bunch of problems you don't have to deal with when working with convex shapes.

[entryway]

Graf Zahl said:

Well, now that ZDoom got one, everybody needs it, right...? :P

I have noticed your implementation is unprecise. I have 5-10mm vibration of textures during rotation of automap at max zoom with GZDoom. You should use precise version of AM_rotatePoint(). Something like that:

static void AM_rotate_f(float *x, float *y, angle_t a)
{
  float rot = (float)a / (float)(1u << 31) * (float)M_PI;
  float sinrot = (float)sin(rot);
  float cosrot = (float)cos(rot);
  
  float tmpx = ((*x) * cosrot) - ((*y) * sinrot);
  *y = ((*x) * sinrot) + ((*y) * cosrot);
  *x = tmpx;
}

void AM_rotatePoint_f(float *x, float *y)
{
  float pivotx = (float)m_x + (float)m_w/2.0f;
  float pivoty = (float)m_y + (float)m_h/2.0f;
  *x -= pivotx;
  *y -= pivoty;
  AM_rotate_f(x, y, ANG90 - plr->mo->angle);
  *x += pivotx;
  *y += pivoty;
}