Page MenuHome

Constrained Delaunay Triangulation for Blenlib

Authored by Howard Trickey (howardt) on Aug 6 2019, 2:00 PM.



See design task T68277 for a design task that explains the motivation and design for this library addition to Blenlib.

There are some math and vector routines in double precision that I will move to the appropriate header and C files in Blenlib for vector and math, either before submitting this change or as a refactor afterwards, at reviewer's choice.

Diff Detail

rB Blender

Event Timeline

Campbell Barton (campbellbarton) requested changes to this revision.Aug 9 2019, 9:26 AM

Tested the patch with a bmesh operator, work well in my tests.

This review is mainly as an API user, as well as some details I ran into going over the code.

I've updates the patch in the branch temp-D5423-update, initial commits are fairly straightforward, the last few were left last since they're more opinionated.

Unless you have any issues with changes from temp-D5423-update, think they're fine to apply on top of this patch as-is.

Further I don't see any issues with this patch, other changes could be done in master.

Memory storage for e.g. could be reused between calls, but this isn't a priority.


Reading over this I still miss info about which cases are supported.

Notes about result in the case of degenerate input would be useful too.

  • Input verts inside existing faces.
  • Input edges inside existing faces.
  • Input edge/face constraints are self intersecting.

Could use a comment to explicitly state face input/output usage.

"While n-gons are supported as constraints, all newly created faces will be triangles."


Hole in n-gons are sometimes defined by looping back on the same edges, is this supported?


Could comment if there is any issues with a zero epsilon, or if having a large epsilon is going to cause errors.

(tested and zero epsilon seems fine, short statement about recommended use would be helpful for API users).




Why is coords a pointer to the coordinate? Seems this isn't needed.


The second arg looks like it will only be initialized when the debug code above runs.

This revision now requires changes to proceed.Aug 9 2019, 9:26 AM
Howard Trickey (howardt) marked 7 inline comments as done.Aug 9 2019, 1:27 PM

I haven't looked at your patch-on-my-patch yet, but assume it will be ok when I look later, and if so, will submit the modified code. Will also address all of your comments as I commented in response to them, before submitting.


Will clarify in comments. These cases are all handled.


Will more comments about inputs handled and what happens in output.

In fact, in two of the output_types (CDT_CONSTRAINTS and CDT_CONSTRAINTS_VALID_BMESH) the newly created faces may be ngons.


The input can have that, yes. No restrictions on repeating of vert indices is imposed on input faces. For output, the holes made this way will be triangulated, as will the face surrounding (though again, both of those things will not be true for the last two output types). But in any case, the output will specify faces to fill the holes. A possible future enhancement to this CDT routine is to allow input to specify holes that will NOT get filled with faces in the output. One possible way to do that would be to just specify a list of 2d coords that are inside holes, with the understanding that you eat away the mesh until you hit a constraint edge from such hole points. Another possible way would be to extend the input to have hole faces inside main faces explicitly specified by the user.


In general, zero epsilon won't work as expected (that is, "never merge"). I think it might be too hard to make the code work reliably if there are coincident or nearly-coincident vertices that stay unmerged. The current code sets epsilon to 1e-8 if the user gave a 0. I'll comment.


Whoops, that was the name from the paper, ("constraint rep") which I changed to input_ids at some point. Will fix, thanks.


Silly mistake from me, forgetting that coords[2] is already a pointer. Will fix.


Thanks, good catch! I will remove the ifdef code immediately above from the part that sets symedge.