vtkBooleanOperationPolyDataFilter creates non-manifold edges

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

vtkBooleanOperationPolyDataFilter creates non-manifold edges

normanius
This post was updated on .
Hi all

This is an issue that has been raised already. But I wanted to ask whether there is a workaround or whether it actually is a bug that has been properly reported.

The attached sample code reproduces the problem: If I union two overlapping, watertight objects A and B, the resulting object C very likely won't be watertight (it shows border edges and non-manifold edges).

The sample code in essence does this:
- create cylinder A as a vtk.vtkCylinderSource
- create sphere B as a vtk.vtkSphereSource
- extract triangles from A and B
- create union C with vtk.vtkBooleanOperationPolyDataFilter() with SetOperationToUnion()

The problem occurs also, if I use other objects than cylinders or spheres.
The problem occurs also, if I "clean/condition" the surfaces of A and B before calculating the union. (I tried vtkCleanPolyData(), vtkFillHolesFilter() and addition of small noise on the vertices, which sometimes helps to regularise operations on objects)

In the following two screenshots. The first one indicates the two objects to union. The second one shows the result, with the non-manifold and border edges.

Input: objects A and B
Output: Union of A and B, results in non-manifold and border edges.

Because I often make use of vtkBooleanOperationPolyDataFilter, the problem is really annoying for me. That's why I thought to seek help in the community. Any ideas of how to handle this?
Cleaning the surface (set flag cleanOutputSurface=True in my code) does improve the situation in some cases - but it cannot be that one has to do that extra cleanup step after every such basic operation, right?!

By the way: this problem has been reported already: see here and here.

Thanks for any inputs from your side.

Sample file: reproduced_problem.py.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: vtkBooleanOperationPolyDataFilter creates non-manifold edges

Andras Lasso
> but it cannot be that one has to do that extra cleanup step after every such basic operation, right?!

Performing Boolean operation on meshes may sound easy but is an extremely difficult problem. It would be nice if VTK had a solution that worked reliably, so it's great that you submit reports on specific problems you find.

However, I'm not sure if there is anybody who could work on fixing these issues in the near future. So, if you cannot fix them yourself then most likely your best bet is to work around the problem by converting all meshes to images, combining them, and regenerating a mesh.

Andras

-----Original Message-----
From: vtkusers [mailto:[hidden email]] On Behalf Of normanius
Sent: May 15, 2016 4:54 AM
To: [hidden email]
Subject: [vtkusers] vtkBooleanOperationPolyDataFilter creates non-manifold edges

Hi all

This is an issue that has been raised already. But I wanted to ask whether there is a workaround or whether it actually is a bug that has been properly reported.

Find attached sample code which reproduces the problem: If I union two overlapping, watertight objects A and B, the resulting object C very likely won't be watertight (it shows border edges and non-manifold edges).

The sample code in essence does this:
- create cylinder A as a vtk.vtkCylinderSource
- create sphere B as a vtk.vtkSphereSource
- extract triangles from A and B
- create union C with vtk.vtkBooleanOperationPolyDataFilter() with
SetOperationToUnion()

The problem occurs also, if I use other objects than cylinders or spheres.
The problem occurs also, if I "clean/condition" the surfaces of A and B before calculating the union. (I tried vtkCleanPolyData(),
vtkFillHolesFilter() and addition of small noise on the vertices, which sometimes helps to regularise operations on objects)

In the following two screenshots. The first one indicates the two objects to union. The second one shows the result, with the non-manifold and border edges.

<http://vtk.1045678.n5.nabble.com/file/n5738088/input.png>
<http://vtk.1045678.n5.nabble.com/file/n5738088/result.png>

Because I often make use of vtkBooleanOperationPolyDataFilter, the problem is really annoying for me. That's why I thought to seek help in the community. Any ideas of how to handle this?
Cleaning the surface (set flag cleanOutputSurface=True in my code) does improve the situation in some cases - but it cannot be that one has to do that extra cleanup step after every such basic operation, right?!

