search

POV-Ray / povray

The Persistence of Vision Raytracer: http://www.povray.org/
GNU Affero General Public License v3.0
1.35k stars 282 forks source link

Port of FS81 - sphere_sweep generating artifacts #147

Open wfpokorny opened 7 years ago

wfpokorny commented 7 years ago

http://bugs.povray.org/task/81

(See too github sphere_sweep issues #59 #285 #287)

Also: FS92.zip where FS92 closed but referenced herein.

Details

I'm running POV-Ray for (64 bit) Windows v3.62 on (64 bit) Windows Vista

This pov file:

#include "colors.inc"
#include "metals.inc"

light_source { <6, 9, -21> color White }
camera { location <0, 0, -3> look_at <0, 0, 0> }

sphere_sweep {
                cubic_spline
                6
                <-2.0, 0, 0> 0.05

                <0.000,0,0> 0.2
                <0.025,0,0> 0.2
                <0.050,0,0> 0.2
                <0.075,0,0> 0.2

                <3.0,0,0> 0.2
                pigment { color White }
}

Produces two strange artifacts: A disk at the center of the sweep, and a faint "halo" or veil which shows as 4 faint hyperbolas centered around the origin.

I have tried tweaking tolerance (for no other reason than I saw that someone else was tweaking it to solve a problem) but this does not seem to change things.

For a look at MY result when I run this, view this image:

riventree.comarchivebugdatapovrayspheresweepartifacts.jpg

Alain reports the same behavior in the latest version: "It's still there with the latest version: 3.7 beta 35a." This MAY move the status to "confirmed", but I can't do that

Someone else says that changing the scale (!) "solves" the problem by moving the disk and the halo offscreen, but that sounds like a bad idea to me.

-Jeff Evarts, first-time POVRay bug reporter

SphereSweepArtifacts.jpg (30.4 KiB)

See: FS81.zip

Comments:

Comment by Jeff Evarts (JeffEvarts) - Sunday, 21 March 2010, 12:23 GMT+5

From

http://news.povray.org/povray.bugreports/thread/<web.4b9ad12c8fcde48e18d0cecb0%40news.povray.org>

Your post and Alain's comments got me to thinking about this long-standing problem, so I did some experiments (and a few animations). Here's what I've come up with (in v3.6.1) using your code unchanged:

1) The cubic_spline type is by far the worst offender. It produces those hyperbolas outside the object, plus the vertical 'plane' that Alain mentioned. It also takes MUCH longer to render than either a b_spline or linear_spline (about 10X longer!). The ENTIRE scene renders slower-every pixel. Moving the camera way back-so that the sphere_sweep is barely visible in the scene-doesn't change this; in fact, the scene renders even slower, which is completely counter-intuitive. Changing the tolerance value doesn't affect it. Putting all of this together, it seems as though there's a 'visible' part of the object (the one we see) and an infinitely large INVISIBLE part as well, that POV-Ray is also having to do render calculations on -the outside artifacts showing up as vestiges of this part. BTW, my animation tests seem to show that the 'plane' artifact is at the location of the asymptote of the hyperbolas (or one of them, anyway.) Not sure about that, though. And I still can't tell why this 'plane' is showing up where it does; it has nothing to do with the sphere_sweep being made near POV's <0,0,0> origin location. (See 3) below.)

2) The b_spline and linear spline don't produce any artifacts outside the object, except for that 'plane'-and it's actually more pronounced with a linear_spline than either of the other two spline types.

3) Creating the sphere_sweep somewhere other than near the origin (via its spline points OR by translating it afterward)-and moving the camera likewise-doesn't alter the artifacts. Changing the tolerance helps somewhat, but not with the cubic_spline's hyperbolas.

4) The artifacts don't seem to change their positions relative to the object, when the camera moves around. (I thought at first it was some kind of camera/sphere_sweep 'interaction'; but moving the camera via animation doesn't really alter their behavior or location, it just shows them in 3-D space.)

My own conclusion is that the cubic_spline code (at least when used in a sphere_sweep) needs to be re-worked. That may not fix ALL of the sphere_sweep artifacts, but would surely help!

