Map Tessellation Testing

[Argh]

Ok... basically, it's like this. Groundscars are performing very poorly. We know this, but I think I know why.

They're tessellating far more than they need to. This is in addition to the problems with shadows, which appears to a totally separate problem. Check this little enlargement of a screenshot I made today:



It's a little hard to see, but the weird "fuzziness" on those dots (which are caused by whatever bugs are present in the shadowmap code atm) ... is excess tessellation.

This is a perfectly-flat heightmap with ground deformation OFF, btw.

I've seen a number of other disturbing things:

1. Tessellation is incredibly inefficient. I'm seeing hundreds to thousands of triangles where I should see a few dozen at most, on tests with perfectly flat surfaces. I tested this because I'm trying to figure out how to wring enough performance from Spring to get really complex visuals on people's screens... and found that flat maps offer practically no real performance advantages over hilly ones. According to what I read about how that algorithm I talked about last week is supposed to work... that should not be happening. Instead, wide flat areas should always be very efficiently tesselated to a very low triangle count.

It's almost like the renderer is treating heightmap squares in isolation, instead of the entire heightmap that's within the view frustrum... or something else is majorly borked.

2. When the camera is near the center of the world, you see this, with wiremap on:



See the density of triangles near the bottom? I think it gets even smaller nearer and nearer the bottom, we just can't see them- my guess is that eventually the sub-divided squares are one texel in size.

I dunno what the circle is, anybody have any idea what we're seeing there?

3. Repeated tests have revealed that the CPU hit is not trivial, when you add in groundscars, because they're being inefficiently tessellated, CPU-side, then are being tessellated again by the vertex and fragment programs. We're talking loads of tens of thousands of triangles... for something that should be a quad, on a flat map, then tessellated only enough for the quite-large texels of the shadowmap.



I'll be the first to say, I don't know how to address this, or even have a (crappy) clue as to where to go- this is way outside my comfort zone with rendering systems. I wish I could, frankly, it's a pretty messed-up area, and I know jK and Kloot are both busy on things that are more important atm.

I saw various notes in the ground-drawing code that said that some of SJ's hackish stuff was still in there, and presumably hasn't been fixed. I'm guessing that there are real fundamental issues here, and that we should see this area as a serious optimization area worth some time spent. To put it into perspective... without any objects in the scene, at game start... all Widgets off... CPU hits for the map and wiremap on hit anywhere from 10% up to 20% in short bursts.

For a static, absolutely flat heightmap that will not be changing, that's ridiculous, imo. It's not the SMF format that's the problem, it's the fundamental drawing code.

In fact, I have a sneaking suspicion that if that part of Spring was fixed up, SM3 might start looking... practical.

The other thing that could (and IMO at least, should) get changed is the update frequency for re-tessellating the mesh. Currently it appears to operate once a frame. I'd have to vote that, unless there's a real need (explosion, Lua event), then it should wait no less than a SlowUpdate (although I'd offset it one frame, since it's a big CPU hit and there's so much going on then). It's simply not necessary, to update the mesh every frame- show the ugly version, if the camera jumps, then clean it up a half-second later at most.

Yeah, I know, it's not quite as smooth or pretty, but meh, it'd be a lot faster.

It is my (no-doubt somewhat ill-informed) opinion that addressing these issues could:

A. Speed up map rendering dramatically, immediately.

B. Make it easier to arrive at a very fast shader-based approach as a future game option. After all, the formula's practically the same- and it really appears that there's something fundamentally wrong, that won't get fixed like magic by just sending it to a shader. It'll offload it, sure, and that'll allow uber-systems to plow through map geometry, just like they're plowing through on pure CPU (I know whereof I speak, since I've been doing playtesting on two pretty modern machines, it's amazing what throwing enough CPU at the crunchy stuff can do for this engine ).

To reach even current-gen levels of beauty, this is a Rubicon we'll have to cross. I think that this needs to get solved first.

C. Make maps with true-flat spaces attractive for the same reasons they're attractive in commercial game engines- efficiency. Ok, and better gameplay... but that's not the main reason that so many RTS engines use a lot of true-flat terrain, and various chunks of incidental geometry using a system somewhat like World Builder to perform culling.

D. Make splatting approaches of various kinds (even "incidental" or procedurally-built) far more practical than they are now. After all, the real reason they're sucking is that they're putting out far too many triangles on the CPU side, so far as my testing shows.

[AF]

Arent we running in a tile based map format? As such though the map could be represented as a single pair of triangles, that would effectively be a single tile, though I can imagine there are numerous ways of doing this, such as rendering the map texture to an fbo and then using that texture on the quad instead, meh that has issues too.

Someone who knows what theyre on about comment?

[Argh]

Arent we running in a tile based map format?

The issue isn't with the tiles, I don't think. I think jK's mainly fixed that step, it's a lot faster than it was, and I think the only way it's getting faster is with splatting, so that we're not throwing huge textures across the bus all the time, but are instead storing an atlas or three in a map, and the map's mainly just calling out points which coorespond to a scale and a set of texture coordinates on a given texture (an idea I keep having- I'm pretty sure that's the way to do splatting very very efficiently, I just don't know jack squat about how to do the projection stuff required, and every time I sit down to read that stuff, I find that I have something else to do).

