Hey let's switch away from bullet to anything else (discussion)

Everything about development and the OpenMW source code.
Chris
Posts: 1558
Joined: 04 Sep 2011, 08:33

Re: Hey let's switch away from bullet to anything else (discussion)

Post by Chris » 13 Dec 2018, 01:00

Stomy wrote:
12 Dec 2018, 15:54
With OpenMW we have a few more luxuries, such as knowing that the exterior world is divided into a 2D grid of a fixed size with each cell having a heightmap at a fixed resolution. That immediately gives us some direction as, for example we can ignore any comparisons with objects in other cells if a trace never crosses any cell borders.
Except if a static object crosses a cell boundary. See the Pelagiad castle walls. Also there's no saying if we'll have an option to change the heightmap resolution in the future, or add features for overhangs or tunneling caves. Cloth physics have also been a desirable option.

User avatar
wareya
Posts: 335
Joined: 09 May 2015, 13:07

Re: Hey let's switch away from bullet to anything else (discussion)

Post by wareya » 13 Dec 2018, 01:01

They're basically just saying that you can use cells as an initial broadphase stage and only look for objects that are touching the cells that the actor you're moving is touching.

Dynamics like cloth physics or jigglebones can be given by keeping bullet but only for those dynamics, and making kinematic bodies like actors ignore them entirely. Or, if you want to be like HL2, find a way to make kinematics and dynamics work well together. HL2 doesn't use havok for player-vs-world collisions, even though you can do seesaw puzzles with the player and everything.
paying attention to #1751 #2473 #3609 #3862/#3929 #3807 #4297 #4623

Chris
Posts: 1558
Joined: 04 Sep 2011, 08:33

Re: Hey let's switch away from bullet to anything else (discussion)

Post by Chris » 13 Dec 2018, 08:56

wareya wrote:
13 Dec 2018, 01:01
They're basically just saying that you can use cells as an initial broadphase stage and only look for objects that are touching the cells that the actor you're moving is touching.
That's basically a quad-tree, isn't it? Surely Bullet (or any collision/physics library worth its salt) has something like it. Ideally, I think actually, it should be a dynamically-sized oct-tree, since some cells will have more collision objects than others, and interiors are a single cell each, possibly with a lot of vertical overlap.
Or, if you want to be like HL2, find a way to make kinematics and dynamics work well together.
Bullet allows that. An object with 0 mass won't ever be moved automatically, the app is responsible for any and all change for it. Bullet will let you know when you hit with other objects (be they similarly 0 mass, or a dynamic rigid body), allowing the game logic to respond appropriately. And since Bullet would need to track the collision world anyway, why not use it to do the trace tests for the game's desired movement. Either way, the resulting position of non-dynamic bodies is ultimately up to the app.

User avatar
wareya
Posts: 335
Joined: 09 May 2015, 13:07

Re: Hey let's switch away from bullet to anything else (discussion)

Post by wareya » 13 Dec 2018, 09:42

Less like a quadtree (which is a recursive structure) and more like a presence array/grid. Cells are a fundamental part of OpenMW's design, so they're a PERFECT candidate for the very first phase of a broadpass. We could do something like giving each cell its own octree, for example. In "big" engines, the collision broadphase usually has multiple passes, usually from some kind of grid or bounding volume hierarchy down to AABBs.

>Bullet allows that. An object with 0 mass won't ever be moved automatically, the app is responsible for any and all change for it.

I'm talking about something else.
paying attention to #1751 #2473 #3609 #3862/#3929 #3807 #4297 #4623

User avatar
Stomy
Posts: 46
Joined: 11 Dec 2018, 02:55
Location: Fhloston Paradise!
Contact:

Re: Hey let's switch away from bullet to anything else (discussion)

Post by Stomy » 13 Dec 2018, 09:59

Chris wrote:
13 Dec 2018, 01:00
Except if a static object crosses a cell boundary. See the Pelagiad castle walls.
Then it is added to the potentially-colliding-set for both cells, or you clip its mesh along the boundary which is what I'm going to be trying first.
Chris wrote:
13 Dec 2018, 01:00
Also there's no saying if we'll have an option to change the heightmap resolution in the future, or add features for overhangs or tunneling caves.
Even if it does the heightmap will not vary within a cell, nor is there likely to be cells of different dimensions in the same worldspace, which means the algorithm still doesn't change, just a couple of constants.
Chris wrote:
13 Dec 2018, 08:56
That's basically a quad-tree, isn't it? Surely Bullet (or any collision/physics library worth its salt) has something like it. Ideally, I think actually, it should be a dynamically-sized oct-tree, since some cells will have more collision objects than others, and interiors are a single cell each, possibly with a lot of vertical overlap.
No not quite, all trees require comparisons at every subdivision to see which side you're on, and the number of comparisons increases as the tree gets deeper so its traversal time scales with the amount of objects in the scene. With a grid you do an integer-divide of the tracing object's position by the length of a cell and you can immediately get its column and row on a 2D map with just four division operations per point tested, regardless of how many cells are being tested.