Question (a bit off-topic): Is POV's b_spline the same as a natural_spline? Looking them up on Wikipeadia doesn't give me a clear answer.

Ken

Comment by Christoph Lipka (clipka) - Wednesday, 24 March 2010, 01:49 GMT+5

Sphere sweep artifacts are also reported for POV-Ray 3.7.0.beta.36 (see news://news.povray.org:119/web.4ba914139ed5c41e66d05d110@news.povray.org)

Comment by Thorsten Fröhlich (thorsten) - Wednesday, 24 March 2010, 15:08 GMT+5

A note about this issue: It is an ancient bug with the spline interpolation bounding computations not working. It has been known ever since sphere_sweeps where added to POV-Ray (as the bug existed in the original source). It was even discussed back then (3.5 beta), but nobody ever volunteered to implement the somewhat complicated mathematical solution to computing the correct bounding for spline based sweeps. The issue is that the code guesses the bounding for splines rather than computing it. The guessing fails for splines with "more extreme" splines where the sweep simply ends up being outside the bounding volume, causing plenty of artifacts due to intersections not being computed.

Comment by Jeff Evarts (JeffEvarts) - Thursday, 25 March 2010, 20:18 GMT+5

I don't think that's correct. It explains the slowness, but not the halos.

If it were MERELY a bounding problem, then either the bounding object would "clip" the object (if it was too "small" in places) or it wouldn't make any difference at all (if it was too large everywhere). Likewise, the problem would go away completely if you turned bounding off (since it would be very very slow, but still only draw things that belonged there).

This is a case where rays which SHOULD miss the object altogether are colliding with it, so it's a problem with more than just the bounding object.

Right?

Comment by Jeff Evarts (JeffEvarts) - Thursday, 25 March 2010, 20:19 GMT+5

And we should probably bump it from "possible bug" to "bug", too.

Comment by Christoph Lipka (clipka) - Thursday, 25 March 2010, 22:22 GMT+5

Field changed: Task Type (Possible Bug -> Definite Bug)

I absolutely agree with Jeff - we actually have two bugs: The non-existent bounding, and the artifacts.

(Which presently leaves us with the question which of them Chris has committed himself to fix.)

Comment by Jeff Evarts (JeffEvarts) - Friday, 26 March 2010, 03:50 GMT+5

Surely the bug isn't "fixed" until the customer is satisfied, right? lol

-Jeff

Comment by Jeff Evarts (JeffEvarts) - Wednesday, 31 March 2010, 04:44 GMT+5

Chris? Christoph?

Any word on this?

-Jeff

Comment by Chris Cason (chrisc) - Wednesday, 31 March 2010, 04:47 GMT+5

I'm a little snowed right now - will comment shortly.

Comment by Jeff Evarts (JeffEvarts) - Saturday, 10 April 2010, 06:08 GMT+5

Any word, here?

Comment by Chris Cason (chrisc) - Saturday, 10 April 2010, 06:09 GMT+5

Promise I'll get to it this weekend: it's on the top of my list now.

Comment by Chris Cason (chrisc) - Monday, 12 April 2010, 19:21 GMT+5

Ok, as mentioned it's clear that there are two issues - the bounding and the artifacts.

For reasons mentioned above, fixing the bounding properly is difficult, so in the near term we need to consider what means could be used to work around this for the average user (i.e. someone not aware of the issue). For those in the know, it is possible to use bounded_by to manually specify the bounds.

The question then becomes, can we detect (or infer) the cases in which the bounding is behaving badly (either by being too small or too large). If we can it might have to be at run-time. If so, what do we do about it? Issue a warning that points to the docs discussing this?

The other option (less likely to happen) is to code a correct solution; if someone can correctly describe the maths needed then I would at least take a stab at coding it.

As to the artifacts, I'll have a look at that to see if I can locate the cause.

NB feel free to create a new bug about the bounding.

Comment by Jeff Evarts (JeffEvarts) - Tuesday, 13 April 2010, 00:57 GMT+5

OK, so this is officially the artifact bug. Gotcha. (That's great, since my project isn't hampered by the bounding issue.)

Comment by Jeff Evarts (JeffEvarts) - Saturday, 17 April 2010, 01:49 GMT+5

Any progress this week?

Comment by Jeff Evarts (JeffEvarts) - Monday, 19 April 2010, 07:38 GMT+5

Chris Carson/chrisc: Any word on this bug? It still shows as "0% progress".

Comment by Christoph Lipka (clipka) - Monday, 19 April 2010, 13:09 GMT+5

The disc artifact apparently has the same root cause as the artifacts described in FS#92 (fixing that error by modifying the square root solver will also make the disc in this cubic_spline issue go away). The other artifacts still remain unsolved, but I wouldn't be surprised if the underlying problem was similar (small polynomial coefficients, and a failure of the root solver or calling code to somehow normalize the polynom before trying to short-cut some computations).

Comment by Christoph Lipka (clipka) - Monday, 19 April 2010, 18:11 GMT+5

While it must be conceded that we do have artifacts with the cubic_spline, this particular case is probably not a suitable example: The extreme choice of the first and last control point coordinates makes it a pathological case anyway, even if the algorithms were perfect. The long X coordinate distance causes a massive overshoot into the next interval, "telescoping" the sphere_sweep into itself, making it hard to tell which effects are due to this "telescoping" and which are real bugs in the sphere sweep code.

The following scene shows artifacts that are unrelated to such "telescoping":

#include "colors.inc"

light_source { <6, 9, -21> color White }
camera {
  location <0.0, 0.0, -3> look_at <0,0,0>
}

sphere_sweep {
  cubic_spline
  4
  <-20.0,-2.0, 0> 0.2
  <- 1.0,-1.0, 0> 0.2
  <  1.0, 1.0, 0> 0.2
  < 20.0, 2.0, 0> 0.2
  pigment { color White }
}

From what I could find out so far, the primary reason for these artifacts is that the code does not directly try to solve for intersection points, but rather the location on the spline itself that corresponds to these intersections. This leads to problems when the front and back intersection correspond to (almost) the same location on the spline, in which case the respective intersection points cannot be unambiguously computed from the location on the spline, and will "flip" due to precision issues.

Chris, I think we'll need to come up with different math for the cubic spline sweep.

Comment by Chris Cason (chrisc) - Monday, 19 April 2010, 18:35 GMT+5

Chris, I think we'll need to come up with different math for the cubic spline sweep

I concur - the code was already in need of fixing, so if it's also a fundamental issue there's not much point trying to solve this as well.

Comment by Jeff Evarts (JeffEvarts) - Tuesday, 20 April 2010, 21:21 GMT+5

Does that mean my artifacts will remain (with no workaround) until the date of the cubic spline change? I'd like to use POVRay for this project, but if this is a "wait for the next revision" kind of fix, then I'll probably need to change that plan.

Comment by Chris Cason (chrisc) - Tuesday, 20 April 2010, 21:30 GMT+5

Does that mean my artifacts will remain (with no workaround) until the date of the cubic spline change?

I can't comment on whether or not there's no workaround (since for all I know someone might come up with another way for you to achieve what you need), but insofar as the existing code is concerned, there's really no straightforward way of fixing it: the issue is fundamental to the maths involved; i.e. it's not really a coding bug (insofar as we can tell).

I'll try to drop Jochen Lippert (the author of the original sphere sweep code) a line and see if he's interested in taking a look at it.

Comment by Christoph Lipka (clipka) - Tuesday, 20 April 2010, 22:31 GMT+5

Does that mean my artifacts will remain (with no workaround) until the date of the cubic spline change? I'd like to use POVRay for this project, but if this is a "wait for the next revision" kind of fix, then I'll probably need to change that plan.

The disk artifact will be fixed in the next 3.7 beta (as a beneficial side effect of the fix for FS#92 ); if you need a fix earlier or can't use the betas, you will have to create and patch a custom version of POV-Ray, changing "polysolv.cpp" as follows: Locate the function "solve_quadratic"; in there, locate the statement reading "d = b b - 4.0 a * c;" (after the first if-block); before that line, place the following instructions: "b /= a; c /= a; a = 1.0;" (The function hasn't changed from 3.6 tp 3.7.) The function should now read:

static int solve_quadratic(DBL *x, DBL  *y)
{
  DBL d, t, a, b, c;

  a = x[0];
  b = -x[1];
  c = x[2];

  if (a == 0.0)
  {
  ...
  }

  // PATCH: normalize the coefficients
  b /= a;
  c /= a;
  a  = 1.0;

  d = b * b - 4.0 * a * c;
  ...

As for the other artifacts, there is also a fix that reduces them considerably, though it will not eliminate them completely, nor do I know how it will affect performance: In file "sphsweep.cpp", locate the function "Intersect_Sphere_Sweep_Segment" (or "SphereSweep::Intersect_Segment" if you're patching a current 3.7 beta); in there, locate the second "switch" statement, subsection "case 4:". In there, you will find an "if(fabs(fp1) > ZERO_TOLERANCE) { ... } else { ... }" statement. replace the condition with "false"; your code should now look something like this:

        ...
                case 4:
                        for (m = 0; m < Num_Poly_Roots; m++)
                        {
                                fp0 = 6.0 * f * Root[m] * Root[m] * Root[m] * Root[m] * Root[m]
                                        + 5.0 * g * Root[m] * Root[m] * Root[m] * Root[m]
                                        + 4.0 * h * Root[m] * Root[m] * Root[m]
                                        + 3.0 * i * Root[m] * Root[m]
                                        + 2.0 * j * Root[m]
                                        + k;
                                fp1 = 3.0 * b * Root[m] * Root[m]
                                        + 2.0 * c * Root[m]
                                        + d;

                                if(false) // PATCH - was: if(fabs(fp1) > ZERO_TOLERANCE)
                                {
                                        t = -fp0 / fp1;
                                        ...
                                }
                                else
                                {
                                        // Calculate center of single sphere
                                        VAddScaled(Temp_Sphere.Center, Segment->Center_Coef[0], Root[m], Segment->Center_Coef[1]);
                                        VAddScaledEq(Temp_Sphere.Center, Root[m] * Root[m], Segment->Center_Coef[2]);
                                        VAddScaledEq(Temp_Sphere.Center, Root[m] * Root[m] * Root[m], Segment->Center_Coef[3]);
                                        ...
                                }
                        }
                        break;
        ...

Note that neither did I test these patches with 3.6, nor do I know how the second patch affects rendering speed (it will not solve the drastic bounding-box related slowdown; you will have to use custom bounding for that). However, it should get you somewhere in case you can't wait for an official fixed release or beta.

@Chris: In case the general overhaul of the cubic_spline sweep should take a while, we might try that second workaround as well for 3.7 betas. I think it's better than nothing, even despite leaving some residual artifacts and possibly being slower.

Comment by Christoph Lipka (clipka) - Tuesday, 20 April 2010, 22:43 GMT+5

See attached file (_test.png) for a rendering with both patches applied (to POV-Ray 3.7 beta.36 in this case). Note that both disk and parabola are eliminated, and the artifacts on the right end cap as well; a thin line between left end cap and the sweep remains as a residual artifact though. _test.png (7.1 KiB)

Comment by Jeff Evarts (JeffEvarts) - Wednesday, 21 April 2010, 03:31 GMT+5

Any idea when the next beta will be? Looks like the last one was in December?!?

Comment by Chris Cason (chrisc) - Wednesday, 21 April 2010, 03:51 GMT+5

Any idea when the next beta will be?

I think there's enough changes in there to make a new beta worthwhile. I'll see about doing one in the next few days.

Comment by Christoph Lipka (clipka) - Thursday, 22 April 2010, 13:30 GMT+5

checked in the described 2nd patch as change #4947.

Comment by Jeff Evarts (JeffEvarts) - Sunday, 25 April 2010, 23:51 GMT+5

Any word on the new beta and whether or not it will include change 4947?

Comment by Chris Cason (chrisc) - Sunday, 25 April 2010, 23:56 GMT+5

See http://news.povray.org/4bd3a743%241@news.povray.org (and yes, it does).

Comment by Christoph Lipka (clipka) - Sunday, 25 April 2010, 23:59 GMT+5

Chris is on it (see news://news.povray.org:119/4bd3a743$1@news.povray.org); change #4947 will be included.

Comment by Jeff Evarts (JeffEvarts) - Monday, 31 May 2010, 10:32 GMT+5

and the news is...

Comment by Christoph Lipka (clipka) - Monday, 31 May 2010, 16:11 GMT+5

... yes, Jeff? Did you test beta.37?

Comment by Thorsten Fröhlich (thorsten) - Tuesday, 23 August 2011, 11:25 GMT+5

What is the status of this?

Comment by Grimbert Jérôme (Le_Forgeron) - Sunday, 23 February 2014, 12:21 GMT+5

February 2014: a counter-example for the patch has been posted : sw.pov.

Without the patch, it's fine. With the section of code in comment from the patch in sphsweep.cpp (#if 0), there is black shadow on the bottom left part of the picture. sw.pov (2.8 KiB)

Comment by Grimbert Jérôme (Le_Forgeron) - Friday, 07 March 2014, 03:01 GMT+5

More investigations, that seems to work:
1. cancel the "#if 0" preliminary work
2. RAISE ZERO_TOLERANCE (yes, instead of 1e-4, use 0.1)

It keeps the good section for the counter-example of 2014-02-13 (which need the section under #if 0), and keep the benefit of "#if 0" for the original scene of this issue.

Still to check against the scene of fs#92, and the double-shadow of a sphere-sweep posted in the newsgroups.

Comment by Grimbert Jérôme (Le_Forgeron) - Friday, 07 March 2014, 03:30 GMT+5

Post found (2013-06-02) in p.b.images, attached scene.

The modifications of previous comment seems ok to render that scene correctly too.

Same for fs#92: it works (as did the 3.7 too). ricky.pov (0.4 KiB)

...

wfpokorny commented 7 years ago

Documenting the recent sphere_sweep commits do not directly address this issue.

wfpokorny commented 7 years ago

See the newsgroup thread:

http://news.povray.org/povray.beta-test/thread/%3C591ae5eb%241%40news.povray.org%3E/

for more on the remaining issues. Most of these happen when the control points for segments of the overall sphere_sweep sit in a plane perpendicular - or near perpendicular - to the ray direction. The worst case involves use of an orthographic camera looking at sphere_sweep in a plane in a way such that all rays are perpendicular to that plane.

Pending further fixes, an often viable workaround in versions 3.7.1 onward is to replace such camera { orthographic } set ups with a near-orthographic user_defined camera set up where the direction is slightly skewed relative to the sphere_sweep's plane. For a square render of a sphere_sweep defined on an x,y,z=0 plane, use something like: 

#declare OrthoMult = 5.0;
camera { 
      user_defined
      location {
        function { OrthoMult*x }
        function { OrthoMult*y }
        function { -OrthoMult  }
      }
      direction {
        function { 0 + 5e-2 }  // Skewing hack. Scene shifts slightly leftward. 
        function { 0 }        
        function { 1 }
      }
}

to avoid the solver artifacts.

wfpokorny commented 6 years ago

Solver updates mostly related to accuracy in this branch:

https://github.com/wfpokorny/povray/tree/fix/polynomialsolverAccuracy

partly address the remaining artifacts herein. See too the newsgroup thread at:

http://news.povray.org/povray.binaries.images/thread/%3C5ae324d7%241%40news.povray.org%3E/

c-lipka commented 3 years ago

Does someone have the time to compile a TL;DR of what problems still remain, as well as what porposals exist to fix them, and plonk this report into a new issue so we can work on the residual problems in a more focused manner?

c-lipka commented 3 years ago

For the records: I consider this a precision issue that we don't want to tackle in a hurry while we prepare for v3.8.0 release.