Hi,
at the moment the sturmian root solver calculates all roots in the 
interval [0, MAX_DISTANCE] even if some of these roots are not needed at 
all. I suggest the following changes to speed up the sturmian root solver:

- Add two arguments to Solve_Polynomial(), DBL min_bound and DBL 
max_bound with default values of 0 and MAX_DISTANCE. Prototype:
int Solve_Polynomial (int n, DBL *c, DBL *r, int sturm, DBL epsilon, 
const TraceThreadData *Thread, DBL min_bound = 0, DBL max_bound = 
MAX_DISTANCE);

- Add two arguments to polysolve() replacing DBL min_value and DBL 
max_value with default values of 0 and MAX_DISTANCE. Prototype:
static int polysolve (int order, DBL *Coeffs, DBL *roots, DBL min_value = 
0, DBL max_value = MAX_DISTANCE);

- In Solve_Polynomial(), pass min_bound and max_bound to polysolve().

- For all shapes that support the sturmian root solver, pass the smallest 
and greatest intersection depths of its bounding volume to 
Solve_Polynomial(). This may require more expensive bounding volume tests 
in some cases but often the depths can be calculated with minimal effort.

I implemented this suggestion for the blob primitive (with keyword sturm) 
which decreased the render time of a test scene considerably. (~50% speed 
up with the blob hand from the documentation using sturm keyword)
I also implemented an ad hoc adjustment of max_value by inspecting the 
polynomial which leads to a minor speed up for all shapes that support 
sturm. If you understand German you can find information about it at 
http://de.wikipedia.org/wiki/Polynom#Reelle_Nullstellenschranken.
Regards,
Lukas Winter

Post a reply to this message