• Advertisement
Sign in to follow this  

Algorithm CSG collision and visibility in 2017

Recommended Posts

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?

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites
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.

Edited by scarypajamas

Share this post


Link to post
Share on other sites
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.

 

 

 

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Edited by scarypajamas

Share this post


Link to post
Share on other sites
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.

 

 

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Advertisement
  • Advertisement
  • Popular Tags

  • Advertisement
  • Popular Now

  • Similar Content

    • By Descent
      Wow what a wild game by GalaXa Games Entertainment Interactive. Play now... it's really fun but IF you have epilepsy then don't play. It does not feature flashing pictures, but there is lots of animated stuff that might get ya. Anyway, 4 levels, 2 endings, insane action, BY INFERNAL. Please play it, right nao! Also , nice midi music composed by me is in the game.
       
      demons.rar
    • By Stewie.G
      Hi,
       
      I've been trying to implement a basic gaussian blur using the gaussian formula, and here is what it looks like so far:
      float gaussian(float x, float sigma)
      {
          float pi = 3.14159;
          float sigma_square = sigma * sigma;
          float a = 1 / sqrt(2 * pi*sigma_square);
          float b = exp(-((x*x) / (2 * sigma_square)));
          return a * b;
      }
      My problem is that I don't quite know what sigma should be.
      It seems that if I provide a random value for sigma, weights in my kernel won't add up to 1.
      So I ended up calling my gaussian function with sigma == 1, which gives me weights adding up to 1, but also a very subtle blur.
      Here is what my kernel looks like with sigma == 1
              [0]    0.0033238872995488885    
              [1]    0.023804742479357766    
              [2]    0.09713820127276819    
              [3]    0.22585307043511713    
              [4]    0.29920669915475656    
              [5]    0.22585307043511713    
              [6]    0.09713820127276819    
              [7]    0.023804742479357766    
              [8]    0.0033238872995488885    
       
      I would have liked it to be more "rounded" at the top, or a better spread instead of wasting [0], [1], [2] with values bellow 0.1.
      Based on my experiments, the key to this is to provide a different sigma, but if I do, my kernel values no longer adds up to 1, which results to a darker blur.
      I've found this post 
      ... which helped me a bit, but I am really confused with this the part where he divide sigma by 3.
      Can someone please explain how sigma works? How is it related to my kernel size, how can I balance my weights with different sigmas, ect...
       
      Thanks :-)
    • By MonterMan
      Hi all. I have been looking for a real-time global illumination algorithm to use in my game. I've found voxel cone tracing and I'm debating whether or not it's an algorithm worth investing my time researching and implementing. I have this doubt due to the following reasons:
      . I see a lot of people say it's really hard to implement.
      . Apparently this algorithm requires some Nvidia extension to work efficiently according to the original paper (I highly doubt it though)
      . Barely real-time performance, meaning it's too slow to be implemented in a game 
       
      So in order to determine if I should invest time in voxel cone tracing, I want to ask the following questions:
      . Is the algorithm itself flexible enough so that I can increase the performance by tweaking it (probably lowering the GI quality at the same time, but I don't care)
      . Can I implement it without any driver requirement or special extensions, like the paper claims?
    • By shintiger
      I understand what stationary OBB intersection test is get min/max scalar in 15 axises, when all overlap, then minimum interval overlapping is the axis that used to push away 2 OBBs to "just touch". I have complete this.
      So in sweep test, how to choose the right axis projecting and how every projection transform? I only need a ratio of current velocity when start intersect from disjoint.
      I have read Ron Levine's post:
      http://www.realtimecollisiondetection.net/files/levine_swept_sat.txt
       
      And oliii's:
      I get the code but cannot get it works as expect when port to my project, even I don't clearly know what params refer to.
       
      For further optimization, I wish somebody can teach me how velocity part works conceptually instead of just code.
      My case is DOBB-OBB only(dynamic to stationary).
    • By Octane_Test
      I am developing a cross platform game for which I needs to generate unique identifier (User ID) for each user. I known some platform (Android or iOS) specific approaches to get device related identifiers but I am looking for a solution independent of the device identifiers.
      User ID Requirements:
       1. Independent of the device's platform
       2. Offline implementation (no communication with any servers)
       3. Without sign-up process
      I have implemented one approach to create User IDs where I store the system time when the game was launched for the first time on the device.
      I have following questions:
       1. Are there any other approaches to generate User IDs (which will meet the above requirements)?
       2. What are the common approaches to create unique identifiers with taking any information from the user?
       3. Are there any third party plug-ins to implement User IDs?
      I would appreciate any suggestions and thoughts on this topic.
      EDIT:
      There are lot of responses to use UUID/GUID. Generally, this approach looks fine but I am looking for a solution which can generate same User ID even if the user reinstall the game.
  • Advertisement