• Advertisement
  • Popular Tags

  • Popular Now

  • Advertisement
  • Similar Content

    • By akshayMore
      Hello,
      I am trying to make a GeometryUtil class that has methods to draw point,line ,polygon etc. I am trying to make a method to draw circle.  
      There are many ways to draw a circle.  I have found two ways, 
      The one way:
      public static void drawBresenhamCircle(PolygonSpriteBatch batch, int centerX, int centerY, int radius, ColorRGBA color) { int x = 0, y = radius; int d = 3 - 2 * radius; while (y >= x) { drawCirclePoints(batch, centerX, centerY, x, y, color); if (d <= 0) { d = d + 4 * x + 6; } else { y--; d = d + 4 * (x - y) + 10; } x++; //drawCirclePoints(batch,centerX,centerY,x,y,color); } } private static void drawCirclePoints(PolygonSpriteBatch batch, int centerX, int centerY, int x, int y, ColorRGBA color) { drawPoint(batch, centerX + x, centerY + y, color); drawPoint(batch, centerX - x, centerY + y, color); drawPoint(batch, centerX + x, centerY - y, color); drawPoint(batch, centerX - x, centerY - y, color); drawPoint(batch, centerX + y, centerY + x, color); drawPoint(batch, centerX - y, centerY + x, color); drawPoint(batch, centerX + y, centerY - x, color); drawPoint(batch, centerX - y, centerY - x, color); } The other way:
      public static void drawCircle(PolygonSpriteBatch target, Vector2 center, float radius, int lineWidth, int segments, int tintColorR, int tintColorG, int tintColorB, int tintColorA) { Vector2[] vertices = new Vector2[segments]; double increment = Math.PI * 2.0 / segments; double theta = 0.0; for (int i = 0; i < segments; i++) { vertices[i] = new Vector2((float) Math.cos(theta) * radius + center.x, (float) Math.sin(theta) * radius + center.y); theta += increment; } drawPolygon(target, vertices, lineWidth, segments, tintColorR, tintColorG, tintColorB, tintColorA); } In the render loop:
      polygonSpriteBatch.begin(); Bitmap.drawBresenhamCircle(polygonSpriteBatch,500,300,200,ColorRGBA.Blue); Bitmap.drawCircle(polygonSpriteBatch,new Vector2(500,300),200,5,50,255,0,0,255); polygonSpriteBatch.end(); I am trying to choose one of them. So I thought that I should go with the one that does not involve heavy calculations and is efficient and faster.  It is said that the use of floating point numbers , trigonometric operations etc. slows down things a bit.  What do you think would be the best method to use?  When I compared the code by observing the time taken by the flow from start of the method to the end, it shows that the second one is faster. (I think I am doing something wrong here ).
      Please help!  
      Thank you.  
    • By ethancodes
      I'm working on an endless wave-based arkanoid/space invaders style hybrid. Bricks spawn above the screen and move down line by line. You must destroy all bricks before they hit the bottom of the screen. There will be multiple types of bricks and random power-up spawns. Currently I am just using a simple Log function that takes in the current wave as a parameter. This works to increase the number of bricks spawned each wave, but I want to find a way to make this much more complicated. Here is a list of everything that should be effected by the increase in difficulty:
      1. Number of bricks
      2. Types of bricks (1 hit bricks, 2 hit bricks, 3 hit bricks, etc.) 
      3. Speed that the bricks move down the screen
      4. How often power-ups spawn
      The biggest problem here is that I can't just increase all of these with each new wave. If I did that, it would quickly become far to difficult. What I would like is an algorithm that gives some amount of variance in the increase between all 4 of these. Say one wave we put 60% of the increase to number of bricks, 20% increase to power-up spawns, 10% to types of bricks and 10% to speed of bricks. But on the next wave those percentages are all moved around and we now have say 105% to work with so the overall difficulty has increased as well. The different types of bricks need to also change to the point where if someone has made it to a certain wave, such as wave 50 for example, there are no longer any 1 hit bricks. We now would have just 2-4 hit bricks, and if they are crazy good and make it all the way to round 100, Now it's just 3-5 hit bricks, etc. 
      If anybody has any good ideas or suggestions on this, I'd appreciate anything you've got! Thanks!
    • By fazook
      Hi, guys!
      I have a rather abstract question, because I don't know which side to approach to its solution. So, I would appreciate any information.
      I have a task to create a simple game that generates floor plans and I following by this perfect algorithm (https://www.hindawi.com/journals/ijcgt/2010/624817/). At the moment I use squarified treemaps (http://www.win.tue.nl/~vanwijk/stm.pdf) and here no problems. I create nested array in which elements are rooms with size. Problems starts when I trying to represent generated "rooms" as edges and vertexes (a, b, c, d steps in attached picture) That representation can give me access to this elements as special "entities" in future game versions.
      I don't have skills in graphs (and do I need graphs?) and at the moment totally stucked at this step. How can I represent room walls as trees (or graphs?) at this step? Calculate size of squares (rooms) and convert sides to a vectors? Then in loop find shared vectors (same position by "x" or "y") and determine them as shared walls? The instinct tells me that there exist more elegant and efficient ways.
      Anyway, thanks for any information about this.

    • By Januario
      Hey guys!,
      So, I'm basically working on an explorer right now.
      It should, as the name suggests, explore the entire thing, the most efficient way possible.
      Your character has vision around you, of, 10x10. The map is much bigger, 100x100. However, it can't just go straight from a corner to another, because: The tiles can be an occupied, or un-occupied one. You can add weights to the tiles, so feel free to use this in your advantage (let's say, adding an extra weight to a visited tile so you can compare visited against non-visited ones). You can use the Pathfinder I'm using, based on the A* algorithm. So, I could be wrong, but by basic logic, I assumed that the "fastest way" to explore the entire thing, is answering the question "What is the nearest tile that I can walk in, that is not occupied and that can reveal as much fog-of-war (unvisited tile) as possible?"...
      My questions are:
      1) Is my question correct? is that really the best way to explore the entire map? 2) If so, what's the best way to know "which is the tile that could reveal the most fog of war"? Once I get the tile that reveals the most fog of war possible, then I just throw the pathfinder to it.
      But I'm having problems doing a good way to achieve that :'( 
      I hope you guys can help me on this one! 
      Thank you
    • By Scouting Ninja
      So what is up? What did I miss?
      I finally get my PC working and am bombarded with emails asking about marching cubes. Get on Gamedev.net and it's even here people are researching marching cubes. All of the gaming forums is a buzz with players theories on how marching cubes work, developers looking for teams to build a marching cube games.
      So why the spike? Reminds me of when Minecraft released.
  • Advertisement
  • 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