[vtk-developers] Re: Logic Problem in vtkFixedPointVolumeRayCastMapper (SOLUTION)?

[Randall Hand]

All of this has been logged as bug 5519, along with the diff patch.

http://www.vtk.org/Bug/view.php?id=5519

-- 
----------------------------------------
Randall Hand
Visualization Scientist
ERDC MSRC-ITL

On 8/16/07, Randall Hand <randall.hand at gmail.com> wrote:
>
> ok.. After several days of looking into this, I think I finally figured it
> out and came up with a fix that (in my tests) fixes the problem 100%.
>
> The problem seems to be in the loss of accuracy involved with converting
> between Floating-Point and Fixed-Point.  The loss of accuracy is a "known
> issue", and typically not much of a problem, but the small numbers involved
> when the Direction approaches 0 yields some odd answers.  This is further
> compounded by the way that the Endpoints of the Ray and the Direction of the
> ray are computed.  Previously, the number of steps to take along the ray
> were computed on each axis independently, and then the smallest number was
> used.    Presumably, this was because if anything bigger was used then the
> ray would leave the volume & the array index routines ran the risk of
> overflowing (leading to Segfaults).  But because of the accuracy of the
> arithmetic with very-small numbers, the answers are simply wrong sometimes.
> This leads to oddities where rayStart + Direction*NumSteps does not
> necessarily equal the end of the ray.
>
> So, I modified the code to take the Largest, rather than the smallest, of
> the 3 numbers calculated.   Then, to prevent overflow, recompute the
> Fixed-Point ray direction to ensure that End = Start + Direction*numSteps.
> a Diff Patch to make these changes is shown below (and attached to this
> email).
>
> The time require to generate a volume rendering is effectively unchanged
> (144seconds before, 148 seconds now).
>
> ---
> ../../backup/VTK/VolumeRendering/vtkFixedPointVolumeRayCastMapper.cxx
> 2006-12-02 11:10: 35.000000000 -0600
> +++ vtkFixedPointVolumeRayCastMapper.cxx        2007-08-16 09:51:
> 07.070980624 -0500
> @@ -1979,7 +1979,7 @@ float vtkFixedPointVolumeRayCastMapper::
>
> ((rayDirection[0]<0)?(-rayDirection[0]):(rayDirection[0])) );
>        }
>
> -    if ( diff[1] >= diff[0] && diff[1] >= diff[2] && rayDirection[2])
> +    if ( diff[1] >= diff[0] && diff[1] >= diff[2] && rayDirection[1])
>        {
>        steps = 1 + static_cast<int>( diff[1] /
>
> ((rayDirection[1]<0)?(-rayDirection[1]):(rayDirection[1])) );
> @@ -2043,12 +2043,31 @@ float vtkFixedPointVolumeRayCastMapper::
>              }
>            }
>
> -        if ( !stepsValid || currSteps < *numSteps )
> +        if ( !stepsValid || currSteps > *numSteps )
>            {
>            *numSteps = currSteps;
>            stepsValid = 1;
>            }
>          }
> +      for ( stepLoop = 0; stepLoop < 3; stepLoop++ )
> +        {
> +        unsigned int endVal =
> this->ToFixedPointPosition(rayEnd[stepLoop]);
> +        if (dir[stepLoop]&0x80000000)
> +          {
> +          if (endVal >= pos[stepLoop])
> +            {
> +            dir[stepLoop] =  (endVal - pos[stepLoop]) / *numSteps;
> +            dir[stepLoop] = dir[stepLoop] | 0x80000000;
> +            }
> +          }
> +          else
> +          {
> +            if (endVal <= pos[stepLoop])
> +              {
> +              dir[stepLoop] =  (pos[stepLoop] - endVal) / *numSteps;
> +              }
> +          }
> +        }
>        }
>      }
>  }
>
>
> --
> ----------------------------------------
> Randall Hand
> Visualization Scientist
> ERDC MSRC-ITL
>
> On 8/15/07, Randall Hand <randall.hand at gmail.com> wrote:
> >
> > Anyone looking at this?
> >
> > Also, I believe I found a typo bug in
> > vtkFixedPointVolumeRayCastMapper.cxx.  Line 1982 reads:
> >
> >     if ( diff[1] >= diff[0] && diff[1] >= diff[2] && rayDirection[2])
> >
> > But I'm pretty sure it should be:
> >
> >     if ( diff[1] >= diff[0] && diff[1] >= diff[2] && rayDirection[1])
> >
> > (Wrong rayDirection Index).
> >
> > --
> > ----------------------------------------
> > Randall Hand
> > Visualization Scientist
> > ERDC MSRC-ITL
> >
> > On 8/13/07, Randall Hand < randall.hand at gmail.com> wrote:
> > >
> > > I've been looking into a problem in the
> > > vtkFixedPointVolumeRayCastMapper and I've about exhausted my immediate
> > > expertise in the situation, so I present it here in hopes that someone else
> > > can chime in (Lisa, are you reading this?)
> > >
> > > I'm rendering vtkImageData with the FixedPoint mapper, and seeing odd
> > > problems along the zero-crossings when the data is presented in a
> > > Perspective view direct-on to the user (or close to it).  The problem
> > > doesn't manifest in Parallel/Orthographic views, and it's fairly difficult
> > > to see.  The visual problem is black lines (black background in my case)
> > > presented in the center of the data on the X & Y image axes, but not
> > > completely through the data.  The part of the data closer to the viewer is
> > > rendered properly, but the distant part is not rendered at all.
> > >
> > > After alot of printfs, I've started to narrow down the problem.  In
> > > vtkFixedPointVolumeRayCastMapper.cxx's "ComputeRayInfo" function, the
> > > "numSteps" seems to be computed incorrectly.  Currently, you compute the
> > > numSteps necessary along each of the 3 axis directions, and keep the
> > > smallest number.  This works most of the time, except when the "direction"
> > > component is near-0.  You have an "if" check for equal to zero, but when the
> > > alignment is such that the "direction" becomes 1 or -1 (which is
> > > infinitesimally close to zero once the Fixed-Point conversion is made), the
> > > math seems to come out wrong.  In my dataset:
> > >
> > > i=435, j=3, numSteps = 156
> > > i=436, j=3, numSteps = 149
> > > i=437, j=3, numSteps = 134
> > > i=438, j=3, numSteps = 90
> > > i=439, j=3, numSteps = 90
> > > i=440, j=3, numSteps = 134
> > > i=441, j=3, numSteps = 149
> > > i=442, j=3, numSteps = 156
> > > i=443, j=3, numSteps = 160
> > > i=444, j=3, numSteps = 163
> > > i=445, j=3, numSteps = 165
> > >
> > > (generated with printf's I added to the code).  At the center of the
> > > image, when i=438 & 439, you'll see the numSteps takes an unusual drop.  The
> > > same happens when the j crosses the center of the image, because the Y
> > > component of the direction drops to near-0.  The result is that the rays
> > > terminate early, without fully passing through the volume.
> > >
> > > Now, I can "alleviate" this problem by changing:
> > >         if ( !(dir[stepLoop]&0x7fffffff ))
> > >           {
> > >           continue;
> > >           }
> > >
> > > to
> > >         if ( (dir[stepLoop]&0x7fffffff ) < 10)
> > >           {
> > >           continue;
> > >           }
> > >
> > > But that doesn't really "solve" the problem.  I think that perhaps the
> > > method used to compute "currSteps" needs to be changed, although I haven't
> > > been able to find a method that seems to work any better.
> > >
> > > Hopefully this can help someone find the cause of this problem.
> > > --
> > > ----------------------------------------
> > > Randall Hand
> > > Visualization Scientist
> > > ERDC MSRC-ITL
> >
> >
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20070816/be182e27/attachment.html>