BSP trees for geometry culling

Everything about development and the OpenMW source code.
Post Reply
ajira2
Posts: 55
Joined: 30 Oct 2017, 14:27

BSP trees for geometry culling

Post by ajira2 »

Hi, one thing that bugged the hell out of me about OpenMW was (years ago) that when I was facing a wall the fps was like 20fps in Seyda Neen and when facing the open town the fps was the same.

I expected the fps to go a lot higher when facing directly to a wall, exponentially. I don't know why I got so low fps, maybe it was the mods. It's not relevant. The point I'm doing here is that I believe that geometry is drawn behind the wall and then overdrawn by the wall.

This is bugging me. I thought about BSP trees, like Doom and Quake used to preprocess all the map and drawn things correctly without overdrawing. This is a preprocessing step before launching the game.

Image

Would it be cool or wise to test a fork or a branch with BSP trees involved? What would I need in order to do that and test it by myself? I'm fluent in C++, SDL, Tilengine and SFML, and object-oriented programming, but have not touched or compiled the code of OpenMW.

This links are informative:
ajira2
Posts: 55
Joined: 30 Oct 2017, 14:27

Re: BSP trees for geometry culling

Post by ajira2 »

Oh, nevermind, sorry... (ChatGPT 4)
Can BSP trees be applied to OpenMW engine to do geometry culling and gain fps?
Yes, Binary Space Partitioning (BSP) trees can theoretically be applied to OpenMW, an open-source reimplementation of The Elder Scrolls III: Morrowind game engine, for geometry culling and potentially improving FPS (frames per second). BSP trees are a data structure commonly used in 3D computer graphics to efficiently organize and subdivide 3D space, which helps with tasks like visibility determination, collision detection, and rendering.

Geometry culling, in this context, refers to the process of identifying and removing (culling) objects or parts of the scene that aren't visible to the camera or player. By implementing a BSP tree, you can efficiently determine which parts of the scene are visible and which are not, reducing the number of objects that need to be rendered, which may lead to better performance and higher FPS.

However, applying BSP trees to OpenMW may not be a straightforward process. OpenMW uses OSG (OpenSceneGraph) for rendering, which already employs various culling techniques and spatial data structures (such as bounding volume hierarchies and octrees) to improve rendering efficiency. Integrating BSP trees into the existing system would require a deep understanding of the engine's architecture and potentially significant modifications to the codebase.

Moreover, the benefits of using BSP trees for culling in OpenMW might not be as significant as in other engines, as the performance gains from using different data structures and culling techniques can vary depending on the type of game world, the complexity of the scenes, and the specific requirements of the engine. It's possible that the current culling techniques in OpenMW already provide a sufficient balance of efficiency and performance for the game's needs.

In summary, while it's theoretically possible to apply BSP trees to the OpenMW engine for geometry culling and potential FPS gains, it would require significant effort to implement and may not yield substantial improvements over the existing culling techniques used by the engine.
User avatar
AnyOldName3
Posts: 2668
Joined: 26 Nov 2015, 03:25

Re: BSP trees for geometry culling

Post by AnyOldName3 »

This is a little like suggesting adding pistons to a family car because you've heard racing cars have pistons and they go faster. The pistons are related to the speed, but they're a tiny part of it overall. BSP trees are just one of many possible spatial partitioning systems, and we do have a spatial partitioning system (although it's not using binary, or even particularly even, splits). You can use BSP trees for things completely unrelated to occlusion culling, and you can do occlusion culling without BSP trees.

You've correctly noticed that we don't have occlusion culling, though. This isn't because we don't want to have occlusion culling, but:
  • Most games don't implement their own occlusion culling system, they buy in some middleware called Umbra, and let a company that does nothing but occlusion culling deal with every aspect of it for them. We can't do this firstly because as a volunteer-run project, we can't afford it, and secondly because even if we could, they wouldn't let us publish their source code, and OpenMW's GPL licenced, so we have to make source code available.
  • Most games prepare all the occlusion data before the game's shipped by running a tool that analyses every environment in the game, and converts it to a compact representation that allows you to quickly look up for any camera position which things are likely to occlude a lot of other things, and which things are likely to be occluded by those things. You can then do a quick check for each frame of a relatively small number of objects. For all intents and purposes, OpenMW's data comes from the user and could be different for every individual person, so we can't bake anything ahead of time, and people would be cross with a several-hour baking process each time they booted the game up.
  • Games without baked occlusion at least have big obvious meshes marked as occluders in the game data. Morrowind's data isn't marked, and things that look like big obvious occluders are usually actually lots of little meshes put together to look like a big one, so we can't easily autodetect stuff.
  • The algorithms that avoid needing to know about specific occluders either:
    • Rely on GPU occlusion queries which can take several frames to get results back to the CPU from, so you either end up with pop-in because you didn't draw things you weren't sure about, or end up drawing lots of hidden things you weren't sure about, or both.
    • Are quite difficult to implement well enough that they don't take so long to decide what's occluded that it would have been faster just to draw everything.
    • Are quite difficult to implement well enough that they can say enough stuff's occluded to bother with them in the first place.
ajira2
Posts: 55
Joined: 30 Oct 2017, 14:27

Re: BSP trees for geometry culling

Post by ajira2 »

Thank you for you response.

It has just occurred to me: couldn't we launch BSP baking for just the current cell while game is launching (in a separate thread, with GPU computation this stuff, CUDA or whatever) and user is navigating between menus and starting the game?

And when he/she moves to another cell do the same? Or at least have an option to do so if the player wills?
User avatar
AnyOldName3
Posts: 2668
Joined: 26 Nov 2015, 03:25

Re: BSP trees for geometry culling

Post by AnyOldName3 »

A BSP tree is pretty trivial to create, but as I've said already, not really much use for anything we want to do. Actual baked occlusion data is a lot more expensive to create, around a few minutes per cell, and would need creating every time the game world changed at all. People don't tend to spend that long hanging around in menus when the game's starting up or tolerate a wait that long when walking into another cell. They also tend not to spend long enough in a single cell that asynchronously computing occlusion data for neighbouring cells would be done before they leave.
ajira2
Posts: 55
Joined: 30 Oct 2017, 14:27

Re: BSP trees for geometry culling

Post by ajira2 »

Hello, thanks again for responding, :) I appreciate it very much.

