normals.cpp File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <boost/pool/object_pool.hpp>
#include "stl.h"

Include dependency graph for normals.cpp:

Go to the source code of this file.

Macros
#define	BOOST_POOL_NO_MT

Functions
static void	reverse_facet (stl_file *stl, int facet_num)
static bool	check_normal_vector (stl_file *stl, int facet_num, int normal_fix_flag)
void	stl_fix_normal_directions (stl_file *stl)
void	stl_fix_normal_values (stl_file *stl)
void	stl_reverse_all_facets (stl_file *stl)

Macro Definition Documentation

BOOST_POOL_NO_MT

#define BOOST_POOL_NO_MT

Function Documentation

check_normal_vector()

static bool check_normal_vector ( stl_file *  stl, int  facet_num, int  normal_fix_flag  )

static

{
  stl_facet *facet = &stl->facet_start[facet_num];
 
  stl_normal normal;
  stl_calculate_normal(normal, facet);
  stl_normalize_vector(normal);
  stl_normal normal_dif = (normal - facet->normal).cwiseAbs();
 
  const float eps = 0.001f;
  if (normal_dif(0) < eps && normal_dif(1) < eps && normal_dif(2) < eps) {
    // Normal is within tolerance. It is not really necessary to change the values here, but just for consistency, I will.
    facet->normal = normal;
    return false;
  }
 
  stl_normal test_norm = facet->normal;
  stl_normalize_vector(test_norm);
  normal_dif = (normal - test_norm).cwiseAbs();
  if (normal_dif(0) < eps && normal_dif(1) < eps && normal_dif(2) < eps) {
    // The normal is not within tolerance, but direction is OK.
    if (normal_fix_flag) {
        facet->normal = normal;
        ++ stl->stats.normals_fixed;
    }
    return false;
  }
 
  test_norm *= -1.f;
  normal_dif = (normal - test_norm).cwiseAbs();
  if (normal_dif(0) < eps && normal_dif(1) < eps && normal_dif(2) < eps) {
    // The normal is not within tolerance and backwards.
    if (normal_fix_flag) {
        facet->normal = normal;
        ++ stl->stats.normals_fixed;
    }
    return true;
  }
  if (normal_fix_flag) {
    facet->normal = normal;
    ++ stl->stats.normals_fixed;
  }
  // Status is unknown.
  return false;
}

References cwiseAbs(), stl_file::facet_start, stl_facet::normal, stl_stats::normals_fixed, stl_file::stats, stl_calculate_normal(), and stl_normalize_vector().

Referenced by stl_fix_normal_directions(), and stl_fix_normal_values().

Here is the call graph for this function:

Here is the caller graph for this function:

reverse_facet()

static void reverse_facet ( stl_file *  stl, int  facet_num  )

static

{
  ++ stl->stats.facets_reversed;
 
  int neighbor[3] = { stl->neighbors_start[facet_num].neighbor[0], stl->neighbors_start[facet_num].neighbor[1], stl->neighbors_start[facet_num].neighbor[2] };
  int vnot[3] = { stl->neighbors_start[facet_num].which_vertex_not[0], stl->neighbors_start[facet_num].which_vertex_not[1], stl->neighbors_start[facet_num].which_vertex_not[2] };
 
  // reverse the facet
  stl_vertex tmp_vertex = stl->facet_start[facet_num].vertex[0];
  stl->facet_start[facet_num].vertex[0] = stl->facet_start[facet_num].vertex[1];
  stl->facet_start[facet_num].vertex[1] = tmp_vertex;
 
  // fix the vnots of the neighboring facets
  if (neighbor[0] != -1)
    stl->neighbors_start[neighbor[0]].which_vertex_not[(vnot[0] + 1) % 3] = (stl->neighbors_start[neighbor[0]].which_vertex_not[(vnot[0] + 1) % 3] + 3) % 6;
  if (neighbor[1] != -1)
    stl->neighbors_start[neighbor[1]].which_vertex_not[(vnot[1] + 1) % 3] = (stl->neighbors_start[neighbor[1]].which_vertex_not[(vnot[1] + 1) % 3] + 4) % 6;
  if (neighbor[2] != -1)
    stl->neighbors_start[neighbor[2]].which_vertex_not[(vnot[2] + 1) % 3] = (stl->neighbors_start[neighbor[2]].which_vertex_not[(vnot[2] + 1) % 3] + 2) % 6;
 
  // swap the neighbors of the facet that is being reversed
  stl->neighbors_start[facet_num].neighbor[1] = neighbor[2];
  stl->neighbors_start[facet_num].neighbor[2] = neighbor[1];
 
  // swap the vnots of the facet that is being reversed 
  stl->neighbors_start[facet_num].which_vertex_not[1] = vnot[2];
  stl->neighbors_start[facet_num].which_vertex_not[2] = vnot[1];
 
  // reverse the values of the vnots of the facet that is being reversed
  stl->neighbors_start[facet_num].which_vertex_not[0] = (stl->neighbors_start[facet_num].which_vertex_not[0] + 3) % 6;
  stl->neighbors_start[facet_num].which_vertex_not[1] = (stl->neighbors_start[facet_num].which_vertex_not[1] + 3) % 6;
  stl->neighbors_start[facet_num].which_vertex_not[2] = (stl->neighbors_start[facet_num].which_vertex_not[2] + 3) % 6;
}

References stl_file::facet_start, stl_stats::facets_reversed, stl_file::neighbors_start, and stl_file::stats.

Referenced by stl_fix_normal_directions(), and stl_reverse_all_facets().

Here is the caller graph for this function:

