@MASTERSTHESIS\{IMM2006-04668,
    author       = "M. Josefsson",
    title        = "Rigidity investigations in virtual Lego models",
    year         = "2006",
    school       = "Informatics and Mathematical Modelling, Technical University of Denmark, {DTU}",
    address      = "Richard Petersens Plads, Building 321, {DK-}2800 Kgs. Lyngby",
    type         = "",
    note         = "Supervised by Thomas Bolander, {IMM}. Thesis not public available.",
    url          = "http://www2.compute.dtu.dk/pubdb/pubs/4668-full.html",
    abstract     = "In this thesis, we investigate the potential improvement of the algorithms detecting rigid structures in virtual Lego models in the computer application Lego Digital Designer.

First, the previously achieved results are presented. This mainly involves a heuristic triangle rigidity detection algorithm described in a Bachelor’s thesis.

Then, the two theoretical fields framework rigidity and generic rigidity are examined. The aim is to apply them to virtual Lego models. The two theoretical fields face different obstacles. Framework rigidity does not seem suitable for detecting rigid structures; it also suffers from its dependence on the rank computations of a matrix that can grow very large and its compliance with infinitesimal rigidity instead of the kind of rigidity desired in the application. Generic rigidity most importantly fails because of its loss of geometric information, which leads to incorrect calculations of rigidity properties, and the fact that Laman’s theorem does not generalize to three dimensions for general graphs.

Finally, a heuristic approach is chosen. A rigidity detection algorithm for so-called “prism structures” is presented in pseudo code. The worst-case time complexity for the algorithm to detect prism rigidity after a brick has been added is O(r3), where r is the number of previously detected rigid structures in the model.

We conclude that the emphasis of future research should be put on heuristic approaches, e.g. treating three-dimensional structures with four (or more) one-dimensional joints, the removal of bricks, and the consequences of adding the domain of Technics bricks to the Digital Designer application."
}