Bullet actually doesn't use quadtrees or octrees, it uses DBVT for the initial broadphase which is a pair of Bounding Volume Hierarchies. BVHs are faster to build than quadtrees, octrees, or BSP trees, but are the most expensive to traverse because each step down the tree has an arbitrary number of comparisons to the chosen bounding volume (Bullet defaults to AABBs I think) rather than a fixed number of comparisons against a plane. Furthermore we then currently have a third BVH for every single mesh leading to even more traversal time before you ever get to comparisons.
wareya wrote:
13 Dec 2018, 09:42
We could do something like giving each cell its own octree, for example. In "big" engines, the collision broadphase usually has multiple passes, usually from some kind of grid or bounding volume hierarchy down to AABBs.
That's pretty much exactly my plan. I'll be implementing Octrees, BSPs, and BVHs to see which ones give the best balance of construction-time vs traversal-time in-game, but otherwise you've got the idea pretty much in one.
Never attribute to bad code, that which can be adequately explained with clever hacks

User avatar
wareya
Posts: 335
Joined: 09 May 2015, 13:07

Re: Hey let's switch away from bullet to anything else (discussion)

Post by wareya » 13 Dec 2018, 10:38

Stomy wrote:
13 Dec 2018, 09:59
Then it is added to the potentially-colliding-set for both cells, or you clip its mesh along the boundary which is what I'm going to be trying first.
Clipping would probably cause problems for anything that ever tries to move, e.g. by a script (that includes statics as well), and then there also activators.
paying attention to #1751 #2473 #3609 #3862/#3929 #3807 #4297 #4623

User avatar
Stomy
Posts: 46
Joined: 11 Dec 2018, 02:55
Location: Fhloston Paradise!
Contact:

Re: Hey let's switch away from bullet to anything else (discussion)

Post by Stomy » 13 Dec 2018, 11:03

wareya wrote:
13 Dec 2018, 10:38
Clipping would probably cause problems for anything that ever tries to move, e.g. by a script (that includes statics as well), and then there also activators.
I'm concerned more about clipping taking precious time to do, but the idea is to treat statics and other instances differently.

The plan with statics is that all triangles are stored in a separate table annotated with their source instance's refnum, sorted by the same refnum. Adding a new static after cell-load/tree-build results in its triangles filtered and clipped into leaves rather than triggering a rebuild. The triangle table is updated with the new triangles, and the existing contents already being sorted allows this to be done faster. New refnums don't even require a check, they can just be appended to the end with the last refnum + 1. Moving or removing a static via scripts requires deletion of its triangles from the sorted list and a traversal over the tree to delete all references to it, this last part could potentially be a problem area.

For statics that get moved a lot, like if ship mods allowing piloting, an idea I've used before is to have a list of the last 20 or so moved statics and if a static shows up a few times in quick succession it is flagged as "dynamic" and treated as a regular actor from the point on without being clipped. These ones would then probably still need their own personal tree but I think they're rare enough that they could be treated as a special case. Worst case scenario their performance would be no worse than Bullet's current handling of them with btScaledBVHTriangleMeshes anyway.

For other objects I haven't really settled on a single solution yet. With trees they have to traverse every time they move anyway so their references may as well be filtered in during movement and their old references deleted at the same time. This could end up being costly depending on the tree used but I'll see how it turns out. For all we know actors could simply be brute-force compared based on the tiles they cover in the heightmap, or just straight-up pair checked as they'll be using such simple primitives. That would be a problem for huge numbers of NPCs per-cell but most mods I've seen stick somewhat close to Bethesda's per-cell limits anyway.
Never attribute to bad code, that which can be adequately explained with clever hacks

nwah
Posts: 41
Joined: 21 Nov 2013, 07:40

Re: Hey let's switch away from bullet to anything else

Post by nwah » 20 Dec 2018, 22:37

Chris wrote:
04 Dec 2018, 05:00
Just to throw it out there, nVidia just open sourced PhysX, under the simple BSD-3 license. Should be usable by GPL apps, though I can't say anything about the API or how easy it is to use.
PhysX 4.0 came out today, also open source.

https://www.phoronix.com/scan.php?page= ... 0-Released

User avatar
Ace (SWE)
Posts: 827
Joined: 15 Aug 2011, 14:56

Re: Hey let's switch away from bullet to anything else

Post by Ace (SWE) » 21 Dec 2018, 13:45

nwah wrote:
20 Dec 2018, 22:37
Chris wrote:
04 Dec 2018, 05:00
Just to throw it out there, nVidia just open sourced PhysX, under the simple BSD-3 license. Should be usable by GPL apps, though I can't say anything about the API or how easy it is to use.
PhysX 4.0 came out today, also open source.

https://www.phoronix.com/scan.php?page= ... 0-Released
PhysX 4.0 is the open-sourced BSD 3-clause version of it. They just released the license change a month in advance of the code itself.

My assumption is that they wanted to make sure that there wasn't anything left in the codebase that couldn't be relicensed.

User avatar
Stomy
Posts: 46
Joined: 11 Dec 2018, 02:55
Location: Fhloston Paradise!
Contact:

Re: Hey let's switch away from bullet to anything else (discussion)

Post by Stomy » 09 Jan 2019, 13:39

I found out today that a couple of comments on this dedicated collision branch have been removed from GitLab as of me doing a rebase and force push to bring into line with master. I'll probably merge in changes instead of rebasing from now on to preserve any discussion.

I remember @wareya and I think @psi29a had some comments on the plans, somebody mentioned that Vanilla collision uses AABBs to test actors against the world so I was intending on seeing if it was worth emulating that or if capsules would suffice. Now that I've repeated that here there is at least some record after GitLab ate it.

I'll keep this thread up to date with how its going once there's actually something playable to show, and anyone is welcome to discuss the dedicated system's design decisions here or on my fork on GitLab.
Never attribute to bad code, that which can be adequately explained with clever hacks

Post Reply