My name is Thijs Roumen Hasso Plattner Institute, and I
present autoAssembler, a software tool that automatically
converts 2D cutting plans
to 3D models for laser cutting.
This conversion to 3D allows users to make 3D parametric
changes very easily,
which is crucial for customizing models downloaded from the web.
Sharing and reuse is key for any field to mature. However, to
make shared laser cut models useful, users need to customize
them. For this VR headset to be valuable to users, they may want
to change the model so that it fits their prescription,
adjust the inter-ocular distance,
reduce the weigh,t or stretch it vertically so as to allow their
phone to fit in
a series of changes that are all trivial to do in 3D, but hard to
do in the 2D formats in which these models are currently
shared.
assembler^3 our CHI 2021 paper is a tool that converts to share
2D cutting plans to 3D models manually. Users assist the
algorithm by puzzling together the model. This means that users
need to know about the structure and the parts of the model,
which is fine for the current uses of laser cutters. But what
if the other 99% of people wanted to do this, they are
interested in the VR headset and nothing the puzzle of assembling
it.
We therefore present autoAssembler, a beam search
algorithm that automates the process of reconstructing laser
cut models.
AutoAssembler uses the same import routine as assembler^3;
users load 2D cutting plans into the editor. But now
autoAssembler attempts to assemble the model in the
background.
Once this is done, users click import and make the desired
modification to the model.
Under the hood, autoAssembler beam searches the space of
possible assemblies. It starts with the plate with most joints,
and then assembles next plates into the model. It scores each
of these assemblies based on its heuristic function and picks the
four best assemblies.
It then recursively executes this routine until all plates
are assembled into the model.
The beam search algorithm makes it tractable for autoAssembler
to track the exponential space of assemblies is worst case
complexity is O of d times k, in which d is the depth or the
number of plates in the model, and k is the beam width
multiplied by the maximum fanout
the fanout are all the possible next combinations at each state.
And in our case that is actually proportional to the depth or the
other plates that are still in the model. And therefore the
worst case complexity is quadratic in the number of
plates.
However, autoAssembler limits this fan out by only pairing up
joints that are candidates to the current state, thereby
drastically reducing the typical complexity. Unless all joints in
the model are exactly the same.
AutoAssembler achieves this using a data structure that we
presented in assembler^3, a hash table of the shape of the joints
of the model.
If we look up a joint on our model, like this green one
highlighted here in that hash table, we retrieve the orange
collisions in constant time, which are all the joints that
fit to the current candidate joint.
So the hash table gives us a joint which matches but there's
so many ways to combine the fitting plates into new
assembled states. Therefore, autoAssembler uses a heuristic
function that scores the states to decide what assemblies to
favor. This function is made up of six heurstics, which I will
introduce in detail in the next section.
AutoAssembler gives preference to compact candidates.
AutoAssembler scores compactness is by minimizing the size of the
bounding box of candidates. This magazine holder therefore gets a
much worse score and this one
AutoAssembler avoids intersections between plates. It
therefore assigns a low score to this train wagon, and a much
higher score to this one.
AutoAssembler gives preference to the use of unambiguous
joints. Here directly it can be assembled in 12 different ways.
And this ambiguity further goes up when assembling the next
plate after that. Instead, autoAssembler assigns a better
score to this plate which has little ambiguity, and then this
plate after that. Together they now constrain what used to be
direct plate.
AutoAssembler minimizes the number of unmatched joints
assembling this red made leads to a strong increase of the
search space.
As it opens up a lot of new joints. AutoAssembler therefore
assigns a better score to this green plate, which closes down
two joints and opens up only one. To keep the search space
tractable.
AutoAssembler prefers to assemble plates that make use of
constraints by other plates. Rather than assembling this red
nosepiece here, which can be assembled in many different
ways, autoAssembler first assembled this green plate here,
which is fully constrained by its neighbors, and this plate
now in turn constraints the nosepiece that we were trying to
assemble before to finish off that headset.
Finally, we found that most models are symmetric in nature.
AutoAssembler therefore assigns a bad score to this plate which
is flipped along the symmetry axis and assigns a good score to
this plate which is assembled in the correct orientation.
to tune the weights of the heuristics, we use hyper
parameter optimization based on the tree position estimator as
proposed by Long Wen et al., in 2020. This algorithm converges
after feeding around 1000 assembled states as input.
Intuitively, we had expected to see a much higher score for
intersections. But the truth is we aim to save computational
resources when scoring plates as also several rensis scoring many
many times. And therefore we find false positives when we're
looking for intersections, which is why the hyper parameter
optimization is assigned a lower weight to the intersection
finding.
We ran the algorithm on a benchmark of lasercut models we
used to evaluate assembler^3, we limited this through the models
that have joints at their edges, as autoAssembler only wor
s on those,
we achieve a success rate of 79% in a fully automated fashion.
And by using up to four clicks of our manual disambiguation
tool, the total success rate goes up to 97%, which we show
here at this example of assembling a series of models.
So in conclusion, I have been tackling the challenge of how to
reconstruct 3D models twice, in my CHI paper assembler^3 by let
ing users manually puzzle tog ther a 3D model from 2D pla
es. And in this paper, I've sta ted to automate that pro
ess. What gets me excited abo t this is that these 3D mod
ls now allow others to rep oduce and customize the mod
ls, resulting in a future whe e rather than reinventing mod
ls every time, we could rea ly start to build on the wor
of others and achieve much hig er levels of complexity with o
r lasercut models.
Finally, I want to thank my co authors at the Hasso Plattner
nstitute for a fantastic ollaboration on this project.
And I look forward to discuss this research with you hear in t
e Q&A or later in my demo sessio . Thank you so much for yo
r attentio