Geometric optimization and processing for fabrication and simulation

Abstract

Finding an optimal geometric structures with some constraints satisfied has always been an interesting and important topic, and the number of graphics literatures trying to attack such problem is considerable. This thesis shows the applications of geometric optimization techniques in new scenarios like 3D printing, augmented reality, and the application of geometric processing techniques in traditional simulation problems.

The first part of the thesis shows the application of geometric optimization in 3D printing, where we find an optimal internal supporting structure insides 3D printed objects, trying to minimize the material cost while making sure the 3D printed object is strong enough for daily usage. As the material cost is proportional to the volume which in turn has cubic relation with the size of object, the cost to print a solid medium sized object would beyond many people's means. But a \naive/ hollowing method would make the object less durable for everyday use. Inspired from the skeleton structure of animals, we use the a similar geometric structure, the medial axis, as the base for building a tree like internal supporting structure inside a hollowed object. Experiments shows that our method could reduce the material usage significantly without compromising the strength of objects too much.

The second part of the thesis shows the application of geometric optimization in augmented reality, where we find an optimal stroke decomposition and drawing order to guide people to draw a wireframe model in the air with the 3D drawing pen. 3D drawing pen is a small handheld 3D printer where materials extruded will stabilize immediately thus people can create 3D strokes freely in the air. But the shift from 2D drawing to 3D drawing is a challenge for most people. Inspired from the copying technique when people practice calligraphy, we use augmented reality devices to assist the copying of 3D wireframe models, thus people can draw accurately and confidently. However, one problem not arising in 2D calligraphy copying scenario is that the strokes order is well known, while this is not the case for arbitrary wireframe models, so we designed an optimization algorithm to decompose a wireframe model into strokes in an order intuitive for drawing. Experiments show that the drawing quality is largely improved when our strokes sequences are presented to the user.

The third part of thesis shows the application of geometric processing in simulation, where we build a multi-block quad decomposition of the simulation domain with features constraints, then a structured mesh could be generated on each sub-block. Compared with existing works, our algorithm eliminates T-junctions as locally as possible, which reduces the number of resulting blocks and the complexity of later structured mesh generation for each sub-block.