Optimizations

marcov · Post by **marcov** » Apr 12, 2011 9:18

agamemnus wrote:
marcov wrote:
agamemnus wrote:
The reason for macros is because the code inside Gonzo's for loop should not have to be repeated more than once...
It's like fixing a small bad with a big one :-)
???? :\

Replacing minor Code duplication with a macro I mean.

Gonzo · Post by **Gonzo** » Apr 12, 2011 19:37

it's true i could separate this into 2 versions, where 1 is running 8 sides and the other straight 0 to x-1
but, as it happens its a very complex operation and i don't want spaghetti code :)
i will simply have to live with nested if's that worked better
or find a completely different way to iterate sectors, which i havent yet

im guessing that if's by themselves cost alot, which makes sense if the cpu likes to execute line by line
so thats what i always aim for, but saving at least some of the average 2k iterations for a world that constantly has 131k sectors is a constant battle :)

rolliebollocks · Post by **rolliebollocks** » Apr 13, 2011 0:07

it's true i could separate this into 2 versions, where 1 is running 8 sides and the other straight 0 to x-1
but, as it happens its a very complex operation and i don't want spaghetti code :)

Well, that's where the macro would come into play. You have spaghetti code with GOTO nxt, you can get rid of that by setting up two different loops, it would probably be easier to read. Set it up as a macro and it's even easier to read.

My bad, agamemnus.

agamemnus · Post by **agamemnus** » Apr 13, 2011 4:05

Gonzo wrote: so thats what i always aim for, but saving at least some of the average 2k iterations for a world that constantly has 131k sectors is a constant battle :)

2k per frame, or 2k per sector?

rolliebollocks wrote:My bad, agamemnus.

DW. You're my homie.

Gonzo · Post by **Gonzo** » Apr 13, 2011 5:26

its 2048 iterations per sector (which is a total of 131072 at any time)

agamemnus · Post by **agamemnus** » Apr 13, 2011 19:21

Well, that's pretty bad. Is there any reason why you need to iterate through empty blocks? Do you iterate through empty sectors?

Gonzo · Post by **Gonzo** » Apr 14, 2011 15:55

agamemnus wrote:Well, that's pretty bad. Is there any reason why you need to iterate through empty blocks? Do you iterate through empty sectors?

no, i dont iterate nullsectors :)
i also don't iterate hidden sectors (covered by hardsolids (see first post))
but how else could i do it :P i dont know any fancy algorithms for doing something that theres literally no other way to do
i have to iterate through every block to calculate its visible faces

there are some cases where i iterate an entire sector and get 0 visible faces, but thats impossible to predict

agamemnus · Post by **agamemnus** » Apr 14, 2011 23:08

But you do iterate through empty blocks. There's no need to do that. Just keep a list of blocks in a sector and iterate through those.

You don't need to iterate through non-empty blocks either:

Each block has 6 sides. Keep 6 lists per sector, each list corresponding to a side. When the user adds or removes a block, update the adjacent blocks and the corresponding lists...

Gonzo · Post by **Gonzo** » Apr 17, 2011 14:35

rendering is fast, as fast as it can be, i sort by shader more or less
and only visible faces are rendered from precomputed lists

this code was from the precompiler which comes before the compiler, which is again before the renderer

multithreaded:
generator -> (except empty) precompiler -> (except sectors without visible faces) compiler -> (visible sectors) render

it can't get any more complicated :)

i have a new question though:

Code: Select all

#Macro IsHalfblock(ID)
	(ID >= lowblock_start And ID <= lowblock_end)
#EndMacro

#Macro mVisibilityComp(ID)
	ID = _AIR Or ID >= alpha_barrier Or (IsHalfblock(ID)) 'air or leaf or cross or water
#EndMacro

' which is used by the crawler that finds visible faces:

If mVisibilityComp(glob_sb_x_m->b(blocksz-1,bz,by).id) Then lbx Or= 32      'true

