How a part is broken into simple blocks#
This page explains, step by step and in pictures, how the library takes a solid part and works out what simple blocks it is made of.
Each step is given twice: first in plain terms with a picture, then — in a box like the one below — as the precise definition, in the vocabulary the method is stated in. Read the prose, the boxes, or both.
Formally
Boxes like this one carry the exact statement, and the name the library uses for it. They are the reference; the prose around them is the explanation.
There is no code on this page — it is about the method, not the API. When you want to run it, go to Decomposing a part.
Tip
The part used throughout:
zhang2020_figure_6_a.step
The question being asked#
Look at this part.
It is 80 mm long, 35 mm deep and 55 mm tall. You can describe it in one breath: a flat slab, with a thin wall standing up on it.
That sentence is what we want the computer to produce — not the list of surfaces, which it can already read out of the file, but the description in terms of chunky, simple pieces.
Here is the catch, and it is the single most important idea on this page. That question does not have one answer. Look again:
It is a slab, with a wall on top of it.
It is also a tall wall, with a slab wrapped round its bottom.
Both are correct. Neither is more true. A good method returns all of the sensible answers rather than picking a favourite — and that is what this one does.
Formally
The output is the set of maximal volumes of the solid. They are not a partition: they overlap, and their volumes sum to more than the solid. Every one of them is returned.
What counts as a “simple block”#
Run your finger along the outside of a solid object. At most edges it goes around a corner that sticks out — the corner of a brick, the edge of a table. Sometimes it goes into a corner that folds in, like the inside corner of a step, or where a wall meets a floor.
The rule
A simple block is a lump of material with no inside corners anywhere on it.
A brick has none. A ball has none. A tube has none. An L-shaped block has one, in the crook of the L — so an L-shaped block is not simple, and the method will want to cut it.
Our part has some. Here is where.
The blue face is the top of the slab — the floor the wall stands on. The orange faces are the sides of the wall. Everywhere an orange face meets the blue one, the material folds inward.
There are three such places, one along each exposed side of the wall. The wall’s fourth side does not count: it sits flush with the back of the slab, so the two surfaces run on smoothly into one another and nothing folds in.
Formally
An inside corner is a concave edge. A maximal volume of a solid is a volume that
has no concave edge,
every face of which lies on the extension of a face of the solid, and
is not contained in any other volume satisfying 1 and 2.
Which junctions count as concave is a choice, exposed as the concavity setting. The
default reads only junctions where the two faces genuinely meet at an angle; the
alternative also reads tangent ones, where the faces meet smoothly.
Step 1 — carry the faces on, as sheets#
Take a face that runs into an inside corner — say the blue floor. In the real part that floor stops where the wall begins, but nothing says it has to. Imagine it carrying straight on, through the wall, like a sheet of glass pushed through the part.
Do the same with each of the three orange wall sides: each becomes a sheet carrying on downwards, through the slab.
The part is drawn see-through so you can look inside it. The blue sheet is the floor carried on; the orange sheets are the three wall sides carried down. The colours match the previous picture: each sheet comes from the face of the same colour.
Note that the sheets are not cuts yet — nothing has been removed — and that they stop at the edge of the material rather than running on into thin air.
Formally
Each is an extension face: a trimmed piece of the extended surface of a face carrying a concave edge. Only such faces are extended; a face with no concave edge is never extended, and a free-form face has no unique extension and is refused.
How far the piece reaches is the localisation setting. Localised extension —
the default — bounds the sheet by the neighbouring faces its own face meets across
non-concave edges, and by the solid. Global extension bounds it by neither.
The difference is not cosmetic. On this part the three sheets below are bounded by the wall’s own corners, and unbounding them slices the slab from end to end: seven cells rather than three. On the cast bracket at the foot of this page it is 137 rather than 27. How far a sheet reaches is this one step on its own, in pictures.
Step 2 — cut, and get cells#
Now use the sheets as knives. The part falls into three pieces, shown pulled apart — in the real part they sit snugly together with no gaps.
Cell |
What it is |
Share of part |
|---|---|---|
blue |
the slab, with a notch where the wall stands |
49.8 % |
orange |
the block directly underneath the wall |
18.2 % |
green |
the wall itself |
31.9 % |
The blue piece has a rectangular notch bitten out of it, and the orange block is exactly what fills it. That orange block matters a great deal in a moment. In the assembled part you cannot see it at all — it is buried inside the slab, directly under the wall.
The three shares add to 100 %. Every scrap of the part is in exactly one cell.
Formally
The pieces are cells, and they tile the solid: they are disjoint and their union is the solid. Cells are not necessarily convex — the blue one here is not.
Step 3 — classify every face of every cell#
Each cell is a small solid with faces of its own. Some were always there, on the outside of the original part; others exist only because we cut. Which is which is the only information the next steps use.
There are three kinds, not two, and the distinction between the last two is what makes the method work.
Real, written R — the face is genuinely part of the outside of the part. Nothing lies beyond it but air.
Extension, written E — the face is not part of the original outside, but it lies on a surface the part uses from the same side. Crossing it may push a volume out past real material.
Complement, written C — the face is not part of the original outside, and it lies on a surface the part uses only from the opposite side. A volume must never keep such a face on its boundary.
Here is every face of all three cells, each lettered with its kind. The cells keep the colours they had when they were introduced — blue slab, orange block, green upright — washed out here so the letters read against them.
Each cell is drawn twice: on the left from the front, on the right from directly behind. A face turned away from you in one view is turned towards you in the other, so every face is seen — and lettered on itself — in exactly one of the two. Ten letters for the ten faces of the slab, six each for the boxes.
Read the tallies above each cell. The buried block is the only one with E faces — every direction out of it leads to more metal. The other two carry only R and C. That difference decides the next step.
Formally
Every face lies on a surface, and uses one of that surface’s two sides — the side its material is on. Call two faces same-sided when they lie on one surface and use the same side of it, and opposite-sided when they lie on one surface and use opposite sides. Both are statements about the surface, which is unbounded: two faces can be same-sided while sitting far apart on it, and that is precisely the case this step is about.
Take one face of one cell and compare it against every face of the original solid. It is
an R-CFACE if it lies on one of those faces;
an E-CFACE if it lies on none of them, at least one of them is same-sided with it, and none is opposite-sided;
a C-CFACE if it lies on none of them, none of them is same-sided with it, and at least one is opposite-sided.
The library calls these "real", "extension" and "complement". The three do
not cover everything: a face on a surface the solid uses from both sides is
same-sided and opposite-sided at once, so it is none of them. The library labels such a
face "unclassified", and a cell holding one can never seed a volume.
The classification belongs to the pair (face, cell), not to the face. The face between two cells is seen from opposite sides, so one cell may call it an E-CFACE where the other calls it a C-CFACE.
Step 4 — pick somewhere to start#
We build volumes back up out of cells, and we need somewhere to begin. Not every cell will do.
A cell can start a volume only if it has no extension face. An extension face means there is material beyond it that any volume containing this cell would also have to hold — so a cell with one is a piece of something bigger, never the innermost part of it.
By that rule, the notched slab and the upright can both start a volume. The buried block cannot: all four of its cut faces have more metal beyond them.
Formally
A seed cell is a cell all of whose faces are R-CFACEs or C-CFACEs. Two facts make the method work, and both are properties of the construction rather than assumptions: when a solid is decomposed into cells by extending the faces carrying concave edges, seed cells always exist; and every maximal volume contains at least one.
That is what bounds the search. The library calls a seed cell a nucleus, and reports
them on the result as nuclei.
Step 5 — grow#
Start from a seed cell and spread outward, cell by cell, deciding at each face whether to take the cell on the other side of it. The three kinds of face are handled differently, and this is where they earn their names:
Real — never crossed. There is no cell on the other side; the volume ends here.
Complement — always crossed. A volume may not keep a complement face on its boundary, so the cell beyond is always taken.
Extension — crossed unless the volume already holds a real face lying on that same surface. If it does, crossing would push the volume out past the real skin of the part, so it stops.
Repeat on every newly taken cell until there is nothing left to take. What you have then is one collection of cells — one answer.
Formally
This is the cell-collection rule, applied recursively from each seed cell until no cell remains to be collected:
R-CFACEs take no part — there is no adjacent cell across them.
C-CFACEs — the adjacent cell is always collected, since a maximal volume must not retain a complement halfspace of the original solid.
E-CFACEs — the adjacent cell is collected only if no already-collected cell has an R-CFACE whose geometry is the same as that E-CFACE’s. If one does, the adjacent cell is not collected.
The rule is local — it reads only the classifications of faces between neighbouring cells — and it is order-dependent by construction, since whether an E-CFACE is crossed depends on what has already been collected.
Step 6 — the two answers#
Do that from each of the two seed cells, and two volumes come out.
From the notched slab, growth crosses into the buried block and stops. The result is the complete base slab:
That is the answer “this part is a slab, 80 × 35 × 20 mm, with something standing on it.” It accounts for 68.1 % of the part.
From the upright, growth goes downward into the buried block and stops. The result is the wall carried all the way to the ground:
That is the answer “this part is an upright, 50 × 15 × 55 mm, standing on the floor, with material packed around its foot.” It accounts for 50.2 % of the part.
Both are complete volumes with no inside corner anywhere on them, and neither is contained in the other. The method returns both and refuses to choose.
Why the shares add up to more than everything#
68.1 % + 50.2 % = 118.2 %.
That is not a mistake, and understanding why is understanding the whole method. The two answers share a piece — the buried block belongs to both:
It is part of the slab, when you read the part as a slab. It is the foot of the upright, when you read the part as an upright. It cannot be given to one and taken from the other without making one of the two answers wrong.
The volumes overlap by design. They are not slices of a cake that must add to 100 %; they are descriptions, and one piece of metal can honestly belong to more than one.
Warning
If the volumes add up to more than the part, that is expected. What would be a problem
is the reverse — material belonging to no volume at all. That is measured separately, as
covered_fraction; see Decomposing a part.
The last rule: biggest wins#
Suppose growing from two different seed cells gave a volume, and a smaller volume sitting entirely inside it. The smaller tells you nothing new, and is discarded.
There is also a repair step for the case where growth returns a collection that still has a concave edge on it. It is not patched up or grown further. It is treated as a solid in its own right and the whole method is run again on it from the beginning — find its concave edges, extend, cut, grow — and its pieces stand in for it. Repair is by splitting, not by growing. Anything surviving even that is handed back and flagged rather than quietly dropped.
Formally
A collection whose cells are a subset of another’s is discarded on the spot. That is not the whole test: two collections can tile the same region out of different cells, so neither cell set contains the other while the volumes do. The remainder is settled geometrically, by intersecting the volumes.
Volumes still holding a concave edge after the recursion are reported in
concave_volumes rather than dropped, since dropping them would remove their material
from the reading without saying so.
The same method on real parts#
Nothing above was special to a two-block shape. The three parts below are ordinary engineering parts, and each one is put through the identical procedure.
A bearing saddle#
A bore, mounting flanges and a raised boss.
It has 44 faces. The concave edges produce extension faces which cut it into 29 cells, and growing from every seed cell yields seven volumes, together accounting for 100 % of the material:
Volume |
How many |
Share of part |
|---|---|---|
the main body, spanning the whole footprint |
1 |
58.2 % |
the upright side plates, one on each side |
2 |
17.0 % each |
the flat end flanges, one at each end |
2 |
13.1 % each |
the raised boss on top, read two ways |
2 |
8.8 % and 6.4 % |
You can read the part off that list in words: a main body, two side plates, two end flanges and a boss on top — produced from nothing but the shape, with no drawing, no model tree and no hints.
Notice the last row. Two of the seven volumes sit at exactly the same place, with the same square footprint, differing only in how far up they reach: two readings of the boss. The overlap you met on the simple part, on a real one.
A clamp arm#
Smaller, and worth looking at for how little there is to say about it. Five cells, three volumes, all of the material covered.
Red is the clamped block with its bore, at 27.5 % of the part; blue the arm carrying it, at 63.5 %; green the mounting flange it stands on, at 22.0 %. Read the colours out and you have said what the part is: a block with a bore, on an arm, on a flange.
The blue arm reaches into the red block rather than stopping at it — 113 % between the three — which is the same overlap again: the arm is as much a beam running the length of the part as it is a beam ending where the block starts.
A cast bracket#
Curves, tapers, and three bores on two axes. Twenty-seven cells, seven volumes, all of the material covered.
Volume |
How many |
Share of part |
|---|---|---|
the upright wall along the top, with its end lug |
1 |
41.6 % |
the slab under it, spanning the same footprint |
1 |
34.1 % |
the tube around the main bore, carried down through the slab |
1 |
19.9 % |
the tapered legs, one on each side |
2 |
15.9 % each |
the eyes at the ends of the legs |
2 |
4.7 % each |
Three things this part shows that a prismatic one cannot.
Curves and tapers are not a special case. The wavy edge of the slab and the sloping sides of the legs are not planes, and nothing about the method needed to change for them: an extension face is taken from whatever surface the concave edge sits on, be it flat, cylindrical or sloped, and is bounded the same way.
A block with a hole through it is already a simple block. The tube around the main bore and the two eyes at the ends of the legs come back whole. A hole’s wall never makes an inside corner — cross the rim of a bore and the material turns the convex way — so there is nothing there to cut, and no volume is ever grown into a hole.
Symmetry produces equal volumes, and both are kept. The pair at 15.9 % and the pair at 4.7 % are mirror images of each other. Only a volume contained in another is discarded, and neither of a mirrored pair contains the other, so both stay in the answer. Dropping one would leave the part describing half of itself.
Where to go next#
Decomposing a part — how to run this on your own file, and how to read the result
Decomposition — the rest of this section