[vtkusers] Problems with ComputeOBB - wrong OBB computed

[Oliver Weinheimer]

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.