Page MenuHome

Rework carve integration into boolean modifier
ClosedPublic

Authored by Sergey Sharybin (sergey) on Jan 30 2014, 1:41 PM.

Details

Summary

Goal of this commit is to support NGons for boolean modifier
(currently mesh is being tessellated before performing boolean
operation) and also solve the limitation of loosing edge custom
data layers after boolean operation is performed.

Main idea is to make it so boolean modifier uses Carve library
directly via it's C-API, avoiding BSP intermediate level which
was doubling amount of memory needed for the operation and which
also used quite reasonable amount of overhead time.

Diff Detail

Event Timeline

This is *Work In Progress* so no axtual review is requested yet. Needed to send the patch here so others (aka @Lukas Toenne (lukastoenne) :) could start playing around with it.

extern/carve/carve-capi.cc
45

For some efficiency you can vertices.reserve(num_verts) on std vectors IIRC. Same goes for all other vectors we know the size of ahead of time - avoid resizing.

95

picky, space before *

@Martin Felke (scorpion81): Added you here since you're probably interested to test this with fracture code too.

extern/carve/carve-capi.cc
220

Is This addinog both edges to the map, just with different ordering? couldn't it just order them and add once? (like BLI_edgehash does)

Sergey Sharybin (sergey) updated this revision to Unknown Object (????).Jan 31 2014, 2:26 PM

Updated development snapshot:

  • Bring back union of intersecting manifolds of the same operand.

This solves wrong inner/outer detection in some cases.

  • Optimized a bit that part of code, but it is to be rewritten to

make it more clear and perhaps faster.

  • Dropped unused files.
  • Added original index for carve geometry, so it could be mapped

back to blender's original operand geometry.

  • Implemented custom data copy from original geometry to the result.

Still TODO:

  • Implement custom data interpolation.
  • Implement non-flat N-gons detection.
  • Optimize the code.
Sergey Sharybin (sergey) updated this revision to Unknown Object (????).Feb 1 2014, 12:12 PM
  • Some code cleanup in carve-capi, use references when possible
  • Implemented loop interpolation. Works pretty neat actually :)

Still loads of room for optimization, and need to interpolate edges
by the looks of it.

Sergey Sharybin (sergey) updated this revision to Unknown Object (????).Feb 2 2014, 7:49 PM

Fix for wrong custom data copy for vertices

It was a left-over from the debug times. Now added proper
origindex for vertices and do custom data copy based on
this index.

Sergey Sharybin (sergey) updated this revision to Unknown Object (????).Feb 2 2014, 7:52 PM

Fill in vertex CD_ORIGINDEX custom data later

Forgot this in previous update.

Sergey Sharybin (sergey) updated this revision to Unknown Object (????).Feb 3 2014, 11:15 AM

Solved assert failure in cases when mesh does have open edges

Also made some optimization by getting geometry arrays in an
advance rather than getting them for each loop.

Sergey Sharybin (sergey) updated this revision to Unknown Object (????).Feb 3 2014, 12:31 PM

Attempt to fix compilation error with CLang

Sergey Sharybin (sergey) updated this revision to Unknown Object (????).Feb 6 2014, 9:51 AM

Fixed stupid typo in vert data copy

Sergey Sharybin (sergey) updated this revision to Unknown Object (????).Feb 7 2014, 7:31 AM

Fix crash in special cases when union intersection meshes gives empty mesh

This doesn't make test file fully working tho, but the remaining issue is
caused by non-flat nature of the meshes.

Sergey Sharybin (sergey) updated this revision to Unknown Object (????).Feb 7 2014, 3:23 PM

Triangulate non-flat ngons

This does triangulation of all quads and ngons if they are
not flat. For now they'll be kept triangulated in the result
as well.

After discussion with @Campbell Barton (campbellbarton) we agreed it's not a
stopper for merge and un-touched faces could be kept as-is
in the future.

Uses Carve's triangulator which might be different from what
3D viewport uses or triangulation operator uses. But it gives
pretty adequate results here, so think this is all fine.
Could also be improved later.

Performance is still lower than in previous release, but
still see some room for optimization. This i also consider
a task for later and not actual stopper for now.

Sergey Sharybin (sergey) updated this revision to Unknown Object (????).Feb 7 2014, 3:41 PM

Tweak eps values so flat ngons are detected as flat now.

TODO: Projection normal is still wrong, easy to fix before
commit, don't prevent review tho.

Sergey Sharybin (sergey) updated this revision to Unknown Object (????).Feb 7 2014, 4:42 PM

WIP update for proper normal being reported

However ngon tesellation is kind of broken now,
projection doesn't seem to be correct.

Either bug in how axis matri is computed or
column-major vs. row-major thing.

Don't really have time to look into it now, sorry.

Sergey Sharybin (sergey) updated this revision to Unknown Object (????).Feb 7 2014, 5:15 PM

Fixed the tessellation!

Did quick test of this and looks very good.

Most suggestions I have are small/picky.

One thing I would do is reduce sign conversion - try include BLI_strict_flags.h in the files that do mesh conversion.

a few other comments inline.

extern/carve/carve-capi.cc
198

could alloca here, I dont have a strong preference though.

230

Might the total number of loops be a better choice? (total number of face corners)

extern/carve/carve-util.cc
656

You could use BLI_polyfill2d.h - this is what bmesh uses and should be fairly trivial to get working.

