MantisBT - Community
View Issue Details
0023894Community[OCCT] OCCT:Visualizationpublic2013-04-11 18:582013-12-19 13:55
WindowsVC++ 200864 bit
[OCCT] 6.6.0 
[OCCT] 6.7.0[OCCT] 6.7.0 
v3d voxel(012)
0023894: Voxel_BooleanOperation (Cut) gives incorrect results
Performing Voxel_BooleanOperation::Cut gives incorrect results while cutting a box with a sphere.

For instance, for the code given below in Voxel_BooleanOperation::Cut, for
ix = 28, iy = 52, iz = 40

the line 131
Standard_Boolean value2 = theVoxels2.Get(ix, iy, iz);

returns 0, meaning there is no material at this place, while this position is definitely located inside the sphere. Consequently, the voxels from the box are not substracted/cut.

Consult the images to see the problem.

On the first one (Voxel_BoolDS_Cut_SphereBox01.png) no voxels are cut near one of the edges of the box - pay attention to the gray strip.
On the second one (Voxel_BoolDS_Cut_SphereBox02.png) many gray strips are visible - no material is detected inside the sphere.
I'm not sure how to reproduce the problem in DRAW therefore only C++ reproducer:

TopoDS_Shape shape = BRepPrimAPI_MakeSphere(gp_Pnt(11,8,11), 7);
TopoDS_Shape shape1 = BRepPrimAPI_MakeBox(gp_Pnt(7, 10, 10), 5, 3, 3);

Standard_Real delfection = 0.1;
Standard_Integer nbx = 200, nby = 200, nbz = 200;
Voxel_BoolDS theVoxels(0,0,0, 50, 50, 50, nbx, nby, nbz);
Voxel_BoolDS theVoxels1(0,0,0, 50, 50, 50, nbx, nby, nbz);
Standard_Integer nbThreads = 1;

Voxel_FastConverter fcp(shape, theVoxels, delfection, nbx, nby, nbz, nbThreads);
Standard_Integer progress;

Voxel_FastConverter fcp1(shape1, theVoxels1, delfection, nbx, nby, nbz, nbThreads);
progress = 0;

Voxel_BooleanOperation op;
Standard_Boolean result = op.Cut(theVoxels1, theVoxels);

You can also try using a bigger box:

TopoDS_Shape shape1 = BRepPrimAPI_MakeBox(gp_Pnt(5, 10, 10), 10, 20, 30);

