decompose method

List<Float32List> decompose(Float32List verticesArray, Int16List triangles)

Implementation

List<Float32List> decompose(Float32List verticesArray, Int16List triangles) {
  final Float32List vertices = verticesArray;
  final List<Float32List> convexPolygons = this.convexPolygons;
  polygonPool.freeAll(convexPolygons);
  convexPolygons.length = 0;

  final List<Int16List> convexPolygonsIndices = this.convexPolygonsIndices;
  polygonIndicesPool.freeAll(convexPolygonsIndices);
  convexPolygonsIndices.length = 0;

  List<int> polygonIndices = polygonIndicesPool.obtain()..length = 0;

  List<double> polygon = polygonPool.obtain()..length = 0;

  // Merge subsequent triangles if they form a triangle fan.
  int fanBaseIndex = -1, lastWinding = 0;
  final int n = triangles.length;
  for (int i = 0; i < n; i += 3) {
    final int t1 = triangles[i] << 1,
        t2 = triangles[i + 1] << 1,
        t3 = triangles[i + 2] << 1;
    final double x1 = vertices[t1], y1 = vertices[t1 + 1];
    final double x2 = vertices[t2], y2 = vertices[t2 + 1];
    final double x3 = vertices[t3], y3 = vertices[t3 + 1];

    // If the base of the last triangle is the same as this triangle, check if they form a convex polygon (triangle fan).
    bool merged = false;
    if (fanBaseIndex == t1) {
      final int o = polygon.length - 4;
      final int winding1 = Triangulator.winding(
          polygon[o], polygon[o + 1], polygon[o + 2], polygon[o + 3], x3, y3);
      final int winding2 = Triangulator.winding(
          x3, y3, polygon[0], polygon[1], polygon[2], polygon[3]);
      if (winding1 == lastWinding && winding2 == lastWinding) {
        polygon
          ..add(x3)
          ..add(y3);
        polygonIndices.add(t3);
        merged = true;
      }
    }

    // Otherwise make this triangle the new base.
    if (!merged) {
      if (polygon.isEmpty) {
        convexPolygons.add(Float32List.fromList(polygon));
        convexPolygonsIndices.add(Int16List.fromList(polygonIndices));
      } else {
        polygonPool.free(polygon);
        polygonIndicesPool.free(polygonIndices);
      }
      polygon = polygonPool.obtain()
        ..length = 0
        ..add(x1)
        ..add(y1)
        ..add(x2)
        ..add(y2)
        ..add(x3)
        ..add(y3);
      polygonIndices = polygonIndicesPool.obtain()
        ..length = 0
        ..add(t1)
        ..add(t2)
        ..add(t3);
      lastWinding = Triangulator.winding(x1, y1, x2, y2, x3, y3);
      fanBaseIndex = t1;
    }
  }

  if (polygon.isNotEmpty) {
    convexPolygons.add(Float32List.fromList(polygon));
    convexPolygonsIndices.add(Int16List.fromList(polygonIndices));
  }

  final int nn = convexPolygons.length;
  // Go through the list of polygons and try to merge the remaining triangles with the found triangle fans.
  for (int i = 0; i < nn; i++) {
    polygonIndices = convexPolygonsIndices[i];
    if (polygonIndices.isEmpty) continue;
    final int firstIndex = polygonIndices[0];
    final int lastIndex = polygonIndices[polygonIndices.length - 1];

    polygon = convexPolygons[i];
    final int o = polygon.length - 4;
    double prevPrevX = polygon[o], prevPrevY = polygon[o + 1];
    double prevX = polygon[o + 2], prevY = polygon[o + 3];
    final double firstX = polygon[0], firstY = polygon[1];
    final double secondX = polygon[2], secondY = polygon[3];
    final int winding = Triangulator.winding(
        prevPrevX, prevPrevY, prevX, prevY, firstX, firstY);

    for (int ii = 0; ii < n; ii++) {
      if (ii == i) continue;
      final Int16List otherIndices = convexPolygonsIndices[ii];
      if (otherIndices.length != 3) continue;
      final int otherFirstIndex = otherIndices[0];
      final int otherSecondIndex = otherIndices[1];
      final int otherLastIndex = otherIndices[2];

      final Float32List otherPoly = convexPolygons[ii];
      final double x3 = otherPoly[otherPoly.length - 2],
          y3 = otherPoly[otherPoly.length - 1];

      if (otherFirstIndex != firstIndex || otherSecondIndex != lastIndex) {
        continue;
      }
      final int winding1 =
          Triangulator.winding(prevPrevX, prevPrevY, prevX, prevY, x3, y3);
      final int winding2 =
          Triangulator.winding(x3, y3, firstX, firstY, secondX, secondY);
      if (winding1 == winding && winding2 == winding) {
        otherPoly.length = 0;
        otherIndices.length = 0;
        polygon
          ..add(x3)
          ..add(y3);
        polygonIndices.add(otherLastIndex);
        prevPrevX = prevX;
        prevPrevY = prevY;
        prevX = x3;
        prevY = y3;
        ii = 0;
      }
    }
  }

  // Remove empty polygons that resulted from the merge step above.
  for (int i = convexPolygons.length - 1; i >= 0; i--) {
    polygon = convexPolygons[i];
    if (polygon.isEmpty) {
      convexPolygons.removeAt(i);
      polygonPool.free(polygon);
      polygonIndices = convexPolygonsIndices[i];
      convexPolygonsIndices.removeAt(i);
      polygonIndicesPool.free(polygonIndices);
    }
  }

  return convexPolygons;
}