ModRoundnessT.hh 11.2 KB
Newer Older
1 2 3
/*===========================================================================*\
 *                                                                           *
 *                               OpenMesh                                    *
Jan Möbius's avatar
Jan Möbius committed
4
 *      Copyright (C) 2001-2013 by Computer Graphics Group, RWTH Aachen      *
5 6
 *                           www.openmesh.org                                *
 *                                                                           *
7
 *---------------------------------------------------------------------------*
8 9
 *  This file is part of OpenMesh.                                           *
 *                                                                           *
10
 *  OpenMesh is free software: you can redistribute it and/or modify         *
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
 *  it under the terms of the GNU Lesser General Public License as           *
 *  published by the Free Software Foundation, either version 3 of           *
 *  the License, or (at your option) any later version with the              *
 *  following exceptions:                                                    *
 *                                                                           *
 *  If other files instantiate templates or use macros                       *
 *  or inline functions from this file, or you compile this file and         *
 *  link it with other files to produce an executable, this file does        *
 *  not by itself cause the resulting executable to be covered by the        *
 *  GNU Lesser General Public License. This exception does not however       *
 *  invalidate any other reasons why the executable file might be            *
 *  covered by the GNU Lesser General Public License.                        *
 *                                                                           *
 *  OpenMesh 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 Lesser General Public License for more details.                      *
 *                                                                           *
 *  You should have received a copy of the GNU LesserGeneral Public          *
 *  License along with OpenMesh.  If not,                                    *
 *  see <http://www.gnu.org/licenses/>.                                      *
 *                                                                           *
33
\*===========================================================================*/
34 35

/*===========================================================================*\
36
 *                                                                           *
37 38 39 40
 *   $Revision$                                                         *
 *   $Date$                   *
 *                                                                           *
\*===========================================================================*/
Jan Möbius's avatar
Jan Möbius committed
41 42

/** \file ModRoundnessT.hh
43

Jan Möbius's avatar
Jan Möbius committed
44 45 46 47 48 49 50 51
 */

//=============================================================================
//
//  CLASS ModRoundnessT
//
//=============================================================================

52 53
#ifndef OPENMESH_DECIMATER_MODROUNDNESST_HH
#define OPENMESH_DECIMATER_MODROUNDNESST_HH
Jan Möbius's avatar
Jan Möbius committed
54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74


//== INCLUDES =================================================================

#include <OpenMesh/Tools/Decimater/ModBaseT.hh>
#include <math.h>

#if defined(OM_CC_MSVC)
#  define OM_ENABLE_WARNINGS 4244
#  pragma warning(disable : OM_ENABLE_WARNINGS )
#endif

//== NAMESPACE ================================================================

