1 Replies - 786 Views - Last Post: 14 July 2012 - 04:37 AM Rate Topic: -----

#1 BetaWar   User is online

  • #include "soul.h"
  • member icon

Reputation: 1513
  • View blog
  • Posts: 8,295
  • Joined: 07-September 06

[Discussion] Culling objects quickly and efficiently

Posted 14 July 2012 - 12:09 AM

tl;dr?:: What types of culling do you employ to quickly narrow down the number of objects you have to look at before drawing them to the screen?

I recently dove into OpenGL in an attempt to learn it, and possibly make some money along the way. As a first project I figured that a simple Minecraft clone would be in order, so that meant drawing blocks, lots of blocks, quickly and efficiently to the screen.

NOTE - Though I am using OpenGL I don't expect you to also be using it to participate in this discussion, it is just what I picked up first.

Now, I am not going to talk about the ways to draw the blocks, that is a topic for another place (well, the same place, but another thread) and another time. Instead I am going to open a discussion about how to cull out massive numbers of blocks quickly and easily before even having to determine what is going to be visible. After all, the lower the number of blocks you have to look at to determine if they are visible or not the quicker you should be able to get an image to the screen.

So far I have come up with two ideas and have employed both of them, at least in part, to determine what should be culled and what should be kept around for a chance at being drawn to the screen (though in actuality, at the moment I am just drawing everything that isn't culled out and will worry about what is actually visible later on).

The first idea was to simply create a 3D mesh for a "bounding object" and determine if any given block is at least partially within the "bounding object". This is accomplished by some nifty vector-based dot and cross product and works wonderfully. However, as is normally the case with things of this nature, it also seems to reduce the frame rate that the game is getting to about 6 FPS (not ideal, obviously).

The second idea was to use the player's current position and facing direction to come up with a few triangles in 3D space which could then be used, with a few equations, to determine if a given point was within them or not. This seems to run faster overall, but is significantly harder to set up and more prone to error with even simple changes. Not to mention that you basically need a separate function for each of the 4 cardinal directions to get it working remotely properly. I receive about 7 FPS here, so not a huge improvement, but considering that these FPS readings are based off an Ubuntu virtual machine with no 3D hardware support (as VMWare doesn't have 3D acceleration for linux-based VMs at the moment) I think it is a pretty good improvement.

That being said I have chosen to go with the bounding object method for the time being and am hoping to modify it, or otherwise find a way to further speed it up at some point in the future (this thread may help with the theory there). As the game progresses though I could have up to (absolute maximum, also impossible to reach) 8 million blocks to look through and cull out before drawing to the screen, so a quick and efficient method of narrowing the selection is essential.

Now, to the discussion: What types of tricks do you employ when needing to cull out objects quickly? What have you found to work nice, and what is simply more headache than it is worth? How many objects do you typically draw to the screen at a given shot? What types of cutoffs do you use?

And, for getting this far, your prize:
Attached Image
Yes, that is a nice, simple visual representation of the two methods I spoke of above. Enjoy.

Is This A Good Question/Topic? 3
  • +

Replies To: [Discussion] Culling objects quickly and efficiently

#2 anonymous26   User is offline

  • D.I.C Lover

Reputation: 2
  • View blog
  • Posts: 3,638
  • Joined: 26-November 10

Re: [Discussion] Culling objects quickly and efficiently

Posted 14 July 2012 - 04:37 AM

A very interesting topic, with an interesting use of culling with a subspace clipping technique.

When looking to cull large amounts of on-screen objects there are several questions you should ask yourself first:

1. How computationally expensive is the algorithm I'm using?
2. Is there a sweet spot for balancing the number of objects on screen whilst maintaining performance?
3. What is the minimum number of objects that I can have on-screen at any one time to maintain aesthetics but reduce computation load and make <insert culling algorithm here> actually redundant.

Why these questions? It is often misconceived by people writing games that the objective of a good game engine of any kind is to be able to do a huge amount without a performance hit, this isn't true. If you have an expensive algorithm doing anything you are affecting the performance of the overall game and not just the graphics system for example. What you in fact should be aiming for is how to approach the best and not necessarily ideal solution to a problem using a very inexpensive algorithm. This is the challenge.

Question (1) should always be your first question whenever trying to solve an interesting problem like this. As soon as you can spot a performance bottleneck with an algorithm, scrap it and look for alternatives.

Question (2) is important if there is no elegant solution. Generally, if an algorithm is complicated and cannot be significantly refined then you reduce the amount of data that has to be manipulated using the algorithm. This will involve the removal of some objects on screen that would otherwise be processed, and finding an alternative, simple way of approximating the same effect.

Question (3) is a question that you should always ask yourself without exception, and kind of leads on from (1). When writing games you are trying to omit complexity, not introduce it. An example being for me at work yesterday, I was presented with a problem, I found a solution that any college kid could understand but it had a profound effect! This should always be your goal. Game programming is about finding simple solutions for maximum effect.

Look at any game out there, even the most beautiful looking have a compact view volume. Why? Because no matter how powerful the hardware platform is, a game can find ways of pushing that platform to its limits.

Have fun! :)
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1