On 2006-10-21, tsuraan wrote: > >You COULD try to reimplement that algorithm. But to get efficient > >hardware, you'd probably want to reexamine the whole problem from the > >ground up. Flatten it completely, and turn sequential code into state > >machines and pipelines. > > I was hoping to test the idea for the algorithm in C (and it does seem to > work) before committing the time to > figuring out how to do the same in hardware, but at the same time having an > algorithm that can translate to hardware. I was thinking that since > recursion is commonly used in hardware (think flip-flops), maybe there was > some commonly used pattern for describing it.
The "recusion" in a flip-flop is of a different kind which I would rather call feedback. The effect of this feedback is to make a bi-stable system, thus carrying one bit of information, whereas a non-tail-recursive function needs to store an arbitrary number intermediate results. I don't think recursion and feedback are very related apart from the cyclic form of the call-graph/diagram. > Since there doesn't seem to > be anything like that, I'll work on converting to a PDA. The biggest > problem I have is that Bezier curves are naturally drawn recursively, using > deCasteljau's algorithm (probably spelled wrong), which is basically a > divide-and-conquer approach. At least with divide-and-conquer your space requirements goes logarithmic with the size of the problem. I don't know deCasteljau's algorithm, but assuming it only needs one non-tail call and it scales with the pixels in one dimonsion, you could assume 2048 pixels max. That means you can limit the depth of the stack to 11. If it scales with the number of pixel in total, you still only need twice that. If my assumptions are right, it seems feasible to use the block RAM. I'll leave it to Tim to knock me in the head with a strict block RAM budget ;-) _______________________________________________ Open-graphics mailing list [email protected] http://lists.duskglow.com/mailman/listinfo/open-graphics List service provided by Duskglow Consulting, LLC (www.duskglow.com)
