misc: incremental world rebuilding...

[BGB]

just figured I would write about all this, in case anyone cares or has
comments.


Notes: the term "brush" in this context means a convex polyhedron
defined in terms of a number of intersecting planes (although there are
bezier patches and mesh-objects, which may also be called brushes, but
for now these will be ignored).

I am writing in relation to a world structure composed of a flat list of
"entities", each of which may contain another flat list of "brushes".

in my case, my engine uses a world structure similar to that used in
Quake-family engines.


once, long ago, I had implemented 3D worlds the traditional/"sane" way:
doing all the CSG clipping;
building a BSP from the clipped geometry;
building lightmaps, and performing lighting;
building visibility data;
...

but, eventually, this fell apart.


as a side effort, at the time, I had started work on a mapper.
in a mapper, one needs to modify the worlds interactively.

the early implementation simply drew the worlds full-bright, relying on
the fact that, at the time (and now), video cards were fast enough to
draw Quake 1 maps fullbright in real-time simply by walking the brush
list and drawing everything there.

as a later feature, I added vertex-lighting, and then switched to
(initially) using depth-fail shadows, and also (initially) using the
built-in lights in OpenGL, but I soon switched to using GLSL based
lighting shaders (and later migrated to depth-pass).


however, the performance was unusably terrible in all but the most
trivial maps.

this is because a naive implementation has a running time of
O(lights*brushes), which with a map with, say, 200 lights and 2000
brushes, suddenly one has to draw around 400k brushes each frame.


so, at the time, I improvised some:

an approximate "BSP" was built, which sort of skipped out on all the
"expensive" parts, such as performing CSG clipping between brushes, or
building a polygon-based BSP (I tried this initially, but found it far
too slow for real-time use, as it would require many seconds to rebuild
the BSP this way).

instead, an algorithm had been devised in a prior use, where a strategy
similar to Quicksort was used to quickly build a tree and recursively
subdivide the scene. the tree was instead build mostly to sort out brush
objects. this was sufficiently fast for interactive use (but, then and
now, does result in a significant drop in framerate while altering
something).

initially, the main purpose of the BSP was mostly just so that lights
could query only the stuff in close range of them, making the
frame-rates "almost usable".

unlike a traditional BSP, it makes no attempt to divide on face-places,
does not directly attack polygons to nodes or leaves, and does not
"split" things across the node plane, ... anything brush/object which
straddles a plane is simply attached to the node, rather than somewhere
further down the left or right side of the tree. the termination
condition is a failure to correctly split the list (either the left or
right side sub-tree would be empty).

the plane is figured by estimating the centroid, followed by estimating
how the "mass" is distributed relative to this centroid (the algo is
vaguely similar to the inertia-tensor calculation).


some fiddling went over the years into fiddling with things to improve
performance, mostly by devising elaborate ways to cull things, and doing
real-time visibility determination type stuff (given static visibility
information is fairly expensive to build with any algos I am aware of),
and also by building more temporary structures (such as geometry-lists
for static light sources, ...).

more recently, I have switched mostly to using the OpenGL occlusion
query feature, which actually turns out to be a little faster.

framerates are "generally usable", albeit still somewhat lower than
Doom3 (which I suspect uses a more costly but precise BSP-building
strategy, or maybe due to other reasons). Doom3 generally hits 63 fps in
many cases on my current HW, whereas my engine typically only "maxes
out" if one is off looking in a corner or similar (whereas looking down
a hallway or across a room is more often 30-40 or similar, although
sadly dropping below 30 fps is still not all that uncommon).


an issue observed though, when integrating mapped functionality back
into the main engine (such that one can fiddle with geometry in-game),
is that the notable drop in framerate when altering geometry is still a
bit annoying, since as-is, this implies rebuilding the BSP each frame.

this wouldn't be too much of an issue, except that things are altered
via "click and drag" and similar, hence why it is an "once every frame"
rebuild rather than a "once in a while" rebuild when doing this. as-is,
the framerate drop is severe enough to impede usability (may easily drop
below 10 or 15 fps).

example cases would be, say, while grabbing and moving around a wall, or
resizing a wall or floor, ...


a thought involves the possibility of finding a less drastic way of
dealing with alterations to world geometry, like say, having an
algorithm which may determine that the alteration will not compromise
the existing BSP, and so will not rebuild the entire BSP in this case
(probably only the geometry on a particular brush will need to be
rebuilt, and possibly adjacent brushes if inter-brush CSG were being done).

the current strategy is basically a "flush everything and rebuild"
whenever a brush is altered, but this may be a bit expensive.

the most likely algo would be to make sure that the altered brush will
not cross a BSP node-plane (and thus end up in a different node). if the
BSP structure would remain intact, then the algo may avoid a complete
rebuild.


any thoughts / comments?...