Hi,
as I was very interested in the isosurface intersection code I did a 
complete rewrite of it based on the beta source. My new code moves all 
the global and thread global structures and variables into classes and I 
implemented some optimisations:
- Every isosurface now has a separate cache with multiple entries (speeds 
up camera ray tests, shadow ray tests and reflection ray tests)
- Intersection points are interpolated, so much smaller accuracies are 
sufficient
- An expensive optimisation that could speed up calculations when using 
very slow functions (and slow down when using faster functions...)
- General code cleanup

Mostly due to the bigger cache raw isosurface performance (tested with 
Christoph Hormann's SCC3 entry, all rays hit the isosurface, radiosity 
off) is now about 25% bigger. The new code makes about 10% less function 
VM calls. I did not do long tests but the new code is always faster... I 
implemented almost (some statistics code is missing) all features of the 
current beta. The results are not identical but the reason is 
interpolation which leads to a higher quality!
If anyone is interested in the code I will post it on 
povray.binaries.programming.
Regards,
Lukas Winter

Post a reply to this message

> If anyone is interested in the code

	Are you kidding?  Of course we are *not*  ;-)

	- NC

Post a reply to this message

Lukas Winter schrieb:

> Hi,
> as I was very interested in the isosurface intersection code I did a 
> complete rewrite of it based on the beta source. My new code moves all 
> the global and thread global structures and variables into classes and I 
> implemented some optimisations:
> - Every isosurface now has a separate cache with multiple entries (speeds 
> up camera ray tests, shadow ray tests and reflection ray tests)

I am not sure how this is meant - the existing isosurface cache IIRC 
speeds up subsequent rays missing the surface.

> - Intersection points are interpolated, so much smaller accuracies are 
> sufficient

This is already in MegaPOV and i thought it also was in 3.7.

> - An expensive optimisation that could speed up calculations when using 
> very slow functions (and slow down when using faster functions...)

More details would be required on this.

> 
> Mostly due to the bigger cache raw isosurface performance (tested with 
> Christoph Hormann's SCC3 entry, all rays hit the isosurface, radiosity 
> off) is now about 25% bigger. The new code makes about 10% less function 
> VM calls. I did not do long tests but the new code is always faster... I 
> implemented almost (some statistics code is missing) all features of the 
> current beta. The results are not identical but the reason is 
> interpolation which leads to a higher quality!

Interpolating the intersection point should converge to the same result 
as not doing so in all well defined cases.

-- Christoph

Post a reply to this message

Am Wed, 12 Mar 2008 13:50:29 +0100 schrieb Christoph Hormann:
>> - Every isosurface now has a separate cache with multiple entries
>> (speeds up camera ray tests, shadow ray tests and reflection ray tests)
> 
> I am not sure how this is meant - the existing isosurface cache IIRC
> speeds up subsequent rays missing the surface.
The existing cache explicitely excludes shadow rays. It also does a poor 
job when there are several isosurfaces in the scene. The reason is that 
most of the time subsequent tests come in the same order, i.e. several 
_different_ kinds of tests repeat in a certain order but the cache only 
speeds up _similiar_ rays. So one cache entry overrides another and there 
are a lot of cache misses that could have been avoided if the cache kept 
older entries. On the other hand the cache should not be too big to avoid 
expensive tests against very old entries. I usually use 2 or 3 cache 
entries per isosurface.

>> - Intersection points are interpolated, so much smaller accuracies are
>> sufficient
> This is already in MegaPOV and i thought it also was in 3.7.
The isosurface code of beta 25 is nearly identical to that of 3.6.1. 
There are some changes to make it thread-safe and the object is now a 
class.

>> - An expensive optimisation that could speed up calculations when using
>> very slow functions (and slow down when using faster functions...)
> More details would be required on this.

The code tries to move the point where it splits the current interval in 
two intervals to a better place under some circumstances. But a speed-up 
thanks to this is very rare.

> Interpolating the intersection point should converge to the same result
> as not doing so in all well defined cases.
True. But as we just do an approximation, self-shadowed areas will look 
slightly different. In the current beta and 3.6.1 the transition between 
shadowed and lit areas will always look grainy even with high accuracies. 
With interpolation they look smooth.

Post a reply to this message

Lukas Winter schrieb:
> 
> The existing cache explicitely excludes shadow rays. It also does a poor 
> job when there are several isosurfaces in the scene. The reason is that 
> most of the time subsequent tests come in the same order, i.e. several 
> _different_ kinds of tests repeat in a certain order but the cache only 
> speeds up _similiar_ rays. So one cache entry overrides another and there 
> are a lot of cache misses that could have been avoided if the cache kept 
> older entries. On the other hand the cache should not be too big to avoid 
> expensive tests against very old entries. I usually use 2 or 3 cache 
> entries per isosurface.

is this cache per thread or global?  The former would make more sense 
since the rays are only correlated in a thread and not between several 
ones.  Also it would make sense to exclude radiosity rays.

> The code tries to move the point where it splits the current interval in 
> two intervals to a better place under some circumstances. But a speed-up 
> thanks to this is very rare.

Sounds much like the sphere tracing technique to me - i once tried this 
and it did not seem to be have a significant advantage to me.  Some more 
on this can be found in stuff on:

http://graphics.cs.uiuc.edu/~jch/papers/?cat=implicit

If more information is known about the isosurface function things can be 
different of course.

-- Christoph

Post a reply to this message

Am Thu, 13 Mar 2008 08:15:23 +0100 schrieb Christoph Hormann:
> 
> is this cache per thread or global?  The former would make more sense
> since the rays are only correlated in a thread and not between several
> ones.  Also it would make sense to exclude radiosity rays.
> 
There is one cache per thread per isosurface via 
boost::thread_specific_ptr. I figured out that the number of cache 
entries should be kept smaller than (number of lightsources + number of 
reflective textures on the isosurface). So only one cache entry is enough 
for most simple scenes with non-reflective isosurfaces.

> 
> Sounds much like the sphere tracing technique to me - i once tried this
> and it did not seem to be have a significant advantage to me.

You are right. I did not know what this technique was called. The current 
POV implementation finds a root on an interval [t_min, t_max] in a fixed 
number of recursions. I tried to lower this number somehow but it did not 
work out well.

Post a reply to this message