source/blender/modifiers/intern/MOD_boolean_util.c
42

*picky* can kick MEM_guardedalloc.h BLI_memarena.h BLI_scanfill.h can go

Will update patch here soon.

extern/carve/carve-capi.cc
198

alloca is actually considered a bad practice to be used in a production -- this is a straight way to run into stack overflow issues which you couldn't control. Some systems have rather small default stack size which would lead to unwanted crashes. Don't feel good about using it actually.

220

Yes, it could. Marked as TODO in local patch.

230

Yes, this is good idea. Done.

extern/carve/carve-util.cc
656

Yep, but not directly.Will pass it as a callback of mesh_importer.

source/blender/modifiers/intern/MOD_boolean_util.c
42

Yep, those are residuals from the testing..

Forgot to mention -- that'd suck trying to reduce sign conversion here. First we'll need to make DM API consistent in signs with the rest of mesh API. Currently is' rather annoying mix to try using strict flags and i'm not motivated at all trying to make strict flags here at this point -- just use signed ints for now.

For example getNumVerts() and getNumEdges() will give you signed int. So you'll iterate using signed int. Stuff like getVertData() and getEdgeData() accepts signed int as well. However, if you'll request for MEdge to know it's vertices you'll have unsigned index of verts of the edge. There are more examples of inconsistencies which will ruin all the attempts redusicng sign conversion.

And one more thing -- this is false thought we could avoid sign conversion syncing importer/exporter API with Mesh structures. In half of the cases you'll just move sign conversion from MOD_boolean_util to carve-capi. because of sign mismatch between blender and carve.

Wouldn't suggest spending time on this now, we've got tracker full of stoppers. Such a sign conversion cleanup we could make later -- agree they're annoying but don't think they're ever harmful for artists. And we'll need to cleanup DM API first anyway :)

Sergey Sharybin (sergey) updated this revision to Unknown Object (????).Feb 10 2014, 9:37 AM

Address some of Campbell's feedback

  • Use number of loops to reserve face indices vector
  • Drop unused includes
  • Expose BLI_polyfill_calc() to carve triangulator
  • Reshuffle some code and rename some variables

Still use Carve triangulator tho because BLI's one tends
to generate degenerated faces. For xample for such a plane
(median point is on scene origin, edge lengths are of 2.0)

(2)---------(1)
 |           |
(3)---------(0)
 |           |
(4)---------(5)

BLI_polyfill_calc() will return one of triangles of
(0, 1, 5) which is obviously a degenerate face which we
never want to have.

Sergey Sharybin (sergey) updated this revision to Unknown Object (????).Feb 10 2014, 2:35 PM

Made some optimizations.

Just figured out that those cases which i thought are bottlenecks
and could be optimized are in fact NOT a bottleneck.

So now boolean modifier is 40% slower :S

Still trying to make it as fast as master's one..

@Sergey Sharybin (sergey). re: polyfill2d, right - this doesn't attempt to rotate edges or give nice tessellation, however it does give nice even tessellation for convex faces.
eg: http://www.graphicall.org/ftp/ideasman42/fill.png

Probably going with carves tessellator is fine, just replying because the case where edges in a poly are co-linear could be handled by polyfill2d, either by passing an epsilon or by making the code check for this case.

Users may notice this issue with UV's in the viewport so it could be good to handle this case better anyway.

@Campbell Barton (campbellbarton), yes i see the issue/ However polyfill2d is just useless -- degenerated faces would ruin boolean operation. Edge classifier doesn't work for them at all. You'll have random inner/outer manifolds flip.

Currently working on some optimizations. Will update the patch soon.

Sergey Sharybin (sergey) updated this revision to Unknown Object (????).Feb 11 2014, 8:57 AM

Optimization of boolean modifier

It's still around 30% slower than master branch, but at this
moment all the preparation being done by us takes an order of
magnitude less time than performing boolean operation.

So not sure i'll end up with some genius idea to make things
faster..

Sergey Sharybin (sergey) updated this revision to Unknown Object (????).Feb 11 2014, 6:05 PM

Some noticeable speed-up

Issue was caused by the wrong magnitude in flat quad detection
which considered more quads as non-flat comparing to the master
branch.

Tweaked the eps there so it should work the same.

Also avoid some float<->double conversions.

This makes my test files works pretty close to the master branch.
There're some further optimizations in some other areas (like in
the triangulation code). But not sure we'll be able to beat master
branch speed.

Sergey Sharybin (sergey) updated this revision to Unknown Object (????).Feb 12 2014, 11:43 AM

Hopefully latest update before commit

  • Optimized triangulation a little bit, it was allocating extra array. Reason of this came from experimentation time using BLI's triangulator.
  • Solved issue with black vertex color coming from operands which doesn't have vertex color.

Found a bug in vertex color interpolation, see:
http://www.graphicall.org/ftp/ideasman42/bool_vcol_bug.blend

I dont think this is anything especially strange, it failed for any common case here

Campbell Barton (campbellbarton) requested changes to this revision.Feb 12 2014, 7:31 PM
Sergey Sharybin (sergey) updated this revision to Unknown Object (????).Feb 13 2014, 11:10 AM

Fix vertex color interpolation

Was a mistake caused by local space mismatch between operands.

Also made flatness detection more robust.

Sergey Sharybin (sergey) updated this revision to Unknown Object (????).Feb 13 2014, 11:33 AM

Further tweak to planar detection