I see it seems not a wise path. Nevertheless, I have a couple of additional questions, just for the sake of ruling this out and/or understanding more of the matter. Don't mind my stubbornness, please.

You say it would be a few minutes to compute the first cell on launch. I assume you are talking pure vanilla? You are talking CPU or GPU? If CPU: Couldn't we “pass” pure CPU instructions to the GPU, with the stuff “general-purpose computing on graphics processing units” (GPGPU).

More on that. Couldn't we apply GPGPU to process different threads like audio, physics, texture loading, meshes loading, background cell loading, partition the rendering calls / rendering draw calls between threads, etc.? (I mean for instance partitioning each frame into four squares and rendering it in 4 threads, or 8 threads or what is available in the CPU or GPU).

I remember in 2006 or so I used 3dsmax with my laptop and normal computer and set it up to render a scene half top in the normal computer and low half in the laptop, for instance.

I doubted of my memory here, so I asked ChatGPT again, yes, I was correct:
could you set up 3dsmax to render half scene in one computer and half on another, right?

Yes, it is possible to set up 3ds Max to render half of the scene on one computer and the other half on another. This process is called "distributed rendering", and it allows you to split the rendering workload across multiple computers, which can significantly reduce rendering times.
Returning to my first point: With GPU or GPGPU a vanilla first cell could be occlusion-computated in less than minutes?

Even if it couldn't: couldn't we run the computation in the background and let the player begin the game and continue computing in the background and “switch” in real-time when the computation is done? And cap the % GPU consumption or memory to a certain % selectable by the user? Or, of course, give the option to disable this stuff to the user.

Would be a significant gain of FPS when it's done? Specially with heavily modded builds.

Now I read Octrees would be better (in my understanding) than BSP trees, for OpenMW, quoting ChatGPT:

Image
“Both Octrees and BSP trees are commonly used for occlusion culling in computer graphics, but which one is better depends on the specific application and its requirements.”



“In general, octrees are better suited for large-scale environments with a high density of objects, while BSP trees are better suited for indoor environments and complex geometries. However, both data structures have their strengths and weaknesses and may be more or less suitable depending on the specific application.”
Here, he/she calculates octrees in a complex geometry in order of milliseconds: https://www.youtube.com/watch?v=Qb93QSvxXrs

Here it goes from 20fps to 9000fps with octrees: https://www.youtube.com/watch?v=DoHPx5RQ7P4
User avatar
psi29a
Posts: 5356
Joined: 29 Sep 2011, 10:13
Location: Belgium
Gitlab profile: https://gitlab.com/psi29a/
Contact:

Re: BSP trees for geometry culling

Post by psi29a »

You're still having to 'bake' these before starting the game. Nothing against this though, it's still an extra step to do before running which can be time-consuming on such a large area as Morrowind. Add to that it will be need to be done every time someone adds/removes/changes a mod.

I personally don't mind that it's something you do extra outside of openmw, we already do the same thing for navmesh generation.

Question is, how time consuming it will be.
User avatar
AnyOldName3
Posts: 2668
Joined: 26 Nov 2015, 03:25

Re: BSP trees for geometry culling

Post by AnyOldName3 »

Again, you're talking about pretty general things that can be a small part of a solution as if they're the whole solution on their own.
User avatar
akortunov
Posts: 899
Joined: 13 Mar 2017, 13:49
Location: Samara, Russian Federation

Re: BSP trees for geometry culling

Post by akortunov »

ajira2 wrote: 11 Apr 2023, 08:58 Here, he/she calculates octrees in a complex geometry in order of milliseconds: https://www.youtube.com/watch?v=Qb93QSvxXrs
It is just a single object in a single scene. Morrowind (even witout Tamriel Rebuilt) has an open world with thousands of locations, and each of them consists of hundreds or even thousands of objects. So several milliseconds per object means several seconds per cell and several hours for the whole game world. And if such speed is with GPU-side calculations, it will be much slower with low-end GPUs, and we probably will not be able to make it parallel.
Post Reply