to see the problem occurs frequently.
No tags attached.
png Voxel_BoolDS_Cut_SphereBox02.png (54,267) 2013-04-11 19:08
png Voxel_BoolDS_Cut_SphereBox01.png (50,178) 2013-04-11 19:14
png SphereMinusBox.png (48,105) 2013-05-08 16:40
png Voxel_BoolDS_Cut_SphereBox02_Fixed.png (77,214) 2013-06-07 01:13
Issue History
2013-04-11 18:58PawelNew Issue
2013-04-11 18:58PawelAssigned To => san
2013-04-11 18:58PawelFile Added: Voxel_BoolDS_Cut_SphereBox01.png
2013-04-11 19:07PawelAssigned Tosan => vro
2013-04-11 19:07PawelDescription Updatedbug_revision_view_page.php?rev_id=5316#r5316
2013-04-11 19:07PawelSteps to Reproduce Updatedbug_revision_view_page.php?rev_id=5318#r5318
2013-04-11 19:08PawelFile Added: Voxel_BoolDS_Cut_SphereBox02.png
2013-04-11 19:10PawelDescription Updatedbug_revision_view_page.php?rev_id=5319#r5319
2013-04-11 19:12PawelDescription Updatedbug_revision_view_page.php?rev_id=5320#r5320
2013-04-11 19:12PawelSteps to Reproduce Updatedbug_revision_view_page.php?rev_id=5321#r5321
2013-04-11 19:14PawelFile Deleted: Voxel_BoolDS_Cut_SphereBox01.png
2013-04-11 19:14PawelFile Added: Voxel_BoolDS_Cut_SphereBox01.png
2013-04-11 19:15PawelDescription Updatedbug_revision_view_page.php?rev_id=5322#r5322
2013-04-11 19:17PawelSteps to Reproduce Updatedbug_revision_view_page.php?rev_id=5323#r5323
2013-05-08 16:39vroNote Added: 0024343
2013-05-08 16:39vroAssigned Tovro => Pawel
2013-05-08 16:39vroStatusnew => feedback
2013-05-08 16:40vroFile Added: SphereMinusBox.png
2013-05-08 16:43vroNote Added: 0024344
2013-05-08 18:56PawelNote Added: 0024349
2013-05-08 19:00PawelNote Added: 0024350
2013-05-08 19:00PawelAssigned ToPawel => vro
2013-05-08 19:00PawelStatusfeedback => assigned
2013-05-08 19:20PawelNote Added: 0024351
2013-05-17 18:51PawelNote Added: 0024429
2013-05-21 19:12PawelNote Added: 0024456
2013-06-07 01:13PawelFile Added: Voxel_BoolDS_Cut_SphereBox02_Fixed.png
2013-06-07 01:32PawelNote Added: 0024682
2013-06-07 01:32PawelStatusassigned => resolved
2013-06-10 11:02vroNote Added: 0024707
2013-06-10 11:02vroStatusresolved => reviewed
2013-06-10 12:47mkvAssigned Tovro => mkv
2013-06-11 12:30mkvNote Added: 0024729
2013-06-11 12:31mkvTest case number => v3d voxel(012)
2013-06-11 12:31mkvAssigned Tomkv => bugmaster
2013-06-11 12:31mkvStatusreviewed => tested
2013-06-14 12:18PawelChangeset attached => occt master f03671a0
2013-06-14 12:18PawelAssigned Tobugmaster => Pawel
2013-06-14 12:18PawelStatustested => verified
2013-06-14 12:18PawelResolutionopen => fixed
2013-12-19 13:53bugmasterStatusverified => closed
2013-12-19 13:55bugmasterFixed in Version => 6.7.0

2013-05-08 16:39   
Hi Pawel,
Thank you for the full information on the bug.
I put a break point at the line 131 of Voxel_BooleanOperation::Cut() - it returns 1 for the voxel (28, 52, 40).
Also, I noticed that you subtract a sphere from the box. It would be better to subtract a box from the sphere because the sphere is greater and contains the whole box (I attach a picture).
I made the tests on Visual Studio 2010, 32bits. Let me know please if the bug still presents in your environment and I will check it Visualo Studio 2008, 64bits.
2013-05-08 16:43   
In the picture SphereMinusBox I used VoxelDemo - a free sample application. It allows visualization of voxels displaying only a part of them (clipping the view by a plane). In the picture you may see a sphere and subtracted voxels from the place where the box is located. Visually - the operation is performed without a defect.
2013-05-08 18:56   
Dear vro,

thanks for your feedback!

I have double-checked and here are the results:

My system is Win7 x64, VS2008, I used OCCT 660 (current master) as 32 and 64 bit.
I took two shapes:
TopoDS_Shape shape = BRepPrimAPI_MakeSphere(gp_Pnt(11,8,11), 7);
TopoDS_Shape shape1 = BRepPrimAPI_MakeBox(gp_Pnt(7, 10, 10), 5, 3, 3);

I subtracted the sphere from the box which should produce 'void' but I still get this strip as depicted.

I also noticed that Voxel_FastConverter::FillInVolume never fills the voxel (28, 52, 40) of the sphere. The line 336:

 ((Voxel_BoolDS*)myVoxels)->Set(ix, iy, iz, inner);

is called for ix = 29 but not sooner. This is actually the reason why the line 131:

Standard_Boolean value2 = theVoxels2.Get(ix, iy, iz);

