Opened 11 years ago

Last modified 11 years ago

#2039 new enhancement

Implement caching of terrain normals

Reported by: wraitii Owned by:
Priority: Should Have Milestone: Backlog
Component: Core engine Keywords:
Cc: sanderd17 Patch:

Description (last modified by wraitii)

After #1988 was committed, and because of other bits of code already using it (foam generation for the water, decal generation)

Calculating terrain normals is fairly slow, uses a ton of temporary memory, and is generally not a good idea to do on the fly. #1988 means we'll be calculating normals all the time. We should cache the values of each vertex normal, which will considerably speed up such a task.

I'm fairly sure "CalcExactNormal" also relies on the vertex normals.

A few concerns:
-Atlas needs a way to not cache terrain or to invalidate the terrain cache (there is a message for that I believe)
-A cache should be as quickly accessed as possible.
-We need to sort out the fixed v not fixed issue with normals. Imo, we should use the non-fixed version as much as possible for anything graphical (ie not checked for OOS), because it's simply faster.

Normals are most likely calculated first in PatchRData, when building the terrain mesh.

Attachments (2)

FasterNormalCalc.patch (3.2 KB ) - added by wraitii 11 years ago.
exact_normal_unnormalized.diff (1.4 KB ) - added by sanderd17 11 years ago.

Download all attachments as: .zip

Change History (16)

comment:1 by wraitii, 11 years ago

Description: modified (diff)

by wraitii, 11 years ago

Attachment: FasterNormalCalc.patch added

comment:2 by wraitii, 11 years ago

Furthermore the functions to calculate terrain normals are not very efficient, relying a lot on "CalcPosition" which isn't efficient in that case. My patch changes the normal and the fixed version to take into account the specificity of what's asked. haven't tested, but it can only be faster.

(note: I increment X and Z by 4 because that's the value of TERRAIN_TILE_SIZE, we might want to use that instead.)

Last edited 11 years ago by wraitii (previous) (diff)

comment:3 by historic_bruno, 11 years ago

#1987 should be used for addressing efficiency of the normal calculations, so far a better, similarly-accurate alternative hasn't been found. If the float version is more efficient, it can be used easily for #1988 by adding CalcExactNormal to CmpTerrain to expose the CTerrain function.

Caching seems like a good idea, it could be part of CTerrain so lots of code can reuse it, and it wouldn't require Atlas-specific logic. CmpTerrain::MakeDirty is used whenever terrain changes, it could be responsible for updating the relevant part of CTerrain's cached normal data.

Last edited 11 years ago by historic_bruno (previous) (diff)

comment:4 by historic_bruno, 11 years ago

Cc: sanderd17 added

comment:5 by sanderd17, 11 years ago

CalcNormal takes the average between 4 cross normalised products, so is highly inefficient by itself, and the only method available through CmpTerrain.

CalcExactNormal does some minor checks to see on which triangle of the tile it is (of the 4 triangles a tile has), and then uses only one normalised cross product to calculate the normal on that triangle. So is a lot more efficient.

Note that #1987 makes CalcNormal to only use one sqrt. But this implies a different averaging method (something I missed at first), so the average is not between 4 normalised vectors, but (so to speak) between the 4 non-normalised ones, giving prevalence to more steep terrain. It won't matter that much (certainly since the normal on a vertex isn't really defined), but it breaks the tests.

Caching is indeed the one possibility. But we need to discuss what to cache.

It looks like the CalcNormalFixed method is never called, apart from the Anchor patch (#1988), but in my opinion, it should be replaced by the CalcExactNormal function.

My proposal:

  • Cache all values for CalcExactNormal (this is 4 times the number of tiles, as there are 4 triangles per tile)
  • In the CalcNormal function, use the cache from CalcExactNormal, and return the average over the 4 neighbouring triangles of the vertex. This will also require a sqrt, but it's a simplification from 4 sqrts to one, and (I hope I'm right this time) shouldn't alter the test values.
  • Add a method to CmpTerrain that calculates the exact normal, and use that method for Anchor calculations (explained in #1988 why)
  • Don't change CalcNormalFixed, as it doesn't get used anyway, and there's no need to store an other list of all fixed values.

comment:6 by historic_bruno, 11 years ago

I did some profiling using Very Sleepy (Core i7-2600K, Win 7 64-bit, VC++ 2010)) on replays from a test map with several hundred anchored units moving (siege rams and cavalry), indeed UpdateXZRotation takes about 1/4 the total execution time using CalcNormal (0.29%) compared to CalcNormalFixed (1.22%). Normalizing the vectors takes most of that time, as you say.

Using a simple array for the cache, on a 512 x 512 map, 4 floats per tile would be 4 MB of data. I had forgotten the water manager is already creating a temporary normals cache in CreateSuperfancyInfo, that's 3 MB that nothing else can use. Would the proposed CTerrain cache be enough to avoid the temp water info cache?

Should we generate the cache during map loading?

comment:7 by ben, 11 years ago

In 13571:

Changes terrain anchoring to use faster CalcExactNormal instead of CalcNormalFixed, refs #1988, #2039

comment:8 by wraitii, 11 years ago

I'm actually simply creating a blurred map of normals in the water manager, but I recently optimized it by first caching the normals. If there is a cache in Terrain.cpp, I won't need to do this, so this would be enough.

I think the memory issue is something we'll have to live with. It's one vector/array so it's pretty contiguous, so that's good, and it's "only" about 5MB even in the worst cases. A basic implementation would simply use a CVector3D* array that's allocated at map creation, calculated whenever needed, and destroyed at map destruction. I'd like to have some more profiling data though, with using the cache.

comment:9 by scroogie, 11 years ago

CalcExactNormal does the same as we propose in #1987, but only for one triangle. It even writes the 0s into the vectors that we use to optimize the cross product. I'd write that out, as we did. Why create two CVector3Ds from their components, when you just need the cross-product?

in reply to:  8 comment:10 by historic_bruno, 11 years ago

Replying to wraitii:

I think the memory issue is something we'll have to live with. It's one vector/array so it's pretty contiguous, so that's good, and it's "only" about 5MB even in the worst cases.

It wouldn't be the worst case for maps larger than 512x512 tiles, but "giant" maps are currently 512x512, and I agree it may be something we have to live with.

comment:11 by wraitii, 11 years ago

A thing to note though: we can either cache vertex normal data (easy, since it's per-vertex), but that would only be semi-interesting if the anchor code uses Exact normal, which aren't using vertex normals at all. In that case, we could cache the normals for the 4 potential triangles of each terrain tile. This would seriously bump data usage up, but it would work (and I could adapt my water code to use that, I guess).

by sanderd17, 11 years ago

comment:12 by sanderd17, 11 years ago

The diff I added is not for inclusion, only for testing.

In any case, Anchoring doesn't need a normalized orthogonal, and most other code doesn't need it either (only the direction of the vector is important). So I worked out the cross product, and removed the normalize.

This brings the anchor calculation from 1.05 us to 0.94 us according to my profiling, with a profiling overhead that seems to be around 0.34 us. So that gives a speedup of around 15% when leaving out the profiling overhead.

It certainly break terrain boundary rendering, and probably some water related stuff too, so it's not for inclusion, but a method could be added to calculate an unnormalized orthogonal to speed up anchoring calculation.

It could even make caching unnecessary, as there are not a lot of calculations left.

Last edited 11 years ago by sanderd17 (previous) (diff)

comment:13 by Kieran P, 11 years ago

Milestone: Alpha 14Alpha 15

comment:14 by historic_bruno, 11 years ago

Milestone: Alpha 15Backlog
Note: See TracTickets for help on using tickets.