Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm considering a manufacturing game. A player should assemble parts of an object in given time. The object will be a 3D mesh model. I want to automatically split the 3D mesh into many small pieces to be provided to players. Each divided piece is needed to have area as similar as possible. And I want to control the number of pieces too within range about 2~6. How can I do this?

I know the method to modify a given mesh like adjusting values of vertices, indices. All I need is the algorithm.

share|improve this question
Does your model have a "volume"? Can it be a plane? Can it have "holes"? – Ivan Kuckir Jun 20 '13 at 13:19
It is represented as a polygon surface. Can have a volume, can be a plane, can have holes. It may be a closed surface at the first. – Dish Jun 20 '13 at 13:28
and small pieces should have a volume? Should small pieces for a cube be cubes, or 2 triangles for each cube face? Can you subdivide triangles? – Ivan Kuckir Jun 20 '13 at 13:55
It's okay for pieces not to have a volume. I can subdivide triangles, but I hope to avoid it if possible. – Dish Jun 21 '13 at 1:33
there are many "disjoint subsets of set". Which of them do you want? – Ivan Kuckir Jun 21 '13 at 13:57
up vote 3 down vote accepted

One method I used (in a geometry application not a game) was to traverse the mesh using depth/breadth first search and extract each connected component to a separate mesh . This will give you nice results as far as your mesh is composed of parts that are not connected. The problem though is that if your mesh is connected this doesn't work.

The other method I can think of is you can generate a 3D grid based on the shape and the size of the mesh, and split the mesh based on the distribution of the vertices, the problem; this will look ugly and unnatural.

What I recommend is combining the two methods above. So the first algorithm will split the mesh into parts and the second one to split each part to uniform number of sub-parts and you can iterate until you get satisfactory results. The problem though "realistic results" is something very hard to do without any human input, so I recommend there are some constraints put by the guy who will make the models for each model, this way you will get some randomness from your algorithm while getting more "realistic results" because of the constraints.

Edit: You can also combine some kind of real time constructive solid geometry with the other methods but that might be kind of hard to implement.

Edit: Well, most of the models I worked with were exported from CAD applications and were nicely connected (as they would be in real life), so your best bet might be to design your models with this in mind, but anyway you may want to use some kind of tolerance or graph radius; for example if a certain component has graph radius less than K you don't make it a separate part.

You can also use some geometrical attributes of your mesh (as the traverse only use topological properties) one might be using a tolerance; sometimes a vertex will be duplicate (you have two vertices that have the (almost) same value), in a naive BFS they might be treated as disconnected, in real world though, you may want to "merge" them which might not be good for rendering, in this case you need to merge them only when dealing with connectivity issue and not in the vertex buffer that is going to be rendered.

share|improve this answer
Could you tell me about the traverse method more specifically, please? If I naively use the BFS, results might be ugly shapes. For example, when I'm trying to cut a mesh into 3 pieces, the first BFS and the second BFS may be okay. But the last piece must be made of left un-traversed triangles. So it cannot be a circlelike shape, and in the worst case, it might be composed of many disconnected surfaces. – Dish Jun 20 '13 at 13:50
edited my answer – concept3d Jun 22 '13 at 9:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.