Re: A proposal for the next motion
> Date: Fri, 22 May 2009 11:42:10 -0400
> From: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
> Subject: Re: A proposal for the next motion
> To: STDS-1788@xxxxxxxxxxxxxxxxx
>
> >> > . . .
> >>
> >> One day I wish to write a book about it. In the meantime, I fear it will
> >> be difficult in e-mail disucssions to explain everything (and much of it
> >> would be off-topic). Plus many of these ideas as they pertain to computer
> >> graphics are still, unfortunately, confidential.
> >>
> >> What I can say as a summary is this:
> >>
> >> All of our algorithms use modal interval analysis, so this means {empty}
> >> does not exist in any of our software. Period. One of the reasons we
> >> specifically switched to modal intervals many years ago is because c-set
> >> calculations involving {empty} were giving us problems (see section 8.2
> >> of
> >> my introductory paper for a related topic and example).
> >
> > Actually my question is how either [empty] or NaI would arise
> > in graphics applications involving the rendering of real scenes.
>
> Dan,
>
> The nice thing about working with intervals is it allows the *real* problems
> in fields like computer graphics to be solved, as opposed to some
> approximation based on linear, finite elements. Existing methods in computer
> graphics are based primarily on rendering of polygons and/or shooting
> infinitesimally thin "rays" into the scene, i.e., "ray tracing" or "point
> sampling."
>
> We do none of this. Instead, we attack the underlying nonlinear equations
> and do a true area-based, analytic solution of each pixel. This not only
> includes determining the pixel's visibility, but also the shading or "color"
> of the pixel. This process easily includes rather exotic nonlinear
> mathematics and functions that have poles, singularities or discontinuities.
> Particularly when features like nonlinear motion-blur or displacements
> appear in the scene. So issues of {empty} vs. NaI are commonplace.
Nate,
I'm sure that quadratic surfaces & reflections both specular &
otherwise present you with non-linear processes. I'm not sure
I would characterize them as 'exotic' but that's neither here
nor there.
I'm also sure you know things about this field that are far
beyond the ken of the rest of us.
Still I would like to see some simple example that us mere
mortals can understand. Some image of the princess that cannot
be rendered without NaIs. I'd like you to point to some soft
curve that produces an NaI that allows you to render it in a
way that [empty] or {[empty], NaI} would ruin the image for the
eye. Or perhaps the reflection of the tip of a sword off the
brass armor brestplate that would otherwise appear unreal.
Anything along these lines.
If you say it is so I will believe you. But merely saying it is
so provides me with no understanding of why. Or how.
>
> >> In a few cases where we might need to use a classical algorithm like
> >> interval Newton, we just check to see if the Newton step produces an
> >> improper (non-standard) modal interval. If it does, this is proof of
> >> non-existence of the zeros.
> >
> > This would seem to be the equivalent of proving the non-existence
> > of zeros in an interval that gets contracted to the empty set.
> >
> > Is it not?
>
> The end result is the same, but it does not require {empty}.
>
> In modal intervals, any non-standard interval [b,a] such that b > a is
> "moral equivalence" of {empty} for any classical algorithm.
Very well, if we adopt the definition that any interval [b,a]
such that b > a is considered a representation of the empty
interval then it could be said with equal justification that
NaI is not needed. It depends on your point of view.
Further, something like {[b,a],NaI-tag} allows us to have our
cake & eat it too. The [empty] is there for the c-set interval
people to work with & the NaI is there for you.
The conundrum can be resolved. There *IS* a two-state solution.
>
> >> Otherwise, NaI is used constructively, as indicator that a special
> >> subroutine or graphics algorithm must be used, for example, or to provide
> >> numerical proof that two interval expressions are not equivalent. It is
> >> also a mechanism that has consistently allowed us to find otherwise very
> >> insiduous bugs in the software during development process.
> >
> > Now this is different. If you are INTRODUCING NaI's as some
> > sort of programming indicator then I guess they cannot be
> > avoided. Unless, of course, Vincent's tags included some
> > sort of 'programming hack' tag as well. Its possible I
> > suppose.
> >
> > BTW, your programming trick is similar to the two examples of
> > practical uses for signalling NaNs that were brought to us at
> > 754 when we tried to get rid of sNaNs for performance reasons
> > among others. Prof Kahan & I published an article in Computer
> > Magazine asking the world for sNaN uses & we got only these two.
> >
> > Of these two, one was old enough that the sources no longer
> > existed & the other was an extensible interpretive language
> > that could solve the problem in another way.
> >
> > Perhaps some reflection will show that you can solve your
> > problem in some other way as well.
>
> No!
>
> In the world of intervals, it is misguided to call it a "trick." An example
> was already given in discussions in the ER subgroup, but I will re-present
> it here for those who have not seen:
I once had a professor who said that a trick was something you
used once. A technique was something you used twice. :-)
>
> Given the conditional equation
>
> (x^2-1)/(x-1) = x+1
>
> over domain [-4,4], what is the mathematical *truth* of the situation?
> Clearly the equation is false, because the expressions on left and right
> side are not equivalent, i.e., they are not equal when x = 1. However,
> c-sets say the two expressions are equivalent, because use of {empty} in the
> left side of the equation produces same result as the right side.
>
> So it is a serious mistake, I believe, if 1788 only supports the c-set view
> of things, because, in this case, it violates the "thou shall not lie"
> commandment.
>
> In our modal interval C++ library at Sunfish, the left side of the equation
> over [-4,4] evaluates to NaI and the right side to [-3,5]. So this is
> numerical proof the equations are not equivalent.
>
> It was years of "reflection" that drew me to the conclusion {empty} was the
> source of my problems, not the solution.
>
> >> . . .
> >>
> >> Nate
> >
> > . . .
> >
> > Enjoy,
> >
> > Dan
This example is no more compelling for its repetition. And your
'proof' assumes the result.
It is clear that you & the c-set people have different ideas on
this matter.
Let us not argue them here. I don't think it adds more light to
our discussion than heat.
In the end it may be that this is a religious issue similar to
what is your favorite computer language, text editor, or
operating system.
It would be nice if we could remove all such issues from the
standard in a sort of intervals separation of church & state.
I know the IEEE would like us to do this on grounds of not
favoring any existing vendor. But I fear it will not be the
case.
More's the pity...
Dan