Skip to content

NURBS: Add intersection boolean operation. #595

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
phkahler merged 4 commits into from
May 10, 2020
Merged

NURBS: Add intersection boolean operation. #595

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
4 commits
Select commit Hold shift + click to select a range
b215470
NURBS: Add intersection boolean operation.
ruevs May 8, 2020
0c25c9a
Intersection boolen in triangle mesh mode is properly implemented
ruevs May 10, 2020
7a2b874
UI: Fix the logic for switching between union/assemble and difference…
ruevs May 10, 2020
72ff12e
UI: split "union assemble" and "difference intersection" on two lines.
ruevs May 10, 2020
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
1 change: 1 addition & 0 deletions CHANGELOG.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -5,6 +5,7 @@ Changelog
---

New sketch features:
* New intersection boolean operation for solid models.
* New groups, revolution and helical extrusion.
* Extrude, lathe, translate and rotate groups can use the "assembly"
boolean operation, to increase performance.
Expand Down
35 changes: 23 additions & 12 deletions src/bsp.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -62,14 +62,17 @@ void SBsp3::InsertInPlane(bool pos2, STriangle *tr, SMesh *m) {
ll = ll->more;
}

if(m->flipNormal && ((!pos2 && !onFace) ||
(onFace && !sameNormal && m->keepCoplanar)))
{
m->AddTriangle(tr->meta, tr->c, tr->b, tr->a);
} else if(!(m->flipNormal) && ((pos2 && !onFace) ||
(onFace && sameNormal && m->keepCoplanar)))
{
m->AddTriangle(tr->meta, tr->a, tr->b, tr->c);
if((!onFace && ((m->keepInsideOtherShell && !pos2) ||
(!m->keepInsideOtherShell && pos2))) ||
(onFace && ((m->keepCoplanar && m->flipNormal && !sameNormal) ||
(m->keepCoplanar && !m->flipNormal && sameNormal)))) {
// We have decided that we need to keep a triangle either inside,
// outside or on the other shell. So add it and flip it if requested.
if(!(m->flipNormal)) {
m->AddTriangle(tr->meta, tr->a, tr->b, tr->c);
} else {
m->AddTriangle(tr->meta, tr->c, tr->b, tr->a);
}
} else {
m->atLeastOneDiscarded = true;
}
Expand Down Expand Up @@ -101,10 +104,15 @@ void SBsp3::InsertHow(BspClass how, STriangle *tr, SMesh *instead) {
return;

alt:
if(how == BspClass::POS && !(instead->flipNormal)) {
instead->AddTriangle(tr->meta, tr->a, tr->b, tr->c);
} else if(how == BspClass::NEG && instead->flipNormal) {
instead->AddTriangle(tr->meta, tr->c, tr->b, tr->a);
if(((BspClass::POS == how) && !instead->keepInsideOtherShell) ||
((BspClass::NEG == how) && instead->keepInsideOtherShell)) {
// We have decided that we need to keep a triangle (either inside or
// outside the other shell. So add it and flip it if requested.
if(!(instead->flipNormal)) {
instead->AddTriangle(tr->meta, tr->a, tr->b, tr->c);
} else {
instead->AddTriangle(tr->meta, tr->c, tr->b, tr->a);
}
} else if(how == BspClass::COPLANAR) {
if(edges) {
edges->InsertTriangle(tr, instead, this);
Expand Down Expand Up @@ -431,6 +439,9 @@ SBsp3 *SBsp3::InsertConvex(STriMeta meta, Vector *vertex, size_t cnt, SMesh *ins
SBsp3 *SBsp3::InsertOrCreate(SBsp3 *where, STriangle *tr, SMesh *instead) {
if(where == NULL) {
if(instead) {
// ruevs: I do not think this code is reachable, but in
// principle should we use instead->keepInsideOtherShell
// in place of instead->flipNormal ?
if(instead->flipNormal) {
instead->atLeastOneDiscarded = true;
} else {
Expand Down
24 changes: 17 additions & 7 deletions src/groupmesh.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -143,7 +143,7 @@ void Group::GenerateForStepAndRepeat(T *steps, T *outs, Group::CombineAs forWhat
// And tack this transformed copy on to the return.
if(soFar->IsEmpty()) {
scratch->MakeFromCopyOf(&transd);
} else if (forWhat == CombineAs::ASSEMBLE) {
} else if(forWhat == CombineAs::ASSEMBLE) {
scratch->MakeFromAssemblyOf(soFar, &transd);
} else {
scratch->MakeFromUnionOf(soFar, &transd);
Expand All @@ -170,12 +170,22 @@ void Group::GenerateForBoolean(T *prevs, T *thiss, T *outs, Group::CombineAs how

// So our group's shell appears in thisShell. Combine this with the
// previous group's shell, using the requested operation.
if(how == CombineAs::UNION) {
outs->MakeFromUnionOf(prevs, thiss);
} else if(how == CombineAs::DIFFERENCE) {
outs->MakeFromDifferenceOf(prevs, thiss);
} else {
outs->MakeFromAssemblyOf(prevs, thiss);
switch(how) {
case CombineAs::UNION:
outs->MakeFromUnionOf(prevs, thiss);
break;

case CombineAs::DIFFERENCE:
outs->MakeFromDifferenceOf(prevs, thiss);
break;

case CombineAs::INTERSECTION:
outs->MakeFromIntersectionOf(prevs, thiss);
break;

case CombineAs::ASSEMBLE:
outs->MakeFromAssemblyOf(prevs, thiss);
break;
}
}

Expand Down
23 changes: 20 additions & 3 deletions src/mesh.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -265,11 +265,12 @@ void SMesh::MakeFromUnionOf(SMesh *a, SMesh *b) {
SBsp3 *bspb = SBsp3::FromMesh(b);

flipNormal = false;
keepCoplanar = false;
AddAgainstBsp(b, bspa);
keepInsideOtherShell = false;

flipNormal = false;
keepCoplanar = true;
AddAgainstBsp(b, bspa);

keepCoplanar = false;
AddAgainstBsp(a, bspb);
}

Expand All @@ -279,11 +280,27 @@ void SMesh::MakeFromDifferenceOf(SMesh *a, SMesh *b) {

flipNormal = true;
keepCoplanar = true;
keepInsideOtherShell = true;
AddAgainstBsp(b, bspa);

flipNormal = false;
keepCoplanar = false;
keepInsideOtherShell = false;
AddAgainstBsp(a, bspb);
}

void SMesh::MakeFromIntersectionOf(SMesh *a, SMesh *b) {
SBsp3 *bspa = SBsp3::FromMesh(a);
SBsp3 *bspb = SBsp3::FromMesh(b);

keepInsideOtherShell = true;
flipNormal = false;

keepCoplanar = false;
AddAgainstBsp(a, bspb);

keepCoplanar = true;
AddAgainstBsp(b, bspa);
}

void SMesh::MakeFromCopyOf(SMesh *a) {
Expand Down
2 changes: 2 additions & 0 deletions src/polygon.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -252,6 +252,7 @@ class SMesh {
List<STriangle> l;

bool flipNormal;
bool keepInsideOtherShell;
bool keepCoplanar;
bool atLeastOneDiscarded;
bool isTransparent;
Expand All @@ -269,6 +270,7 @@ class SMesh {
void AddAgainstBsp(SMesh *srcm, SBsp3 *bsp3);
void MakeFromUnionOf(SMesh *a, SMesh *b);
void MakeFromDifferenceOf(SMesh *a, SMesh *b);
void MakeFromIntersectionOf(SMesh *a, SMesh *b);

void MakeFromCopyOf(SMesh *a);
void MakeFromTransformationOf(SMesh *a, Vector trans,
Expand Down
3 changes: 2 additions & 1 deletion src/sketch.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -239,7 +239,8 @@ class Group {
enum class CombineAs : uint32_t {
UNION = 0,
DIFFERENCE = 1,
ASSEMBLE = 2
ASSEMBLE = 2,
INTERSECTION = 3
};
CombineAs meshCombine;

Expand Down
26 changes: 20 additions & 6 deletions src/srf/boolean.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,6 +1,6 @@
//-----------------------------------------------------------------------------
// Top-level functions to compute the Boolean union or difference between
// two shells of rational polynomial surfaces.
// Top-level functions to compute the Boolean union, difference or intersection
// between two shells of rational polynomial surfaces.
//
// Copyright 2008-2013 Jonathan Westhues.
//-----------------------------------------------------------------------------
Expand All @@ -16,6 +16,10 @@ void SShell::MakeFromDifferenceOf(SShell *a, SShell *b) {
MakeFromBoolean(a, b, SSurface::CombineAs::DIFFERENCE);
}

void SShell::MakeFromIntersectionOf(SShell *a, SShell *b) {
MakeFromBoolean(a, b, SSurface::CombineAs::INTERSECTION);
}

//-----------------------------------------------------------------------------
// Take our original pwl curve. Wherever an edge intersects a surface within
// either agnstA or agnstB, split the piecewise linear element. Then refine
Expand Down Expand Up @@ -213,6 +217,13 @@ static bool KeepRegion(SSurface::CombineAs type, bool opA, SShell::Class shell,
return inShell || inSame;
}

case SSurface::CombineAs::INTERSECTION:
if(opA) {
return inShell;
} else {
return inShell || inSame;
}

default: ssassert(false, "Unexpected combine type");
}
}
Expand Down Expand Up @@ -463,7 +474,10 @@ SSurface SSurface::MakeCopyTrimAgainst(SShell *parent,
// point opposite to the surface normal.
bool bkwds = true;
if((tn.Cross(b.Minus(a))).Dot(sn) < 0) bkwds = !bkwds;
if(type == SSurface::CombineAs::DIFFERENCE && !opA) bkwds = !bkwds;
if((type == SSurface::CombineAs::DIFFERENCE && !opA) ||
(type == SSurface::CombineAs::INTERSECTION)) { // Invert all newly created edges for intersection
bkwds = !bkwds;
}
if(bkwds) {
inter.AddEdge(tb, ta, sc->h.v, 1);
} else {
Expand Down Expand Up @@ -573,7 +587,7 @@ SSurface SSurface::MakeCopyTrimAgainst(SShell *parent,
// we can get duplicate edges if our surface intersects the other shell
// at an edge, so that both surfaces intersect coincident (and both
// generate an intersection edge).
final.CullExtraneousEdges();
final.CullExtraneousEdges(/*both=*/true);

// Use our reassembled edges to trim the new surface.
ret.TrimFromEdgeList(&final, /*asUv=*/true);
Expand Down Expand Up @@ -849,14 +863,14 @@ void SBspUv::InsertEdge(Point2d ea, Point2d eb, SSurface *srf) {
m->more = more;
more = m;
} else if(fabs(dea) < LENGTH_EPS) {
// Point A lies on this lie, but point B does not
// Point A lies on this line, but point B does not
if(deb > 0) {
pos = InsertOrCreateEdge(pos, ea, eb, srf);
} else {
neg = InsertOrCreateEdge(neg, ea, eb, srf);
}
} else if(fabs(deb) < LENGTH_EPS) {
// Point B lies on this lie, but point A does not
// Point B lies on this line, but point A does not
if(dea > 0) {
pos = InsertOrCreateEdge(pos, ea, eb, srf);
} else {
Expand Down
3 changes: 2 additions & 1 deletion src/srf/surface.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -256,7 +256,7 @@ class SSurface {
enum class CombineAs : uint32_t {
UNION = 10,
DIFFERENCE = 11,
INTERSECT = 12
INTERSECTION = 12
};

int tag;
Expand Down Expand Up @@ -386,6 +386,7 @@ class SShell {
void MakeFirstOrderRevolvedSurfaces(Vector pt, Vector axis, int i0);
void MakeFromUnionOf(SShell *a, SShell *b);
void MakeFromDifferenceOf(SShell *a, SShell *b);
void MakeFromIntersectionOf(SShell *a, SShell *b);
void MakeFromBoolean(SShell *a, SShell *b, SSurface::CombineAs type);
void CopyCurvesSplitAgainst(bool opA, SShell *agnst, SShell *into);
void CopySurfacesTrimAgainst(SShell *sha, SShell *shb, SShell *into, SSurface::CombineAs type);
Expand Down
29 changes: 21 additions & 8 deletions src/textscreens.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -210,11 +210,19 @@ void TextWindow::ScreenChangeGroupOption(int link, uint32_t v) {
if(g->type == Group::Type::EXTRUDE) {
// When an extrude group is first created, it's positioned for a union
// extrusion. If no constraints were added, flip it when we switch between
// union and difference modes to avoid manual work doing the same.
if(g->meshCombine != (Group::CombineAs)v && g->GetNumConstraints() == 0 &&
((Group::CombineAs)v == Group::CombineAs::DIFFERENCE ||
g->meshCombine == Group::CombineAs::DIFFERENCE)) {
g->ExtrusionForceVectorTo(g->ExtrusionGetVector().Negated());
// union/assemble and difference/intersection modes to avoid manual work doing the same.
if(g->meshCombine != (Group::CombineAs)v && g->GetNumConstraints() == 0) {
// I apologise for this if statement
if((((Group::CombineAs::DIFFERENCE == g->meshCombine) ||
(Group::CombineAs::INTERSECTION == g->meshCombine)) &&
(Group::CombineAs::DIFFERENCE != (Group::CombineAs)v) &&
(Group::CombineAs::INTERSECTION != (Group::CombineAs)v)) ||
((Group::CombineAs::DIFFERENCE != g->meshCombine) &&
(Group::CombineAs::INTERSECTION != g->meshCombine) &&
((Group::CombineAs::DIFFERENCE == (Group::CombineAs)v) ||
(Group::CombineAs::INTERSECTION == (Group::CombineAs)v)))) {
g->ExtrusionForceVectorTo(g->ExtrusionGetVector().Negated());
}
}
}
g->meshCombine = (Group::CombineAs)v;
Expand Down Expand Up @@ -375,21 +383,26 @@ void TextWindow::ShowGroupInfo() {
g->type == Group::Type::HELIX) {
bool un = (g->meshCombine == Group::CombineAs::UNION);
bool diff = (g->meshCombine == Group::CombineAs::DIFFERENCE);
bool intr = (g->meshCombine == Group::CombineAs::INTERSECTION);
bool asy = (g->meshCombine == Group::CombineAs::ASSEMBLE);

Printf(false, " %Ftsolid model as");
Printf(false, "%Ba %f%D%Lc%Fd%s union%E "
"%f%D%Lc%Fd%s difference%E "
"%f%D%Lc%Fd%s assemble%E ",
&TextWindow::ScreenChangeGroupOption,
Group::CombineAs::UNION,
un ? RADIO_TRUE : RADIO_FALSE,
&TextWindow::ScreenChangeGroupOption,
Group::CombineAs::ASSEMBLE,
(asy ? RADIO_TRUE : RADIO_FALSE));
Printf(false, "%Ba %f%D%Lc%Fd%s difference%E "
"%f%D%Lc%Fd%s intersection%E ",
&TextWindow::ScreenChangeGroupOption,
Group::CombineAs::DIFFERENCE,
diff ? RADIO_TRUE : RADIO_FALSE,
&TextWindow::ScreenChangeGroupOption,
Group::CombineAs::ASSEMBLE,
(asy ? RADIO_TRUE : RADIO_FALSE));
Group::CombineAs::INTERSECTION,
intr ? RADIO_TRUE : RADIO_FALSE);

if(g->type == Group::Type::EXTRUDE || g->type == Group::Type::LATHE ||
g->type == Group::Type::REVOLVE || g->type == Group::Type::HELIX) {
Expand Down