is the value "glob_sb_x_m->b(blocksz-1,bz,by).id" calculated for each ID?
or is the value computed first, and then tested against each ID? im hoping the latter is the case :)
[/code]

TJF · Post by **TJF** » Apr 17, 2011 16:06

Gonzo wrote:is the value "glob_sb_x_m->b(blocksz-1,bz,by).id" calculated for each ID?
or is the value computed first, and then tested against each ID? im hoping the latter is the case :)
[/code]

Your macro expands to

Code: Select all

IF glob_sb_x_m->b(blocksz-1,bz,by).id = _AIR OR _
   glob_sb_x_m->b(blocksz-1,bz,by).id >= alpha_barrier OR _
  (glob_sb_x_m->b(blocksz-1,bz,by).id >= lowblock_start AND _
   glob_sb_x_m->b(blocksz-1,bz,by).id <= lowblock_end) _
     THEN lbx OR= 32

So blocksz-1 is calcutaled 4 times. And the dereferencing is done 4 times.

You can watch the macro expansion by using the -pp compiler option. It'll generate a file name.pp.bas with the output of the FB precompiler.

Gonzo · Post by **Gonzo** » Apr 17, 2011 20:51

thanks :) helped greatly!

Gonzo · Post by **Gonzo** » May 08, 2011 19:33

i'm having a problem finding a cheap way to make a pattern based on a 3d position

Code: Select all

If (bx And 3) And (by And 3) And (bz And 3) Then
  algorithm A, visibility check that is unfriendly towards adding more faces
Else
  algorithm B, visibility check that is friendly towards adding more faces
Endif

is the code to determine wether or not a specific face (important!) will be visible in a tree
so, there can be 6656 faces in a sector, potentially (16, 8, 16 blocks)

unfriendly means it won't add a face there if theres a leaf-block on the opposite end
friendly means it assumes theres no faces in that position already and adds it even if a leaf-block could potentially be there

1. my algorithm must not create aliasing (faces in the same position)!
2. it must me seamless against neighboring sectors, ie. the pattern cannot use odd numbers!
3. the outer edges of trees are always solid! that's taken care of!

i used to have the algorithm if (bx + by + bz) and 1 then
but it only removed every 2nd face, and thus every face would still be there (consider the opposite block!) :)
all it did was fix aliasing

please help!

EDIT: to make sure we are talking about the same thing, here is a tree :P
http://fbcraft.fwsnet.net/tree.png
as you can see my current version creates corridors, which is bad :(

TJF · Post by **TJF** » May 08, 2011 20:07

How many BITs are stored in bx, by and bz?

If it's less than 8 (16), you may consider storing all in one UINTEGER (ULONGINT) and use just one AND instruction like

IF BxByBz AND &b10000000100000001000 THEN

At least you can use ANDALSO:

IF (bx AND 3) ANDALSO (by AND 3) ANDALSO (bz AND 3) THEN

Gonzo · Post by **Gonzo** » May 08, 2011 20:23

it's not a matter of packing it, the problem is the pattern
i want to make a pattern that doesn't make corridors like shown in the image

bx, by and bz are integers (but they will only ever have values from 0 to 15)
while i appreciate optimizations (because its a bottlenecked part of the code)
it will cost 10 times more if the algorithm passes

the goal is to make a pattern that excludes every 3rd 4th 5th, or similar face, but doesnt introduce any aliasing, and not alias against neighboring sectors either

that part is what makes it hard to do anything but a "every 2nd" test
whereas my "every 4th" test makes corridors as shown in the image, which is bad, because it can be seen from close range outside the trees

TJF · Post by **TJF** » May 08, 2011 21:17

Just for my understanding:

You're searching for an expression that returns:

-1 for (bx + by + bz) = 0
0 for (bx + by + bz) = 1
0 for (bx + by + bz) = 2
-1 for (bx + by + bz) = 3
0 for (bx + by + bz) = 4
0 for (bx + by + bz) = 5
-1 for (bx + by + bz) = 6
...