Collaboration diagram for HashTableEdges:

Public Member Functions
	HashTableEdges (size_t number_of_faces)

	~HashTableEdges ()

void	insert_edge_exact (stl_file *stl, const HashEdge &edge)

void	insert_edge_nearby (stl_file *stl, const HashEdge &edge)

Public Attributes
std::vector< HashEdge * >	heads

HashEdge *	tail

int	M

boost::object_pool< HashEdge >	pool

size_t	malloced = 0

size_t	freed = 0

size_t	collisions = 0

Private Member Functions
template<typename MatchNeighbors >
void	insert_edge (stl_file *stl, const HashEdge &edge, MatchNeighbors match_neighbors)

Static Private Member Functions
static size_t	hash_size_from_nr_faces (const size_t nr_faces)

static bool	edges_equal (const HashEdge &edge_a, const HashEdge &edge_b)

static void	record_neighbors (stl_file *stl, const HashEdge &edge_a, const HashEdge &edge_b)

static void	match_neighbors_nearby (stl_file *stl, const HashEdge &edge_a, const HashEdge &edge_b)

Detailed Description

Constructor & Destructor Documentation

◆ HashTableEdges()

HashTableEdges::HashTableEdges ( size_t number_of_faces )

inline

                                         {
    this->M = (int)hash_size_from_nr_faces(number_of_faces);
    this->heads.assign(this->M, nullptr);
    this->tail = pool.construct();
    this->tail->next = this->tail;
    for (int i = 0; i < this->M; ++ i)
      this->heads[i] = this->tail;
  }

References hash_size_from_nr_faces(), heads, M, HashEdge::next, pool, and tail.

Here is the call graph for this function:

◆ ~HashTableEdges()

HashTableEdges::~HashTableEdges ( )

inline

                    {
#ifndef NDEBUG
    for (int i = 0; i < this->M; ++ i)
        for (HashEdge *temp = this->heads[i]; temp != this->tail; temp = temp->next)
            ++ this->freed;
    this->tail = nullptr;
#endif /* NDEBUG */
  }

References freed, heads, M, HashEdge::next, and tail.

Member Function Documentation

◆ edges_equal()

static bool HashTableEdges::edges_equal	(	const HashEdge &	edge_a,
		const HashEdge &	edge_b
	)

inlinestaticprivate

  {
      return edge_a.facet_number != edge_b.facet_number && edge_a == edge_b;
  }

References HashEdge::facet_number.

Referenced by insert_edge().

Here is the caller graph for this function:

◆ hash_size_from_nr_faces()

static size_t HashTableEdges::hash_size_from_nr_faces ( const size_t nr_faces )

inlinestaticprivate

  {
    // Good primes for addressing a cca. 30 bit space.
    // https://planetmath.org/goodhashtableprimes
    static std::vector<uint32_t> primes{ 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741 };
    // Find a prime number for 50% filling of the shared triangle edges in the mesh.
    auto it = std::upper_bound(primes.begin(), primes.end(), nr_faces * 3 * 2 - 1);
    return (it == primes.end()) ? primes.back() : *it;
  }

Referenced by HashTableEdges().

Here is the caller graph for this function:

◆ insert_edge()

template<typename MatchNeighbors >

void HashTableEdges::insert_edge	(	stl_file *	stl,
		const HashEdge &	edge,
		MatchNeighbors	match_neighbors
	)

