Select Git revision
delaunay3d.cpp
Forked from
gmsh / gmsh
Source project has a limited visibility.
delaunay3d.cpp 39.05 KiB
// Gmsh - Copyright (C) 1997-2017 C. Geuzaine, J.-F. Remacle
//
// See the LICENSE.txt file for license information. Please report all
// bugs and problems to the public mailing list <gmsh@onelab.info>.
#if defined(_OPENMP)
#include <omp.h>
#endif
#include <stdio.h>
#include <stdlib.h>
#include <list>
#include <set>
#include <stack>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include "SBoundingBox3d.h"
#include "OS.h"
#include "delaunay3d_private.h"
#include "delaunay3d.h"
#include "MVertex.h"
#include "MEdge.h"
#include "MTetrahedron.h"
#include "meshGRegionLocalMeshMod.h"
#if defined(_HAVE_NUMA)
#include <numa.h>
#endif
//int Tet::in_sphere_counter = 0;
struct HilbertSortB
{
// The code for generating table transgc from:
// http://graphics.stanford.edu/~seander/bithacks.html.
int transgc[8][3][8];
int tsb1mod3[8];
int maxDepth;
int Limit;
SBoundingBox3d bbox ;
void ComputeGrayCode(int n);
int Split(Vert** vertices,
int arraysize,int GrayCode0,int GrayCode1,
double BoundingBoxXmin, double BoundingBoxXmax,
double BoundingBoxYmin, double BoundingBoxYmax,
double BoundingBoxZmin, double BoundingBoxZmax);
void Sort(Vert** vertices, int arraysize, int e, int d,
double BoundingBoxXmin, double BoundingBoxXmax,
double BoundingBoxYmin, double BoundingBoxYmax,
double BoundingBoxZmin, double BoundingBoxZmax, int depth);
HilbertSortB (int m = 0, int l=2) : maxDepth(m), Limit(l)
{
ComputeGrayCode(3);
}
void MultiscaleSortHilbert(Vert** vertices, int arraysize,
int threshold, double ratio, int *depth,
std::vector<int> &indices)
{
int middle = 0;
if (arraysize >= threshold) {
(*depth)++;
middle = (int)(arraysize * ratio);
MultiscaleSortHilbert(vertices, middle, threshold, ratio, depth, indices);
}
indices.push_back(middle);
// printf("chunk starts at %d and size %d\n",middle, arraysize - middle);
Sort(&(vertices[middle]),arraysize - middle,0,0,
bbox.min().x(),bbox.max().x(),