Convex hull bmesh operator

As part of my skin modifier work I added a convex hull operation. I think this can be useful as a general modeling tool, this patch contains the BMesh operator and corresponding MESH_OT_convex_hull.

Example: http://nicholasbishop.net/wordpress/wp-content/uploads/2012/04/hull.gif

[ideasman42, 2012-04-27 03:23:59]

Tried on this file and it gives a problem at the top monkeys head. The problem
happens when triangulated too.

http://www.graphicall.org/ftp/ideasman42/2_monkey_head_error.blend


Know this is not really the purpose but it works quite well as a bridge tool for
convex edge loops, could consider..
- copying UV's and materials from connected faces
- removing selected faces (so as to create a tube between 2 surfaces).
- 2 triangles between 2 edges make into quads.
... Or we could just make our bridge tool better..

http://codereview.appspot.com/6114060/diff/1/source/blender/bmesh/operators/b...
File source/blender/bmesh/operators/bmo_hull.c (right):

http://codereview.appspot.com/6114060/diff/1/source/blender/bmesh/operators/b...
source/blender/bmesh/operators/bmo_hull.c:50: t =
MEM_callocN(sizeof(HullTriangle), "HullTriangle");
(while performance probably isn't horrible) - could use mempool here.

http://codereview.appspot.com/6114060/diff/1/source/blender/bmesh/operators/b...
source/blender/bmesh/operators/bmo_hull.c:176: const int hull_flag_interior_vert
= 1;
trivial - but why not use enum?
(thats the convention at least defines or enum, though have been using enums
more - recently)

http://codereview.appspot.com/6114060/diff/1/source/blender/editors/mesh/edit...
File source/blender/editors/mesh/editmesh_tools.c (right):

http://codereview.appspot.com/6114060/diff/1/source/blender/editors/mesh/edit...
source/blender/editors/mesh/editmesh_tools.c:4303: EDBM_update_generic(C, em,
TRUE);
need to call selection flush here too, running this in face mode leaves them
unselected.

[nicholasbishop, 2012-04-28 03:24:26]

Thanks for reviewing :) New patch attached, comments below:

> Tried on this file and it gives a problem at the top monkeys head. The problem
> happens when triangulated too.
> 
> http://www.graphicall.org/ftp/ideasman42/2_monkey_head_error.blend
Fixed now, along with a lot of corner cases. The hull code has gotten quite a
bit longer, but is much more robust.

> Know this is not really the purpose but it works quite well as a bridge tool
for
> convex edge loops, could consider..
> - copying UV's and materials from connected faces
Hull output now searches for an adjacent face to use as an example, so materials
etc. get copied. Wasn't sure about UVs; since these are new faces do I need to
do anything there?

> - removing selected faces (so as to create a tube between 2 surfaces).
Added new "make holes" option that does this.

> - 2 triangles between 2 edges make into quads.
> ... Or we could just make our bridge tool better..
Added an optional call to the join_triangles bmop. Gave the hull operator all of
the join_triangles properties; UI is a bit cluttered but output looks good.