inlineprivate

  {
    int       chain_number = edge.hash(this->M);
    HashEdge *link         = this->heads[chain_number];
    if (link == this->tail) {
      // This list doesn't have any edges currently in it.  Add this one.
      HashEdge *new_edge = pool.construct(edge);
#ifndef NDEBUG
      ++ this->malloced;
#endif /* NDEBUG */
      new_edge->next = this->tail;
      this->heads[chain_number] = new_edge;
    } else if (edges_equal(edge, *link)) {
      // This is a match.  Record result in neighbors list.
      match_neighbors(edge, *link);
      // Delete the matched edge from the list.
      this->heads[chain_number] = link->next;
      // pool.destroy(link);
#ifndef NDEBUG
      ++ this->freed;
#endif /* NDEBUG */
    } else {
      // Continue through the rest of the list.
      for (;;) {
        if (link->next == this->tail) {
          // This is the last item in the list. Insert a new edge.
          HashEdge *new_edge = pool.construct();
#ifndef NDEBUG
          ++ this->malloced;
#endif /* NDEBUG */
          *new_edge = edge;
          new_edge->next = this->tail;
          link->next = new_edge;
#ifndef NDEBUG
          ++ this->collisions;
#endif /* NDEBUG */
          break;
        }
        if (edges_equal(edge, *link->next)) {
          // This is a match.  Record result in neighbors list.
          match_neighbors(edge, *link->next);
          // Delete the matched edge from the list.
          HashEdge *temp = link->next;
          link->next = link->next->next;
          // pool.destroy(temp);
#ifndef NDEBUG
          ++ this->freed;
#endif /* NDEBUG */
          break;
        }
        // This is not a match.  Go to the next link.
        link = link->next;
#ifndef NDEBUG
        ++ this->collisions;
#endif /* NDEBUG */
      }
    }
  }

References collisions, edges_equal(), freed, HashEdge::hash(), malloced, HashEdge::next, pool, and tail.

Referenced by insert_edge_exact(), and insert_edge_nearby().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert_edge_exact()

void HashTableEdges::insert_edge_exact	(	stl_file *	stl,
		const HashEdge &	edge
	)

inline

  {
    this->insert_edge(stl, edge, [stl](const HashEdge& edge1, const HashEdge& edge2) { record_neighbors(stl, edge1, edge2); });
  }

References insert_edge(), and record_neighbors().

Referenced by stl_check_facets_exact(), and stl_fill_holes().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert_edge_nearby()

void HashTableEdges::insert_edge_nearby	(	stl_file *	stl,
		const HashEdge &	edge
	)

inline

  {
    this->insert_edge(stl, edge, [stl](const HashEdge& edge1, const HashEdge& edge2) { match_neighbors_nearby(stl, edge1, edge2); });
  }

References insert_edge(), and match_neighbors_nearby().

Referenced by stl_check_facets_nearby().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ match_neighbors_nearby()

static void HashTableEdges::match_neighbors_nearby	(	stl_file *	stl,
		const HashEdge &	edge_a,
		const HashEdge &	edge_b
	)

