Thursday, September 11, 2014

Chamfering polyhedron

My friend (and artist), looking at my 3D Dice Roller asked me to add small pretty chamfers for the dices. This was a reasonable thing, I had thought, and tried to make it. And meet... uh... a tough puzzle. Well, I had three or four attempts to solve it, but each time I failed due a lack of time and patience.

This is really pure algorithmic task, just a such one I love. And today I got the solution.
With the next version of the Roller, the selector screen will be changed to be like this:

My friend was right, chamfered dices are much more cute. Especially in comparing with old version:

What was so hard? Well, I have no dice models prepared in 3D-editor. There are only arrays of vertices and faces, that's all that I have. To make chamfers you have to create additional vertices, corner faces and edge ones. Moreover, vertices direction of each face should be strictly in CCW order. This last thing was frustrating =)

Let's zoom.
Dice with no chamfer:

Dice with normal chamfer:

And special dice with wide chamfer for better understanding:

Red line shows original shape and size of face "2".

First of all, I reduce sizes of main faces. For each face a center point is calculated, after that all vertices of the face are moved slightly to the center point.
Next step is to find all pairs of faces linked with their common edge. Having this pairs helps to create edge faces. The thing that must be kept in mind is that direction of vertices should be in CCW order. To manage this, I check corresponded vertex orders of original paired faces.
Finally, corner faces to be created. For each original vertex I find chamfed vertices (in our example, there are five of them). List of them is not a face yet, because order of vertices is chaotic. I sort them by checking their order in neighbor edge faces.

The algorithm is quite fast as I think, because there are no cross products calculated, and I managed to avoid any affine transformations with normals and vertices of faces.

Anyway, I glad to see this result. The solution contains of only 60 lines of code. I adore such beauty =)

No comments:

Post a Comment