Terrain quad rendering uses unspecified triangulation

[Philip Taylor]

The terrain renderer draws non-planar GL_QUADS. The OpenGL spec just says

For a polygon with more than three edges, we require only that a convex combination of the values of the datum at the polygon's vertices can be used to obtain the value assigned to each fragment produced by the rasterization algorithm.

which in practice seems to result in the quad being triangulated along an arbitrary diagonal. Since there's no way to know exactly what's going to happen, and particularly since what happens isn't very good, we need to split the quads into triangles ourselves.

It is presumably sensible to split each quad along the diagonal that minimises the angle between the two triangles.

[Philip Taylor]

When we have well-defined triangulation here, we should update CTerrain::GetExactGroundLevel to calculate height based on the triangulation instead of bilinear interpolation.

[Xin]

Initial patch of terrain triangulation for testing

[Xin]

I wasn't sure what you meant by needing to triangulate the quads ourselves so what I've done is modified BuildIndices() in CPatchRData to build triangles instead of quads and made relevant changes to RenderBase() and RenderStreams(). I've left BuildBlends() alone for now because it's really long and looks like it'll take some work to get it to use the same triangulations as BuildIndices() did (I also have no idea how it works right now). Consequently, I've disabled the blend pass in TerrainRenderer because it looks really ugly when it attempts to blend a quad onto a tri and because it's easier to verify that triangulation is working without the blend pass.

For some reason, I couldn't get triangle strips to work; I kept getting missing triangles (or maybe their normals were facing away from the camera) and stretched triangles, as if it was using vertices from outside of the quad to make triangles. If someone could figure out how to make triangle strips work, that'd save a bit of memory and rendering time.

Finally, wouldn't it be better to have the modelers triangulate the terrain mesh? That way they can ensure that the terrain looks like it's supposed to.

[Erik Johansson]

I'll let the programmers reply to the more technical things, but I believe I can answer the last question you posted. (At least as long as you mean "people who create 3D models" when you say modelers - as opposed to some kind of automated OpenGL thing :) )

The terrain isn't modeled in the same sense as units/buildings/etc, it's either created via a random map script that automatically creates the terrain or with the help of Atlas (the scenario editor, see ​http://trac.wildfiregames.com/wiki/Atlas_User%2527s_Guide for usage info) that allows users to interactively shape the terrain. It's never directly created by a modeler however. So things need to be automated. I'm sure Philip can explain in more technical terms/details though.

[Xin]

Oh, I see. In that case, it makes more sense why triangulation is being done at run-time for the terrain.

Also I forgot to mention, I removed the ShadowMapIndices stuff as well. It seems to be left-over from a previous shadow mapping implementation because the current shadow mapping stuff doesn't seem to rely on those indices at all. Unless it's there for some other purpose I can't discern?

[Philip Taylor]

Building triangles instead of quads is what I meant, so this looks like a good start :-)

I think the normal1.Normalize(); calls shouldn't be necessary - all the triangle edge vectors have the same length so they'll cancel out without the expensive normalizing.

BuildBlends: Hmm, yeah, that's a bit tricky (and also sometimes buggy). I don't understand it enough to know how to fix it.

After drawing some confusing diagrams, I'm not sure whether triangle strips can possibly work in general, even just for a single row of tiles - switching the direction of triangulation seems to be impossible. I think we definitely want to be able to switch the direction - if you make e.g. a narrow tall spire in the terrain then it's all ugly and asymmetric in the old system, but nice and consistent after this patch. Unless there's some trick I'm missing, I guess we'll have to stick with indexed triangles (which isn't so bad really).

ShadowMapIndices looks like a remnant of the old different shadow system from many years ago which no longer exists, so it's good to clean that up.

It could be possible to let scenario designers control the triangulation but that seems to be a lot of complexity (providing UI, saving/loading in map files, documenting, etc) and a lot of effort for designers and not really that useful. And we need an automatic system for random map scripts, and for dynamic in-game modification of terrain (e.g. flattening underneath buildings), so it's probably best to just do it all automatically.

[Xin]

Great!

I'll remove those normalize calls. It hadn't occurred to me that all the terrain quads were of uniform size.

I'll look at the BuildBlends some more, see if I can figure it out. It doesn't help that I don't have any understanding of texturing and what not, but then again, that's why I'm here :)

I was thinking of using triangle strips instead of the quads, not to have a triangle strip for an entire row, but I might be misunderstanding how OpenGL renders triangle strips. Does a glBegin/glEnd pair segregate the drawing of primitives? I was thinking that a glBegin/glEnd pair would tell the GL that it's finished drawing this triangle strip and subsequent glBegin/glEnd will start off a new triangle strip so that it won't attempt to connect previous triangle strips to each other. Is that wrong? (I haven't had time to go through the entirety of the OpenGL spec yet and what's also confusing is that since the engine has been in development for like 9 years, OpenGL has gone through several versions so I don't know what version of OpenGL we're targeting. For instance, GL_QUADS and glDrawElements has been deprecated since I think OpenGL 3.0, which is almost two years old now.)

Ok, I'll remove the rest of the references then.