>
http://codereview.appspot.com/6114060/diff/1/source/blender/bmesh/operators/b...
> source/blender/bmesh/operators/bmo_hull.c:50: t =
> MEM_callocN(sizeof(HullTriangle), "HullTriangle");
> (while performance probably isn't horrible) - could use mempool here.
Done.

>
http://codereview.appspot.com/6114060/diff/1/source/blender/bmesh/operators/b...
> source/blender/bmesh/operators/bmo_hull.c:176: const int
hull_flag_interior_vert
> = 1;
> trivial - but why not use enum?
> (thats the convention at least defines or enum, though have been using enums
> more - recently)
Done (dunno why I didn't do that in the first place...)

>
http://codereview.appspot.com/6114060/diff/1/source/blender/editors/mesh/edit...
> source/blender/editors/mesh/editmesh_tools.c:4303: EDBM_update_generic(C, em,
> TRUE);
> need to call selection flush here too, running this in face mode leaves them
> unselected.
Added a call to EDBM_selectmode_flush(em), is that correct?

Thanks again for reviewing.

[ideasman42, 2012-04-28 10:59:34]

Some more feedback,

If you want to copy loop data from adjacent faces call this after creating each
face.
 - BM_face_copy_shared()

Not certain this will always give good results though I think it the case of
typical bridge usage it would be good.

http://codereview.appspot.com/6114060/diff/10001/source/blender/bmesh/operato...
File source/blender/bmesh/operators/bmo_hull.c (right):

http://codereview.appspot.com/6114060/diff/10001/source/blender/bmesh/operato...
source/blender/bmesh/operators/bmo_hull.c:105: new =
MEM_callocN(sizeof(HullBoundaryEdge), "HullBoundaryEdge");
another use for mempool? didnt check how often this runs but expect a fair bit.

http://codereview.appspot.com/6114060/diff/10001/source/blender/bmesh/operato...
source/blender/bmesh/operators/bmo_hull.c:278: if (v1 > v2)
expect you intend this - but could add comment...

/* verts can be in any order, just pick lower pointer for consistency */

... since the first vert may be after the last vert (when comparing pointer
addresses), if you dont mean this, then better compare index values.

http://codereview.appspot.com/6114060/diff/10001/source/blender/bmesh/operato...
source/blender/bmesh/operators/bmo_hull.c:386: 
could use INIT_MINMAX & DO_MINMAX here? - think its more straightforward.

http://codereview.appspot.com/6114060/diff/10001/source/blender/bmesh/operato...
source/blender/bmesh/operators/bmo_hull.c:512: if (BMO_slot_bool_get(op,
"make_holes"))
better not do string lookups in a loop, this can be passed as an arg to the
function (then no need to pass 'op')

[nicholasbishop, 2012-04-28 20:05:01]

Thanks, new patch uploaded.

> If you want to copy loop data from adjacent faces call this after creating
each
> face.
>  - BM_face_copy_shared()
> 
> Not certain this will always give good results though I think it the case of
> typical bridge usage it would be good.

Done.

> 
>
http://codereview.appspot.com/6114060/diff/10001/source/blender/bmesh/operato...
> File source/blender/bmesh/operators/bmo_hull.c (right):
> 
>
http://codereview.appspot.com/6114060/diff/10001/source/blender/bmesh/operato...
> source/blender/bmesh/operators/bmo_hull.c:105: new =
> MEM_callocN(sizeof(HullBoundaryEdge), "HullBoundaryEdge");
> another use for mempool? didnt check how often this runs but expect a fair
bit.

Done.

> 
>
http://codereview.appspot.com/6114060/diff/10001/source/blender/bmesh/operato...
> source/blender/bmesh/operators/bmo_hull.c:278: if (v1 > v2)
> expect you intend this - but could add comment...
> 
> /* verts can be in any order, just pick lower pointer for consistency */
> 
> ... since the first vert may be after the last vert (when comparing pointer
> addresses), if you dont mean this, then better compare index values.

Done, added comment.

> 
>
http://codereview.appspot.com/6114060/diff/10001/source/blender/bmesh/operato...
> source/blender/bmesh/operators/bmo_hull.c:386: 
> could use INIT_MINMAX & DO_MINMAX here? - think its more straightforward.

Didn't look like these could work since I'm finding BMVert pointers rather than
coordinates.

> 
>
http://codereview.appspot.com/6114060/diff/10001/source/blender/bmesh/operato...
> source/blender/bmesh/operators/bmo_hull.c:512: if (BMO_slot_bool_get(op,
> "make_holes"))
> better not do string lookups in a loop, this can be passed as an arg to the
> function (then no need to pass 'op')

Done.

[ideasman42, 2012-04-28 20:36:46]

LGTM,

one more general comment is that I think having the operator delete the holes
its self might not be so good.

Instead the blender operator could do this on faces tagged as original. - This
isnt really bad, just think it can get a bit messy if a lot of operators call
eachother because of functionality users might want. rather have them low level
and the callers can mix together the operators that make sense in some context.
In this case the caller is the wmOperator

[nicholasbishop, 2012-04-28 21:18:42]

On 2012/04/28 20:36:46, ideasman42 wrote:
> LGTM,
> 
> one more general comment is that I think having the operator delete the holes
> its self might not be so good.
> 
> Instead the blender operator could do this on faces tagged as original. - This
> isnt really bad, just think it can get a bit messy if a lot of operators call
> eachother because of functionality users might want. rather have them low
level
> and the callers can mix together the operators that make sense in some
context.
> In this case the caller is the wmOperator

Before, I was doing deletion in the wmOperator, but the code got a bit more
complex than just deleting original faces -- all the code in
hull_delete_unused() and hull_make_holes(). Agree it gets trickier to combine
operators now, but on the other hand  the hull operator has flags to disable
these operations too.

So, not sure which option is best:
a) In the hull bmop, find elements to be deleted and tag them in an output slot,
then actually delete in the wm op
b) Move both the find-deleteable-elements and deletion to the wm op
c) Leave both in the bmop and let other operators disable with slot booleans

