On 2006-10-21, tsuraan wrote: > 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. 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. So, do you have any tips for implementing > divide-and-conquer in hardware? The calculation of points on the curve is > naturally pipelined (three levels deep), so I'd also like to take advantage > of that, but I'm not sure how to. I'll post a bit more later on how the > drawing works so maybe I can get some more specific advice; I have to get > back to work now...
I looked up this on Wikipedia, http://en.wikipedia.org/wiki/De_Casteljau%27s_algorithm. Whereas the discussion of how to implement recursive algorithms is interresting, this problem seems solvable without it. The three coordinate components can be computed independently, so we only need to consider one component. If I'm looking at the right algorithm, it can be solved by n iterations over an array of n components, where n is the number of control points: float de_Casteljau(int n, float x[], float t) /* OBS! untested */ { int i, j; float u = 1.0 - t; for (j = 1; j < n; ++j) for (i = n - j - 1; i >= 0; --i) x[i] = x[i]*u + x[i + 1]*t return x[0]; } _______________________________________________ Open-graphics mailing list [email protected] http://lists.duskglow.com/mailman/listinfo/open-graphics List service provided by Duskglow Consulting, LLC (www.duskglow.com)
