[BUG] function "trace" fails to find intersections in distances of more than 10⁷ units

[hatzfeld]

Summary

I have a scenario where the function trace correctly finds the intersection. When I scale it up, it does not find the intersection anymore.

POV-Ray Version

• Incarnation: POV-Ray for UNIX (POV-Ray 3.7.0.4.unofficial)

Runtime Environment

• Operating system: Ubuntu 18.04.6 LTS
• Hardware architecture: x86-64
• CPU model: Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz

Scene

#version 3.7;
global_settings { assumed_gamma 1.0 charset utf8 }

// Demonstration of a bug in povray

// The trace function (used with quite big numbers) has a false "no hit" result,
// which turns into a correct result when the scenario is scaled down

// loop with Base = 1000 results in "no hit"
// loop with Base = 1 give a correct result

#declare Base = 1000; // will not find the intersection
// #declare Base = 450; // will not find the intersection
// #declare Base = 400; // works
// #declare Base = 1 ; // works

#declare Earth = sphere { 0, Base };

#declare SatPos = <-Base,Base/2,-Base1.5>;
#declare SunPos = <-4500, 0, -4500>; // to be scaled to realistic length in the next step:
#declare Sun = SunPos(Base*23560/vlength(SunPos));

#debug concat("\nSun located at < ",vstr(3,Sun,", ",0,3)," >\n")

// a slightly red ball representing earth
sphere { Earth
pigment { color rgb <.5,1,.7> }
}

// a blueish satellite which will create a shadow on the "earth"
sphere { SatPos, Base/20
pigment { color rgb <.5,.5,1> }
}

// calculate position of shadow and create a red sphere there
#declare Norm = <0, 0, 0>;
#declare Shadow = trace(Earth,Sun,SatPos-Sun,Norm);
#if (vlength(Norm) != 0)
sphere { Shadow, Base/10 pigment { color rgb <1,.3,.3> } }
#else
#debug "Function trace did not found an intersection.\n"
#end

light_source { Sun, 1 }

camera { location <0,0,-10*Base> look_at 0 angle 30 }

Command Line Options

povray +P test-scalingbug.pov

Expected Behavior

The shadow of the smaller sphere ("satellite") falls on the bigger sphere ("earth") at a spot, which is calculated by trace and then marked by a small red sphere.

Actual Behavior

trace does not find that spot if the numbers (e.g. distance of light source) are big

Output

Sun located at < -16659435.765, 0.000, -16659435.765 >
Function trace did not found an intersection.

[ingoogni]

Maybe: http://wiki.povray.org/content/Knowledgebase:Language_Questions_and_Tips#Topic_24

[hatzfeld]

I did further investigations: The function trace does not find intersections which are more than 10000000 units away from the starting point of the ray.

To be clear: 10000000 (i.e. 10⁷) is not an approximate value, it is an exact limit and it concerns the distance described above, not e.g. the length of the direction vector (the 3d parameter of trace).

If this behaviour could be explained by the problem described in
http://wiki.povray.org/content/Knowledgebase:Language_Questions_and_Tips#Topic_24
it would not disappear simply by scaling down the whole scene.

Here a scene which calculates the limit mentioned above:

#version 3.7;
global_settings { assumed_gamma 1.0 charset utf8 }

// Demonstration of a bug in povray

// The trace function does not find intersections
// if the distance between ray start and intersection is higher (or equal?) 10,000,000 units

// targeted precision of ray length (if too low, it will be limited by hardware!)
#declare PrecEnd = 0;
#if(PrecEnd!=0)
  #debug concat("Calculation with limited precision of ",str(PrecEnd,0,10),"\n")
#end
// max number of loops (just in case ...)
#declare MaxLoops = 666;

text {
  ttf "timrom.ttf" "Distance to intersection in trace" 1, 0
  pigment { color rgb <0,1,0> }
  translate <-8,2.5,0>
  scale 70
}

// add randomness to prove that result not specific for special ray direction
#declare Random = seed(now*24*60*60);
#declare SatPosRandShift = <0.5-rand(Random),0.5-rand(Random),0.5-rand(Random)> * 0.03;
// uncomment the next line to exclude random data, if you wish
// #declare SatPosRandShift = <0,0,0>;

// start values for loop
#declare MinBase=.1;
#declare MaxBase=10000;
#declare BaseStep=1000;