[ideasman42, 2012-04-29 06:13:32]

On 2012/04/28 21:18:42, nicholasbishop wrote:
> On 2012/04/28 20:36:46, ideasman42 wrote:
> > LGTM,
> > 
> > one more general comment is that I think having the operator delete the
holes
> > its self might not be so good.
> > 
> > Instead the blender operator could do this on faces tagged as original. -
This
> > isnt really bad, just think it can get a bit messy if a lot of operators
call
> > eachother because of functionality users might want. rather have them low
> level
> > and the callers can mix together the operators that make sense in some
> context.
> > In this case the caller is the wmOperator
> 
> Before, I was doing deletion in the wmOperator, but the code got a bit more
> complex than just deleting original faces -- all the code in
> hull_delete_unused() and hull_make_holes(). Agree it gets trickier to combine
> operators now, but on the other hand  the hull operator has flags to disable
> these operations too.
> 
> So, not sure which option is best:
> a) In the hull bmop, find elements to be deleted and tag them in an output
slot,
> then actually delete in the wm op
> b) Move both the find-deleteable-elements and deletion to the wm op
> c) Leave both in the bmop and let other operators disable with slot booleans

Leave this up to you, but some things to consider.

I Don't think the way its doing it now is horrible, off hand (a) looks most in
keeping with bmop design, but if for some reasons there are complications then
suggest stick with what you have (c).

b) may be more trouble then its worth, but if it could be done cleanly then I'd
consider it - rip tool does this for eg.

[nicholasbishop, 2012-04-29 16:11:35]

On 2012/04/29 06:13:32, ideasman42 wrote:
> On 2012/04/28 21:18:42, nicholasbishop wrote:
> > On 2012/04/28 20:36:46, ideasman42 wrote:
> > > LGTM,
> > > 
> > > one more general comment is that I think having the operator delete the
> holes
> > > its self might not be so good.
> > > 
> > > Instead the blender operator could do this on faces tagged as original. -
> This
> > > isnt really bad, just think it can get a bit messy if a lot of operators
> call
> > > eachother because of functionality users might want. rather have them low
> > level
> > > and the callers can mix together the operators that make sense in some
> > context.
> > > In this case the caller is the wmOperator
> > 
> > Before, I was doing deletion in the wmOperator, but the code got a bit more
> > complex than just deleting original faces -- all the code in
> > hull_delete_unused() and hull_make_holes(). Agree it gets trickier to
combine
> > operators now, but on the other hand  the hull operator has flags to disable
> > these operations too.
> > 
> > So, not sure which option is best:
> > a) In the hull bmop, find elements to be deleted and tag them in an output
> slot,
> > then actually delete in the wm op
> > b) Move both the find-deleteable-elements and deletion to the wm op
> > c) Leave both in the bmop and let other operators disable with slot booleans
> 
> Leave this up to you, but some things to consider.
> 
> I Don't think the way its doing it now is horrible, off hand (a) looks most in
> keeping with bmop design, but if for some reasons there are complications then
> suggest stick with what you have (c).
> 
> b) may be more trouble then its worth, but if it could be done cleanly then
I'd
> consider it - rip tool does this for eg.

Implemented option (a), committed to r46080 and r46081.