Does anyone have a workable algorithm for converting an irregular polygon (representing a body of water like, say, a lake) into faces with 3 or 4 sides?
other than what you get with shift+f?
as in you want it reasonably subdivided and stuff?
[in which case you want essentially something like extruding that shape and using boolean intersection with a grid…?]
Hmmm.
The polygon is an irregular shape with islands, peninsulars, bays, etc.
I need some way to divide up the shape into 3 or 4 sided faces.
I have a couple of ideas, but they’re not quite working out just now and I’m getting a little bit frustrated.
It can’t be a unique problem; somebody must’ve solved it.
Dave
okay, so picture this
the edges you want to go inside of are oriented counter clockwise [to the left] and the ones you want to go outside of are oriented clockwise [to the right]
starting from one vert, find the nearest vert on the other surface, then try to find a vert that makes a counter clockwise triangle.
make sure you don’t repeat, and try to fill the shortest edges. Also, you will have to connect the islands and the lake to themselves in places.
I don’t think I have described this well enough
what I’m trying to describe is a way to fill a region with polygons as curves [2d, filled] in blender do [try converting one to a mesh]
… I can’t seem to find a resource online about it very quickly …
Have you looked into using the marching cubes algorithm ?
Hopefully there is a better solution to this, but I had a similar problem and solved it with the help of a program called “Triangle” http://www-2.cs.cmu.edu/~quake/triangle.html. If you can define the polygon as a list of sequential points going around the polygon in order, this will work. Basically, you tell “Triangle” the X and Y for each point in order, then you connect them up as well - “A connected to B, B connected to C, C connected to D, D connected back to A”. Then you tell “Triangle” that you would like it to be a constrained Delaunay triangulation and have it export in “OFF - Object File Format”, which Blender can import with no problem. “Triangle” will create triangles out of any complex 2-D polygon you throw at it.
It would be much easier if you could via python create a curve in Blender with your series of points and then programmatically ask Blender to convert to a mesh. Someone please correct me if I’m wrong, but this feature doesn’t seem to exist anymore in the latest versions of Blender.
See the first pages of the boolean script thread (by SpkyElectrc). The face filler is based on an simple method I came up with, it is explained there. The boolean tool will have a much better filler than Blender’s internal shift-S. The image I posted there is missing but here it is:
It is interesting because the numbers show the order in which the faces are created, creating convex quads always before triangles.
A face filler is a good idea for a script.
By the way, I have an implementation of a filler, based on the method toloban’s described. It’s designed to be fairly generic and easy for any script to use. Here’s a .blend with the scripts, a little explaination, and demo:
http://astro.scu.edu/~ted/oss/blender/pyfill/pyloopfill01.blend
Basically you send it a lists of points, defining loops, and a normal vector, and it gives you a set of quads & tris back as lists of the original points.