#declare Base = MinBase;
#declare BaseOld = MinBase;
#declare LoopNo = 0;
#declare LastRayLength=1; // highest value of ray length (start -> intersection) found until now
#declare LastRayLengthOld=0; // penultimate valid value
#declare Prec = 10000; // (here still ficticious) precision of ray length

#while (LoopNo < MaxLoops & Prec > PrecEnd)

  #declare LoopNo = LoopNo +1;
  #declare BaseOld = Base;
  #declare Base = Base + BaseStep;

  #declare Earth = sphere { 0, Base };

  #declare SatPos = Base * (<-1,.5,-1.5> + SatPosRandShift);
  #declare SunPos = <-4500, 0, -4500>; // to be scaled to realistic length in the next step:
  #declare Sun = SunPos*(Base*23560/vlength(SunPos));

  // calculate position of shadow and create a red sphere there
  #declare Norm = <0, 0, 0>;
  #declare PlotPlaceX = 1000*(Base-MinBase)/(MaxBase-MinBase)-500;
  #declare PlotPlace = <PlotPlaceX,0,0>;
  #declare Shadow = trace(Earth,Sun,2*(SatPos-Sun),Norm);

  // intersection found?
  #if (vlength(Norm) != 0)
    #declare LastRayLengthOld = LastRayLength;
    #declare LastRayLength = vlength(Sun-Shadow);
    #declare Prec = LastRayLength - LastRayLengthOld;
  #else
    #declare Base = BaseOld;
    #declare BaseStep = BaseStep/8;
  #end

#end

#if (LoopNo < MaxLoops)
  #debug concat("Found maximum ray length (start -> intersection) ",str(LastRayLength,0,10),"\n")
  #declare Text = concat("Maximum: ",str(LastRayLength,0,10));
#else
  #debug "Error: Loop limit exceeded.\n"
  #declare Text = "Loop limit exceeded.";
#end

text {
  ttf "timrom.ttf" Text 1, 0
  pigment { color rgb <1,0,0> }
  translate <-8,-2.5,0>
  scale 70
}

light_source { <-4500,0,-4500>, 1 }

camera { location <0,0,-2500> look_at 0 angle 30 }

(If you see a response "loop limit exceeded", this means that in your case this limit does not exist.

[wfpokorny]

Thank you for the nice test case.

With respect to the test case, in v3.7, the only option is to move to some other basic shape type which doesn't implement a performance cheat in the parser which eliminates many transforms (including scale as represented by the radius) by replacing them with equivalent raw spheres.

Try replacing:

#declare Earth = sphere { 0, Base }

with:

    #include "functions.inc"
    #declare Earth = isosurface {
        function { f_sphere(x,y,z,Base) }
        contained_by { sphere { 0,Base+2.0 } }
        threshold 0
        accuracy 0.0005
        max_gradient 1.1
    }

Background:

In all official versions of POV-Ray there are some hard internal limits floating around. One is MAX_DISTANCE which is set to 1e7 and it's supposed to represent the maximum intersection distance which is, generally, numerically stable across all objects. You are exceeding this limit.

Aside: Something apparently changed during v3.8 development because in all v3.8 releases I have currently compiled, I can defeat the parser's, numerically-unfortunate, performance optimization by doing a very slight asymmetric scale of 'scale <1,1,1+1e-15>. When the transform is kept in v3.8, the numerical sanity checking gets applied in a more reasonable way to a unit sphere with a transform matrix attached.

I believe the parser optimizations like those being implemented with spheres (also sphere_sweeps IIRC and perhaps other shapes too) should be removed. These sorts of optimizations are a bad idea numerically for more reasons than just the one you hit here.

That said. There are always numerical issues floating about in a ray tracer.

There are currently bounding limits in POV-Ray at +-1e10 IIRC (bounding in official releases is all done with 32 bit floats) (*) .

Bill P.

(*) FYI. The trace() function itself bypasses the object bounding mechanism. Plus, you can get better render speed for your test scene by reducing the bounding threshold limit to 2 (+mb2) - text{} objects are relatively expensive.

[CousinRicky]

My 0.02: I have an old book, The Elements of Programming Style by Brian W. Kernighan and P. J. Plauger, which strongly discourages absolute limits, at least when it comes to numerical precision. Thorsten may have a reason for having absolute limits; I’ve seen him defend absolute precision on the small end, precisely the context that this book warns against.