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

Question

我尝试在Three.js中显示由构造路径命令构造的几何图形，如moveto like to 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#裁剪器(JS版本就是从这个版本移植过来的)的作者Angus Johnson认为使用浮动会导致健壮性问题，尽管根据我的测试，原来的C#浮动版本并不存在。浮动版本使用起来更简单，你可以在那里尝试一个小的负偏移量:例如。-0.001或-0.01。

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

最后一个办法就是用坏笔尖的-function。它检测所有伪重复的点，并对它们进行断笔笔尖-effect，因此结果是没有任何重复的。附图显示了此效果的含义，使用较大的nib- effect -value使效果含义更清晰。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);
    }
  };

​