Re: [Raypp-general] Re: C++ performance optimizations

[Martin R. <ma...@MP...>]

Hi!

> I'm not really an expert on the subject as I just discovered this technique
> recently. I thought that you could get some performance optimizations
> whenever more vector or matrix operations are combined to a long expression.
> But you are probably right, I just skimmed through some of the code
> and there's actually nothing like that...

Actually, there might be quite a lot of such expressions (for example,
a ray is transformed into another coordinate system, and afterwards
evaluated at a certain distance). But we usually have to keep the intermediate
results (in this case the transformed ray), since we need them again later.
So the expression templates (which eliminate the intermediate result) don't
help here.

>>The most promising area of speedup is IMO the bounding box hierarchy
>>generation. The current algorithm is very ad-hoc and could certainly be
> 
> improved.
> 
> You're talking about POV_HMAKER, right?

Yes.

> From that name I was assuming
> it is the same technique POVRay uses (which can't be that bad, although I
> don't
> know it).

It was at first based on the POVRay one, but I added some additional criteria
which seemed to speed things up, and by now it is probably quite different.

> Could you give a short intro how it works?

I'll try (and hope I remember correctly).

1) first all infinite objects are discarded (they don't belong in the bounding box hierarchy).
2) if the number of remaining objects in the list is smaller than some constant, the algorithm stops.
3) The list of objects is sorted along the x-axis and is split in two parts
    in such a way that a cost function is minimized. The cost function measures the cost for
    an intersection test, if both parts were enclosed in a bounding box each).
4) The same is done for y- and z- directions
5) The split direction with the smallest cost is chosen.
6) For both newly-created parts, step 2) is executed recursively.

This is meant to be an approximation of the Goldsmith & Salmon algorithm, which I didn't fully
understand at the time I read it. It might be worthwhile to try this one now.

Cheers,
   Martin