connect.cpp File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <boost/predef/other/endian.h>
#include <boost/log/trivial.hpp>
#include <boost/pool/object_pool.hpp>
#include "stl.h"

Include dependency graph for connect.cpp:

Go to the source code of this file.

Classes
struct	HashEdge
struct	HashTableEdges

Macros
#define	BOOST_POOL_NO_MT

Functions
void	stl_check_facets_exact (stl_file *stl)
void	stl_check_facets_nearby (stl_file *stl, float tolerance)
void	stl_remove_unconnected_facets (stl_file *stl)
void	stl_fill_holes (stl_file *stl)
void	stl_add_facet (stl_file *stl, const stl_facet *new_facet)

Macro Definition Documentation

BOOST_POOL_NO_MT

#define BOOST_POOL_NO_MT

Function Documentation

stl_add_facet()

void stl_add_facet	(	stl_file *	stl,
		const stl_facet *	new_facet
	)

{
  assert(stl->facet_start.size() == stl->stats.number_of_facets);
  assert(stl->neighbors_start.size() == stl->stats.number_of_facets);
  stl->facet_start.emplace_back(*new_facet);
    // note that the normal vector is not set here, just initialized to 0.
    stl->facet_start[stl->stats.number_of_facets].normal = stl_normal::Zero();
    stl->neighbors_start.emplace_back();
  ++ stl->stats.facets_added;
  ++ stl->stats.number_of_facets;
}

References stl_file::facet_start, stl_stats::facets_added, stl_file::neighbors_start, stl_stats::number_of_facets, and stl_file::stats.

Referenced by stl_fill_holes().

Here is the caller graph for this function:

stl_check_facets_exact()

void stl_check_facets_exact

(

stl_file *

stl

)

{
  assert(stl->facet_start.size() == stl->neighbors_start.size());
 
    stl->stats.connected_edges         = 0;
    stl->stats.connected_facets_1_edge = 0;
    stl->stats.connected_facets_2_edge = 0;
    stl->stats.connected_facets_3_edge = 0;
 
    // If any two of the three vertices are found to be exactally the same, call them degenerate and remove the facet.
    // Do it before the next step, as the next step stores references to the face indices in the hash tables and removing a facet
    // will break the references.
    for (uint32_t i = 0; i < stl->stats.number_of_facets;) {
    stl_facet &facet = stl->facet_start[i];
      if (facet.vertex[0] == facet.vertex[1] || facet.vertex[1] == facet.vertex[2] || facet.vertex[0] == facet.vertex[2]) {
        // Remove the degenerate facet.
        facet = stl->facet_start[-- stl->stats.number_of_facets];
      stl->facet_start.pop_back();
      stl->neighbors_start.pop_back();
        stl->stats.facets_removed += 1;
        stl->stats.degenerate_facets += 1;
      } else
        ++ i;
    }
 
    // Initialize hash table.
    HashTableEdges hash_table(stl->stats.number_of_facets);
  for (auto &neighbor : stl->neighbors_start)
    neighbor.reset();
 
    // Connect neighbor edges.
  for (uint32_t i = 0; i < stl->stats.number_of_facets; ++ i) {
    const stl_facet &facet = stl->facet_start[i];
    for (int j = 0; j < 3; ++ j) {
      HashEdge edge;
      edge.facet_number = i;
      edge.which_edge = j;
      edge.load_exact(stl, &facet.vertex[j], &facet.vertex[(j + 1) % 3]);
      hash_table.insert_edge_exact(stl, edge);
    }
  }
 
#if 0
  printf("Number of faces: %d, number of manifold edges: %d, number of connected edges: %d, number of unconnected edges: %d\r\n", 
      stl->stats.number_of_facets, stl->stats.number_of_facets * 3, 
      stl->stats.connected_edges, stl->stats.number_of_facets * 3 - stl->stats.connected_edges);
#endif
}

References stl_stats::connected_edges, stl_stats::connected_facets_1_edge, stl_stats::connected_facets_2_edge, stl_stats::connected_facets_3_edge, stl_stats::degenerate_facets, HashEdge::facet_number, stl_file::facet_start, stl_stats::facets_removed, HashTableEdges::insert_edge_exact(), HashEdge::load_exact(), stl_file::neighbors_start, stl_stats::number_of_facets, stl_file::stats, stl_facet::vertex, and HashEdge::which_edge.

