godot/thirdparty/manifold/src/collider.h

// 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.

#pragma once
#include "./parallel.h"
#include "./sparse.h"
#include "./utils.h"
#include "./vec.h"
#include "manifold/common.h"

#ifdef _MSC_VER
#include <intrin.h>
#endif

#if (MANIFOLD_PAR == 1)
#include <tbb/combinable.h>
#endif

namespace manifold {

namespace collider_internal {
// Adjustable parameters
constexpr int kInitialLength = …;
constexpr int kLengthMultiple = …;
constexpr int kSequentialThreshold = …;
// Fundamental constants
constexpr int kRoot = …;

#ifdef _MSC_VER

#ifndef _WINDEF_
typedef unsigned long DWORD;
#endif

uint32_t inline ctz(uint32_t value) {
  DWORD trailing_zero = 0;

  if (_BitScanForward(&trailing_zero, value)) {
    return trailing_zero;
  } else {
    // This is undefined, I better choose 32 than 0
    return 32;
  }
}

uint32_t inline clz(uint32_t value) {
  DWORD leading_zero = 0;

  if (_BitScanReverse(&leading_zero, value)) {
    return 31 - leading_zero;
  } else {
    // Same remarks as above
    return 32;
  }
}
#endif

constexpr inline bool IsLeaf(int node) { … }
constexpr inline bool IsInternal(int node) { … }
constexpr inline int Node2Internal(int node) { … }
constexpr inline int Internal2Node(int internal) { … }
constexpr inline int Node2Leaf(int node) { … }
constexpr inline int Leaf2Node(int leaf) { … }

struct CreateRadixTree { … };

template <typename T, const bool selfCollision, typename Recorder>
struct FindCollision { … };

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

#if (MANIFOLD_PAR == 1)
template <const bool inverted>
struct ParCollisionRecorder {
  tbb::combinable<SparseIndices>& store;
  inline void record(int queryIdx, int leafIdx, SparseIndices& ind) const {
    // Add may invoke something in parallel, and it may return in
    // another thread, making thread local unsafe
    // we need to explicitly forbid parallelization by passing a flag
    if (inverted)
      ind.Add(leafIdx, queryIdx, true);
    else
      ind.Add(queryIdx, leafIdx, true);
  }
  SparseIndices& local() { return store.local(); }
};
#endif

struct BuildInternalBoxes { … };

struct TransformBox { … };

constexpr inline uint32_t SpreadBits3(uint32_t v) { … }
}  // namespace collider_internal

/** @ingroup Private */
class Collider { … };

}  // namespace manifold