Jump to content
  • Advertisement
Sign in to follow this  
TheComet

O(pow(N,12))

This topic is 1388 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Advertisement

I assume you're referring to the GenerateIndexVertexBuffers method. That's a monster, codewise, but in terms of complexity, I think it's just O(n3), not O(n12). The inner nine loops all have a small, constant range (e.g. x to x+1).

 

But wow. That's pretty awful-looking. Almost as bad as the Sudoku-solving program I wrote when I first learned C (that had a series of 18 for loops and 8 if statements directly nested together at its worst point).  This beats my solver in terms of crazy nesting. I never thought I'd see this day.

Share this post


Link to post
Share on other sites

in  generateIndexVertexBuffers()   use either a  GOTO  or ELSE IF  to skip code when the condition becomes  canBeSeen = true;

 

(your mileage with your compiler may vary so try both ways and profile/speed test each way to find which one is fastest)

 

 

 

For those  indents in   // brute force against the VoxelCloud

 

the multiple tests  like   if( basex + ox1 + ox >= x )   can be one ANDed  IF statement

 

if (( basex + ox1 + ox >= x ) && ( basex + ox1 + ox <= x + 1 ) && ( basey + oy1 + oy >= y ) && 

   &&  ( basey + oy1 + oy <= y + 1 ) && ( basez + oz1 + oz >= z ) && ( basez + oz1 + oz <= z + 1 )    etc...

 

to eliminate alot of that gross indentation for the meat of the loops  (the compiler should be smart enough to quick exit on the first false clause   (at least as that logic is now ....if you cant simplify that logic/loops drastically)

 

 

more indent elimination for the similar logic clauses  :

like  if( mVisVoxelStructure[basex][basey][basez]->mExist == true )   can be ANDed    '&&'   and dont need so much indenting

 

 

you might also crush out alot of duplicate math by having some    temp variables    like   

basex_ox = basex + ox         done once higher in the loops   (the compilker probably does this, but it can make your code less bulky looking)

 

--------

 

You should be able to move some of those massivlely nested loop test higher into the nesting structure to eliminate alot of unneeded processing

 

if( mVisVoxelStructure[basex][basey][basez]->mExist == true )   should goimmediately within the level of the  basex,basey,basez  loops as there is no point running the tests beyond that for those loop values  if the voxel point there doesnt exist

 

look at the patterns and you will probably find similar higher repositionings for the

if( mVisVoxelStructure[basex + ox][basey + oy][basez + oz]->mExist == true )

and

if( mVisVoxelStructure[basex + ox + ox1][basey + oy + oy1][basez + oz + oz1]->mExist == true )

and the others too

 

----

 

Another possible Simplification   -- you have a very small regular pattern    of combinations of  {0..1}  and  {-1..1} for 3 nested XYZ variables   and there might be a way of having those offsets be static in several arrays which only a single loop need traverse   (short enough combinations that you might be able to do that (static) for 6 range variables in one loop

 

 

For me (something Ive done to speed things up even more) was with fixed array sizes for the asteroid data to do pointer offsets arithmetic  staticized to eliminate the overhead of multiple dimension arrays -- but again that wound NOT work if you are applying this to a more generalized solution  (ie  ASTEROID_SIZE  being variable to any size)

 

-----

 

 

You also might want to use a 1 cell deep empty boundry around your asteroid data  to eliminate the need for the missing boundry checking  (and adjust all your loops accordingly)  as some of your offsets appear to sometimes try to access the array with coordinate  values of      -1     or  ASTEROID_SIZE     which would go outside the proper array ranges and be incorrect (if they didnt cause a segment fault)

Edited by wodinoneeye

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!