Referenced by stl_repair(), and Slic3r::trianglemesh_repair_on_import().

Here is the call graph for this function:

Here is the caller graph for this function:

stl_check_facets_nearby()

void stl_check_facets_nearby	(	stl_file *	stl,
		float	tolerance
	)

{
  assert(stl->stats.connected_facets_3_edge <= stl->stats.connected_facets_2_edge);
  assert(stl->stats.connected_facets_2_edge <= stl->stats.connected_facets_1_edge);
  assert(stl->stats.connected_facets_1_edge <= stl->stats.number_of_facets);
 
    if (stl->stats.connected_facets_3_edge == stl->stats.number_of_facets)
      // No need to check any further.  All facets are connected.
      return;
 
    HashTableEdges hash_table(stl->stats.number_of_facets);
    for (uint32_t i = 0; i < stl->stats.number_of_facets; ++ i) {
      //FIXME is the copy necessary?
      stl_facet facet = stl->facet_start[i];
      for (int j = 0; j < 3; j++) {
          if (stl->neighbors_start[i].neighbor[j] == -1) {
            HashEdge edge;
            edge.facet_number = i;
            edge.which_edge = j;
            if (edge.load_nearby(stl, facet.vertex[j], facet.vertex[(j + 1) % 3], tolerance))
                // Only insert edges that have different keys.
                hash_table.insert_edge_nearby(stl, edge);
          }
      }
    }
}

References stl_stats::connected_facets_1_edge, stl_stats::connected_facets_2_edge, stl_stats::connected_facets_3_edge, HashEdge::facet_number, stl_file::facet_start, HashTableEdges::insert_edge_nearby(), HashEdge::load_nearby(), stl_file::neighbors_start, stl_stats::number_of_facets, stl_file::stats, stl_facet::vertex, and HashEdge::which_edge.

Referenced by stl_repair(), and Slic3r::trianglemesh_repair_on_import().

Here is the call graph for this function:

Here is the caller graph for this function:

stl_fill_holes()

void stl_fill_holes

(

stl_file *

stl

)

{
  // Insert all unconnected edges into hash list.
  HashTableEdges hash_table(stl->stats.number_of_facets);
  for (uint32_t i = 0; i < stl->stats.number_of_facets; ++ i) {
      stl_facet facet = stl->facet_start[i];
    for (int j = 0; j < 3; ++ j) {
        if(stl->neighbors_start[i].neighbor[j] != -1)
          continue;
      HashEdge edge;
        edge.facet_number = i;
        edge.which_edge = j;
        edge.load_exact(stl, &facet.vertex[j], &facet.vertex[(j + 1) % 3]);
        hash_table.insert_edge_exact(stl, edge);
    }
  }
 
  for (uint32_t i = 0; i < stl->stats.number_of_facets; ++ i) {
    stl_facet facet = stl->facet_start[i];
    int neighbors_initial[3] = { stl->neighbors_start[i].neighbor[0], stl->neighbors_start[i].neighbor[1], stl->neighbors_start[i].neighbor[2] };
    int first_facet = i;
    for (int j = 0; j < 3; ++ j) {
        if (stl->neighbors_start[i].neighbor[j] != -1)
          continue;
 
        stl_facet new_facet;
        new_facet.vertex[0] = facet.vertex[j];
        new_facet.vertex[1] = facet.vertex[(j + 1) % 3];
        bool direction = neighbors_initial[(j + 2) % 3] == -1;
        int facet_num = i;
        int vnot = (j + 2) % 3;
 
        for (;;) {
        int pivot_vertex = 0;
        int next_edge = 0;
          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 == 0) {
                pivot_vertex = (vnot + 1) % 3;
                next_edge = vnot;
              } else {
                pivot_vertex = (vnot + 2) % 3;
                next_edge = pivot_vertex;
              }
          }
 
          int next_facet = stl->neighbors_start[facet_num].neighbor[next_edge];
          if (next_facet == -1) {
              new_facet.vertex[2] = stl->facet_start[facet_num].vertex[vnot % 3];
            stl_add_facet(stl, &new_facet);
              for (int k = 0; k < 3; ++ k) {
                HashEdge edge;
                edge.facet_number = stl->stats.number_of_facets - 1;
                edge.which_edge = k;
                edge.load_exact(stl, &new_facet.vertex[k], &new_facet.vertex[(k + 1) % 3]);
                hash_table.insert_edge_exact(stl, edge);
              }
              break;
          }
 
            vnot = stl->neighbors_start[facet_num].which_vertex_not[next_edge];
            facet_num = next_facet;
 
          if (facet_num == first_facet) {
              // back to the beginning
            BOOST_LOG_TRIVIAL(info) << "Back to the first facet filling holes: probably a mobius part. Try using a smaller tolerance or don't do a nearby check.";
              return;
          }
        }
    }
  }
}

