Why a NavOctree?

I feel summoned! :slight_smile:

First of all Navigation Octree can contain lots of physics-unrelated items, the navigation modifiers. Fortnite for example makes a huge use of that.

Another reason (even though the first one is enough actually) is CPU performance. NavOctree contains pre-digested data that navmesh generator processes really fast. If we wanted to extract that information from physx on the fly we’d be in deep trouble in navmesh-generation-intensive games (like Fortnite!).

A final note, 4.8 will ship the significant improvements we did while working on the GDC demo (make sure to try it out once it’s out, if it isn’t already). Before those changes navigation octree of the GDC demo’s 256 km^2 map was using up 5GB or RAM! After the changes it was more like 70MB.

Stay curious! :smiley:

Cheers,

–mieszko

Background: For those of you who are unaware, UE4 maintains an octree of navigation-relevant objects, keyed by their bounding box and with geometry/modifier/voxel data stored. This is used by the navigation generator to collect relevant geometry and modifiers for a given navmesh tile.

My question (and I’ll admit it’s more one of curiosity than practicality) is, why? The physics engine already maintains a broadphase of UPrimitiveComponents’ physics representations, and there would be several ways to associate navigation-specific data with relevant physics objects (and with non-colliding objects, for non-physics-relevant things like NavModifiers). The NavOctree has nontrivial memory, processing, and code-complexity costs, so I’m sure putting it in there wasn’t an idle decision.

Was the decision to have a separate NavOctree made to allow physics-less navigation? Was it to make asynchronous generation easier? Was it something even more subtle? Mieszko, I summon you! :smiley:

Cripes, you’re fast. Thanks, that makes a lot of sense.

I want to drill in on one specific issue you mentioned, that of predigested geometry data. Extracting Recast-ready data from UBodySetups on a per-tile-generation basis would definitely be slow. But why not simply have a map associating UPrimitiveComponents (and, by extension, physx::PxRigidActor*s) with FNavigationRelevantDatas? It seems like FNavigationOctree + physx::PxScene leads to a lot of redundant spatial tree management.

Thanks again!