bmo_normals.c

Go to the documentation of this file.

/*
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 */
 
#include "MEM_guardedalloc.h"
 
#include "BLI_linklist_stack.h"
#include "BLI_math.h"
 
#include "bmesh.h"
 
#include "intern/bmesh_operators_private.h" /* own include */
 
/********* Right-hand faces implementation ****** */
 
#define FACE_FLAG (1 << 0)
#define FACE_FLIP (1 << 1)
#define FACE_TEMP (1 << 2)
 
static bool bmo_recalc_normal_loop_filter_cb(const BMLoop *l, void *UNUSED(user_data))
{
  return BM_edge_is_manifold(l->e);
}
 
static int recalc_face_normals_find_index(BMesh *bm,
                                          BMFace **faces,
                                          const int faces_len,
                                          bool *r_is_flip)
{
  const float eps = FLT_EPSILON;
  float cent_area_accum = 0.0f;
  float cent[3];
  const float cent_fac = 1.0f / (float)faces_len;
 
  bool is_flip = false;
  int f_start_index;
  int i;
 
  struct {
    float dist_sq;
    float edge_dot;
    float loop_dot;
  } best, test;
 
  UNUSED_VARS_NDEBUG(bm);
 
  zero_v3(cent);
 
  /* first calculate the center */
  for (i = 0; i < faces_len; i++) {
    float f_cent[3];
    const float f_area = BM_face_calc_area(faces[i]);
    BM_face_calc_center_median_weighted(faces[i], f_cent);
    madd_v3_v3fl(cent, f_cent, cent_fac * f_area);
    cent_area_accum += f_area;
 
    BLI_assert(BMO_face_flag_test(bm, faces[i], FACE_TEMP) == 0);
    BLI_assert(BM_face_is_normal_valid(faces[i]));
  }
 
  if (cent_area_accum != 0.0f) {
    mul_v3_fl(cent, 1.0f / cent_area_accum);
  }
 
  /* Distances must start above zero,
   * or we can't do meaningful calculations based on the direction to the center */
  best.dist_sq = eps;
  best.edge_dot = best.loop_dot = -FLT_MAX;
 
  /* used in degenerate cases only */
  f_start_index = 0;
 
  for (i = 0; i < faces_len; i++) {
    BMLoop *l_iter, *l_first;
 
    l_iter = l_first = BM_FACE_FIRST_LOOP(faces[i]);
    do {
      bool is_best_dist_sq;
      float dir[3];
      sub_v3_v3v3(dir, l_iter->v->co, cent);
      test.dist_sq = len_squared_v3(dir);
      is_best_dist_sq = (test.dist_sq > best.dist_sq);
      if (is_best_dist_sq || (test.dist_sq == best.dist_sq)) {
        float edge_dir_pair[2][3];
        mul_v3_fl(dir, 1.0f / sqrtf(test.dist_sq));
 
        sub_v3_v3v3(edge_dir_pair[0], l_iter->next->v->co, l_iter->v->co);
        sub_v3_v3v3(edge_dir_pair[1], l_iter->prev->v->co, l_iter->v->co);
 
        if ((normalize_v3(edge_dir_pair[0]) > eps) && (normalize_v3(edge_dir_pair[1]) > eps)) {
          bool is_best_edge_dot;
          test.edge_dot = max_ff(dot_v3v3(dir, edge_dir_pair[0]), dot_v3v3(dir, edge_dir_pair[1]));
          is_best_edge_dot = (test.edge_dot > best.edge_dot);
          if (is_best_dist_sq || is_best_edge_dot || (test.edge_dot == best.edge_dot)) {
            float loop_dir[3];
            cross_v3_v3v3(loop_dir, edge_dir_pair[0], edge_dir_pair[1]);
            if (normalize_v3(loop_dir) > eps) {
              float loop_dir_dot;
              /* Highly unlikely the furthest loop is also the concave part of an ngon,
               * but it can be contrived with _very_ non-planar faces - so better check. */
              if (UNLIKELY(dot_v3v3(loop_dir, l_iter->f->no) < 0.0f)) {
                negate_v3(loop_dir);
              }
              loop_dir_dot = dot_v3v3(dir, loop_dir);
              test.loop_dot = fabsf(loop_dir_dot);
              if (is_best_dist_sq || is_best_edge_dot || (test.loop_dot > best.loop_dot)) {
                best = test;
                f_start_index = i;
                is_flip = (loop_dir_dot < 0.0f);
              }
            }
          }
        }
      }
    } while ((l_iter = l_iter->next) != l_first);
  }
 
  *r_is_flip = is_flip;
  return f_start_index;
}
 
