Convex Hull Node #87315

New Issue

Henrik D. · 2021-04-08T22:13:48+02:00

Henrik D. commented

2021-04-08 22:13:48 +02:00

This node creates a convex hull of a mesh or a point cloud. If you don't know what a convex hull is, here is a quick refresher https:*en.wikipedia.org/wiki/Convex_hull. It can be used to create an enclosing geometry around a set of points. This can be useful as is for various effects, but can also be used in combination with the point instance node to create a minkowski sum of convex shapes (https:*en.wikipedia.org/wiki/Minkowski_addition) which is very useful in some situations, like perfect convex bevels.

An example of a Minkowski sum can be seen in the second image above. There is a torus with the convex hull node and a cube. The torus gets instanced on the vertices of the cube and then the convex hull is created to get the Minkowski sum.

The node also handles mixed type geometry and instanced geometry.

Implementation

For the implementation there is a convex hull operator in edit mode. That one just calls the convex hull operation implemented in Bullet the rigid body physics engine. That implementation is very stable and fast. It is also simple to adapt the BMesh operation to instead work with normal Meshes, which are preferred for speed.

Open Questions

There are multiple ways to handle instances.

The simplest way is to make them all real and then create the convex hull.

If the instances themself are not convex, then it might be worth running the convex hull operation on them first and only accumulate the vertices which are on the hull, to reduce the overall complexity. But this is also something the user can do with a second convex hull node, before instancing.

It would also be possible to build the convex hull in an incremental fashion, by calling the convex hull operation after a certain number (1?) of instances are added. This would eliminate most of the memory consumption of making the instances real, but would likely be much slower.

![Screenshot_20210408_215104.png](https://archive.blender.org/developer/F9926097/Screenshot_20210408_215104.png) ![Screenshot_20210408_224244.png](https://archive.blender.org/developer/F9926137/Screenshot_20210408_224244.png) This node creates a convex hull of a mesh or a point cloud. If you don't know what a convex hull is, here is a quick refresher https:*en.wikipedia.org/wiki/Convex_hull. It can be used to create an enclosing geometry around a set of points. This can be useful as is for various effects, but can also be used in combination with the point instance node to create a minkowski sum of convex shapes (https:*en.wikipedia.org/wiki/Minkowski_addition) which is very useful in some situations, like perfect convex bevels. An example of a Minkowski sum can be seen in the second image above. There is a torus with the convex hull node and a cube. The torus gets instanced on the vertices of the cube and then the convex hull is created to get the Minkowski sum. The node also handles mixed type geometry and instanced geometry. ## Implementation For the implementation there is a convex hull operator in edit mode. That one just calls the convex hull operation implemented in Bullet the rigid body physics engine. That implementation is very stable and fast. It is also simple to adapt the BMesh operation to instead work with normal Meshes, which are preferred for speed. ## Open Questions There are multiple ways to handle instances. The simplest way is to make them all real and then create the convex hull. If the instances themself are not convex, then it might be worth running the convex hull operation on them first and only accumulate the vertices which are on the hull, to reduce the overall complexity. But this is also something the user can do with a second convex hull node, before instancing. It would also be possible to build the convex hull in an incremental fashion, by calling the convex hull operation after a certain number (1?) of instances are added. This would eliminate most of the memory consumption of making the instances real, but would likely be much slower.

Henrik D. commented

2021-04-08 22:13:48 +02:00

Changed status from 'Needs Triage' to: 'Confirmed'

Henrik D. commented

2021-04-08 22:13:48 +02:00

Added subscriber: @HDMaster84

Wannes Malfait commented

2021-04-08 22:27:40 +02:00

Added subscriber: @wannes.malfait

Wannes Malfait commented

2021-04-08 22:27:40 +02:00

Maybe for instances the convex hull can be instanced as well (so created once for each kind of object that is instanced)? Don't know if that is possible or useful.

Henrik D. commented

2021-04-08 22:39:03 +02:00

Oh sorry maybe I was a bit unclear, let me post some more images.
My plan was to make a convex hull around any position data passed to the node.

Oh sorry maybe I was a bit unclear, let me post some more images. My plan was to make a convex hull around any position data passed to the node.

Kenzie commented

2021-04-08 23:42:09 +02:00

Added subscriber: @KenzieMac130

Hans Goudey commented

2021-04-09 15:28:38 +02:00

Added subscriber: @HooglyBoogly

Henrik D. was assigned by Hans Goudey

2021-04-09 15:28:38 +02:00

Hans Goudey commented

2021-04-09 15:28:38 +02:00

In #87315#1143320, @wannes.malfait wrote:
Maybe for instances the convex hull can be instanced as well (so created once for each kind of object that is instanced)? Don't know if that is possible or useful.

I think that's a bit counter to the current design philosophy for geometry nodes, that instances are mainly an implementation detail and are realized when necessary.
However we don't really have the tools to apply the same operation to a bunch of different geometries, so I see where that idea comes from, hmm.

> In #87315#1143320, @wannes.malfait wrote: > Maybe for instances the convex hull can be instanced as well (so created once for each kind of object that is instanced)? Don't know if that is possible or useful. I think that's a bit counter to the current design philosophy for geometry nodes, that instances are mainly an implementation detail and are realized when necessary. However we don't really have the tools to apply the same operation to a bunch of different geometries, so I see where that idea comes from, hmm.

blender-admin commented

2021-06-09 18:58:08 +02:00

This issue was referenced by df2a19eac7

This issue was referenced by df2a19eac7daf4943b22f74890cebd14eb811f4e

Dalai Felinto commented

2021-06-15 11:59:00 +02:00

Changed status from 'Confirmed' to: 'Resolved'

Dalai Felinto closed this issue

2021-06-15 11:59:00 +02:00

Ben Jackson commented

2021-08-14 22:35:38 +02:00

Added subscriber: @bjj

Ben Jackson commented

2021-08-14 22:35:38 +02:00

Instances have a unique ID (although it seems to be lost when they are meshified?) but assuming the ID could get through it would be very useful for the convex hull node to have a "partition by" input and then you could select "ID" so that you'd get individual convex hulls per unique ID

Sign in to join this conversation.

No Label

Download

What's New

Blender Studio

Manual

Developers Blog

Documentation

Benchmark

Blender Conference

Development Fund

One-time Donations

Convex Hull Node #87315

Implementation

Open Questions