How to divide polygon into Multiple Quads?

Hello everyone, I have an idea now, as the title says, I’m not sure if it can be achieved. Thank you in advance!

By polygon, I assume you mean a larger quad that you then divide into 4 smaller quads of the same size?
If that’s what you mean, that’s called a quadtree and yes it works.

My telepathy is broken today, but your idea (whatever it is), could be achievable.

It might be good if you share (details about) your idea, as well as other important things, like what type of polygon (regular? convex? concave? self-intersecting?), what type of quads (only existing vertices? with new vertices? maximizing minimal angles? minimizing area difference?), etc.

3 Likes

Keep in mind that three.js renders triangles, not quads. If you’re trying to create the appearance of quads, you may need to use triangles or lines to give the same visual effect. If you’re instead trying to subdivide some hypothetical representation of a mesh that IS NOT a THREE.Mesh, then yes, it’s completely possible to divide [certain] polygons into quads.

I found a similar library,
But the number of sides he decomposes into polygons is not fixed. I hope to decompose any polygon, whether convex or concave, into a shape with a specified number of sides.

Not a quadtree, I just want to decompose any polygon to generate some new blocks with a specified number of edges.

Are we talking about “tesselation” here?

Similar to tessellation, but what I need to subdivide is a two-dimensional polygon, and the result of subdivision is not a triangle. I hope it can be a polygon with a specified number of sides :sweat_smile:

One way to divide a polygon into multiple quads is to triangulate the polygon, then split each triangle into three quads with the Catmull-Clark subdivision.

When I try this approach, the red concave polygon is split into multiple quads (too many quads, but it is OK as long as it is not required to divide into the minimal number of quads):

2 Likes

Thank you! This looks great,Can you share a snippet of your code?

Sure, here it is: https://codepen.io/boytchev/pen/gOZbQZB

However, I’d strongly advice you to try to make it by yourself. It is not that difficult, once you have the main idea. For triangulation there is Earcut.triangulate method in Three.js. It will convert polygon → triangles. For the second step, triangle → quads, just use the midpoints of the sides and the center of the triangle, as shown in this image (this is how Catmull-Clark subdivision algorithm converts triangles to quads):
image

3 Likes

Thank you. You provided me with a good start :handshake:

1 Like

this is tessellation, catmull-clark will apply weights and overall “smooth” the original geometry.

The Catmull-Clark algorithm works with a mesh with a mixture of different types of n-gons, but after the first refinement step the mesh will become only quads. And it will remain quads till the end. In my suggestion I’m referring to this feature, not to the whole algorithm. So, yes, you are right that the algorithm has smoothing, that is not used here.