Subdividing 3D mesh into arbitrarily sized pieces

Question

I have a mesh defined by 4 points in 3D space. I need an algorithm which will subdivide that mesh into subdivisions of an arbitrary horizontal and vertical size. If the subdivision size isn't an exact divisor of the mesh size, the edge pieces will be smaller.

All of the subdivision algorithms I've found only subdivide meshes into exact powers of 2. Does anyone know of one that can do what I want?

Failing that, my thoughts about a possible implementation is to rotate the mesh so that it is flat on the Z axis, subdivide in 2D and then translate back into 3D. That's because my mind finds 3D hard ;) Any better suggestions?

Using C# if that makes any difference.

Answer 1

Now that you've explained things a bit more clearly, I don't see your problem: you have a rectangle and you want to divide it up into rectangular tiles. So the mesh points you want are regularly spaced in both orthogonal directions. In 2D this is trivial, surely ? In 3D it's also trivial though the maths is a little trickier.

Off the top of my head I would guess that transforming from 3D to 2D (and aligning the rectangle with the coordinate axes at the same time) then calculating the mesh points, then transforming back to 3D is probably about as simple (and CPU-time consuming) as working it all out in 3D in the first place.

Yes, using C# means that I'm not able to propose a code to help you.

Comment or edit you question if I've missed the point.

Answer 2

If you only have to work with a rectangle in 3D, then you simply need to obtain the two edge vectors and then you can generate all the interior points of the subdivided rectangle. For example, say your quad is defined by (x0,y0),...,(x3,y3), in order going around the quad. The edge vectors relative to point (x0,y0) are u = (x1-x0,y1-y0) and v = (x3-x0,y3-y0).

Now, you can generate all the interior points. Suppose you want M edges along the first edge, and N along the second, then the interior points are just

(x0,y0) + i/(M -1)* u + j/(N-1) * v

where i and j go from 0 .. M-1 and 0 .. N-1, respectively. You can figure out which vertices need to be connected together by just working it out on paper.

This kind of uniform subdivision works fine for triangular meshes as well, but each edge must have the same number of subdivided edges.

If you want to subdivide a general mesh, you can just do this to each individual triangle/quad. This kind of uniform subdivision results in poor quality meshes since all the original flat facets remain flat. If you want something more sophisticated, you can look at Loop subidivision, Catmull-Clark, etc. Those are typically constrained to power-of-two levels, but if you research the original formulations, I think you can derive subdivision stencils for non-power-of-two divisions. The theory behind that is a bit more involved than I can reasonably describe here.