inlinestaticprivate

  {
    record_neighbors(stl, edge_a, edge_b);
 
    // Which vertices to change
    int facet1 = -1;
    int facet2 = -1;
    int vertex1, vertex2;
    stl_vertex new_vertex1, new_vertex2;
    {
      int v1a; // pair 1, facet a
      int v1b; // pair 1, facet b
      int v2a; // pair 2, facet a
      int v2b; // pair 2, facet b
      // Find first pair.
      if (edge_a.which_edge < 3) {
        v1a = edge_a.which_edge;
        v2a = (edge_a.which_edge + 1) % 3;
      } else {
        v2a = edge_a.which_edge % 3;
        v1a = (edge_a.which_edge + 1) % 3;
      }
      if (edge_b.which_edge < 3) {
        v1b = edge_b.which_edge;
        v2b = (edge_b.which_edge + 1) % 3;
      } else {
        v2b = edge_b.which_edge % 3;
        v1b = (edge_b.which_edge + 1) % 3;
      }
 
      // Of the first pair, which vertex, if any, should be changed
      if (stl->facet_start[edge_a.facet_number].vertex[v1a] != stl->facet_start[edge_b.facet_number].vertex[v1b]) {
        // These facets are different.
        if (   (stl->neighbors_start[edge_a.facet_number].neighbor[v1a] == -1)
              && (stl->neighbors_start[edge_a.facet_number].neighbor[(v1a + 2) % 3] == -1)) {
            // This vertex has no neighbors.  This is a good one to change.
            facet1 = edge_a.facet_number;
            vertex1 = v1a;
            new_vertex1 = stl->facet_start[edge_b.facet_number].vertex[v1b];
        } else {
            facet1 = edge_b.facet_number;
            vertex1 = v1b;
            new_vertex1 = stl->facet_start[edge_a.facet_number].vertex[v1a];
        }
      }
 
      // Of the second pair, which vertex, if any, should be changed.
      if (stl->facet_start[edge_a.facet_number].vertex[v2a] == stl->facet_start[edge_b.facet_number].vertex[v2b]) {
        // These facets are different.
        if (  (stl->neighbors_start[edge_a.facet_number].neighbor[v2a] == -1)
             && (stl->neighbors_start[edge_a.facet_number].neighbor[(v2a + 2) % 3] == -1)) {
            // This vertex has no neighbors.  This is a good one to change.
            facet2 = edge_a.facet_number;
            vertex2 = v2a;
            new_vertex2 = stl->facet_start[edge_b.facet_number].vertex[v2b];
        } else {
            facet2 = edge_b.facet_number;
            vertex2 = v2b;
            new_vertex2 = stl->facet_start[edge_a.facet_number].vertex[v2a];
        }
      }
    }
 
    auto change_vertices = [stl](int facet_num, int vnot, stl_vertex new_vertex)
    {
      int first_facet = facet_num;
      bool direction = false;
 
      for (;;) {
        int pivot_vertex;
        int next_edge;
        if (vnot > 2) {
          if (direction) {
            pivot_vertex = (vnot + 1) % 3;
            next_edge = vnot % 3;
          }
          else {
            pivot_vertex = (vnot + 2) % 3;
            next_edge = pivot_vertex;
          }
          direction = !direction;
        }
        else {
          if (direction) {
            pivot_vertex = (vnot + 2) % 3;
            next_edge = pivot_vertex;
          }
          else {
            pivot_vertex = (vnot + 1) % 3;
            next_edge = vnot;
          }
        }
  #if 0
        if (stl->facet_start[facet_num].vertex[pivot_vertex](0) == new_vertex(0) &&
          stl->facet_start[facet_num].vertex[pivot_vertex](1) == new_vertex(1) &&
          stl->facet_start[facet_num].vertex[pivot_vertex](2) == new_vertex(2))
          printf("Changing vertex %f,%f,%f: Same !!!\r\n", new_vertex(0), new_vertex(1), new_vertex(2));
        else {
          if (stl->facet_start[facet_num].vertex[pivot_vertex](0) != new_vertex(0))
            printf("Changing coordinate x, vertex %e (0x%08x) to %e(0x%08x)\r\n",
              stl->facet_start[facet_num].vertex[pivot_vertex](0),
              *reinterpret_cast<const int*>(&stl->facet_start[facet_num].vertex[pivot_vertex](0)),
              new_vertex(0),
              *reinterpret_cast<const int*>(&new_vertex(0)));
          if (stl->facet_start[facet_num].vertex[pivot_vertex](1) != new_vertex(1))
            printf("Changing coordinate x, vertex %e (0x%08x) to %e(0x%08x)\r\n",
              stl->facet_start[facet_num].vertex[pivot_vertex](1),
              *reinterpret_cast<const int*>(&stl->facet_start[facet_num].vertex[pivot_vertex](1)),
              new_vertex(1),
              *reinterpret_cast<const int*>(&new_vertex(1)));
          if (stl->facet_start[facet_num].vertex[pivot_vertex](2) != new_vertex(2))
            printf("Changing coordinate x, vertex %e (0x%08x) to %e(0x%08x)\r\n",
              stl->facet_start[facet_num].vertex[pivot_vertex](2),
              *reinterpret_cast<const int*>(&stl->facet_start[facet_num].vertex[pivot_vertex](2)),
              new_vertex(2),
              *reinterpret_cast<const int*>(&new_vertex(2)));
        }
  #endif
        stl->facet_start[facet_num].vertex[pivot_vertex] = new_vertex;
        vnot = stl->neighbors_start[facet_num].which_vertex_not[next_edge];
        facet_num = stl->neighbors_start[facet_num].neighbor[next_edge];
        if (facet_num == -1)
          break;
 
        if (facet_num == first_facet) {
          // back to the beginning
          BOOST_LOG_TRIVIAL(info) << "Back to the first facet changing vertices: probably a mobius part. Try using a smaller tolerance or don't do a nearby check.";
          return;
        }
      }
    };
 
    if (facet1 != -1) {
      int vnot1 = (facet1 == edge_a.facet_number) ? 
          (edge_a.which_edge + 2) % 3 :
        (edge_b.which_edge + 2) % 3;
      if (((vnot1 + 2) % 3) == vertex1)
          vnot1 += 3;
      change_vertices(facet1, vnot1, new_vertex1);
    }
    if (facet2 != -1) {
      int vnot2 = (facet2 == edge_a.facet_number) ?
          (edge_a.which_edge + 2) % 3 :
        (edge_b.which_edge + 2) % 3;
      if (((vnot2 + 2) % 3) == vertex2)
          vnot2 += 3;
      change_vertices(facet2, vnot2, new_vertex2);
    }
    stl->stats.edges_fixed += 2;
  }