stl_fix_normal_directions()

void stl_fix_normal_directions

(

stl_file *

stl

)

{
  // This may happen for malformed models, see: https://github.com/prusa3d/PrusaSlicer/issues/2209
    if (stl->stats.number_of_facets == 0)
      return;
 
  struct stl_normal {
      int         facet_num;
      stl_normal *next;
    };
 
    // Initialize linked list.
    boost::object_pool<stl_normal> pool;
    stl_normal *head = pool.construct();
    stl_normal *tail = pool.construct();
  head->next = tail;
  tail->next = tail;
 
  // Initialize list that keeps track of already fixed facets.
  std::vector<char> norm_sw(stl->stats.number_of_facets, 0);
  // Initialize list that keeps track of reversed facets.
    std::vector<int>  reversed_ids;
    reversed_ids.reserve(stl->stats.number_of_facets);
 
    int facet_num = 0;
    // If normal vector is not within tolerance and backwards:
    // Arbitrarily starts at face 0.  If this one is wrong, we're screwed. Thankfully, the chances
    // of it being wrong randomly are low if most of the triangles are right:
    if (check_normal_vector(stl, 0, 0)) {
      reverse_facet(stl, 0);
        reversed_ids.emplace_back(0);
    }
 
    // Say that we've fixed this facet:
    norm_sw[facet_num] = 1;
  int checked = 1;
 
    for (;;) {
      // Add neighbors_to_list. Add unconnected neighbors to the list.
      bool force_exit = false;
      for (int j = 0; j < 3; ++ j) {
          // Reverse the neighboring facets if necessary.
          if (stl->neighbors_start[facet_num].which_vertex_not[j] > 2) {
            // If the facet has a neighbor that is -1, it means that edge isn't shared by another facet
            if (stl->neighbors_start[facet_num].neighbor[j] != -1) {
                if (norm_sw[stl->neighbors_start[facet_num].neighbor[j]] == 1) {
                    // trying to modify a facet already marked as fixed, revert all changes made until now and exit (fixes: #716, #574, #413, #269, #262, #259, #230, #228, #206)
                    for (int id = int(reversed_ids.size()) - 1; id >= 0; -- id)
                        reverse_facet(stl, reversed_ids[id]);
                    force_exit = true;
                    break;
                }
                reverse_facet(stl, stl->neighbors_start[facet_num].neighbor[j]);
                reversed_ids.emplace_back(stl->neighbors_start[facet_num].neighbor[j]);
            }
          }
          // If this edge of the facet is connected:
          if (stl->neighbors_start[facet_num].neighbor[j] != -1) {
            // If we haven't fixed this facet yet, add it to the list:
            if (norm_sw[stl->neighbors_start[facet_num].neighbor[j]] != 1) {
                // Add node to beginning of list.
                stl_normal *newn = pool.construct();
                newn->facet_num = stl->neighbors_start[facet_num].neighbor[j];
                newn->next = head->next;
                head->next = newn;
            }
          }
      }
 
      // an error occourred, quit the for loop and exit
      if (force_exit)
        break;
 
      // Get next facet to fix from top of list.
      if (head->next != tail) {
          facet_num = head->next->facet_num;
            assert(facet_num < stl->stats.number_of_facets);
          if (norm_sw[facet_num] != 1) { // If facet is in list mutiple times
            norm_sw[facet_num] = 1; // Record this one as being fixed.
            ++ checked;
          }
          stl_normal *temp = head->next;  // Delete this facet from the list.
          head->next = head->next->next;
          // pool.destroy(temp);
      } else { // If we ran out of facets to fix: All of the facets in this part have been fixed.
          ++ stl->stats.number_of_parts;
          if (checked >= int(stl->stats.number_of_facets))
            // All of the facets have been checked.  Bail out.
            break;
        // There is another part here.  Find it and continue.
        for (uint32_t i = 0; i < stl->stats.number_of_facets; ++ i)
            if (norm_sw[i] == 0) {
              // This is the first facet of the next part.
              facet_num = i;
              if (check_normal_vector(stl, i, 0)) {
                  reverse_facet(stl, i);
                  reversed_ids.emplace_back(i);
              }
              norm_sw[facet_num] = 1;
              ++ checked;
              break;
            }
      }
    }
 
  // pool.destroy(head);
  // pool.destroy(tail);
}

References check_normal_vector(), head(), stl_file::neighbors_start, stl_stats::number_of_facets, stl_stats::number_of_parts, reverse_facet(), stl_file::stats, and tail().

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_fix_normal_values()

void stl_fix_normal_values

(

stl_file *

stl

)

{
  for (uint32_t i = 0; i < stl->stats.number_of_facets; ++ i)
      check_normal_vector(stl, i, 1);
}

References check_normal_vector(), stl_stats::number_of_facets, and stl_file::stats.

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_reverse_all_facets()

void stl_reverse_all_facets

(

stl_file *

stl

)

{
  stl_normal normal;
    for (uint32_t i = 0; i < stl->stats.number_of_facets; ++ i) {
      reverse_facet(stl, i);
      stl_calculate_normal(normal, &stl->facet_start[i]);
      stl_normalize_vector(normal);
      stl->facet_start[i].normal = normal;
    }
}

References stl_file::facet_start, stl_stats::number_of_facets, reverse_facet(), stl_file::stats, stl_calculate_normal(), and stl_normalize_vector().

Referenced by stl_calculate_volume(), stl_mirror_xy(), stl_mirror_xz(), stl_mirror_yz(), and stl_repair().

Here is the call graph for this function:

Here is the caller graph for this function: