# [vtkusers] Problems with ComputeOBB - wrong OBB computed

Oliver Weinheimer mail at oliwe.com
Tue Aug 12 08:54:58 EDT 2014

```Hi all,

the problem with

void vtkOBBTree::ComputeOBB(vtkPoints *pts, double corner, double max,
double mid, double min, double size)

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 = x - mean; xp = x - mean; xp = x - mean;
for (i=0; i < 3; i++)
{
a0[i] += xp * xp[i];
a1[i] += xp * xp[i];
a2[i] += xp * 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 = x - mean;
xp = x - mean;
xp = x - mean;
for (i = 0; i < 3; i++)
{
a0[i] += (xp * xp[i] - a0[i])/(pointId+1);
a1[i] += (xp * xp[i] - a1[i])/(pointId+1);
a2[i] += (xp * 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.
```