I wonder what's faster algorithmically - given a convex hull of one format or another, finding corner points from side planes or finding side planes from corner points?
the basic algorithm for both seems to be O(n^4)
planes ➡️ points: [1,2] create a ray, [3] intersect against remaining planes, [4] check if point is inside the volume
points ➡️ planes: [1,2,3] create a plane, [4] check if all points are on one side of it
but maybe there's an optimization somewhere?
I'd still keep both in data (because O(n^4) at runtime is unbelievably silly) but this matters in terms of what would be best to expose for editing purposes or as a construction input
that said, for the latter it might be easier to require passing both of them
for editing maybe incremental edits are the way to go (only recalculate the affected parts) but that probably only shaves one n and it's still O(n^3)
also don't want to overload myself with work too early
turns out it's quite painful to move to a different volume representation
the original one was fairly well chosen for the game in that it allowed doing 2D-based measurements easily
unfortunately I do need a new one to build new 3D spaces
so I need new algorithms for
- roughly measuring the walkable (floor) area
- editor volume side raycast (from inside and outside) with snapping to edges
I also need a new shader encoding for the data (first a temporary one, to be improved later)
thinking that it might also be useful to precalculate the face polygons
the idea is that there could be a hash grid where each cell is a binary tree
inserting into the tree requires that the faces are finite, to determine whether they intersect with the planes in the tree
it might not require that the faces are polygons however (an unordered pile of vertices might be enough to intersect a plane)
polygons might help with other things tho (ray tests/volume paths)
finally added support for convex decomposition
a very basic divide-and-conquer algo atm: find worst concavity, find nearest vertex that fully solves the concavity, subdivide into 2 polygons and process them recursively
(note that I'm not yet checking if the vertex is visible or have fallbacks for partial solving, will need to fix that for more complex cases)
this can be used to convert from the old data and also for making rooms from concave polygons in the future
wondering how crazy it would be to have a hash grid of small BSP trees for my volumes
BSP tree building is full of O(n^2) code
hopefully most of the time n would be very small (1 on the edge, 2-3 inside a huge volume)
one corner is n=24 (3 corner faces x 8 solids), may need to precalculate parallel planes, getting most corners down to n=3/8 hybrid (3 planes but they reappear in subtrees)
may also need to subdivide specific grid cells that contain too many corners
the use case is streaming of partitioned world sections
thinking that in theory streaming should be set up so that it can take a while and happen over several frames
so if volumes get introduced to the world cell by cell, it shouldn't be an issue in theory
also, usually the volumes shouldn't overlap globally so sections could come with most cells being precalculated and only the sides would require live recalculation
accelerating the lookup of densely packed volumes is a complicated problem overall
it's probably why:
- BSP-based engines have been largely phased out
- open world games tend to strictly separate outdoor and indoor sections
- of those that don't separate, most end up finding a way to enclose indoor sections into very few OBBs via design, either by making them thin and staying away from walls to allow oversizing the OBBs (MGS 5), or by making the exterior box-shaped (GR:W)
Hitman (2016+ series engine) is a notable exception but they seem to sidestep the need for perfectly accelerated volume lookup by relying on screen space portals (rectangles) to find where one volume ends and another one begins
if I fail to accelerate volume lookup, that's my backup idea
it has the downside that the camera can't escape interior geometry - if it does, outdoor lighting would need to be assumed for all pixels that don't pass through a portal
the reason why I'm avoiding it at the moment is that it would prevent the use of a corpo/ghost-style camera that isn't limited by the world
not only that, it would also prevent the use of top-down/sidescroller cameras, however in those cases arguably 2D or 2.5D volumes can be used, which tend to be much easier to look up quickly anyway
so it is admittedly a very limited use case - one can definitely make and sell great games without it
... but also because it looks like volume lookup could be a lot more GPU-friendly
the beauty of hash grids and BSP are that the loops are shallow:
- loop 1: for each cell under the same hash
(1:1 mapping from coord to cell so no nesting needed)
- loop 2: while node is a branch, node = point in front ? node.front : node.back
(also 1:1 coord to leaf)
no inner loops/branches means that the loops should be highly parallel even when the data slightly differs
the best I can currently come up with for portals:
- screen space grid lookup
- for portal in grid cell:
- end loop if current volume doesn't match portal entry volume
- intersect the portal plane
- go to the next portal if pixel is outside portal quad (and optionally texture mask)
- change the current volume to portal exit volume and skip to the first portal for that volume
the portal shape has to be O(1) for this to work
in order to avoid spending too much time on plan A unnecessarily, opted to finish plan B first
nearly finished portal screen space grid lookup data generation code (cpu-side, ~150loc, similar to what's needed for tiled shading, still needs near z clipping and testing)
I also still need the shader code, gpu resource mgmt/upload, renderer integration and light space portal integration
would be really nice if I could make it work over the weekend
here's light portals at different stages of finally getting them to work
not fully optimized - and still no z clip or camera-based CPU side portal walk yet - but much of the rest seems to be done
the grid is very low-res as I want processing to take ~0.1ms
portal walk should help things be a bit faster overall (less portals to process), right now I'm just throwing all the portals at the system
lighting being incorrect outside portals isn't fun wrt map editing
clipping done (?)
for now w>0 clipping only
also found a silly bug where I set the structured buffer before updating it - if it got released and recreated during the update, old data would be used for the frame (causing a one-time glitch when the screen grid cell portal lists buffer receives more data than in the previous frame)
I should stress-test this thing by building a worst case sliced up hallway (many overlapping portals)
added portal walk and created a small stress test (10 portals)
I can scale it up later if needed, so far I'm not expecting more than 10 per tile (and even then the camera would need to be very zoomed-in to go through all 10 for most tiles)
will probably also need some editor features to make lighting easier to preview (e.g. using pivot as light origin, different camera modes) but in any case, this might be good enough for now
Arvīds Kokins