Yea, that makes sense.

[Philip Taylor]

Oh, hmm, I suppose they're not actually of uniform size - they are in 2D but not in 3D. So it's not as simple as I thought...

But: If you compute all the normal vectors from the edges of the tile (not the diagonals - e.g. don't use v3-v1 or v4-v2), and don't call Normalize, then (unless I'm mistaken) you'll get the same vector directions as before, with lengths such that each dot product will give you the cos multiplied by the same four tile edge lengths, so they cancel out and it works okay. Hopefully. (Should be possibly to verify it from the maths :-) )

glBegin/glEnd does start a new independent triangle strip, but they're an immediate-mode API and quite inefficient and we shouldn't be using them much. Most things should be drawn with vertex arrays instead (glVertexPointer, glDrawElements, etc), preferably in a few large arrays to minimise the batch overhead. And you can only do a single connected triangle strip per draw (at least without using futuristic features (Primitive Restart)). I don't have any numbers or much experience, but I'd guess it's better to do the simple brute force approach (a big array of (indexed) triangles) rather than a fancier approach (splitting into lots of small carefully-constructed triangle strips to reduce the total number of vertexes sent).

(We're targeting OpenGL 1.4 as the minimum requirement; new desktop GL drivers will continue to support that forever (so it's not too important that some features are deprecated in later versions). We're optionally using some GL 2.0 features (shaders) and some extensions but not much.)

[Xin]

Ok, that makese sense. I'll modify the calculations then.

I was reading in the spec that glDrawElements implicitly calls glBegin/glEnd so that's why I framed my question in that context. But, like I said, I've had no luck getting them to display properly. My best guess is that has to do with vertex winding order and the orientation of independent triangle strips. Whatever, indexed triangles are fine.

I'll use the 2.0 spec as my reference then.

[Xin]

Just to show that I haven't given up on this and that I haven't disappeared (although admittedly, I've been distract by videogames and anime), here's an updated patch with initial work into triangulating the blends and the previous discussions about the normals :)

I'm actually posting this because I've run into a problem that's got me stumped. My search routine for finding the matching triangulation used in BuildIndices works up until near the end when all of a sudden, m_Vertices starts returning junk data to me. It doesn't look like an index out of bound issue and I don't understand how data that was fine before suddenly turns into garbage so I'm looking to the more experienced devs for some guidance. If you apply the patch, you should hopefully see what I mean.

[Xin]

Initial work into triangulating BuildBlends. Submitted for debugging help. See comment: ​http://trac.wildfiregames.com/ticket/169#comment:10

[Xin]

Woops, I forgot to mention that I'm just loading the Latium map to get the problem.

[Philip Taylor]

Running in Valgrind, the first reported error is:

Trying to add vertex1 (68.000000,21.106556,424.000000)
Trying to add vertex2 (72.000000,21.797813,424.000000)
Trying to add vertex3 (72.000000,21.837431,428.000000)
Trying to add vertex4 (68.000000,21.095629,428.000000)
==9914== Invalid read of size 8
==9914==    at 0x80DA35: CPatchRData::BuildBlends() (PatchRData.cpp:313)
==9914==    by 0x80E4C9: CPatchRData::Build() (PatchRData.cpp:571)
==9914==    by 0x80E5E2: CPatchRData::CPatchRData(CPatch*) (PatchRData.cpp:58)
==9914==    by 0x7CD3A7: TerrainRenderer::Submit(CPatch*) (TerrainRenderer.cpp:116)
==9914==    by 0x7B614F: CRenderer::Submit(CPatch*) (Renderer.cpp:1395)
==9914==    by 0x77FA25: CGameView::EnumerateObjects(CFrustum const&, SceneCollector*) (GameView.cpp:371)
==9914==    by 0x7B874E: CRenderer::RenderScene(Scene*) (Renderer.cpp:1446)
==9914==    by 0x77FC4B: CGameView::Render() (GameView.cpp:303)
==9914==    by 0x7046E9: Render() (GameSetup.cpp:206)
==9914==    by 0x5B5F8D: Frame() (main.cpp:330)
==9914==    by 0x5B6151: RunGameOrAtlas(int, char const**) (main.cpp:397)
==9914==    by 0x5B6212: main (main.cpp:410)
==9914==  Address 0x152e3068 is not stack'd, malloc'd or (recently) free'd

which probably indicates where it starts to go wrong.

That seems to occur when p == 0 and m_Indices[p] == 290. m_Vertices only has 289 elements so it's an out-of-bounds access.

It looks like that may be happening because in CPatchRData::BuildIndices you're doing ...+base when computing indexes, which gives you indexes into the shared vertex buffer that's going to be used for rendering, but then you're trying to use them as indexes into the 0-based m_Vertices array too.

[Philip Taylor]

(Adding to CC since I don't know if you'll get notified about this otherwise.)

[Xin]

D'oh! Thanks for catching that. I've fixed it and now the triangulations match up (or at least enabling the blend pass no longer looks like horrible z-fighting). The only problem now is that blending doesn't seem to be working anymore :(. I'll continue working on it, but here's the latest patch.

And I seem to get notified of new comments to a ticket so long as I've posted a comment to that ticket once. It doesn't seem like being the open who opens the ticket is enough? Dunno.

[Xin]

Fixed accessing out of bounds locations.

[Xin]

Ok, blending is semi-working again. There are some tiles where blending doesn't seem to be applying correctly. I'll look through that thread linked to earlier and mess around with Atlas, see if I can figure out what's wrong (or heck, really understand how this alphamap generation is working). Again, I've attached the latest patch; if there's something obvious I'm messing up again, do tell :)

