[vtkusers] Problems with ComputeOBB - wrong OBB computed

[Goodwin Lawlor]

Hi Oliver,

That's a nice method - the mean is gradually accumulated, preserving the
accuracy of the floating point value. I'm sure there are other places in
VTK that would benefit from this code change...

If you're familiar with Gerrit, could you submit this change? I'll have a
poke around the code base to see if there are other similar mean
calculations.

Goodwin


On Tue, Aug 12, 2014 at 1:54 PM, Oliver Weinheimer <mail at oliwe.com> wrote:

> Hi all,
>
> the problem with
>
> void vtkOBBTree::ComputeOBB(vtkPoints *pts, double corner[3], double
> max[3],
> double mid[3], double min[3], double size[3])
>
> is a problem of the accuracy of floating point arithmetic.
> The objects I am dealing with contain several million points.
> This leads to problems with the mean value calculations in ComputeOBB.
> At two locations mean values are calculated in ComputeOBB, the second
> location introduced the greatest part of the errors in my case.
> I replaced the mean calculations with the method you can find in Knuth's
> Vol
> 2 of The Art of Computer Programming, 1998 edition, page 232.
>
> This solved at least my problems with the method!
>
> (1)
> I replaced
>
> --- source code begin
>         for (pointId=0; pointId < numPts; pointId++ )
>         {
>                 pts->GetPoint(pointId, x);
>                 for (i=0; i < 3; i++)
>                 {
>                         mean[i] += x[i];
>                 }
>         }
>         for (i=0; i < 3; i++)
>         {
>                 mean[i] /= numPts;
>         }
> --- source code end
>
> by these lines:
>
> --- source code begin
> for (pointId = 0; pointId < numPts; pointId++)
> {
>         pts->GetPoint(pointId, x);
>         for (i = 0; i < 3; i++){
>                 mean[i] += (x[i] - mean[i])/(pointId+1);
>         }
> }
>
> --- source code end
>
> (2)
>
> and I replaced
>
> --- source code begin
> for (pointId=0; pointId < numPts; pointId++ )
> {
>         pts->GetPoint(pointId, x);
>         xp[0] = x[0] - mean[0]; xp[1] = x[1] - mean[1]; xp[2] = x[2] -
> mean[2];
>         for (i=0; i < 3; i++)
>         {
>                 a0[i] += xp[0] * xp[i];
>                 a1[i] += xp[1] * xp[i];
>                 a2[i] += xp[2] * xp[i];
>         }
> }//for all points
>
> for (i=0; i < 3; i++)
> {
>         a0[i] /= numPts;
>         a1[i] /= numPts;
>         a2[i] /= numPts;
> }
> --- source code end
>
> by
>
> --- source code begin
> for (pointId = 0; pointId < numPts; pointId++)
> {
>         pts->GetPoint(pointId, x);
>         xp[0] = x[0] - mean[0];
>         xp[1] = x[1] - mean[1];
>         xp[2] = x[2] - mean[2];
>         for (i = 0; i < 3; i++)
>         {
>                 a0[i] += (xp[0] * xp[i] - a0[i])/(pointId+1);
>                 a1[i] += (xp[1] * xp[i] - a1[i])/(pointId+1);
>                 a2[i] += (xp[2] * xp[i] - a2[i])/(pointId+1);
>         }
> }
> --- source code end
>
> Best Wishes,
> Oliver
>
>
>
> --
> View this message in context:
> http://vtk.1045678.n5.nabble.com/Problems-with-ComputeOBB-wrong-OBB-computed-tp5728174p5728187.html
> Sent from the VTK - Users mailing list archive at Nabble.com.
> _______________________________________________
> Powered by www.kitware.com
>
> Visit other Kitware open-source projects at
> http://www.kitware.com/opensource/opensource.html
>
> Please keep messages on-topic and check the VTK FAQ at:
> http://www.vtk.org/Wiki/VTK_FAQ
>
> Follow this link to subscribe/unsubscribe:
> http://public.kitware.com/mailman/listinfo/vtkusers
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtkusers/attachments/20140813/d13c934d/attachment.html>