如何使用three.js和jsclipper简化三角剖分的形状

Question

我尝试显示由构造路径命令构造的几何体，例如Three.js中的moveto lineto beziercurveto。因此我创建了一个THREE.ShapePath（）;并执行命令toShapes（isClockwise）。在此之后，我使用THREE.ExtrudeBufferGeometry来创建3D形状。

不幸的是，形状有时非常复杂，并且没有正确创建，这意味着它们是扭曲的。

使用libtess作为三角测量库解决了一些问题。但我仍然扭曲了几何形状。

现在我想使用jsclipper来简化三角测量之前的形状。

我用这样的方式修改了three.js：

在ExtrudeBufferGeometry的方法addShape中我添加了：

$.each(vertices, function(index, item) {
           vertices[index]['X'] = vertices[index]['x']; 
           vertices[index]['Y'] = vertices[index]['y']; 
           delete vertices[index]['x'];
           delete vertices[index]['y'];
      });
      
      if (holes[0]) {
        for (i = 0; i < holes.length; i++ )  {
          $.each(holes[i], function(index, item) {
               holes[i][index]['X'] = holes[i][index]['x']; 
               holes[i][index]['Y'] = holes[i][index]['y']; 
               delete holes[i][index]['x'];
               delete holes[i][index]['y'];
          });
        }
      }
      
      var scale = 100;
      ClipperLib.JS.ScaleUpPaths([vertices], scale);
      if (holes[0]) {
        ClipperLib.JS.ScaleUpPaths(holes, scale);
      }
      vertices = ClipperLib.Clipper.SimplifyPolygons([vertices], ClipperLib.PolyFillType.pftNonZero);
                                             // or ClipperLib.PolyFillType.pftEvenOdd
      if (holes[0]) {
        holes = ClipperLib.Clipper.SimplifyPolygons(holes, ClipperLib.PolyFillType.pftNonZero);
                                             // or ClipperLib.PolyFillType.pftEvenOdd
      }
      
      
//      var cleandelta = 0.1; // 0.1 should be the appropriate delta in different cases
//      vertices = ClipperLib.Clipper.CleanPolygons([vertices], cleandelta * scale);
//      if (holes[0]) {
//        holes = ClipperLib.Clipper.CleanPolygons(holes, cleandelta * scale);
//      }
      
      
                                             
      ClipperLib.JS.ScaleDownPaths(vertices, scale);
      if (holes[0]) {
        ClipperLib.JS.ScaleDownPaths(holes, scale);
      }
      
      for (i = 0; i < vertices.length; i++ )  {
        $.each(vertices[i], function(index, item) {
             vertices[i][index]['x'] = vertices[i][index]['X']; 
             vertices[i][index]['y'] = vertices[i][index]['Y']; 
             delete vertices[i][index]['X'];
             delete vertices[i][index]['Y'];
        });
      }
      if (holes[0]) {
        for (i = 0; i < holes.length; i++ )  {
          $.each(holes[i], function(index, item) {
               holes[i][index]['x'] = holes[i][index]['X']; 
               holes[i][index]['y'] = holes[i][index]['Y']; 
               delete holes[i][index]['X'];
               delete holes[i][index]['Y'];
          });
        }
      }

现在我可以看到顶点被“缩小”了。

但var faces = ShapeUtils.triangulateShape（顶点，孔）;不再为某些例子生成面孔。

请问一个人如何正确地简化形状？

Answer 1

有点难以弄清楚问题究竟是什么。 Clipper（当使用SimplifyPolygons或SimplifyPolygon时）也只能生成弱简单多边形，这意味着可能存在伪重复点：虽然顺序坐标保证不是同一个，但是下一些点可以共享相同的坐标。坐标也可以在两点之间的线上。

在简化（或任何其他布尔操作）之后，您可以使用具有小负值的Offsetting进行清理步骤：https://sourceforge.net/p/jsclipper/wiki/documentation/#clipperlibclipperoffsetexecute。

这可能会删除所有伪重复点。

我也制作了一个漂浮版的Clipper（http://jsclipper.sourceforge.net/6.4.2.2_fpoint/）。它经过了广泛的测试，但是因为最初的C＃Clipper（其中JS-version是从其移植而来）的作者Angus Johnson认为使用浮点数会导致健壮性问题，尽管根据我的测试，不是这样，原始的C＃浮点数版本不存在。浮动版本更易于使用，您可以在那里尝试一个小的负偏移：例如。 -0.001或-0.01。