The problem seems to be with the actual tessellation / frustum culling step, where we should be seeing very large triangles that have had the FBO applied. We're not- we're seeing teeny-tiny ones. Then they're broken up yet again when the vertex and fragment programs run. Then we repeat all of this inefficiency again when we're dealing with groundscars, unit tracks, and other objects of that type. Fewer, larger triangles and more efficient meshes in the POV would vastly improve overall rendering time-hits to the CPU, regardless of how much loading is going on to deliver the tiles.

I mean... if it really was the tiles... then we wouldn't see that in wiremap, I don't think it takes the tiles into account, it's just showing us geometry hit. Maybe I'm wrong there... but that doesn't make any sense to me, given the weird sizes it's showing, where it's clearly doing the reduction algorithm, but it's not really doing it correctly for the complexity of the scene.

[Kloot]

We know this, but I think I know why.

They're tessellating far more than they need to.

This has been known for a long time. Ground decals do not follow terrain LOD, they are always drawn at the same tesselation level. It's harder to fix than it sounds.

I'm seeing hundreds to thousands of triangles where I should see a few dozen at most, on tests with perfectly flat surfaces.

The main problem is that the SMF drawer does not use an error metric for how well the tesselation matches the heightmap, unlike more advanced terrain rendering algorithms. Just because you don't see any work being done, however, does not mean none is.

[Argh]

I wasn't meaning to imply otherwise, just was thinking about all of this, I got a bit of "sticker shock" when I saw that even using a flat map wasn't curing performance woes.

Didn't know that the issue with ground textures was being caused by that assumption, though- I assume that's to avoid z-fighting?

[Das Bruce]

See the density of triangles near the bottom? I think it gets even smaller nearer and nearer the bottom, we just can't see them- my guess is that eventually the sub-divided squares are one texel in size.

So, as far as I can gather, the engine is rendering at a max of two triangles per pixel dispite the map only containing two triangles per 64 pixels of texture data?

[Argh]

So, as far as I can gather, the engine is rendering at a max of two triangles per pixel dispite the map only containing two triangles per 64 pixels of texture data?

No, it's actually worse than that, I'm pretty sure that it's building more squares than there are actual heightmap pixels in that picture, or at the very least, it's reaching 1:1 density near the bottom. Ideally, this should all be a handful of triangles at most. That's what Kloot's referring to, when he's talking about the error metric, it should be cutting triangles really ruthlessly, on a map that's a plain... but that's not the only place we'll see major benefits, of course. In any maps where the mapper doesn't use a lot of noise, and keeps heightmaps following gradients most of the time (which most mappers do- just about everybody blurs the heightmap a wee bit, to get rid of spikes) the resulting mesh density will be a lot lower than 1:1.

On the topic of the groundscars / ground textures... couldn't a second set of geometry be rendered after the first layer, exactly the same way as the ground, and then just have the textures projected onto it? There's no real reason to use a 1:1 ratio, if the polycount of the underlying mesh is no longer huge, and you already have that geometry, why do it twice... just a thought there, I know that putting the various textures into a projection's no fun, but doing it as 1:1 sectioned into squares / rectangles seems enormously wasteful to me, and the cost of setting up the projection seems like it would be a lot less than the geometry cost ++ doing separate projections.

[lurker]

We really need to have the greatest detail point trace the camera's view, and not sit directly under it...

[Noruas]

Oh god I wish i was as smart as lurker!

[lurker]

O_o

[AF]

O_o

[Argh]

Well, yeah, that would be a start- it basically assumes a OTA view. But it's really not the big issue. The big issue is that it's making far more triangles than it actually needs to.

Fixing the first is inherently part of fixing the second, basically.

[lurker]

