Collision-aware inset. Using 'i' command, check the Individual flag to get this functionality.
Needs ReviewPublic

Authored by Howard Trickey (howardt) on Dec 13 2015, 3:34 PM.
This revision needs review, but there are no reviewers specified.

Details

Reviewers
None

Diff Detail

Repository
rB Blender
Branch
inset (branched from master)
Howard Trickey (howardt) retitled this revision from to Collision-aware inset. Using 'i' command, check the Individual flag to get this functionality..Dec 13 2015, 3:34 PM

This patch adds a library function BLI_polyinset3d to blenlib and uses it to do the main functionality of the 'Inset Face' (shortcut 'i') mesh modeling function (but for now, only when 'Individual' is checked in the panel; and it also doesn't work if 'Offset Relative' is checked). I will continue to work on this to handle the non-Individual case if this patch direction looks promising. When 'Fix Overlaps' is not checked, the functionality is meant to be the same as current. But when 'Fix Overlaps' is checked, the inset thickness is clamped to the point of first collision. Collisions happen in two ways during inset:
(1) two of the lines that go inward from the original vertices meet (and are about to cross)
(2) the inset of a reflex angle hits some other inset edge
The code handles these cases, when 'Fix Overlaps' is checked, by in the case of (1), making a vertex for the intersection point; and in the case of (2), splitting the inner polygon in two at the intersection point. And there are many edge cases where many vertices merge into one point and degenerate polygons need to be cleaned up. The code handles these edge cases.

Some points of information, and maybe for discussion:

  • the algorithm is somewhat complicated; I will do a wiki page describing the algorithm if I end up submitting this. some background on the algorithm can be found by reading up on 'straight skeletons', e.g., http://www.jucs.org/jucs_1_12/a_novel_type_of/Aichholzer_O.pdf
  • the algorithm is not optimized -- there are some O(n^2) loops (n = # of vertices in the face); performance is acceptable, in my opinion, for an interactive tool. if this ever becomes a modifier, there are ways to optimize (using priority queues)
  • the current inset code does everything in BMesh space, and takes pains to reuse the existing polygons as much as possible; this new code just discards the original face and builds new polygons in its place (taking care to copy attributes and do proper UV, etc., interpolations). my opinion is that this makes the code easier to understand and that the efficiency loss is negligible and unnoticeable in an interactive tool; but interested to hear if opinions differ on this point. (By the way, the 'discard and rebuild new polygons' is the approach taken in the knife tool.)
  • the rationale to make this a library function that operates on abstract polygons rather than just do it in BMesh was so that we could also use this function for Curve insets. the functionality here is especially useful when bevel the face of text letters when the letters have serifs because those serifs tend to cause overlaps at very small bevel values.
  • the use of this code in the actual inset command now loops until the desired depth is achieved or there is no more progress possible

Hi Howardt,
Couldn't compile with Scons nor Cmake on win7x64:

11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(90): error C4431: missing type specifier - int assumed. Note: C no longer supports default-int
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(90): error C2054: expected '(' to follow 'inline'
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(91): error C2085: 'next' : not in formal parameter list
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(91): error C2143: syntax error : missing ';' before '{'
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(95): error C4431: missing type specifier - int assumed. Note: C no longer supports default-int
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(95): error C2054: expected '(' to follow 'inline'
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(96): error C2085: 'prev' : not in formal parameter list
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(96): error C2143: syntax error : missing ';' before '{'
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(194): error C4013: 'next' undefined; assuming extern returning int
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(294): error C4431: missing type specifier - int assumed. Note: C no longer supports default-int
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(294): error C2054: expected '(' to follow 'inline'
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(295): error C2057: expected constant expression
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(295): error C2466: cannot allocate an array of constant size 0
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(299): error C2057: expected constant expression
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(299): error C2466: cannot allocate an array of constant size 0
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(300): error C2085: 'edge_event_time' : not in formal parameter list
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(300): error C2143: syntax error : missing ';' before '{'
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(315): error C4013: 'edge_event_time' undefined; assuming extern returning int
11>  rand.c
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(315): error C4244: '=' : conversion from 'int' to 'float', possible loss of data
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(404): error C4013: 'prev' undefined; assuming extern returning int
12>C:\Users\test\blender_git\blender\source\blender\blenloader\intern\readfile.c(826): warning C4146: unary minus operator applied to unsigned type, result still unsigned
12>C:\Users\test\blender_git\blender\source\blender\blenloader\intern\readfile.c(840): warning C4146: unary minus operator applied to unsigned type, result still unsigned
12>  versioning_270.c
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(404): error C4389: '==' : signed/unsigned mismatch
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(466): error C4244: '=' : conversion from 'int' to 'float', possible loss of data
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(491): error C4389: '==' : signed/unsigned mismatch
11>C:\Users\test\blender_git\blender\source\blender\blenlib\intern\polyinset.c(534): error C4389: '==' : signed/unsigned mismatch

Hmm, not sure what the Visual Studio compiler doesn't like about my inline function declaration. This code compiles ok on Mac and Linux. I'll try it on my Windows machine soon (maybe later today).

Hi Howard, any news on that one?

Sorry, no update. I've been too busy with my day job for the last couple of months. Hope to get back to this soon, though.

Same here with day job. Good to know improvements are still planned :)

with this diff : http://www.pasteall.org/68323/diff it compiles on windows properly. A new option "Fix overlaps" is then accessible, but it doesn't seem to really activate when checked. I guess it's an easy fix but can't find it after reading the code many times. Must be tired. @Howard Trickey (howardt) If you could have just a quick look, it would be awesome.

Edit: ok it only works with individual activated. First tests are good :)

Yeah, the reason it is taking so long to finish this is that making it work for the "region" case as opposed to the "individually" case is quite a lot harder. I haven't worked on this for a while because there's a crashing blender bug that also needed a complicated fix (almost done with that now, though).

Individual is already really good as it works with ngons.

found one bug http://www.pasteall.org/blend/41501

Good to hear you are working on the region mode :)