I'm looking for a broad phase algorithm for brush-based worlds. I also need an algorithm for determining which areas of said world are visible from the view frustum.
The Id tech engines in the 90's used BSP's for broad phase collision and PVS for visibility. Doom 3 in 2004 kept BSP's for collision but switched to portals for visibility.
Its now 2017. I'm wonder what approach should be taken today?
1 minute ago, scarypajamas said:I'm looking for a broad phase algorithm for brush-based worlds.
Broadphase generally operates on bounding boxes and spheres. There is no difference to it in a brush-based environment in this regard.
For production-quality examples of these examples, look at the source code of physics libraries, such as Box2D and Bullet.
4 minutes ago, scarypajamas said:I also need an algorithm for determining which areas of said world are visible from the view frustum.
This is literally a google a way.
5 minutes ago, scarypajamas said:The Id tech engines in the 90's used BSP's for broad phase collision and PVS for visibility. Doom 3 in 2004 kept BSP's for collision but switched to portals for visibility.
Not only broadphase, but collision in general. The term you might be looking for is narrowphase.
Quake et al used point-vs-brush collision, meaning that for collision, world geometry was extruded by the player's size. This meant that you could run a point or a pair of points along the collision mesh thus reducing the complexity of the test even further.
Note that brushes, while fast, have a few inherent drawbacks. Trouble with turning corners smoothly comes to mind first.
6 minutes ago, scarypajamas said:Its now 2017. I'm wonder what approach should be taken today?
Things have, indeed, changed dramatically. For narrowphase, read up on GJK.
28 minutes ago, irreversible said:Broadphase generally operates on bounding boxes and spheres. There is no difference to it in a brush-based environment in this regard.
I meant broadphase in the sense of narrowing down the number of solids needing to be checked for collision. In the Quake 3 BSP format that meant tracing down the BSP via hyperplanes until a leaf was reached. The leaf stores the possible brushes that can be collided against. Testing against that small set of brushes is the narrow phase.
28 minutes ago, irreversible said:This is literally a google a way.
My question is not about frustum culling or GJK. Let me be more specific: I need a way of determining what parts of the world are visible without unnecessary overdraw. Quake did this with PVS and Doom 3 did it with portals (and I'm aware of how both of those algorithms function). I'm wondering, in 2017, if there is a better approach.
34 minutes ago, scarypajamas said:I need a way of determining what parts of the world are visible without unnecessary overdraw
Occlusion Culling or Visibilty Determination might be good terms to search.
Since the old times there is hardware occlusion tests on GPU which is new: You can render low poly occluders to a low resolution z-Buffer, build a mip-map pyramid and test bounding boxes against that. This approach can work for dynamic stuff and of course you can do it in software on CPU as well. Probably artists need to make the occluders by hand.
40 minutes ago, scarypajamas said:I meant broadphase in the sense of narrowing down the number of solids needing to be checked for collision. In the Quake 3 BSP format that meant tracing down the BSP via hyperplanes until a leaf was reached. The leaf stores the possible brushes that can be collided against. Testing against that small set of brushes is the narrow phase.
As noted above, broadphase accepts bounding boxes and/or spheres and performs basic preliminary overlap checks to determine potentially colliding pairs. For moving objects, the bounding box becomes a composite of the objects bounding boxes at the start and the end of the update.
To minimize potential pairs (eg the input set to the broadphase), you'll likely want to use something as simple as you can get away with that best matches the nature of the game you're working on. Generally speaking this can be as basic as a regular grid, unless you're dealing with heavily asymmetric object placement, which can really benefit from something like an octree. It really depends on what kind of a game you're working on...
43 minutes ago, scarypajamas said:My question is not about frustum culling or GJK. Let me be more specific: I need a way of determining what parts of the world are visible without unnecessary overdraw. Quake did this with PVS and Doom 3 did it with portals (and I'm aware of how both of those algorithms function). I'm wondering, in 2017, if there is a better approach.
So you mean what are "the cutting edge" level partitioning schemes these days?
Is it safe to assume you're working on an FPS game? Is it indoors/outdoors or has hybrid environments? Are the levels large? Is the world detailed and graphically heavy? Is geometry being procedurally generated/loaded or are you dealing with static levels that are loaded once?
PS - regarding use of the acronym "CSG" in your topic title. This is something you don't generally come across outside of an editor. Boolean operations are usually performed prior to generating collision meshes, unless you're generating something procedurally. Though even then you're likely setting yourself up for a world of hurt performance-wise.
8 hours ago, JoeJ said:Since the old times there is hardware occlusion tests on GPU which is new: You can render low poly occluders to a low resolution z-Buffer, build a mip-map pyramid and test bounding boxes against that. This approach can work for dynamic stuff and of course you can do it in software on CPU as well. Probably artists need to make the occluders by hand.
I have researched occlusion culling and I worry about the accuracy of a hardware solution since there will be latency between whats currently visible versus what was last reported visible by the GPU. The player might turn around quickly or teleport causing brief popping artifacts. A software solution might work.
I also have to consider the visibility of the player from the perspective of the NPC's so this algorithm may run, not just for the players view frustum, but the NPC's as well.
8 hours ago, irreversible said:So you mean what are "the cutting edge" level partitioning schemes these days?
Is it safe to assume you're working on an FPS game? Is it indoors/outdoors or has hybrid environments? Are the levels large? Is the world detailed and graphically heavy? Is geometry being procedurally generated/loaded or are you dealing with static levels that are loaded once?
Lets say its a fast paced first-person stealth game with indoor environments connected by doorways and/or hallways. The levels are static and loaded once, they can be small or large. The world itself will be detailed by brushes and many low-poly model props. If an area is visible, then its content may also be visible.
Based on these requirements I was leaning towards BSP's and portals, but before I go that route I want to be sure there isn't a more modern solution.
25 minutes ago, scarypajamas said:I have researched occlusion culling and I worry about the accuracy of a hardware solution since there will be latency between whats currently visible versus what was last reported visible by the GPU. The player might turn around instantaneously or might teleport causing brief popping artifacts. A software solution might work.
I also have to consider the visibility of the player from the perspective of the NPC's so this algorithm may run, not just for the players view frustum, but the NPC's as well.
You can reproject the depth buffer from the previous frame. (There should be an article here on gamedev.net. Quite a lot games use GPU occlusion queries. IIRC Cryengine uses it and there should be a paper.)
You can also render occluders for the current frame at first and do frustum and occlusion culling on GPU to avaid a read back.
Personally i implented a software approach using low poly occluders:
Put occluders, batches of world geometry, character bounding boxes etc. in an octtree and render coarsely front to back.
Raster the occluders to a framebuffer made of span lists (so no heavy per pixel processing). Test geometry BBox against framebuffer and append to drawlist if it passes.
Advantage: If you are in a room, not only geometry but also occluders behind walls will be rejected quickly because the octree BBox already fails the visibility test and the whole branch gets terminated. Very work efficient. Can cover dynamic scenes or open / closed doors.
Disadvantage: Because the whole system relies on early termination parallelization makes no sense.
Unfortunately i don't know in which situations my method can beat others because i did no comparisions, but you can think of it.
I also remember a paper or article about how an older version of Umbra worked, but can't give any link. They managed to use something like a low resolution framebuffer by rastering portals instead occluders to ensure correctness. The diffulicty is to extract those portals as a preprocess... IIRC
For line of sight tests you sould use simple raytracing. A full blown visibility determination is demanding even for a single camera and no good option for NPC vs. Player even if first person.
I don't think any recent game still uses the same system for collision detection and visibility - Quake was really a special case here.
Based on these comments I'm going to attempt to implement an occlusion query design and benchmark it. Using portals would make things like lightmapping faster since I could eliminate lumels from sectors the light cannot see reducing the overall number of rayscasts. I could hook the occlusion query system into the lightmapper which might help.
It seems like occlusion queries are a good general solution for polygon soup, but since the maps I'll be dealing with are more room oriented my gut still says portals might be more efficient. It also seems intuitively easier to me where portals should be placed (in doorways, hallway entrances) versus where an occluder should be placed.
And for collision I'm thinking a BVH might be good enough.
