Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

FizzleFade

fabiensanglard.net

Post reply on HN
Print view View original

131–140 of 182 posts

Re: FizzleFade

#131

Post by first_amendment »

Orangeair wrote: post #125
antirez wrote: post #105

An alternative approach that works for every resolution: http://antirez.com/news/113

You state that a Feistel network has the property that each input value is mapped to a different output value, but how do you ensure that there isn't some cycle whose length is shorter than that of the size of the set of possible inputs? That is to say, what guarantees that every pixel is reached at least once?

Feistel is a permutation. That means it's a 1:1 mapping between a 16-bit # to another 16-bit #.

You run Feistel for each number 0->65535 (corresponding to the "stage" of the FizzleFade) and out comes the pixel to redden at that stage. Since it's a 16-bit number, some values will fall outside of 320x240 resolution, and you ignore those.

Re: FizzleFade

#132

Post by ksk »

dakom wrote: post #73
pasta wrote: post #5

I have the feeling that knowledge about bits is lacking by a lot of younger coders. And I also think this is what causes bloatware. CPUs are powerful enough to use a naive fade transition. But coders who are aware of the internal workings can make it even faster on todays hardware. Great article and imho still relevant on todays much more powerful computers.

Anecdotal evidence - I cut my teeth on C and a dabble of asm as a kid (even writing z80 opcodes directly for fun!). I vaguely remember wrangling bits to drive logic. I also wrote webpages as Apache C modules with binary logic to parse requests :D That was a long time ago in tech terms (~15 years). In the intervening gap I spent most of my time in scripted languages (as3, c#, etc.). Result? I don't know how to wrangle…

>I rely on Unity, Adobe, Google, etc. to worry about those optimizations so I can stand on their shoulders and benefit.

It seems to me like they might be doing the same thing! For all the supposedly smart people they hire, TBH I can't think of a single product that feels fast/performant to me.

Re: FizzleFade

#133

Post by dre85 »

fpgaminer wrote: post #113
dre85 wrote: post #103

I didn't quite understand why this is guaranteed to reach every pixel coordinate? Is there something inherent about LFSR that generates complete sequences within the cycle? So elements are never repeated or omitted?

Yeah this wasn't covered well in the article. Go back to the article and look at the section just below the first mention of Maximum-Length LFSR. Take a look at that list of numbers and notice something; every number from 1-15 is output once and only once. That's a property of Maximum-Length LFSRs; they output each number in their range once and only once. So, for example, a 17-bit Maximum-Length LFSR will output eve…

Thanks for that explanation! I just wanted to confirm that it's an inherent property of the LFSR.

Re: FizzleFade

#134

Post by antirez »

first_amendment wrote: post #131
Orangeair wrote: post #125

Earlier quoted context omitted.

You state that a Feistel network has the property that each input value is mapped to a different output value, but how do you ensure that there isn't some cycle whose length is shorter than that of the size of the set of possible inputs? That is to say, what guarantees that every pixel is reached at least once?

Feistel is a permutation. That means it's a 1:1 mapping between a 16-bit # to another 16-bit #. You run Feistel for each number 0->65535 (corresponding to the "stage" of the FizzleFade) and out comes the pixel to redden at that stage. Since it's a 16-bit number, some values will fall outside of 320x240 resolution, and you ignore those.

Great TLDR!

Re: FizzleFade

#135

Post by sammoth »

biesnecker wrote: post #78
kutkloon7 wrote: post #75

Earlier quoted context omitted.

I remember a recent example. What I wrote was: int x = somefunction(); int x_dividedby16 = x >> 4; My coworker corrected the second line to something like: int x_dividedby16 = (int)Math.ceil(x / 16.0);

Did your coworker correct it with "this is more readable" or "this is the correct way to do it"? The first is arguable (though I don't personally agree with the argument), the second just betrays a real lack of knowledge.

Don't the two bits of code have completely different behaviour? And the code with the bitshift is undefined on negative integers (in C). So the bottom code could indeed be the "correct way to do it".

Re: FizzleFade

#136

Post by Kiro »

Stupid question: Why can't you just take an array of all the pixels, randomize it and then iterate it to draw?

Re: FizzleFade

#137

Post by bkanber »

Kiro wrote: post #136

Stupid question: Why can't you just take an array of all the pixels, randomize it and then iterate it to draw?

This was written in assembly and to do that you'd have to make a new register of all the references while randomizing. Your approach works great in modern, high level languages where there's no issue copying an array in memory and calling array_shuffle or something, and doubling the memory requirement for the effect is no problem. This approach however seems to only require 17 bits of additional memory.

Re: FizzleFade

#138

Post by bombela »

Kiro wrote: post #136

Stupid question: Why can't you just take an array of all the pixels, randomize it and then iterate it to draw?

because this would take a huge amount of memory. something like xy(sizeof x + sizeof y). not only memory wasn't available cheaply at the time. it would be slow to generate, write to memory, then fetch back to draw.

Re: FizzleFade

#139

Post by wyldfire »

antirez wrote: post #105

An alternative approach that works for every resolution: http://antirez.com/news/113

> A good tool to have in a programmer mental box.

Relates well to Shannon's problem solving process' [1] "Step 2: Fill your 'mental matrix' with solutions to similar problems."

[1] http://www.businessinsider.com/engineer-claude-shannon-probl...

Re: FizzleFade

#140

Post by gall_anonim »

Kiro wrote: post #136

Stupid question: Why can't you just take an array of all the pixels, randomize it and then iterate it to draw?

Because with ideal packing it would take 150 kB (320·240·log2(320·240)/8). Wolf3d needed 640 kB of RAM and using quarter of it just to display death animation wouldn't be a good idea.
Post reply on HN