# O(pow(N,12))

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

## Recommended Posts

So what ? It's only polynomial

... what?

##### Share on other sites
This somehow reminds me of the lugaru source code that was posted here a while ago.

##### Share on other sites
...so much indentation...

##### Share on other sites

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 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 on other sites

I think I just bled a tear :(

##### Share on other sites

So much for an 80 column limit.

1. 1
2. 2
Rutin
23
3. 3
4. 4
5. 5
khawk
14

• 9
• 11
• 11
• 23
• 11
• ### Forum Statistics

• Total Topics
633653
• Total Posts
3013158
×