Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (499)
Games in Android Showcase (118)
games submitted by our members
Games in WIP (568)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Calculating pairs in an octree  (Read 4700 times)
0 Members and 1 Guest are viewing this topic.
Offline lhkbob

JGO Knight


Medals: 32



« Posted 2010-09-08 06:25:02 »

I'm extending the code in an octree I wrote for my graphics engine to have the ability to return all pairs of intersecting objects (by axis-aligned box) for use in a physics engine I'm working on. The octree can contain data elements at non-leaf nodes (i.e. so that data overlapping two leaves is stored in those leaves parent, etc.). This means that only one node ever contains a data element at a time.

The obvious way of figuring out all of the pairs seemed to be:
1  
2  
3  
4  
1. Start at the root node
2. Go through every element in the node and intersect with elements in node (doing smart so we don't duplicate intersection tests).
3. Test every element in the node with all of the elements in the node chain back up to the root
4. Go to #2 with every child node of the current node


Hopefully I explained it well enough.  The algorithm as described works, and is faster than brute force, and faster than doing an octree query for each object in the scene to see which things it intersects with.

My question is whether or not there better approaches to this when using an octree? (I'm not interesting any of the sweep and prune strategies that exist for collision detection).

Offline Nate

JGO Kernel


Medals: 149
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #1 - Posted 2010-09-08 08:00:21 »

Hello, this is great article. I have blog and I thanks to say you thanks. Regards!

Offline Jono
« Reply #2 - Posted 2010-09-08 08:32:47 »

Hello, this is great article. I have blog and I thanks to say you thanks. Regards!
a) Nate's been hacked?

b) For the oct-tree, there are obviously some unnecessary comparisons that are going to be made against elements in the ancestor nodes:

Where the left shows elements in a leaf node, the middle shows elements of its parent, and on the right its grandparent. The nodes in red will be compared against, but don't need to be.

Perhaps you could have each non-leaf node know its height, and to separate its elements up (so into 4 buckets for the height 1 parent, 8 buckets for the height 2 grandparent). There would have to be more house keeping to associate child nodes with their relevant buckets, but it might be worth it.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #3 - Posted 2010-09-08 08:34:11 »

Hello, this is great article. I have blog and I thanks to say you thanks. Regards!
>_BANHAMMER DEPLOYMENT ACTIVATED
>_CHARGING.....
>_!!!EMERGENCY ABORT!!!

As to the octree: I can't see any better way of getting all intersection pairs in general.

I can see one optimisation, but I'm not convinced it'll be terribly useful in the context of a physics engine. At any rate: At each node, check for collisions in descending order of object volume. If you find that an object A lies entirely within another object B, then from that point on you can restrict the search for objects that intersect with A to those that have already been found to intersect B, rather than every other object in that node and above.
However, in a physics engine I imagine that one object lying entirely within another is something that you're trying very hard to avoid. Tongue
Online Roquen
« Reply #4 - Posted 2010-09-08 08:58:40 »

This is more a "food for thought" post.  I've always used data only in leaf strategy, where leafs contain edge data.  Nodes that share an edge are maintained to be within one depth level of one another.  So when you are doing neighborhood queries you only walk edges that your bounding volume crosses and each edge will "lead" to either one or two neighbor nodes.  One trick here is the question of scale and dealing with objects which exists in multiple nodes.  BUT:  I've only done this in native where a primary goal is memory reduction and I haven't thought about it in a java context.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 803
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #5 - Posted 2010-09-08 12:11:22 »

lhkbob: your approach will lead to a lot of items in the root node (or in any parent-node)

Imagine a forest: lots of trees uniformly spread in a huge world (say 100*100km). All trees overlapping the center axes of the root node OR the world-edge, will be stored in the root:

1  
2  
3  
4  
5  
6  
7  
___________________
|        |        |
|        |        |
|________|________|
|        |        |
|        |        |
|________|________|


Let's do some simple math: let's say the world is filled with (about) 1 tree per 3*3m. As you walk in a straight line through the forest, you'll encounter a tree every 3m. There are 6 lines through your world that would resemble the intersection-lines of the root-node, that - if intersected - would cause the item to be put in the root node: 6 100km long lines. A tree every 3m: 6*(100.000/3) = 200.000 trees in your root node.

Ofcourse the same applies for any parent node: it will hold a LOT of items that intersect the child-node edges.

Keep in mind that the above example is more like what happens in a quadtree. In an octtree the problem is (obviously) worse, as you have not 6 but 24 intersection-lines that will cause any object to be stores in the parent (of the parent (of the parent (of the ...))).

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline lhkbob

JGO Knight


Medals: 32



« Reply #6 - Posted 2010-09-08 13:46:22 »