I see a big topic about using complicated methods to cut down on the number of tris on the map, and nothing else, and suggest that first we quickly add a couple lines to recenter what it does right now, and I'm being mocked by multiple people? Clearly I missed something, but I can't see what... any help?

[AF]

I agree with lurker. The re-centering is so obvious that it doesn't even need mentioning and should have been done already (goes to check git rss feed (maybe Ill be pleasantly surprised) )

[lurker]

So it's just mockery for being today's Captian Obvious? I'm fine with that.

[AF]

So it's just mockery for being today's Captian Obvious? I'm fine with that.

pretty much yeah, tho my post was more a hoorah! at noruas than a dig at anybody, ^_^

[Argh]

Is this ever getting fixed?

[lurker]

I haven't seen you make a single suggestion of actual adjustments, just complaints, so don't expect people to have done this for you. You could even just suggest a new detail falloff equation, one line of math!

[Argh]

Uh, I gave you the entire presentation about this very topic from nVidia... which included examples and the relevant math, IIRC.

Just fixing it so that it uses the camera's current vector would be a great (and easy) place to start.

I know that adapting their error-correction algorithm may not be anything like as easy, but that's one major problem with the way it works now that should be a pretty easy fix.

[IllvilJa]

Some random thoughts on this:

Changing the area which is tessellated to the area where the camera is pointed might be slightly tricky if the terrain is hilly and the camera is more horizontal than vertical and close to the ground. The pieces of the ground in view might be located at very disparate locations on the actual map (especially when you are in FPS mode...).

Of course, a trade off could be made so one single, sensible point is selected and then the terrain around that point is the center of tessellation. Not a perfect solution but still a good improvement, compared to let all tessellation occur under your feet where you aren't looking anyway in the situation I described :).

Other thought: I've been looking into the Cube 2, aka Sauerbraten engine (http://www.sauerbraten.org) and is quite intrigued by it's use of a octree world structure. Basically, the world consists of an octree of deformable cubes (where each cube can have it's six sides independently pushed inwards with different slants, so individual cubes are not that fancy). Each deformed cube is quite simple, geometrically but the nice thing with the setup is that one might have a very coarse description of the world at places where things were mainly flat, and then increase the number of cubes (by subdividing cubes into 8 smaller cubes recursively quantum satis) wherever the terrain became more "interesting". In that engine, there are commands for optimizing the layout of the world, so triangles that can be combined (from a texture and geometry point of view) are combined into a few, big triangles.

Even given Springs limitation that the terrain always must be possible to project on a 2D surface, I think such an octree concept could be of interest for Spring, as an alternate format for creating less CPU/GPU demanding maps (yes, those simpler and resource leaner maps do have their fans ). This would unfortunately put even more strain on Spring development, so that probably would prevent this from happening. (I don't have time to try to write this unfortunately and even if I had, I might end up just ruining spring as a program...)

Then I personally have some issues with the particular octree format used in Sauerbraten, my primary gripe being the fact that if you subdivide certain shapes of deformable cubes, the range of allowed shapes prevents the 8 subcubes to be shaped in such a manner that they together form the bigger original deformed cube. The sauerbraten engine fixes this by trying to approximate the original bigger shape, but at the end of the day, the net result is that one in some situations loses control of the shape of the map as a result of increasing the resolution at which one tries to define it. It is quite a paradox, and frustrating when trying a top down design approach (or when letting automated code alter the map), especially as the loss of control can be sever, at least for my preferences. There are ways to address these and other issues with the deformable cube format used in Sauerbraten, but I won't bore you with the details (this post is long enough).

Another potential win with an octree solution is that it is rather cheap to describe certain types of changes in the world, so for instance, if some piece of terrain is deformed during play (say, a heavy bomb detonates and causes a crater) and we accept that the deformation don't have to be "perfectly smooth" but 'slightly blocky' the amount of information describing that change can be reduced, lowering the need for bandwidth to be consumed when communicating it out to other players' clients.

Yet another win [while I'm at expressing fantasies ] is to combine this approach with the current heightmap map definition: the original terrain is a heightmap, but parts of it is amended by using octree structures. Some walls/concrete structures are added which are made up by these octrees at one place, while at another place, negative space, again described by octrees, is used to define how the ground is carved up to create, say, trench-like structures in the map.

Ok, I admit, I'm just contributing with tons of suggestions from a person fuzzy on general details in a context already flooded with such fuzzy detail suggestions. Hope I did not make anyone drown in the 'sea of suggestions' in the process.