Как упростить фигуры для триангуляции с помощью three.js и jsclipper

Question

Я пытаюсь отобразить геометрию, которая построена с помощью команд constructpath, таких как moveto lineto beziercurveto в Three.js.Поэтому я создаю THREE.ShapePath ();и выполните команду toShapes (isClockwise).После этого я использую THREE.ExtrudeBufferGeometry для создания 3D-фигуры.

К сожалению, формы иногда очень сложные и не создаются правильно, что означает, что они искажены.

Использование libtess в качестве библиотеки триангуляции решает некоторыепроблемы.Но у меня все еще искаженная геометрия.

Теперь я хочу использовать jsclipper для упрощения форм до триангуляции.

Я изменил three.js таким образом:

в методеaddShape в ExtrudeBufferGeometry Я добавил:

$.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'];
          });
        }
      }

Теперь я вижу, что вершины «уменьшены».

Но varface = ShapeUtils.triangulateShape (вершины, отверстия);больше не генерирует лица для некоторых примеров.

Можно ли помочь как правильно упростить фигуры?

Answer 1

Немного сложно понять, в чем проблема на самом деле. Clipper (также при использовании SimplifyPolygons или SimplifyPolygon) может создавать только слабо простые многоугольники, что означает, что могут быть псевдопублицированные точки: хотя последовательные координаты гарантируются не идентичными, некоторые из следующих точек могут иметь одну и ту же координату. Также координата может быть на линии между двумя точками.

После упрощения (или любой другой логической операции) вы можете выполнить шаг очистки, используя смещение с небольшим отрицательным значением: https://sourceforge.net/p/jsclipper/wiki/documentation/#clipperlibclipperoffsetexecute.

Это, возможно, удаляет все псевдодублирующиеся точки.

Я также сделал поплавковую версию Clipper (http://jsclipper.sourceforge.net/6.4.2.2_fpoint/).. Она тщательно протестирована, но поскольку Ангус Джонсон, автор оригинальной C # Clipper (из которой перенесена JS-версия), подумал, что использование поплавков вызывает проблемы с устойчивостью, хотя, согласно моим тестам, их нет, исходная версия поплавка C # не существует. Плавающую версию проще использовать, и вы можете попробовать небольшое отрицательное смещение: например, -0.001 или -0.01.

Вы также можете попробовать PolyTree или ExPolygons (https://sourceforge.net/p/jsclipper/wiki/ExPolygons%20and%20PolyTree%206/). ExPolygons можно использовать для получения отверстий и контуров, а PolyTree можно использовать для получения полного родителя-дочернего отношения отверстий и контуров.

Последнее средство - функция сломанной ручки. Он обнаруживает все псевдодублирующиеся точки и создает для них эффект разбитого пера, чтобы в результате не было дубликатов. Прикрепленные изображения показывают, что означает этот эффект, используя большое значение nib-effect, чтобы сделать эффект более понятным. Сбой триангуляции многоугольника Three.js в псевдопублицированных точках . Есть обсуждение 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);
    }
  };