By the way: this problem has been reported already: see  here <http://vtk.1045678.n5.nabble.com/Non-manifold-triangles-after-running-vtkBooleanOperationPolydataFilter-td5713964.html>
and  here
<http://vtk.1045678.n5.nabble.com/Broken-surfaces-for-vtkBooleanOperationPolyDataFilter-Bug-td5735413.html>
reproduced_problem.py
<http://vtk.1045678.n5.nabble.com/file/n5738088/reproduced_problem.py>  .

Thanks for any inputs from your side.



--
View this message in context: http://vtk.1045678.n5.nabble.com/vtkBooleanOperationPolyDataFilter-creates-non-manifold-edges-tp5738088.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

Search the list archives at: http://markmail.org/search/?q=vtkusers

Follow this link to subscribe/unsubscribe:
http://public.kitware.com/mailman/listinfo/vtkusers
_______________________________________________
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

Search the list archives at: http://markmail.org/search/?q=vtkusers

Follow this link to subscribe/unsubscribe:
http://public.kitware.com/mailman/listinfo/vtkusers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: vtkBooleanOperationPolyDataFilter creates non-manifold edges

Cory Quammen-2
Normanius,

On Mon, May 16, 2016 at 5:14 PM, Andras Lasso <[hidden email]> wrote:
>> but it cannot be that one has to do that extra cleanup step after every such basic operation, right?!
>
> Performing Boolean operation on meshes may sound easy but is an extremely difficult problem. It would be nice if VTK had a solution that worked reliably, so it's great that you submit reports on specific problems you find.

Hear hear.

> However, I'm not sure if there is anybody who could work on fixing these issues in the near future. So, if you cannot fix them yourself then most likely your best bet is to work around the problem by converting all meshes to images, combining them, and regenerating a mesh.

There is some new work that should improve the boolean operations filter:

https://gitlab.kitware.com/vtk/vtk/merge_requests/1336
https://gitlab.kitware.com/vtk/vtk/merge_requests/1272

This should hopefully be merged in the near term.

Best regards,
Cory

>
> Andras
>
> -----Original Message-----
> From: vtkusers [mailto:[hidden email]] On Behalf Of normanius
> Sent: May 15, 2016 4:54 AM
> To: [hidden email]
> Subject: [vtkusers] vtkBooleanOperationPolyDataFilter creates non-manifold edges
>
> Hi all
>
> This is an issue that has been raised already. But I wanted to ask whether there is a workaround or whether it actually is a bug that has been properly reported.
>
> Find attached sample code which reproduces the problem: If I union two overlapping, watertight objects A and B, the resulting object C very likely won't be watertight (it shows border edges and non-manifold edges).
>
> The sample code in essence does this:
> - create cylinder A as a vtk.vtkCylinderSource
> - create sphere B as a vtk.vtkSphereSource
> - extract triangles from A and B
> - create union C with vtk.vtkBooleanOperationPolyDataFilter() with
> SetOperationToUnion()
>
> The problem occurs also, if I use other objects than cylinders or spheres.
> The problem occurs also, if I "clean/condition" the surfaces of A and B before calculating the union. (I tried vtkCleanPolyData(),
> vtkFillHolesFilter() and addition of small noise on the vertices, which sometimes helps to regularise operations on objects)
>
> In the following two screenshots. The first one indicates the two objects to union. The second one shows the result, with the non-manifold and border edges.
>
> <http://vtk.1045678.n5.nabble.com/file/n5738088/input.png>
> <http://vtk.1045678.n5.nabble.com/file/n5738088/result.png>
>
> Because I often make use of vtkBooleanOperationPolyDataFilter, the problem is really annoying for me. That's why I thought to seek help in the community. Any ideas of how to handle this?
> Cleaning the surface (set flag cleanOutputSurface=True in my code) does improve the situation in some cases - but it cannot be that one has to do that extra cleanup step after every such basic operation, right?!
>
> By the way: this problem has been reported already: see  here <http://vtk.1045678.n5.nabble.com/Non-manifold-triangles-after-running-vtkBooleanOperationPolydataFilter-td5713964.html>
> and  here
> <http://vtk.1045678.n5.nabble.com/Broken-surfaces-for-vtkBooleanOperationPolyDataFilter-Bug-td5735413.html>
> reproduced_problem.py
> <http://vtk.1045678.n5.nabble.com/file/n5738088/reproduced_problem.py>  .
>
> Thanks for any inputs from your side.
>
>
>
> --
> View this message in context: http://vtk.1045678.n5.nabble.com/vtkBooleanOperationPolyDataFilter-creates-non-manifold-edges-tp5738088.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
>
> Search the list archives at: http://markmail.org/search/?q=vtkusers
>
> Follow this link to subscribe/unsubscribe:
> http://public.kitware.com/mailman/listinfo/vtkusers
> _______________________________________________
> 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
>
> Search the list archives at: http://markmail.org/search/?q=vtkusers
>
> Follow this link to subscribe/unsubscribe:
> http://public.kitware.com/mailman/listinfo/vtkusers