您也可以尝试使用PolyTree或ExPolygons（https://sourceforge.net/p/jsclipper/wiki/ExPolygons%20and%20PolyTree%206/）。 ExPolygons可用于获取孔和轮廓，PolyTree可用于获得孔和轮廓的完整父子关系。

最后的手段是一个破碎的笔尖功能。它检测所有伪重复点并对它们产生破坏笔尖的影响，以便结果没有任何重复。附图显示了这种效果意味着使用大笔尖效果值来使效果更清晰。 Three.js polygon triangulation fails in pseudo duplicate points。有一个讨论https://github.com/mrdoob/three.js/issues/3386这个主题。

  // Make polygons to simple by making "a broken pen tip" effect on each semi-adjacent (duplicate) vertex
  // ORIGPOLY can be a contour
  // or exPolygon structure

  function BreakPenNibs(ORIGPOLY, dist, scale)
  {
    if (!dist || dist < 0) return;
    var sqrt = Math.sqrt;
    var allpoints = {}, point = {};
    var key = "";
    var currX = 0.0,
      currY = 0.0;
    var prevX = 0.0,
      prevY = 0.0;
    var nextX = 0.0,
      nextY;
    var x = 0.0,
      y = 0.0,
      length = 0.0,
      i = 0,
      duplcount = 0,
      j = 0;
    var prev_i = 0,
      next_i = 0,
      last_i;
    var extra_vertices = new Array(100),
      moved_vertices = new Array(100);

    // Get first all duplicates
    var duplicates = new Array(100),
      indexi = "",
      indexstr = "",
      arraystr = "",
      polys, outer, holes;
    if (ORIGPOLY instanceof Array) 
    {
      outer = ORIGPOLY;
    }
    else if (ORIGPOLY.outer instanceof Array) 
    {
      outer = ORIGPOLY.outer;
    }

      else return;
    if (ORIGPOLY.holes instanceof Array) holes = ORIGPOLY.holes;
    else holes = [];
    polys = [outer].concat(holes);
    var polys_length = polys.length;
    // Get first max lenght of arrays
    var max_index_len = 0;
    var arr_len;
    i = polys_length;
    while (i--)
    {
      arr_len = polys[i].length;
      if (arr_len > max_index_len) max_index_len = arr_len;
    }
    max_index_len = max_index_len.toString().length;
    var max_polys_length = polys_length.toString().length;
    var poly;
    j = polys_length;
    var scaling = scale/10;
    while (j--)
    {
      poly = polys[j];
      ilen = poly.length;
      i = ilen;
      while (i--)
      {
        point = poly[i];
        //key = Math.round(point.X) + ":" + Math.round(point.Y);
        
        key = (Math.round(point.X / scaling) * scaling)
        + ":" + (Math.round(point.Y / scaling) * scaling);
        indexi = allpoints[key];
        if (typeof (indexi) != "undefined")
        {
          // first found duplicate
          duplicates[duplcount] = indexi;
          duplcount++;

          arraystr = j.toString();
          while (arraystr.length < max_polys_length) arraystr = "0" + arraystr;
          indexstr = i.toString();
          while (indexstr.length < max_index_len) indexstr = "0" + indexstr;
          duplicates[duplcount] = arraystr + "." + indexstr;
          duplcount++;
        }
        arraystr = j.toString();
        while (arraystr.length < max_polys_length) arraystr = "0" + arraystr;
        indexstr = i.toString();
        while (indexstr.length < max_index_len) indexstr = "0" + indexstr;

        allpoints[key] = arraystr + "." + indexstr;
      }
    }
    if (!duplcount) return;

    duplicates.length = duplcount;
    duplicates.sort();
    //console.log(JSON.stringify(duplicates));

    var splitted, poly_index = 0,
      nth_dupl = 0;
    var prev_poly_index = -1;
    poly_index = 0;
    for (j = 0; j < duplcount; j++)
    {
      splitted = duplicates[j].split(".");

      poly_index = parseInt(splitted[0], 10);
      if (poly_index != prev_poly_index) nth_dupl = 0;
      else nth_dupl++;
      i = parseInt(splitted[1], 10);
      poly = polys[poly_index];
      len = poly.length;
      if (poly[0].X === poly[len - 1].X &&
        poly[0].Y === poly[len - 1].Y)
      {
        last_i = len - 2;
      }
      else
      {
        last_i = len - 1;
      }
      point = poly[i];

      // Calculate "broken pen tip" effect
      // for current point by finding
      // a coordinate at a distance dist
      // along the edge between current and
      // previous point
      // This is inlined to maximize speed
      currX = point.X;
      currY = point.Y;
      if (i === 0) prev_i = last_i; // last element in array
      else prev_i = i - 1;

      prevX = poly[prev_i].X;
      prevY = poly[prev_i].Y;
      
      x=0;y=0;
      if (!point.Collinear)
      {
        length = sqrt((-currX + prevX) * (-currX + prevX) + (currY - prevY) * (currY - prevY));

//console.log(length);
        x = currX - (dist * (currX - prevX)) / length;
        y = currY - (dist * (currY - prevY)) / length;
      }
        // save the found (calculated) point
        moved_vertices[j] = {
          X: x,
          Y: y,
          Collinear:point.Collinear,
          index: i,
          poly_index: poly_index
        };
      
      // "broken nib effect" for next point also
      if (i == len - 1) next_i = 0;
      else next_i = i + 1;
      nextX = poly[next_i].X;
      nextY = poly[next_i].Y;
      x=0;y=0;
      if (!point.Collinear)
      {
      length = sqrt((-currX + nextX) * (-currX + nextX) + (currY - nextY) * (currY - nextY));
      x = currX - (dist * (currX - nextX)) / length;
      y = currY - (dist * (currY - nextY)) / length;
      }
        // save the found (calculated) point
      extra_vertices[j] = {
        X: x,
        Y: y,
        Collinear:point.Collinear,
        index: i + nth_dupl,
        poly_index: poly_index
      };
      prev_poly_index = poly_index;
        
    }

    moved_vertices.length = extra_vertices.length = duplcount;
    //console.log("MOVED:" + JSON.stringify(moved_vertices));
    //console.log("EXTRA:" + JSON.stringify(extra_vertices));

    // Update moved coordinates
    i = duplcount;
    var point2;
    while (i--)
    {
      point = moved_vertices[i];
      x = point.X;
      y = point.Y;
      // Faster than isNaN: http://jsperf.com/isnan-alternatives
      if (x != x || x == Infinity || x == -Infinity) continue;
      if (y != y || y == Infinity || y == -Infinity) continue;
      point2 = polys[point.poly_index][point.index];
      point2.X = point.X;
      point2.Y = point.Y;
      point2.Collinear = point.Collinear;
    }

    // Add an extra vertex
    // This is needed to remain the angle of the next edge
    for (i = 0; i < duplcount; i++)
    {
      point = extra_vertices[i];
      x = point.X;
      y = point.Y;
      // Faster than isNaN: http://jsperf.com/isnan-alternatives
      if (x != x || x == Infinity || x == -Infinity) continue;
      if (y != y || y == Infinity || y == -Infinity) continue;
      polys[point.poly_index].splice(point.index + 1, 0,
      {
        X: point.X,
        Y: point.Y,
        Collinear: point.Collinear
      });
    }
    
    // Remove collinear points
    // and for some reason coming
    // sequential duplicates
    // TODO: check why seq. duplicates becomes
    j = polys.length;
    var prev_point = null;
    while (j--)
    {
      poly = polys[j];
      ilen = poly.length;
      i = ilen;
      while (i--)
      {
        point = poly[i];
        if(prev_point!=null && point.X == prev_point.X && point.Y == prev_point.Y) poly.splice(i, 1);
        else
        if(point.Collinear) poly.splice(i, 1);
      prev_point = point;
      }
    }
    //console.log(JSON.stringify(polys));
    // because original array is modified, no need to return anything
  }
  
  var BreakPenNipsOfExPolygons = function (exPolygons, dist, scale)
  {
    var i = 0,
      j = 0,
      ilen = exPolygons.length,
      jlen = 0;
    for (; i < ilen; i++)
    {
      //if(i!=4) continue;
      BreakPenNibs(exPolygons[i], dist, scale);
    }
  };