static void bmo_recalc_face_normals_array(BMesh *bm,
                                          BMFace **faces,
                                          const int faces_len,
                                          const short oflag)
{
  int i, f_start_index;
  const short oflag_flip = oflag | FACE_FLIP;
  bool is_flip;
 
  BMFace *f;
 
  BLI_LINKSTACK_DECLARE(fstack, BMFace *);
 
  f_start_index = recalc_face_normals_find_index(bm, faces, faces_len, &is_flip);
 
  if (is_flip) {
    BMO_face_flag_enable(bm, faces[f_start_index], FACE_FLIP);
  }
 
  /* now that we've found our starting face, make all connected faces
   * have the same winding.  this is done recursively, using a manual
   * stack (if we use simple function recursion, we'd end up overloading
   * the stack on large meshes). */
  BLI_LINKSTACK_INIT(fstack);
 
  BLI_LINKSTACK_PUSH(fstack, faces[f_start_index]);
  BMO_face_flag_enable(bm, faces[f_start_index], FACE_TEMP);
 
  while ((f = BLI_LINKSTACK_POP(fstack))) {
    const bool flip_state = BMO_face_flag_test_bool(bm, f, FACE_FLIP);
    BMLoop *l_iter, *l_first;
 
    l_iter = l_first = BM_FACE_FIRST_LOOP(f);
    do {
      BMLoop *l_other = l_iter->radial_next;
 
      if ((l_other != l_iter) && bmo_recalc_normal_loop_filter_cb(l_iter, NULL)) {
        if (!BMO_face_flag_test(bm, l_other->f, FACE_TEMP)) {
          BMO_face_flag_enable(bm, l_other->f, FACE_TEMP);
          BMO_face_flag_set(bm, l_other->f, FACE_FLIP, (l_other->v == l_iter->v) != flip_state);
          BLI_LINKSTACK_PUSH(fstack, l_other->f);
        }
      }
    } while ((l_iter = l_iter->next) != l_first);
  }
 
  BLI_LINKSTACK_FREE(fstack);
 
  /* apply flipping to oflag'd faces */
  for (i = 0; i < faces_len; i++) {
    if (BMO_face_flag_test(bm, faces[i], oflag_flip) == oflag_flip) {
      BM_face_normal_flip(bm, faces[i]);
    }
    BMO_face_flag_disable(bm, faces[i], FACE_TEMP);
  }
}
 
void bmo_recalc_face_normals_exec(BMesh *bm, BMOperator *op)
{
  int *groups_array = MEM_mallocN(sizeof(*groups_array) * bm->totface, __func__);
  BMFace **faces_grp = MEM_mallocN(sizeof(*faces_grp) * bm->totface, __func__);
 
  int(*group_index)[2];
  const int group_tot = BM_mesh_calc_face_groups(
      bm, groups_array, &group_index, bmo_recalc_normal_loop_filter_cb, NULL, NULL, 0, BM_EDGE);
  int i;
 
  BMO_slot_buffer_flag_enable(bm, op->slots_in, "faces", BM_FACE, FACE_FLAG);
 
  BM_mesh_elem_table_ensure(bm, BM_FACE);
 
  for (i = 0; i < group_tot; i++) {
    const int fg_sta = group_index[i][0];
    const int fg_len = group_index[i][1];
    int j;
    bool is_calc = false;
 
    for (j = 0; j < fg_len; j++) {
      faces_grp[j] = BM_face_at_index(bm, groups_array[fg_sta + j]);
 
      if (is_calc == false) {
        is_calc = BMO_face_flag_test_bool(bm, faces_grp[j], FACE_FLAG);
      }
    }
 
    if (is_calc) {
      bmo_recalc_face_normals_array(bm, faces_grp, fg_len, FACE_FLAG);
    }
  }
 
  MEM_freeN(faces_grp);
 
  MEM_freeN(groups_array);
  MEM_freeN(group_index);
}