--
Cory Quammen
R&D Engineer
Kitware, Inc.
_______________________________________________
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

Search the list archives at: http://markmail.org/search/?q=vtkusers

Follow this link to subscribe/unsubscribe:
http://public.kitware.com/mailman/listinfo/vtkusers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: vtkBooleanOperationPolyDataFilter creates non-manifold edges

normanius
This post was updated on .
Hi Andras,
Hi Cory

Thanks for your answers.

@Andras: Do you mean poly-data to image conversion like this? Haven't ever used image data in vtk. Could you briefly sketch how to apply boolean operations on (3d) image data and how to generate a mesh from that. I guess this example is a starting point, right?

@Cory: Wow, I can't wait for vtkBooleanOperationPolyDataFilter2. I checked out that branch updega2/vtk-new_intersection, but could not see any difference with the output. Is there something special I need to do to enable Adam's new filter? (Because there is no class named vtkBooleanOperationPolyDataFilter2, I assumed that the former vtkBooleanOperationPolyDataFilter was re-written.)

As an alternative to vtkBooleanOperationPolyDataFilter: I sometimes use vtkImplicitFunction (vtkCylinder, vtkSphere, etc.), combine them with vtkImplicitBoolean and sample then with vtkSampleFunction. This is not always practicable however, because one gets visible artefacts on the borders/edges, and also the meshes get quite large. (The work-around for the latter is to apply triangle decimation, see vtkDecimatePro).
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: vtkBooleanOperationPolyDataFilter creates non-manifold edges

Andras Lasso

Yes, those examples are good starting points. You can use image math filter to compute min/max (intersection/union) and create mesh from image using contour filter.

 

Andras

 

From: [hidden email]
Sent: May 16, 2016 18:27
To: [hidden email]
Subject: Re: [vtkusers] vtkBooleanOperationPolyDataFilter creates non-manifold edges

 

Hi Andras,
Hi Cory

Thanks for your answers.

@Andras: Do you mean poly-data to image conversion like  this
<http://www.vtk.org/Wiki/VTK/Examples/Cxx/PolyData/PolyDataToImageData>  ?
Haven't ever used image data in vtk. Could you briefly sketch how to apply
boolean operations on (3d) image data and how to generate a mesh from that.
I guess  this
<http://www.vtk.org/Wiki/VTK/Examples/Cxx/PolyData/PolyDataToImageData
example is a starting point, right?

@Cory: Wow, I can't wait for vtkBooleanOperationPolyDataFilter2. I checked
out that branch updega2/vtk-new_intersection, but could not see any
difference with the output. Is there something special I need to do to
enable Adam's new filter? (Because there is no class named
vtkBooleanOperationPolyDataFilter2, I assumed that the former
vtkBooleanOperationPolyDataFilter was re-written.)

As an alternative to vtkBooleanOperationPolyDataFilter: I sometimes use
vtkImplicitFunction (vtkCylinder, vtkSphere, etc.), combine them with
vtkImplicitBoolean and sample then with vtkSampleFunction. This is not
always practicable however, because one gets visible artefacts on the
borders, and also the meshes get quite large. (The work-around for the
latter is to apply triangle decimation, see vtkDecimatePro).



