Skip to content
Permalink

Comparing changes

Choose two branches to see what’s changed or to start a new pull request. If you need to, you can also or learn more about diff comparisons.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also . Learn more about diff comparisons here.
base repository: solvespace/solvespace
Failed to load repositories. Confirm that selected base ref is valid, then try again.
Loading
base: 05aa6495083b
Choose a base ref
...
head repository: solvespace/solvespace
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: a7e0a174e309
Choose a head ref
  • 1 commit
  • 1 file changed
  • 1 contributor

Commits on May 8, 2020

  1. Don't create redundant edges in UvGridTriangulate into.

    @phkahler
    phkahler committed May 8, 2020
    Copy the full SHA
    a7e0a17 View commit details
Showing with 72 additions and 52 deletions.
  1. +72 −52 src/srf/triangulate.cpp
124 changes: 72 additions & 52 deletions src/srf/triangulate.cpp
View file
Original file line number Diff line number Diff line change
@@ -437,68 +437,88 @@ void SPolygon::UvGridTriangulateInto(SMesh *mesh, SSurface *srf) {
srf->MakeTriangulationGridInto(&li, 0, 1, /*swapped=*/true);
lj.Add(&v);
srf->MakeTriangulationGridInto(&lj, 0, 1, /*swapped=*/false);
if ((li.n > 3) && (lj.n > 3)) {
// Now iterate over each quad in the grid. If it's outside the polygon,
// or if it intersects the polygon, then we discard it. Otherwise we
// generate two triangles in the mesh, and cut it out of our polygon.
// Quads around the perimeter would be rejected by AnyEdgeCrossings.
std::vector<bool> bottom(lj.n, false); // did we use this quad?
int i, j;
for(i = 1; i < (li.n-1); i++) {
bool prev_flag = false;
for(j = 1; j < (lj.n-1); j++) {
bool this_flag = true;
double us = li[i], uf = li[i+1],
vs = lj[j], vf = lj[j+1];

Vector a = Vector::From(us, vs, 0),
b = Vector::From(us, vf, 0),
c = Vector::From(uf, vf, 0),
d = Vector::From(uf, vs, 0);

// | d-----c
// | | |
// | | |
// | a-----b
// |
// +-------------> j/v axis

if( (i==(li.n-2)) || (j==(lj.n-2)) ||
orig.AnyEdgeCrossings(a, b, NULL) ||
orig.AnyEdgeCrossings(b, c, NULL) ||
orig.AnyEdgeCrossings(c, d, NULL) ||
orig.AnyEdgeCrossings(d, a, NULL))
{
this_flag = false;
}

// Now iterate over each quad in the grid. If it's outside the polygon,
// or if it intersects the polygon, then we discard it. Otherwise we
// generate two triangles in the mesh, and cut it out of our polygon.
int i, j;
for(i = 0; i < (li.n - 1); i++) {
for(j = 0; j < (lj.n - 1); j++) {
double us = li[i], uf = li[i+1],
vs = lj[j], vf = lj[j+1];

Vector a = Vector::From(us, vs, 0),
b = Vector::From(us, vf, 0),
c = Vector::From(uf, vf, 0),
d = Vector::From(uf, vs, 0);

if(orig.AnyEdgeCrossings(a, b, NULL) ||
orig.AnyEdgeCrossings(b, c, NULL) ||
orig.AnyEdgeCrossings(c, d, NULL) ||
orig.AnyEdgeCrossings(d, a, NULL))
{
continue;
}

// There's no intersections, so it doesn't matter which point
// we decide to test.
if(!this->ContainsPoint(a)) {
continue;
// There's no intersections, so it doesn't matter which point
// we decide to test.
if(!this->ContainsPoint(a)) {
this_flag = false;
}

if (this_flag) {
// Add the quad to our mesh
STriangle tr = {};
tr.a = a;
tr.b = b;
tr.c = c;
mesh->AddTriangle(&tr);
tr.a = a;
tr.b = c;
tr.c = d;
mesh->AddTriangle(&tr);

if (!prev_flag) // add our own left edge
holes.AddEdge(d, a);
if (!bottom[j]) // add our own bottom edge
holes.AddEdge(a, b);
} else {
if (prev_flag) // add our left neighbots right edge
holes.AddEdge(a, d);
if (bottom[j]) // add our bottom neighbors top edge
holes.AddEdge(b, a);
}
prev_flag = this_flag;
bottom[j] = this_flag;
}

// Add the quad to our mesh
STriangle tr = {};
tr.a = a;
tr.b = b;
tr.c = c;
mesh->AddTriangle(&tr);
tr.a = a;
tr.b = c;
tr.c = d;
mesh->AddTriangle(&tr);

holes.AddEdge(a, b);
holes.AddEdge(b, c);
holes.AddEdge(c, d);
holes.AddEdge(d, a);
}
}

holes.CullExtraneousEdges();
SPolygon hp = {};
holes.AssemblePolygon(&hp, NULL, /*keepDir=*/true);
// Because no duplicate edges were created we do not need to cull them.
SPolygon hp = {};
holes.AssemblePolygon(&hp, NULL, /*keepDir=*/true);

SContour *sc;
for(sc = hp.l.First(); sc; sc = hp.l.NextAfter(sc)) {
l.Add(sc);
SContour *sc;
for(sc = hp.l.First(); sc; sc = hp.l.NextAfter(sc)) {
l.Add(sc);
}
hp.l.Clear();
}

orig.Clear();
holes.Clear();
li.Clear();
lj.Clear();
hp.l.Clear();

UvTriangulateInto(mesh, srf);
}