[Xin]

Blends semi-work now.

[Xin]

Ok, so it seems like we're finally back to where we started. Blends are functioning like they used to again, but I haven't looked into any texture painting bugs. I've modified TerrainOverlay to draw triangles as well and have it match up to the triangulation done by the patches (which is now stored in a STL map so triangulation matching is logarithmic instead of polynomial yay!). So yea, have a gander and let me know what you guys think.

[Philip Taylor]

(Um, sorry, I'm terrible at this patch-reviewing thing - this got lost in a big pile and I didn't realise it had been so long...)

General thought: With some trivial fixes (below), this works and does exactly what it should, which is great. It feels a bit weird editing terrain in the map editor because it keeps jumping between triangulations, but the result is sensible and more consistent than with quads. I think some of the code can be made simpler and more efficient, so it should be before applying the patch.

Some minor code issues:

m_Triangulation.insert( std::pair<CVector3D,std::list<unsigned short>>(v3,triangulation) );

The >> is a syntax error (it needs a space in the middle). But it's easier to just write

m_Triangulation.insert(std::make_pair(v3, triangulation));

Does it need to use std::list<unsigned short>? A std::vector would be more efficient (less memory usage, quicker iteration).

Does GetTriangulation need to do all those tests instead of simply out.push_back(m_Vertices[*it].m_Position)?

I must have been mistaken about the normalisation :-( . angle1 == angle2 all the time now, so it doesn't pick the right triangulation. I think what I missed was that the Cross is not between two perpendicular vectors, so there's an extra sin(angle) factor in there. It works okay with the Normalize() calls added back, but I don't know if there's a more efficient way to do it (and I'll probably just get it wrong again anyway).

More general issue:

The comparisons between CVector3Ds worry me - floating point comparison is often dangerous, since the compiler might optimise some expressions to use different levels of precision and end up with slightly different numbers that make the equality tests fail unexpectedly. Also it seems like m_Triangulation uses a lot of memory - at least 12 bytes (for CVector3D) + 12 bytes (the list of shorts) per tile, 256 tiles per patch, maybe 81 patches per map, is half a megabyte, not counting the map/list overheads.

Instead of using m_Triangulation, would it be possible to: Compute a boolean (from angle1 < angle2) in BuildIndices, one per tile, and store that in a vector (indexed by j*vsize+i). In BuildBlends, just read that boolean and set up splat.m_Indices in one order or the other. In TerrainOverlay::RenderTile, use a method to read that value (based on i, j) and then draw the GL_TRIANGLES using the appropriate sequence of v1, v2, v3, v4. Then I think it shouldn't need to store any extra data per tile except the boolean, and shouldn't need to do any comparisons of CVector3Ds. (Does that make sense? Am I missing some problems with that approach?)

[Xin]

I haven't looked at the code since I submitted the patch so my memory's a little fuzzy (Dragon Age went on sale and 3 weeks basically disappeared).

Uhh...I think there was a reason I chose to use list instead of vector, but I can't remember why now. I feel like it had something to do with vector not being usable inside a map, but I'm not sure. Could have just been that lists made more semantic sense to me.

Yes, the reason why I do so many tests and why I didn't use the boolean idea was that I think I ran into instances where the vertices weren't stored in the same order so I was getting triangles being rendered incorrectly. So v1, v2, v3, and v4 created from CalculatePosition didn't necessarily correspond to v1, v2, v3, and v4 used in PatchRData in that order. Plus, I have a bias against using booleans because I usually find they obfuscate logic.

I remember doing the math and coming to your conclusion that we could avoid normalization because the sin(angle) would be the same for all the cross products, but whatever needs to be done to get the correct result. In terms of algorithmic efficiency, I don't know of any cleverer ways to find the angle between planes. Computationally, you could probably do LengthSquared and parts of Normalize in SSE asm, but that'd probably be overkill.

I'm not sure there's anything we can do about floating point comparison other than hope that since CVector3D makes use of boost's fixed float conversion the compiler won't try to optimize to anything less than whatever precision boost uses. We could probably rewrite CVector3D to use fixed-precision floats if we really need to (not that I know how). And yes, there's a memory tradeoff for functionality, but I opted to do it that way because of the issue I mentioned before with the ordering of vertices. It also seemed a little silly that other components needed to worry about the order of the vertices used for triangulation when they really don't need to, other than knowing that it exists.

[(none)]

Milestone Environment Demo deleted

[philip]

(In [9054]) # Explicitly triangulate terrain tiles. Store blend splats as indexed triangles. Remove unnecessary copy of vertex data. Fixes #169.