--
View this message in context: http://vtk.1045678.n5.nabble.com/vtkBooleanOperationPolyDataFilter-creates-non-manifold-edges-tp5738088p5738108.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

Search the list archives at: http://markmail.org/search/?q=vtkusers

Follow this link to subscribe/unsubscribe:
http://public.kitware.com/mailman/listinfo/vtkusers

_______________________________________________
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

Search the list archives at: http://markmail.org/search/?q=vtkusers

Follow this link to subscribe/unsubscribe:
http://public.kitware.com/mailman/listinfo/vtkusers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: vtkBooleanOperationPolyDataFilter creates non-manifold edges

Cory Quammen-2
In reply to this post by normanius
> @Cory: Wow, I can't wait for vtkBooleanOperationPolyDataFilter2. I checked
> out that branch updega2/vtk-new_intersection, but could not see any
> difference with the output. Is there something special I need to do to
> enable Adam's new filter? (Because there is no class named
> vtkBooleanOperationPolyDataFilter2, I assumed that the former
> vtkBooleanOperationPolyDataFilter was re-written.)

The vtkBooleanOperationPolyDataFilter2 class is in the second merge
request I listed. It's a little messy right now because I asked Adam
to split out the changes to the intersection filter and the boolean
operation filter. If you try the second merge request branch, you
should hopefully see improved results from
vtkBooleanOperationPolyDataFilter2.

--
Cory Quammen
R&D Engineer
Kitware, Inc.
_______________________________________________
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

Search the list archives at: http://markmail.org/search/?q=vtkusers

Follow this link to subscribe/unsubscribe:
http://public.kitware.com/mailman/listinfo/vtkusers
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: vtkBooleanOperationPolyDataFilter creates non-manifold edges

normanius
This post was updated on .
Hey Cory,

Give that guy a throne! Adam's work does solve my problem. Hurray hurray! :)))

If I switch to that other branch (updega2/vtk-boolean_retry) and change vtkBooleanOperation() to vtkBooleanOperation2() I don't get any non-manifold edges, and also the boundary-edges seem to make sense now (that vtkBooleanOperation messed up completely).

One issue I noticed after applying boolean ops consecutively: while all expected boundary-edges are returned correctly, there is one extra border showing up for which I don't have any interpretation. I'll let you know when I notice any other issues with that new version.

For which release roughly do you think vtkBooleanOperation2 will be available?

And a big thanks to Adam and everyone else involved in this fix. :)))

default_surface.png
default_borders_labeled.png
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: vtkBooleanOperationPolyDataFilter creates non-manifold edges

na_bil
Hi normanius,
I need to use Adam algorithm, could you please guide me how. I use VTK 7.1
Thx
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: vtkBooleanOperationPolyDataFilter creates non-manifold edges

normanius
This post was updated on .
Hi

You need to checkout the version and build it from source.
Unfortunately, Adam's code has not been merged into Master yet.

Documentation of the branch:
[1] https://gitlab.kitware.com/vtk/vtk/merge_requests/1272
[2] https://gitlab.kitware.com/updega2/vtk/commits/boolean_retry

# Clone vtk and checkout Adam's version.
git clone https://gitlab.kitware.com/vtk/vtk.git
git fetch https://gitlab.kitware.com/updega2/vtk.git
git checkout -b updega2/boolean_retry FETCH_HEAD
git rev-parse HEAD
# The last command should return the hash as documented in the second link [2]

# Build vtk (with python wrapper), something like the following works for me:
cd vtk
mkdir build
cd build
cmake .. -DCMAKE_BUILD_TYPE=Release \
                     -DVTK_WRAP_PYTHON=ON -DBUILD_EXAMPLES=ON -DBUILD_SHARED_LIBS=ON \
                     -DBUILD_TESTING=OFF \
                     -DCMAKE_INSTALL_PREFIX="/install/path/vtk-7.1.0-updega2-boolean-retry"
make
make install

Try to use git rebase if you want to use a newer version of vtk as reference, maybe you are lucky and don't get any merge conflicts.

HTH
Loading...