Thread: Updated space game

  1. #16
    Personally, I'm just using bounding sphere testing, after the initial Quad-Tree branch discard, for the per-object frustum cull. It's trivial, and it took about 2 1/2 minutes to implement. I didn't think there was the need for higher accuracy culling in an instance like this. Just a thought.
    "There's always another way"
    -lightatdawn (lightatdawn.cprogramming.com)

  2. #17

    Join Date
    May 2005
    Posts
    1,042
    Yeah I would definitely implement the bounding sphere test first, if nothing else to help narrow down the problem. I only use bounding box tests to cull leafs in the world, where you really need the higher accuracy.
    I'm not immature, I'm refined in the opposite direction.

  3. #18
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    You guys are right. I'm going to use spheres. I don't really need super accurate bounding tests for an FPS space genre game. I do have another question relating to this.

    Do you guys think that a simple distance cull would be sufficient for this type of game? Normally I deal with terrain where some type of spatial partitioning exists like a quadtree or something else. I'm not quite sure what to use here. My thinking is that at most there might be 100 objects (100 bounding volumes that is) in any one sector. Once the bounding volume is close enough then I'll begin rendering what is inside the volume. I may have to use a quadtree or something inside of asteroid fields, but for the most part a simple iterate and check should be sufficient.

  4. #19

    Join Date
    May 2005
    Posts
    1,042
    Naw, I would at least use a bounding sphere test. I mean, what you're suggesting'd probably work out reasonably well enough, but your frustum ought to have a front and back plane to it, therefore the distance test is kind of implied within that method. Besides, the bounding sphere test is fast and trivial enough, so why not use it? Feel free to post code if you're still having problems with it (that really shouldn't be your hang up, although the math for it is interesting).

    EDIT:
    wait, are you talking about culling other spacecraft, or the universe objects (asteroid belts, planets, etc). I answered above as if you were talking about things like spacecraft. I think a quadtree would be a good approach, and a robust implementation can handle large slow-moving things that are transitioning between leafs in the quadtree, by re-linking the entity to the world. If you do take this approach be sure to handle the case where the object spans the plane and momentarily resides in two (or even more) leafs. I've got the implementation for this type of thing worked out for BSP (havent done terrain stuff), but I believe the approach should basically be the same.
    Last edited by BobMcGee123; 03-23-2008 at 01:57 AM.
    I'm not immature, I'm refined in the opposite direction.

  5. #20
    My reason for the spacial partitioning (BSP tree or whatever you're using) was not just for fast culling, but also for collision detection. My initial thought was the same as yours, there would be few objects and I might be able to avoid the complication. I realised however, that since most of those objects are going to be in motion, the number of collision checks per frame was going to be high. I needed a method to easily reduce the working set of testable objects.

    >>be sure to handle the case where the object spans the plane and momentarily resides in two (or even more) leafs.

    I handled this in a slightly unusual way, but it was easy to implement, works quickly, and it works. If an entity does not fit fully inside a node of the tree, the object is placed inside the node 1 resolution above the current node. This obviously means that there are times where an entity is residing inside a space that is checked against by many other entities, but the occurance is small and since the initial tests are sphere based, the penalty is low. I haven't run any other algos to test the speed against, but my assumtions are that it would be comparable enough to hold water. How do you handle this situation?
    "There's always another way"
    -lightatdawn (lightatdawn.cprogramming.com)

  6. #21

    Join Date
    May 2005
    Posts
    1,042
    I needed a method to easily reduce the working set of testable objects.
    A super fast/easy check is to create a bounding sphere that encapsulates the move, from the desired_pos - current_pos vector, then just do a radius^2 check between the two objects you are doing a collision detection for. The move between frames will be small, and this test actually tends to require fewer calculations than traversing a bsp/quad/octree to find the leaf that something resides in. After that, if you choose, you can dot these two vectors together, because there are cases where they may be inside this imaginary bounding sphere but the objects are moving away from each other (just test the sign of the dotproduct). No normalizing, don't need to traverse a partitioning tree.

    As of right now in my little Hovercraft simulation this is how I 'cull' collisions between moving objects.

    EDIT:
    >>works quickly, and it works
    Then it's a good implementation and I wouldn't dream of changing it!
    Last edited by BobMcGee123; 03-23-2008 at 03:13 PM.
    I'm not immature, I'm refined in the opposite direction.

  7. #22
    Workable for a small scale loaded world, but when the loaded set of entities begins to reach into the thousands, and most of these objects (in my case) are in some way moving, then you're testing 1000 entities against 1000 entities (999 I suppose ). My entities track their own location in the Tree. This requires a slightly higher memory hit per entity, some initially difficult code, and an annoying cross-dependancy between entities and the Tree, but the result is that the entity being checked can jump straight into the node that it resides in, check against the objects there, and be done with it quickly.

    I do like the simplicity of your encapsulated move-sphere though, as I'm currently having a hell of a time debugging collision irregularities with my system. I think sometimes that a small frame time hit would be outweighed by code that is easy to write, maintain, and debug.
    "There's always another way"
    -lightatdawn (lightatdawn.cprogramming.com)

  8. #23

    Join Date
    May 2005
    Posts
    1,042
    What type of tree are you using, dawn? Also, when you say 'keeping track of their location in the tree,' doesn't this require a bit of calculations (plane traversals)? For each node in your tree, do you also store the parent node such that you can traverse up the tree? The way you described it that is what it seems you are doing.
    I'm not immature, I'm refined in the opposite direction.

  9. #24
    The engine can handle Quad Trees or Oct Trees. I'm using Oct Trees due to the 3D nature of the space. And yes, each node (CDynamicTreeNode) contains data in this form:

    Code:
    	CDynamicTreeNode * pStem;
    	CDynamicTreeNode * pBranch[EM_TREE_BRANCHES];
    
    	CSafeList<CEntity *> slEntityList;
    	unsigned int ParentID;
    So a jump into any location in the Tree will allow the caller to start traversing to anywhere else in the tree. Not the standard method I know, but it made sense in the context of my engine. Having never recieved any kind of formal education in programming, I tend to come up with some unorthodox solutions at times.

    And how goes the frustum culling, Bubba?
    "There's always another way"
    -lightatdawn (lightatdawn.cprogramming.com)

  10. #25
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Ok couple of updates.

    I never got AABB culling working but I think I found out why. Switching to bounding spheres also did not work right. Objects would display then suddenly cull out and never come back.

    I printed out the positions of all the objects and found nothing out of whack. When I printed the world coords of the bounding sphere's everything went crazy.

    I was essentially doing this:

    Code:
    ...
    D3DXVECTOR3 trans;
    D3DXMatrixTranslation(&matTrans,trans.x,trans.y,trans.z);
    
    D3DXVec3TransformCoord(&m_vecPos,&m_vecPos,&matTrans);
    ...
    The meshes always started in model space around 0.0f,0.0f,0.0f and thus a translation would translate them to their world space. However the AABBs and Spheres would start in model space only once and then their world space coords would be set. So the next time through I thought I was performing a model space to world space transform, but in reality it was a translation from one world location to another world location using the current location as the translation vector. The solution is to either keep the AABBs and spheres in model space and thus the world transform then works as expected just like the meshes or only update the AABBs and sphere's world coords when they change.

    Thanks all for your help.
    Last edited by VirtualAce; 03-12-2011 at 11:41 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Out of space when compiling kernel
    By NuNn in forum Linux Programming
    Replies: 3
    Last Post: 04-01-2009, 02:43 PM
  2. HELP!wanting to make full screen game windowed
    By rented in forum Game Programming
    Replies: 3
    Last Post: 06-11-2004, 04:19 AM
  3. Game Programmer's AIM Circle: Join Today
    By KingZoolerius66 in forum A Brief History of Cprogramming.com
    Replies: 28
    Last Post: 12-20-2003, 12:12 PM
  4. Galaxian or Space invaders for my next game (read this)
    By Leeman_s in forum C++ Programming
    Replies: 7
    Last Post: 11-07-2001, 09:28 PM