in Voxel_BooleanOperation::Cut returns '0'.

So I guess there is something wrong here but at this time I can't say more...
2013-05-08 19:00   
Dear vro,

please consult my comment above.

I guess there is some problem with the filling of the sphere. I might be wrong. I'm a bit puzzled by the fact you weren't able to reproduce the problem.

Maybe because of the different VS version...
2013-05-08 19:20   
When I change the deflection to 0.001 no strip occurs...
2013-05-17 18:51   
Another observation...

I suspect the problem might be caused by the method Voxel_FastConverter::ComputeVoxelsNearTriangle.

I have noticed that for the code

TopoDS_Shape shape = BRepPrimAPI_MakeSphere(gp_Pnt(11,8,11), 7);
Standard_Real delfection = 0.1;
Standard_Integer nbx = 200, nby = 200, nbz = 200;
Voxel_BoolDS theVoxels(0,0,0, 50, 50, 50, nbx, nby, nbz);
Standard_Integer nbThreads = 1;

Voxel_FastConverter fcp(shape, theVoxels, delfection, nbx, nby, nbz, nbThreads);
Standard_Integer progress;

the method finds and sets - (((Voxel_BoolDS*) myVoxels)->Set(ix, iy, iz, Standard_True);) - for instance six surface voxels for the sphere at the specified voxel-coordinate (28,50):


which is obviously wrong because only two surface voxels should be found!

I guess, this might lead to incorrect computation in Voxel_FastConverter::FillInVolume.

Voxel_FastConverter::ComputeVoxelsNearTriangle might use an incorrect precision value somewhere because changing the meshing deflection affects the behaviour described above. However, not sure...
2013-05-21 19:12   
OK, I think I have found the root cause of the problem (although not implemented the solution yet).

Voxel_FastConverter::Convert calls ComputeVoxelsNearTriangle which "Refuses voxels for whom distance from their center to plane of triangle is greater than half of diagonal". In this approach, a triangle-sphere test (sphere has the radius of half of diagonal) - line 460, Voxel_FastConverter.cxx - is performed to decide whether a triangle intersects a voxel. This is wrong in my my opinion because a voxel is considered to be a cube, isn't it? This is the reason why too many voxels are set to Standard_True (see my note above 0024429).

Thus a triangle-box intersection test should be used in ComputeVoxelsNearTriangle to give more accurate results.
2013-06-07 01:32   
Dear Vlad,

branch CR23894 has been pushed and is ready for review.

I have implemented an alternative method converting TopoDS_Shape to voxels. The new method computes triangle-box intersection to judge whether a voxel intersects the triangulation or not.

I guess the old implementation is wrong because it checks the interference of the triangulation with a sphere. I think it is also slower (at least this is what I observed). However, I leave the decision whether to keep it or not to you.

The triangle-box intersection code was derived from Pierre Terdiman's implementation (public domain) used in OPCODE ( [^]).

To see the result of the new method for the box-sphere cut refer to the attached picture(Voxel_BoolDS_Cut_SphereBox02_Fixed.png).
2013-06-10 11:02   
2013-06-11 12:30   
Dear BugMaster,

Branch CR23894 (and products from GIT master) was compiled on Linux and Windows platforms and tested.
SHA-1: 5d043261fc31757919c30ba423d6f9de6d1e4750

Number of compiler warnings:

occt component :
Linux: 2 (2 on master)
Windows: 7 (7 on master)

products component :
Linux: 0 (0 on master)
Windows: 63 (63 on master)

No regressions

No improvements

Testing cases:
v3d voxel - OK.

Testing on Linux:
Total MEMORY difference: 366333156 / 366313324
Total CPU difference: 40875.56000000081 / 43688.52000000147

Testing on Windows:
Total MEMORY difference: 421059316 / 423437552
Total CPU difference: 39796.328125 / 31295.625

There are not differences in images found by testdiff.