namespace OpenMesh { // BEGIN_NS_OPENMESH
namespace Decimater { // BEGIN_NS_DECIMATER


//== CLASS DEFINITION =========================================================


75 76 77 78 79 80 81 82
/** \brief Use Roundness of triangles to control decimation
  *
  *
  * In binary and mode, the collapse is legal if:
  *  - The roundness after the collapse is greater than the given value
  *
  * In continuous mode the roundness after the collapse is returned
  */
83 84
template <class MeshT>
class ModRoundnessT : public ModBaseT<MeshT>
Jan Möbius's avatar
Jan Möbius committed
85
{
86
  public:
87
  DECIMATING_MODULE( ModRoundnessT, MeshT, Roundness );
Jan Möbius's avatar
Jan Möbius committed
88

89
  public:
Jan Möbius's avatar
Jan Möbius committed
90 91 92 93 94

  // typedefs
  typedef typename Mesh::Point                      Point;
  typedef typename vector_traits<Point>::value_type value_type;

95 96
  public:

Jan Möbius's avatar
Jan Möbius committed
97
  /// Constructor
98
  ModRoundnessT( MeshT &_dec ) :
99
    Base(_dec, false),
Jan Möbius's avatar
Jan Möbius committed
100 101
    min_r_(-1.0)
  { }
102

Jan Möbius's avatar
Jan Möbius committed
103 104 105
  /// Destructor
  ~ModRoundnessT() { }

106 107
  public: // inherited

Jan Möbius's avatar
Jan Möbius committed
108 109 110 111
  /** Compute collapse priority due to roundness of triangle.
   *
   *  The roundness is computed by dividing the radius of the
   *  circumference by the length of the shortest edge. The result is
112
   *  normalized.
Jan Möbius's avatar
Jan Möbius committed
113 114 115 116 117
   *
   * \return [0:1] or ILLEGAL_COLLAPSE in non-binary mode
   * \return LEGAL_COLLAPSE or ILLEGAL_COLLAPSE in binary mode
   * \see set_min_roundness()
   */
118 119
  float collapse_priority(const CollapseInfo& _ci)
  {
120
    //     using namespace OpenMesh;
Jan Möbius's avatar
Jan Möbius committed
121 122 123 124 125 126

    typename Mesh::ConstVertexOHalfedgeIter voh_it(Base::mesh(), _ci.v0);
    double                                  r;
    double                                  priority = 0.0; //==LEGAL_COLLAPSE
    typename Mesh::FaceHandle               fhC, fhB;
    Vec3f                                   B,C;
127

Jan Möbius's avatar
Jan Möbius committed
128
    if ( min_r_ < 0.0f ) // continues mode
129
    {
Jan Möbius's avatar
Jan Möbius committed
130
      C   = vector_cast<Vec3f>(Base::mesh().point( Base::mesh().to_vertex_handle(*voh_it)));
131
      fhC = Base::mesh().face_handle( *voh_it );
Jan Möbius's avatar
Jan Möbius committed
132

Jan Möbius's avatar
Jan Möbius committed
133
      for (++voh_it; voh_it.is_valid(); ++voh_it)
Jan Möbius's avatar
Jan Möbius committed
134
      {
135 136
        B   = C;
        fhB = fhC;
Jan Möbius's avatar
Jan Möbius committed
137
        C   = vector_cast<Vec3f>(Base::mesh().point(Base::mesh().to_vertex_handle(*voh_it)));
138
        fhC = Base::mesh().face_handle( *voh_it );
139 140 141 142 143 144 145 146 147

        if ( fhB == _ci.fl || fhB == _ci.fr )
          continue;

        // simulate collapse using position of v1
        r = roundness( vector_cast<Vec3f>(_ci.p1), B, C );

        // return the maximum non-roundness
        priority = std::max( priority, (1.0-r) );
Jan Möbius's avatar
Jan Möbius committed
148 149 150 151 152

      }
    }
    else // binary mode
    {
Jan Möbius's avatar
Jan Möbius committed
153
      C   = vector_cast<Vec3f>(Base::mesh().point( Base::mesh().to_vertex_handle(*voh_it)));
154
      fhC = Base::mesh().face_handle( *voh_it );
Jan Möbius's avatar
Jan Möbius committed
155

Jan Möbius's avatar
Jan Möbius committed
156
      for (++voh_it; voh_it.is_valid() && (priority==Base::LEGAL_COLLAPSE); ++voh_it)
Jan Möbius's avatar
Jan Möbius committed
157
      {
158 159
        B   = C;
        fhB = fhC;
Jan Möbius's avatar
Jan Möbius committed
160
        C   = vector_cast<Vec3f>(Base::mesh().point(Base::mesh().to_vertex_handle(*voh_it)));
161
        fhC = Base::mesh().face_handle( *voh_it );
Jan Möbius's avatar
Jan Möbius committed
162

163 164
        if ( fhB == _ci.fl || fhB == _ci.fr )
          continue;
Jan Möbius's avatar
Jan Möbius committed
165

166 167
        priority = ( (r=roundness( vector_cast<Vec3f>(_ci.p1), B, C )) < min_r_)
	          ? Base::ILLEGAL_COLLAPSE : Base::LEGAL_COLLAPSE;
Jan Möbius's avatar
Jan Möbius committed
168 169 170 171 172
      }
    }

    return (float) priority;
  }
173

174 175 176 177 178 179 180 181 182 183 184 185 186
  /// set the percentage of minimum roundness
  void set_error_tolerance_factor(double _factor) {
    if (this->is_binary()) {
      if (_factor >= 0.0 && _factor <= 1.0) {
        // the smaller the factor, the smaller min_r_ gets
        // thus creating a stricter constraint
        // division by error_tolerance_factor_ is for normalization
        value_type min_roundness = min_r_ * _factor / this->error_tolerance_factor_;
        set_min_roundness(min_roundness);
        this->error_tolerance_factor_ = _factor;
      }
}
  }
187

Jan Möbius's avatar
Jan Möbius committed
188 189 190 191 192 193 194 195 196 197 198

public: // specific methods

  void set_min_angle( float _angle, bool /* _binary=true */ )
  {
    assert( _angle > 0 && _angle < 60 );

    _angle = float(M_PI * _angle /180.0);

    Vec3f A,B,C;

Jan Möbius's avatar
Jan Möbius committed
199 200 201
    A = Vec3f(               0.0f, 0.0f,           0.0f);
    B = Vec3f( 2.0f * cos(_angle), 0.0f,           0.0f);
    C = Vec3f(        cos(_angle), sin(_angle),    0.0f);
Jan Möbius's avatar
Jan Möbius committed
202 203 204 205 206

    double r1 = roundness(A,B,C);

    _angle = float(0.5 * ( M_PI - _angle ));

Jan Möbius's avatar
Jan Möbius committed
207 208 209
    A = Vec3f(             0.0f, 0.0f,           0.0f);
    B = Vec3f( 2.0f*cos(_angle), 0.0f,           0.0f);
    C = Vec3f(      cos(_angle), sin(_angle),    0.0f);
Jan Möbius's avatar
Jan Möbius committed
210 211 212

    double r2 = roundness(A,B,C);

213
    set_min_roundness( value_type(std::min(r1,r2)), true );
Jan Möbius's avatar
Jan Möbius committed
214 215 216 217
  }

  /** Set a minimum roundness value.
   *  \param _min_roundness in range (0,1)
218
   *  \param _binary Set true, if the binary mode should be enabled,
Jan Möbius's avatar
Jan Möbius committed
219
   *                 else false. In latter case the collapse_priority()
220
   *                 returns a float value if the constraint does not apply
Jan Möbius's avatar
Jan Möbius committed
221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245
   *                 and ILLEGAL_COLLAPSE else.
   */
  void set_min_roundness( value_type _min_roundness, bool _binary=true )
  {
    assert( 0.0 <= _min_roundness && _min_roundness <= 1.0 );
    min_r_  = _min_roundness;
    Base::set_binary(_binary);
  }

  /// Unset minimum value constraint and enable non-binary mode.
  void unset_min_roundness()
  {
    min_r_  = -1.0;
    Base::set_binary(false);
  }

  // Compute a normalized roundness of a triangle ABC
  //
  // Having
  //   A,B,C corner points of triangle
  //   a,b,c the vectors BC,CA,AB
  //   Area  area of triangle
  //
  // then define
  //
246
  //      radius of circumference
Jan Möbius's avatar
Jan Möbius committed
247 248 249
  // R := -----------------------
  //      length of shortest edge
  //
250
  //       ||a|| * ||b|| * ||c||
Jan Möbius's avatar
Jan Möbius committed
251 252 253 254 255 256 257 258 259 260
  //       ---------------------
  //             4 * Area                 ||a|| * ||b|| * ||c||
  //    = ----------------------- = -----------------------------------
  //      min( ||a||,||b||,||c||)   4 * Area * min( ||a||,||b||,||c|| )
  //
  //                      ||a|| * ||b|| * ||c||
  //    = -------------------------------------------------------
  //      4 *  1/2 * ||cross(B-A,C-A)||  * min( ||a||,||b||,||c|| )
  //
  //                         a'a * b'b * c'c
261
  // R� = ----------------------------------------------------------
Jan Möbius's avatar
Jan Möbius committed
262 263 264 265 266 267
  //       4 * cross(B-A,C-A)'cross(B-A,C-A) * min( a'a, b'b, c'c )
  //
  //                      a'a * b'b * c'c
  // R = 1/2 * sqrt(---------------------------)
  //                 AA * min( a'a, b'b, c'c )
  //
268
  // At angle 60� R has it's minimum for all edge lengths = sqrt(1/3)
Jan Möbius's avatar
Jan Möbius committed
269
  //
270
  // Define normalized roundness
Jan Möbius's avatar
Jan Möbius committed
271 272 273 274 275 276 277 278 279 280 281
  //
  // nR := sqrt(1/3) / R
  //
  //                         AA * min( a'a, b'b, c'c )
  //     = sqrt(4/3) * sqrt(---------------------------)
  //                              a'a * b'b * c'c
  //
  double roundness( const Vec3f& A, const Vec3f& B, const Vec3f &C )
  {
    const value_type epsilon = value_type(1e-15);

282
    static const value_type sqrt43 = value_type(sqrt(4.0/3.0)); // 60�,a=b=c, **)
Jan Möbius's avatar
Jan Möbius committed
283 284 285 286 287 288 289 290 291 292 293 294 295 296

    Vec3f vecAC     = C-A;
    Vec3f vecAB     = B-A;

    // compute squared values to avoid sqrt-computations
    value_type aa = (B-C).sqrnorm();
    value_type bb = vecAC.sqrnorm();
    value_type cc = vecAB.sqrnorm();
    value_type AA = cross(vecAC,vecAB).sqrnorm(); // without factor 1/4   **)

    if ( AA < epsilon )
      return 0.0;

    double nom   = AA * std::min( std::min(aa,bb),cc );
297
    double denom = aa * bb * cc;
Jan Möbius's avatar
Jan Möbius committed
298 299 300 301 302
    double nR    = sqrt43 * sqrt(nom/denom);

    return nR;
  }

303 304
  private:

Jan Möbius's avatar
Jan Möbius committed
305 306 307 308 309 310 311 312 313 314 315 316 317
  value_type min_r_;
};


//=============================================================================
} // END_NS_DECIMATER
} // END_NS_OPENMESH
//=============================================================================
#if defined(OM_CC_MSVC) && defined(OM_ENABLE_WARNINGS)
#  pragma warning(default : OM_ENABLE_WARNINGS)
#  undef OM_ENABLE_WARNINGS
#endif
//=============================================================================
318
#endif // OPENMESH_DECIMATER_MODROUNDNESST_HH defined
Jan Möbius's avatar
Jan Möbius committed
319 320
//=============================================================================