References HashEdge::facet_number, stl_file::facet_start, HashTableEdges::insert_edge_exact(), HashEdge::load_exact(), stl_file::neighbors_start, stl_stats::number_of_facets, stl_file::stats, stl_add_facet(), stl_facet::vertex, and HashEdge::which_edge.

Referenced by stl_repair(), and Slic3r::trianglemesh_repair_on_import().

Here is the call graph for this function:

Here is the caller graph for this function:

stl_remove_unconnected_facets()

void stl_remove_unconnected_facets

(

stl_file *

stl

)

{
  // A couple of things need to be done here.  One is to remove any completely unconnected facets (0 edges connected) since these are
  // useless and could be completely wrong.   The second thing that needs to be done is to remove any degenerate facets that were created during
  // stl_check_facets_nearby().
  auto remove_facet = [stl](int facet_number)
  {
    ++ stl->stats.facets_removed;
    /* Update list of connected edges */
    stl_neighbors &neighbors = stl->neighbors_start[facet_number];
    // Update statistics on unconnected triangle edges.
    switch (neighbors.num_neighbors()) {
    case 3: -- stl->stats.connected_facets_3_edge; // fall through
    case 2: -- stl->stats.connected_facets_2_edge; // fall through
    case 1: -- stl->stats.connected_facets_1_edge; // fall through
    case 0: break;
    default: assert(false);
    }
 
      if (facet_number < int(-- stl->stats.number_of_facets)) {
        // Removing a face, which was not the last one.
        // Copy the face and neighborship from the last face to facet_number.
        stl->facet_start[facet_number] = stl->facet_start[stl->stats.number_of_facets];
        neighbors = stl->neighbors_start[stl->stats.number_of_facets];
        // Update neighborship of faces, which used to point to the last face, now moved to facet_number.
        for (int i = 0; i < 3; ++ i)
          if (neighbors.neighbor[i] != -1) {
            int &other_face_idx = stl->neighbors_start[neighbors.neighbor[i]].neighbor[(neighbors.which_vertex_not[i] + 1) % 3];
            if (other_face_idx != stl->stats.number_of_facets) {
              BOOST_LOG_TRIVIAL(info) << "in remove_facet: neighbor = " << other_face_idx << " numfacets = " << stl->stats.number_of_facets << " this is wrong";
              return;
            }
            other_face_idx = facet_number;
          }
    }
 
      stl->facet_start.pop_back();
      stl->neighbors_start.pop_back();
  };
 
  auto remove_degenerate = [stl, remove_facet](int facet)
  {
    // Update statistics on face connectivity after one edge was disconnected on the facet "facet_num".
    auto update_connects_remove_1 = [stl](int facet_num) {
      switch (stl->neighbors_start[facet_num].num_neighbors()) {
      case 0: assert(false); break;
      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);
        }
    };
 
    int edge_to_collapse = 0;
      if (stl->facet_start[facet].vertex[0] == stl->facet_start[facet].vertex[1]) {
      if (stl->facet_start[facet].vertex[1] == stl->facet_start[facet].vertex[2]) {
        // All 3 vertices are equal. Collapse the edge with no neighbor if it exists.
        const int *nbr = stl->neighbors_start[facet].neighbor;
        edge_to_collapse = (nbr[0] == -1) ? 0 : (nbr[1] == -1) ? 1 : 2;
      } else {
        edge_to_collapse = 0;
      }
      } else if (stl->facet_start[facet].vertex[1] == stl->facet_start[facet].vertex[2]) {
      edge_to_collapse = 1;
      } else if (stl->facet_start[facet].vertex[2] == stl->facet_start[facet].vertex[0]) {
      edge_to_collapse = 2;
      } else {
        // No degenerate. Function shouldn't have been called.
        return;
      }
 
    int edge[3] = { (edge_to_collapse + 1) % 3, (edge_to_collapse + 2) % 3, edge_to_collapse };
    int neighbor[] = {
      stl->neighbors_start[facet].neighbor[edge[0]],
      stl->neighbors_start[facet].neighbor[edge[1]],
      stl->neighbors_start[facet].neighbor[edge[2]]
    };
    int vnot[] = {
      stl->neighbors_start[facet].which_vertex_not[edge[0]],
      stl->neighbors_start[facet].which_vertex_not[edge[1]],
      stl->neighbors_start[facet].which_vertex_not[edge[2]]
    };
 
    // Update statistics on edge connectivity.
    if ((neighbor[0] == -1) && (neighbor[1] != -1))
      update_connects_remove_1(neighbor[1]);
    if ((neighbor[1] == -1) && (neighbor[0] != -1))
      update_connects_remove_1(neighbor[0]);
 
      if (neighbor[0] >= 0) {
      if (neighbor[1] >= 0) {
        // Adjust the "flip" flag for the which_vertex_not values.
        if (vnot[0] > 2) {
          if (vnot[1] > 2) {
            // The face to be removed has its normal flipped compared to the left & right neighbors, therefore after removing this face
            // the two remaining neighbors will be oriented correctly.
            vnot[0] -= 3;
            vnot[1] -= 3;
          } else
            // One neighbor has its normal inverted compared to the face to be removed, the other is oriented equally.
            // After removal, the two neighbors will have their normals flipped.
            vnot[1] += 3;
        } else if (vnot[1] > 2)
          // One neighbor has its normal inverted compared to the face to be removed, the other is oriented equally.
          // After removal, the two neighbors will have their normals flipped.
          vnot[0] += 3;
      }
      stl->neighbors_start[neighbor[0]].neighbor[(vnot[0] + 1) % 3] = (neighbor[0] == neighbor[1]) ? -1 : neighbor[1];
        stl->neighbors_start[neighbor[0]].which_vertex_not[(vnot[0] + 1) % 3] = vnot[1];
      }
      if (neighbor[1] >= 0) {
      stl->neighbors_start[neighbor[1]].neighbor[(vnot[1] + 1) % 3] = (neighbor[0] == neighbor[1]) ? -1 : neighbor[0];
        stl->neighbors_start[neighbor[1]].which_vertex_not[(vnot[1] + 1) % 3] = vnot[0];
      }
    if (neighbor[2] >= 0) {
      update_connects_remove_1(neighbor[2]);
      stl->neighbors_start[neighbor[2]].neighbor[(vnot[2] + 1) % 3] = -1;
    }
 
      remove_facet(facet);
  };
 
  // remove degenerate facets
  for (uint32_t i = 0; i < stl->stats.number_of_facets;)
    if (stl->facet_start[i].vertex[0] == stl->facet_start[i].vertex[1] ||
      stl->facet_start[i].vertex[0] == stl->facet_start[i].vertex[2] ||
      stl->facet_start[i].vertex[1] == stl->facet_start[i].vertex[2]) {
      remove_degenerate(i);
//      assert(stl_validate(stl));
    } else
      ++ i;
 
  if (stl->stats.connected_facets_1_edge < (int)stl->stats.number_of_facets) {
    // There are some faces with no connected edge at all. Remove completely unconnected facets.
    for (uint32_t i = 0; i < stl->stats.number_of_facets;)
      if (stl->neighbors_start[i].num_neighbors() == 0) {
        // This facet is completely unconnected.  Remove it.
        remove_facet(i);
        assert(stl_validate(stl));
      } else
        ++ i;
  }
}

References stl_stats::connected_facets_1_edge, stl_stats::connected_facets_2_edge, stl_stats::connected_facets_3_edge, stl_file::facet_start, stl_stats::facets_removed, stl_neighbors::neighbor, stl_file::neighbors_start, stl_neighbors::num_neighbors(), stl_stats::number_of_facets, stl_file::stats, stl_validate(), and stl_neighbors::which_vertex_not.

Referenced by stl_repair(), and Slic3r::trianglemesh_repair_on_import().

Here is the call graph for this function:

Here is the caller graph for this function: