ModRoundnessT.hh 11.8 KB
Newer Older
Jan Möbius's avatar
Jan Möbius committed
1
/* ========================================================================= *
2 3
 *                                                                           *
 *                               OpenMesh                                    *
Jan Möbius's avatar
Jan Möbius committed
4
 *           Copyright (c) 2001-2015, RWTH-Aachen University                 *
Jan Möbius's avatar
Typo  
Jan Möbius committed
5
 *           Department of Computer Graphics and Multimedia                  *
Jan Möbius's avatar
Jan Möbius committed
6 7
 *                          All rights reserved.                             *
 *                            www.openmesh.org                               *
8
 *                                                                           *
9
 *---------------------------------------------------------------------------*
Jan Möbius's avatar
Jan Möbius committed
10 11
 * This file is part of OpenMesh.                                            *
 *---------------------------------------------------------------------------*
12
 *                                                                           *
Jan Möbius's avatar
Jan Möbius committed
13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
 * Redistribution and use in source and binary forms, with or without        *
 * modification, are permitted provided that the following conditions        *
 * are met:                                                                  *
 *                                                                           *
 * 1. Redistributions of source code must retain the above copyright notice, *
 *    this list of conditions and the following disclaimer.                  *
 *                                                                           *
 * 2. Redistributions in binary form must reproduce the above copyright      *
 *    notice, this list of conditions and the following disclaimer in the    *
 *    documentation and/or other materials provided with the distribution.   *
 *                                                                           *
 * 3. Neither the name of the copyright holder nor the names of its          *
 *    contributors may be used to endorse or promote products derived from   *
 *    this software without specific prior written permission.               *
 *                                                                           *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS       *
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A           *
 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,  *
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,       *
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR        *
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF    *
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING      *
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS        *
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.              *
Jan Möbius's avatar
Jan Möbius committed
39 40
 *                                                                           *
 * ========================================================================= */
41 42

/*===========================================================================*\
43
 *                                                                           *
44 45 46 47
 *   $Revision$                                                         *
 *   $Date$                   *
 *                                                                           *
\*===========================================================================*/
Jan Möbius's avatar
Jan Möbius committed
48 49

/** \file ModRoundnessT.hh
50

Jan Möbius's avatar
Jan Möbius committed
51 52 53 54 55 56 57 58
 */

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

59 60
#ifndef OPENMESH_DECIMATER_MODROUNDNESST_HH
#define OPENMESH_DECIMATER_MODROUNDNESST_HH
Jan Möbius's avatar
Jan Möbius committed
61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81


//== 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 =========================================================


82 83 84 85 86 87 88 89
/** \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
  */
90 91
template <class MeshT>
class ModRoundnessT : public ModBaseT<MeshT>
Jan Möbius's avatar
Jan Möbius committed
92
{
93
  public:
94
  DECIMATING_MODULE( ModRoundnessT, MeshT, Roundness );
Jan Möbius's avatar
Jan Möbius committed
95

96
  public:
Jan Möbius's avatar
Jan Möbius committed
97 98

  // typedefs
Jan Möbius's avatar
Jan Möbius committed
99
  typedef typename MeshT::Point                      Point;
Jan Möbius's avatar
Jan Möbius committed
100 101
  typedef typename vector_traits<Point>::value_type value_type;

102 103
  public:

Jan Möbius's avatar
Jan Möbius committed
104
  /// Constructor
105
  ModRoundnessT( MeshT &_dec ) :
106
    Base(_dec, false),
Jan Möbius's avatar
Jan Möbius committed
107 108
    min_r_(-1.0)
  { }
109

Jan Möbius's avatar
Jan Möbius committed
110 111 112
  /// Destructor
  ~ModRoundnessT() { }

113 114
  public: // inherited

Jan Möbius's avatar
Jan Möbius committed
115 116 117 118
  /** 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
119
   *  normalized.
Jan Möbius's avatar
Jan Möbius committed
120 121 122 123 124
   *
   * \return [0:1] or ILLEGAL_COLLAPSE in non-binary mode
   * \return LEGAL_COLLAPSE or ILLEGAL_COLLAPSE in binary mode
   * \see set_min_roundness()
   */
125 126
  float collapse_priority(const CollapseInfo& _ci)
  {
127
    //     using namespace OpenMesh;
Jan Möbius's avatar
Jan Möbius committed
128 129 130 131 132 133

    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;
134

Jan Möbius's avatar
Jan Möbius committed
135
    if ( min_r_ < 0.0f ) // continues mode
136
    {
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 );
Jan Möbius's avatar
Jan Möbius committed
139

Jan Möbius's avatar
Jan Möbius committed
140
      for (++voh_it; voh_it.is_valid(); ++voh_it)
Jan Möbius's avatar
Jan Möbius committed
141
      {
142 143
        B   = C;
        fhB = fhC;
Jan Möbius's avatar
Jan Möbius committed
144
        C   = vector_cast<Vec3f>(Base::mesh().point(Base::mesh().to_vertex_handle(*voh_it)));
145
        fhC = Base::mesh().face_handle( *voh_it );
146 147 148 149 150 151 152 153 154

        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
155 156 157 158 159

      }
    }
    else // binary mode
    {
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

Jan Möbius's avatar
Jan Möbius committed
163
      for (++voh_it; voh_it.is_valid() && (priority==Base::LEGAL_COLLAPSE); ++voh_it)
Jan Möbius's avatar
Jan Möbius committed
164
      {
165 166
        B   = C;
        fhB = fhC;
Jan Möbius's avatar
Jan Möbius committed
167
        C   = vector_cast<Vec3f>(Base::mesh().point(Base::mesh().to_vertex_handle(*voh_it)));
168
        fhC = Base::mesh().face_handle( *voh_it );
Jan Möbius's avatar
Jan Möbius committed
169

170 171
        if ( fhB == _ci.fl || fhB == _ci.fr )
          continue;
Jan Möbius's avatar
Jan Möbius committed
172

173 174
        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
175 176 177 178 179
      }
    }

    return (float) priority;
  }
