Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualAllEightUp

Posted 20 April 2013 - 12:18 PM

There are a number of ways to generate the sectors concept ranging from really simple to fairly complex.  As LJ mentions, using a simplified concept such as a quad/octree can give you benefits in this area.  Say with a quad tree you are simply looking for elements completely contained in a quad area (no overlap with other areas), interactions between one and another quad are completely ignored since there is no overlap.  So, say you have 4 objects in quad 1, 4 objects in quad 2 and 4 objects straddling the division.  Normally you have (n-1)*n interactions possible without the quad tree, i.e. (12-1)*12=132.  With 4 objects in quad one, they have to consider themselves and the straddlers, but we leave the straddlers to check interactions between themselves so the equation is (n-1)*(n-s) where s is the straddler count, n is in quad 1 and the straddlers, or in this case: 7*4=28.  The same for the second quad.  And finally check the straddlers against each other for (4-1)*4=12.  So, the total checks needed is down to 2*28+12=68 checks.

 

Not a bad reduction for a simple method of regrouping the data.  (NOTE: May have messed up the general descriptions, but it should be fairly close to correct I believe.)

 

More complicated solutions exist and can get better gains. But, as said, they are more complicated.  I did a system which sat on top of my sweep and prune implementation which did a very nice job (used for something not directly related to reducing interactions since I already had that in the sweep and prune).  But it was a considerable bugger to write and debug.  You probably want to stick to the simple suggestions.


#1AllEightUp

Posted 20 April 2013 - 12:16 PM

There are a number of ways to generate the sectors concept ranging from really simple to fairly complex.  As LJ mentions, using a simplified concept such as a quad/octree can give you benefits in this area.  Say with a quad tree you are simply looking for elements completely contained in a quad area (no overlap with other areas), interactions between one and another quad are completely ignored since there is no overlap.  So, say you have 4 objects in quad 1, 4 objects in quad 2 and 4 objects straddling the division.  Normally you have (n-1)*n interactions possible without the quad tree, i.e. (12-1)*12=132.  With 4 objects in quad one, they have to consider themselves and the straddlers, but we leave the straddlers to check interactions between themselves so the equation is (n-1)*(n-s) where s is the straddler count, n is in quad 1 and the straddlers, or in this case: 7*4=28.  The same for the second quad.  And finally check the straddlers against each other for (4-1)*4=12.  So, the total checks needed is down to 2*28+12=68 checks.

 

Not a bad reduction for a simple method of regrouping the data.  (NOTE: May have messed up the general descriptions, but it should be fairly close to correct I believe.)


PARTNERS