View Issue Details

IDProjectCategoryView StatusLast Update
0023894CommunityOCCT:Visualizationpublic2013-12-19 13:55
ReporterPawel Assigned ToPawel  
PrioritynormalSeverityminor 
Status closedResolutionfixed 
PlatformWindowsOSVC++ 2008 
Product Version6.6.0 
Target Version6.7.0Fixed in Version6.7.0 
Summary0023894: Voxel_BooleanOperation (Cut) gives incorrect results
DescriptionPerforming 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.
Steps To ReproduceI'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;
fcp.Convert(progress);
fcp.FillInVolume(1);

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

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.
TagsNo tags attached.
Test case numberv3d voxel(012)

Attached Files

  • Voxel_BoolDS_Cut_SphereBox02.png (54,267 bytes)
  • Voxel_BoolDS_Cut_SphereBox01.png (50,178 bytes)
  • SphereMinusBox.png (48,105 bytes)
  • Voxel_BoolDS_Cut_SphereBox02_Fixed.png (77,214 bytes)

Activities

Pawel

2013-04-11 19:08

developer  

Voxel_BoolDS_Cut_SphereBox02.png (54,267 bytes)

Pawel

2013-04-11 19:14

developer  

Voxel_BoolDS_Cut_SphereBox01.png (50,178 bytes)

vro

2013-05-08 16:39

developer   ~0024343

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.

vro

2013-05-08 16:40

developer  

SphereMinusBox.png (48,105 bytes)

vro

2013-05-08 16:43

developer   ~0024344

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.

Pawel

2013-05-08 18:56

developer   ~0024349

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...

Pawel

2013-05-08 19:00

developer   ~0024350

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...

Pawel

2013-05-08 19:20

developer   ~0024351

When I change the deflection to 0.001 no strip occurs...

Pawel

2013-05-17 18:51

developer   ~0024429

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;
fcp.Convert(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):

28,50,28
28,50,31
28,50,30
28,50,57
28,50,56
28,50,59

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...

Pawel

2013-05-21 19:12

developer   ~0024456

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.

Pawel

2013-06-07 01:13

developer  

Voxel_BoolDS_Cut_SphereBox02_Fixed.png (77,214 bytes)

Pawel

2013-06-07 01:32

developer   ~0024682

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 (http://www.codercorner.com/Opcode.htm).

To see the result of the new method for the box-sphere cut refer to the attached picture(Voxel_BoolDS_Cut_SphereBox02_Fixed.png).

vro

2013-06-10 11:02

developer   ~0024707

Reviewed!

mkv

2013-06-11 12:30

tester   ~0024729

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)

Regressions:
No regressions

Improvements:
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.

Related Changesets

occt: master f03671a0

2013-06-13 11:19:29

Pawel

Details Diff
0023894: Voxel_BooleanOperation (Cut) gives incorrect results

Implemented a new method using separating axis theorem to compute triangle-box intersection. Based on the intersection result the decision whether to set the voxel is made.
Adjustment of lines (removal of extra-spaces).
Adding test cases for voxel testing
Affected Issues
0023894
mod - src/Voxel/Voxel_FastConverter.cdl Diff File
mod - src/Voxel/Voxel_FastConverter.cxx Diff File
mod - tests/v3d/grids.list Diff File
add - tests/v3d/voxel/A1 Diff File
add - tests/v3d/voxel/A2 Diff File
add - tests/v3d/voxel/A3 Diff File
add - tests/v3d/voxel/A4 Diff File
add - tests/v3d/voxel/A5 Diff File
add - tests/v3d/voxel/A6 Diff File
add - tests/v3d/voxel/A7 Diff File
add - tests/v3d/voxel/A8 Diff File
add - tests/v3d/voxel/A9 Diff File
add - tests/v3d/voxel/B1 Diff File
add - tests/v3d/voxel/B2 Diff File

Issue History

Date Modified Username Field Change
2013-04-11 18:58 Pawel New Issue
2013-04-11 18:58 Pawel Assigned To => san
2013-04-11 18:58 Pawel File Added: Voxel_BoolDS_Cut_SphereBox01.png
2013-04-11 19:07 Pawel Assigned To san => vro
2013-04-11 19:07 Pawel Description Updated
2013-04-11 19:07 Pawel Steps to Reproduce Updated
2013-04-11 19:08 Pawel File Added: Voxel_BoolDS_Cut_SphereBox02.png
2013-04-11 19:10 Pawel Description Updated
2013-04-11 19:12 Pawel Description Updated
2013-04-11 19:12 Pawel Steps to Reproduce Updated
2013-04-11 19:14 Pawel File Deleted: Voxel_BoolDS_Cut_SphereBox01.png
2013-04-11 19:14 Pawel File Added: Voxel_BoolDS_Cut_SphereBox01.png
2013-04-11 19:15 Pawel Description Updated
2013-04-11 19:17 Pawel Steps to Reproduce Updated
2013-05-08 16:39 vro Note Added: 0024343
2013-05-08 16:39 vro Assigned To vro => Pawel
2013-05-08 16:39 vro Status new => feedback
2013-05-08 16:40 vro File Added: SphereMinusBox.png
2013-05-08 16:43 vro Note Added: 0024344
2013-05-08 18:56 Pawel Note Added: 0024349
2013-05-08 19:00 Pawel Note Added: 0024350
2013-05-08 19:00 Pawel Assigned To Pawel => vro
2013-05-08 19:00 Pawel Status feedback => assigned
2013-05-08 19:20 Pawel Note Added: 0024351
2013-05-17 18:51 Pawel Note Added: 0024429
2013-05-21 19:12 Pawel Note Added: 0024456
2013-06-07 01:13 Pawel File Added: Voxel_BoolDS_Cut_SphereBox02_Fixed.png
2013-06-07 01:32 Pawel Note Added: 0024682
2013-06-07 01:32 Pawel Status assigned => resolved
2013-06-10 11:02 vro Note Added: 0024707
2013-06-10 11:02 vro Status resolved => reviewed
2013-06-10 12:47 mkv Assigned To vro => mkv
2013-06-11 12:30 mkv Note Added: 0024729
2013-06-11 12:31 mkv Test case number => v3d voxel(012)
2013-06-11 12:31 mkv Assigned To mkv => bugmaster
2013-06-11 12:31 mkv Status reviewed => tested
2013-06-14 12:18 Pawel Changeset attached => occt master f03671a0
2013-06-14 12:18 Pawel Assigned To bugmaster => Pawel
2013-06-14 12:18 Pawel Status tested => verified
2013-06-14 12:18 Pawel Resolution open => fixed
2013-12-19 13:53 bugmaster Status verified => closed
2013-12-19 13:55 bugmaster Fixed in Version => 6.7.0