180

181 182 183 184 185 186 187
  /// 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
Jan Möbius's avatar
Jan Möbius committed
188
        value_type min_roundness = min_r_ * static_cast<value_type>(_factor / this->error_tolerance_factor_);
189 190 191 192 193
        set_min_roundness(min_roundness);
        this->error_tolerance_factor_ = _factor;
      }
}
  }
194

Jan Möbius's avatar
Jan Möbius committed
195 196 197 198 199 200 201 202 203 204 205

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
206 207 208
    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
209 210 211 212 213

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

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

Jan Möbius's avatar
Jan Möbius committed
214 215 216
    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
217 218 219

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

220
    set_min_roundness( value_type(std::min(r1,r2)), true );
Jan Möbius's avatar
Jan Möbius committed
221 222 223 224
  }

  /** Set a minimum roundness value.
   *  \param _min_roundness in range (0,1)
225
   *  \param _binary Set true, if the binary mode should be enabled,
Jan Möbius's avatar
Jan Möbius committed
226
   *                 else false. In latter case the collapse_priority()
227
   *                 returns a float value if the constraint does not apply
Jan Möbius's avatar
Jan Möbius committed
228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252
   *                 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
  //
253
  //      radius of circumference
Jan Möbius's avatar
Jan Möbius committed
254 255 256
  // R := -----------------------
  //      length of shortest edge
  //
257
  //       ||a|| * ||b|| * ||c||
Jan Möbius's avatar
Jan Möbius committed
258 259 260 261 262 263 264 265 266 267
  //       ---------------------
  //             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
268
  // R� = ----------------------------------------------------------
Jan Möbius's avatar
Jan Möbius committed
269 270 271 272 273 274
  //       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 )
  //
275
  // At angle 60� R has it's minimum for all edge lengths = sqrt(1/3)
Jan Möbius's avatar
Jan Möbius committed
276
  //
277
  // Define normalized roundness
Jan Möbius's avatar
Jan Möbius committed
278 279 280 281 282 283 284 285 286 287 288
  //
  // 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);

289
    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
290 291 292 293 294 295 296 297 298 299 300 301 302 303

    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 );
304
    double denom = aa * bb * cc;
Jan Möbius's avatar
Jan Möbius committed
305 306 307 308 309
    double nR    = sqrt43 * sqrt(nom/denom);

    return nR;
  }

310 311
  private:

Jan Möbius's avatar
Jan Möbius committed
312 313 314 315 316 317 318 319 320 321 322 323 324
  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
//=============================================================================
325
#endif // OPENMESH_DECIMATER_MODROUNDNESST_HH defined
Jan Möbius's avatar
Jan Möbius committed
326 327
//=============================================================================