POV-Ray

The Persistence of Vision Raytracer (POV-Ray).

This is the legacy Bug Tracking System for the POV-Ray project. Bugs listed here are being migrated to our github issue tracker. Please refer to that for new reports or updates to existing ones on this system.

Tasklist

FS#81 - sphere_sweep generating artifacts

Attached to Project: POV-Ray
Opened by Jeff Evarts (JeffEvarts) - Saturday, 13 March 2010, 21:06 GMT
Last edited by William F Pokorny (wfpokorny) - Sunday, 06 November 2016, 12:17 GMT
Task Type Definite Bug
Category Backend → Geometric Primitives
Status Tracked on GitHub
Assigned To Chris Cason (chrisc)
Operating System Windows Vista
Severity Medium
Priority Normal
Reported Version 3.62
Due in Version Undecided
Due Date Undecided
Percent Complete 0%
Votes 0
Private No

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

This task depends upon

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

From

http://news.povray.org/povray.bugreports/message/%3Cweb.4ba05d6e2e5cb7c265f302820%40news.povray.org%3E/#%3Cweb.4ba05d6e2e5cb7c265f302820%40news.povray.org%3E

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) - Tuesday, 23 March 2010, 20:49 GMT

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, 10:08 GMT

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, 15:18 GMT

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, 15:19 GMT

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

Comment by Christoph Lipka (clipka) - Thursday, 25 March 2010, 17:22 GMT
  • 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) - Thursday, 25 March 2010, 22:50 GMT

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

-Jeff

Comment by Jeff Evarts (JeffEvarts) - Tuesday, 30 March 2010, 23:44 GMT

Chris? Christoph?

Any word on this?

-Jeff

Comment by Chris Cason (chrisc) - Tuesday, 30 March 2010, 23:47 GMT

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

Comment by Jeff Evarts (JeffEvarts) - Tuesday, 06 April 2010, 00:56 GMT

<discrete cough>

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

Any word, here?

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

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, 14:21 GMT

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) - Monday, 12 April 2010, 19:57 GMT

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) - Friday, 16 April 2010, 20:49 GMT

Any progress this week?

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

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

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

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, 13:11 GMT

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, 13:35 GMT
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, 16:21 GMT

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, 16:30 GMT
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, 17:31 GMT
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, 17:43 GMT

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.

Comment by Jeff Evarts (JeffEvarts) - Tuesday, 20 April 2010, 22:31 GMT

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

Comment by Chris Cason (chrisc) - Tuesday, 20 April 2010, 22:51 GMT
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, 08:30 GMT

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

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

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

Comment by Chris Cason (chrisc) - Sunday, 25 April 2010, 18:56 GMT Comment by Christoph Lipka (clipka) - Sunday, 25 April 2010, 18:59 GMT

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, 05:32 GMT

and the news is...

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

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

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

What is the status of this?

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

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) - Thursday, 06 March 2014, 22:01 GMT

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) - Thursday, 06 March 2014, 22:30 GMT

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).

Comment by William F Pokorny (wfpokorny) - Sunday, 06 November 2016, 12:17 GMT
  • Field changed: Status (Assigned → Tracked on GitHub)

Now tracked on github as issue #147.

Loading...