godot/thirdparty/manifold/src/boolean3.cpp

// Copyright 2021 The Manifold Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "./boolean3.h"

#include <limits>

#include "./parallel.h"

usingnamespacemanifold;

namespace {

// These two functions (Interpolate and Intersect) are the only places where
// floating-point operations take place in the whole Boolean function. These
// are carefully designed to minimize rounding error and to eliminate it at edge
// cases to ensure consistency.

vec2 Interpolate(vec3 pL, vec3 pR, double x) { … }

vec4 Intersect(const vec3 &pL, const vec3 &pR, const vec3 &qL, const vec3 &qR) { … }

template <const bool inverted>
struct CopyFaceEdges { … };

SparseIndices Filter11(const Manifold::Impl &inP, const Manifold::Impl &inQ,
                       const SparseIndices &p1q2, const SparseIndices &p2q1) { … }

inline bool Shadows(double p, double q, double dir) { … }

inline std::pair<int, vec2> Shadow01(
    const int p0, const int q1, VecView<const vec3> vertPosP,
    VecView<const vec3> vertPosQ, VecView<const Halfedge> halfedgeQ,
    const double expandP, VecView<const vec3> normalP, const bool reverse) { … }

// https://github.com/scandum/binary_search/blob/master/README.md
// much faster than standard binary search on large arrays
size_t monobound_quaternary_search(VecView<const int64_t> array, int64_t key) { … }

struct Kernel11 { … };

std::tuple<Vec<int>, Vec<vec4>> Shadow11(SparseIndices &p1q1,
                                         const Manifold::Impl &inP,
                                         const Manifold::Impl &inQ,
                                         double expandP) {
  ZoneScoped;
  Vec<int> s11(p1q1.size());
  Vec<vec4> xyzz11(p1q1.size());

  for_each_n(autoPolicy(p1q1.size(), 1e4), countAt(0_uz), p1q1.size(),
             Kernel11({xyzz11, s11, inP.vertPos_, inQ.vertPos_, inP.halfedge_,
                       inQ.halfedge_, expandP, inP.vertNormal_, p1q1}));

  p1q1.KeepFinite(xyzz11, s11);

  return std::make_tuple(s11, xyzz11);
};

struct Kernel02 { … };

std::tuple<Vec<int>, Vec<double>> Shadow02(const Manifold::Impl &inP,
                                           const Manifold::Impl &inQ,
                                           SparseIndices &p0q2, bool forward,
                                           double expandP) {
  ZoneScoped;
  Vec<int> s02(p0q2.size());
  Vec<double> z02(p0q2.size());

  auto vertNormalP = forward ? inP.vertNormal_ : inQ.vertNormal_;
  for_each_n(autoPolicy(p0q2.size(), 1e4), countAt(0_uz), p0q2.size(),
             Kernel02({s02, z02, inP.vertPos_, inQ.halfedge_, inQ.vertPos_,
                       expandP, vertNormalP, p0q2, forward}));

  p0q2.KeepFinite(z02, s02);

  return std::make_tuple(s02, z02);
};

struct Kernel12 { … };

std::tuple<Vec<int>, Vec<vec3>> Intersect12(
    const Manifold::Impl &inP, const Manifold::Impl &inQ, const Vec<int> &s02,
    const SparseIndices &p0q2, const Vec<int> &s11, const SparseIndices &p1q1,
    const Vec<double> &z02, const Vec<vec4> &xyzz11, SparseIndices &p1q2,
    bool forward) {
  ZoneScoped;
  Vec<int> x12(p1q2.size());
  Vec<vec3> v12(p1q2.size());

  for_each_n(
      autoPolicy(p1q2.size(), 1e4), countAt(0_uz), p1q2.size(),
      Kernel12({x12, v12, p0q2.AsVec64(), s02, z02, p1q1.AsVec64(), s11, xyzz11,
                inP.halfedge_, inQ.halfedge_, inP.vertPos_, forward, p1q2}));

  p1q2.KeepFinite(v12, x12);

  return std::make_tuple(x12, v12);
};

Vec<int> Winding03(const Manifold::Impl &inP, Vec<int> &vertices, Vec<int> &s02,
                   bool reverse) {
  ZoneScoped;
  // verts that are not shadowed (not in p0q2) have winding number zero.
  Vec<int> w03(inP.NumVert(), 0);
  if (vertices.size() <= 1e5) {
    for_each_n(ExecutionPolicy::Seq, countAt(0), s02.size(),
               [&w03, &vertices, &s02, reverse](const int i) {
                 w03[vertices[i]] += s02[i] * (reverse ? -1 : 1);
               });
  } else {
    for_each_n(ExecutionPolicy::Par, countAt(0), s02.size(),
               [&w03, &vertices, &s02, reverse](const int i) {
                 AtomicAdd(w03[vertices[i]], s02[i] * (reverse ? -1 : 1));
               });
  }
  return w03;
};
}  // namespace

namespace manifold {
Boolean3::Boolean3(const Manifold::Impl &inP, const Manifold::Impl &inQ,
                   OpType op)
    : … { … }
}  // namespace manifold