References stl_stats::edges_fixed, HashEdge::facet_number, stl_file::facet_start, stl_file::neighbors_start, record_neighbors(), stl_file::stats, and HashEdge::which_edge.

Referenced by insert_edge_nearby().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ record_neighbors()

static void HashTableEdges::record_neighbors	(	stl_file *	stl,
		const HashEdge &	edge_a,
		const HashEdge &	edge_b
	)

inlinestaticprivate

  {
    // Facet a's neighbor is facet b
    stl->neighbors_start[edge_a.facet_number].neighbor[edge_a.which_edge % 3] = edge_b.facet_number;  /* sets the .neighbor part */
    stl->neighbors_start[edge_a.facet_number].which_vertex_not[edge_a.which_edge % 3] = (edge_b.which_edge + 2) % 3; /* sets the .which_vertex_not part */
 
    // Facet b's neighbor is facet a
    stl->neighbors_start[edge_b.facet_number].neighbor[edge_b.which_edge % 3] = edge_a.facet_number;  /* sets the .neighbor part */
    stl->neighbors_start[edge_b.facet_number].which_vertex_not[edge_b.which_edge % 3] = (edge_a.which_edge + 2) % 3; /* sets the .which_vertex_not part */
 
    if ((edge_a.which_edge < 3 && edge_b.which_edge < 3) || (edge_a.which_edge > 2 && edge_b.which_edge > 2)) {
      // These facets are oriented in opposite directions, their normals are probably messed up.
      stl->neighbors_start[edge_a.facet_number].which_vertex_not[edge_a.which_edge % 3] += 3;
      stl->neighbors_start[edge_b.facet_number].which_vertex_not[edge_b.which_edge % 3] += 3;
    }
 
    // Count successful connects:
    // Total connects:
    stl->stats.connected_edges += 2;
    // Count individual connects:
    switch (stl->neighbors_start[edge_a.facet_number].num_neighbors()) {
    case 1: ++ stl->stats.connected_facets_1_edge; break;
    case 2: ++ stl->stats.connected_facets_2_edge; break;
    case 3: ++ stl->stats.connected_facets_3_edge; break;
    default: assert(false);
    }
    switch (stl->neighbors_start[edge_b.facet_number].num_neighbors()) {
    case 1: ++ stl->stats.connected_facets_1_edge; break;
    case 2: ++ stl->stats.connected_facets_2_edge; break;
    case 3: ++ stl->stats.connected_facets_3_edge; break;
    default: assert(false);
    }
  }