If I store all of my data at the leaves, I'd have to have elements present in multiple leaves at the same time. This makes it a lot harder to keep out duplicates when searching through the tree.  Does it turn out that the better distributed tree is worth the extra bookkeeping?

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 803
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #7 - Posted 2010-09-08 13:53:48 »

In my (ancient) forest-render, I simply used a HashSet while collecting items from the tree.

Another approach I used, allowing some margin of error, but was blazingly fast, was to only store items in the leafs, solely based on position (ignoring bounding boxes), and make the frustum volume slightly larger to account for the 'general volume of an item'. Ofcourse you'd have to limit the bounding volume of items, but in my code everything was smaller than 10m, and if larger, I cut it in pieces. Advantage of that is that you can render only parts of big items.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline lhkbob

JGO Knight


Medals: 32



« Reply #8 - Posted 2010-09-08 15:21:07 »

Another issue with everything in the leaf nodes is that updating moving elements, or removing them can be expensive because you don't know all of the nodes they're part of without doing a query.

I'm thinking I can use my current octree for dynamic objects and do a leaf-only octree for static shapes.  It's likely that a single moving object will not stay across any axis for that long so the drawback to my structure isn't too bad (and has fast updates). I could even do something to detect how much something seems to move and automatically choose which tree to place it in.

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 803
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #9 - Posted 2010-09-08 15:37:05 »

As said, if you use the second approach, you only have to find 1 leaf. Princec used the slightly 'bad' but super-fast way to store the current-leaf in every unit. That way you can instantly find it, which is always faster than whatever clever algorithm you come up with.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline princec

JGO Kernel


Medals: 391
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #10 - Posted 2010-09-08 16:51:33 »

Yep, that way works a treat, means the fastest possible removal. I still have the problem of when things fall across quadtree boundaries pushing some objects way way up into a much larger quadrant than they need to be in but I also reasoned that the number of such objects is also very small in reality so it was a tradeoff that I could live with.

I could instead make objects part of each quadtree node that any of their corners live in and maintain 4 pointers to these nodes, which would still allow for extremly fast removal and then I think I could get rid of the need to push entities up into bigger nodes than they needed to be in. But then when doing a query on the tree I'd have to cull the duplicates.

Cas Smiley

Offline lhkbob

JGO Knight


Medals: 32



« Reply #11 - Posted 2010-09-08 17:37:21 »

Culling duplicates might be the way to go.  With a scene of 10000 randomly placed same-size cubes, I get about 8500 in non-leaf nodes and only 1500 in the leaf nodes.  Of course that's not 8500 at the root node, but it seems pretty bad.

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 803
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #12 - Posted 2010-09-08 17:40:59 »

"Told you so" Tongue

As you keep subdividing the tree, the chance that an item intersects an edge, eventually converges to 1.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline princec

JGO Kernel


Medals: 391
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #13 - Posted 2010-09-08 18:53:30 »

an edge is fine... it's just certain edges which are the problem.

Cas Smiley

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 803
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #14 - Posted 2010-09-08 18:58:59 »

No, every edge causes the item to be moved to the parent node. if the parent node shared that edge (50% chance) it will be moved to the parent-of-the-parent, if that parent shares that edge (50% of 50% chance) the item will be... etc etc.

This happens in all nodes, and as lhkbob discovered, 85% of all items ended up in non-leafs. As you fill your world uniformly with items, you'll reach 99% pretty quickly.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Online Roquen
« Reply #15 - Posted 2010-09-09 06:15:38 »

Another issue with everything in the leaf nodes is that updating moving elements, or removing them can be expensive because you don't know all of the nodes they're part of without doing a query.

This is one of the reasons I like an edge based representation.  You almost never need to walk the tree.

If the majority of the dynamic objects are bound within a given bounding size, the you can store these objects in a single leaf.  You have the added constraint that the lowest level of the region kd-tree is the bounding volume just large enough to enclose this maximum size.  For the purpose of determine the set of nodes to visit you simple add half this bounding dimension.  Larger objects can be handled either in an aux data structure or by proxy objects which are stored in multiple leaves.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Pippogeek (40 views)
2014-09-24 16:13:29

Pippogeek (31 views)
2014-09-24 16:12:22

Pippogeek (21 views)
2014-09-24 16:12:06

Grunnt (47 views)
2014-09-23 14:38:19

radar3301 (29 views)
2014-09-21 23:33:17

BurntPizza (65 views)
2014-09-21 02:42:18

BurntPizza (37 views)
2014-09-21 01:30:30

moogie (44 views)
2014-09-21 00:26:15

UprightPath (53 views)
2014-09-20 20:14:06

BurntPizza (55 views)
2014-09-19 03:14:18
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!