CustomHeap.h

// CostHeap class interface
//
// CContractionPtr: must have zero-parameter constructor and operator=;
//     must have operator<
// CONSTRUCTION: with (a) CContractionPtr representing negative infinity
// Copy construction of CostHeap objects is DISALLOWED
// Deep copy is supported
//
// ******************PUBLIC OPERATIONS******************
// void Insert( CContractionPtr X ) --> Insert X
// CContractionPtr FindMin( )       --> Return smallest item
// void DeleteMin( )      --> Remove smallest item
// void DeleteMin( CContractionPtr & X ) --> Same, but put it in X
// int IsEmpty( )         --> Return 1 if empty; else return 0
// int IsFull( )          --> Return 1 if full; else return 0
// void MakeEmpty( )      --> Remove all items
// void Toss( CContractionPtr X )   --> Insert X (lazily)
// void FixHeap( )        --> Reestablish heap order property
// ******************ERRORS*****************************
// Predefined exception is propogated if new fails
// EXCEPTION is called for FindMin or DeleteMin when empty
 
#ifndef __COSTHEAP_H
#define __COSTHEAP_H
 
#ifndef PLY_CONFIG
#error PolygonCruncherConfig.h is not included
#endif
 
#include "3DFaceList.h"
#include "3DPointList.h"
 
BEGIN_MOOTOOLS_NAMESPACE
 
typedef enum {
    UNDEFINED_OPTIMAL = 0,
    INVERSEMATRIX_OPTIMAL = 1, // This means matrix contraction is optimal
    LINE_OPTIMAL, // This means line contraction is optimal
    POINT1_OPTIMAL, // This means that Point1() is optimal
    POINT2_OPTIMAL, // This means that Point2() is optimal
    // last value is 4. It cannot be greater than 7
} CONTRACTION_TYPE;
 
// the type is ordered by order of priority
typedef enum
{
    MINIMUM_CONTRACTION_PRIORITY = 0,       // Always the first pair of the heap
    DEFAULT_CONTRACTION_PRIORITY,           // Should be removed at least
    FLAT_TRIANGLE_CONTRACTION_PRIORITY, // Pair contraction generate a triangle which is nearly flat
    FLIP_FACE_CONTRACTION_PRIORITY, // Make a face being flipped => very bad
    // Very important: Last is 3 which is the maximal possible value
    // (Look MAKE_CONTRACTION_INFO)
} CONTRACTION_PRIORITY;
 
typedef enum
{
    X = 0,
    Y,
    Z
} PAIR_XYZ;
 
// Order is a simple way found to scramble the same cost pairs
// this avoid to make optimize around the same group of faces if they have the same cost
// and gives better optimization results.
// Optimization process optimizes same costs pairs regularly on the whole object
 
// it is coded the following way:  111      111      11
//                                order  position priority
#define SET_CONTRACTION_INFO(type, priority) ((unsigned char)((type << 2) + priority))
#define SET_CONTRACTION_PRIORITY(info, priority) ((unsigned char)((info & 0xFC) | (priority & 0x03)))
#define SET_CONTRACTION_ORDER(info, order) ((unsigned char)((info & 0x1F)|(unsigned char)((order) << 5)))
 
#define GET_CONTRACTION_PRIORITY(info) ((unsigned char)(info & 0x03))
#define GET_CONTRACTION_TYPE(info) ((unsigned char)((info >> 2) & 0x07))
#define GET_CONTRACTION_ORDER(info) ((unsigned char)(info >> 5))
 
class CContractionCost;
class CInitialCost : public C3DEdge
{
    friend CContractionCost;
 
protected:
    real cost;
 
    union
    {
        real pos[3]; // The position of the new point (GetPosition() == INVERSEMATRIX_OPTIMAL)
        double linecoef; // The colinear factor (GetPosition() < INVERSEMATRIX_OPTIMAL), use double as sizeof(double)<real pos[3]
    };
 
    unsigned char info;
 
public:
#ifdef MOOTOOLS_PRIVATE_DEBUG
    real exactpos[3];
#endif
 
#ifdef MOOTOOLS_PRIVATE_DEBUG
    CInitialCost();
#endif
 
    real GetCost() const;
    void SetCost(double newcost);
 
    void InitContraction(CONTRACTION_TYPE type, CONTRACTION_PRIORITY priority);
    
    CONTRACTION_TYPE GetType() const;
    void SetPriority(CONTRACTION_PRIORITY priority);
    CONTRACTION_PRIORITY GetPriority() const;
    void SetOrder(unsigned char value);
    unsigned char GetOrder() const;
    double GetLineCoef() const;
 
    // Linecoef is the moving coef along edge(point1, point2).
    // Linecoef = 0.0f the new pos == point2
    // Linecoef = 1.0f the new pos == point1
    void SetLineCoef(double value);
    void SetPos(const C3DPoint& pt);
 
#ifdef MOOTOOLS_PRIVATE_DEBUG
    // 10 01 2012 : GetRemainingIndex code change. Check everything OK. Could be removed
    int PrevGetRemainingIndex();
    int PrevGetReplacedIndex();
#endif
 
    // If linecoef = 0.0 (POINT2_OPTIMAL) or linecoef = 1.0f (POINT1_OPTIMAL) the point does not moves.
    // In this case the remaining index is the point which does not moves.
    // this allows to minimize the CTrackInfo size because we only have to update UV and normals of the faces which own the replaced index.
    //
    // If linecoef > 0.0 && linecoef < 1.0, the remaining index must be point1 and the replaced index must be point2
    int GetRemainingIndex();
    int GetReplacedIndex();
 
    void GetPos(C3DPoint *newpos, C3DPointList *points) const;
};
 
#ifndef MOOTOOLS_NO_INLINE
inline real CInitialCost::GetCost() const
{
    return cost;
}
 
inline void CInitialCost::SetCost(double newcost)
{
    cost = (real)newcost;
}
 
inline void CInitialCost::InitContraction(CONTRACTION_TYPE type, CONTRACTION_PRIORITY priority)
{
    info = SET_CONTRACTION_INFO(type, priority);
    #ifdef MOOTOOLS_PRIVATE_DEBUG
    if (type >= LINE_OPTIMAL)
        linecoef = -1.0; // Check that it was called in GetLineCoef
    #endif
}
 
inline CONTRACTION_TYPE CInitialCost::GetType() const
{
    MOOTOOLS_PRIVATE_ASSERT(GET_CONTRACTION_TYPE(info) >= UNDEFINED_OPTIMAL && GET_CONTRACTION_TYPE(info) <= POINT2_OPTIMAL);
    return (CONTRACTION_TYPE)GET_CONTRACTION_TYPE(info);
}
 
inline void CInitialCost::SetPriority(CONTRACTION_PRIORITY priority)
{
    info = SET_CONTRACTION_PRIORITY(info, priority);
}
 
inline CONTRACTION_PRIORITY CInitialCost::GetPriority() const
{
    MOOTOOLS_PRIVATE_ASSERT(GET_CONTRACTION_PRIORITY(info) >= MINIMUM_CONTRACTION_PRIORITY && GET_CONTRACTION_PRIORITY(info) <= FLIP_FACE_CONTRACTION_PRIORITY);
    return (CONTRACTION_PRIORITY)GET_CONTRACTION_PRIORITY(info);
}
 
inline void CInitialCost::SetOrder(unsigned char value)
{
    info = SET_CONTRACTION_ORDER(info, value);
}
 
inline unsigned char CInitialCost::GetOrder() const
{
    return GET_CONTRACTION_ORDER(info);
}
 
inline double CInitialCost::GetLineCoef() const
{
    MOOTOOLS_PRIVATE_ASSERT(GetType() >= LINE_OPTIMAL); // Other values give incorrect results
    MOOTOOLS_PRIVATE_ASSERT(linecoef != -1.0 && linecoef >= 0.0 && linecoef <= 1.0); // SetLineCoef must have been called
    return linecoef;
}
 
// Linecoef is the moving coef along edge(point1, point2).
// Linecoef = 0.0f the new pos == point2
// Linecoef = 1.0f the new pos == point1
inline void CInitialCost::SetLineCoef(double value)
{
    MOOTOOLS_PRIVATE_ASSERT(GetType() >= LINE_OPTIMAL); // Need to be set only for LINE_OPTIMAL
    MOOTOOLS_PRIVATE_ASSERT(value >= 0.0 && value <= 1.0); // SetLineCoef must have been called
    linecoef = value;
}
 
inline void CInitialCost::SetPos(const C3DPoint& pt)
{
    MOOTOOLS_PRIVATE_ASSERT(GetType() == INVERSEMATRIX_OPTIMAL); // Need to be set only for INVERSEMATRIX_OPTIMAL
    memcpy(pos, pt.ValPtr(), 3 * sizeof(real));
}
 
// If linecoef = 0.0 (POINT2_OPTIMAL) or linecoef = 1.0f (POINT1_OPTIMAL) the point does not moves.
// In this case the remaining index is the point which does not moves.
// this allows to minimize the CTrackInfo size because we only have to update UV and normals of the faces which own the replaced index.
//
// If linecoef > 0.0 && linecoef < 1.0, the remaining index must be point1 and the replaced index must be point2
inline int CInitialCost::GetRemainingIndex()
{
    if (GetType() == POINT2_OPTIMAL)
    {
        MOOTOOLS_PRIVATE_ASSERT(linecoef == 0.0f);
        MOOTOOLS_PRIVATE_ASSERT(point2 == PrevGetRemainingIndex());
        return point2;
    }
 
    MOOTOOLS_PRIVATE_ASSERT(point1 == PrevGetRemainingIndex());
    return point1;
}
 
inline int CInitialCost::GetReplacedIndex()
{
    if (GetType() == POINT2_OPTIMAL)
    {
        MOOTOOLS_PRIVATE_ASSERT(linecoef == 0.0f);
        MOOTOOLS_PRIVATE_ASSERT(point1 == PrevGetReplacedIndex());
        return point1;
    }
 
    MOOTOOLS_PRIVATE_ASSERT(point2 == PrevGetReplacedIndex());
    return point2;
}
#endif // MOOTOOLS_NO_INLINE
 
class CContractionCost : public CInitialCost    
{
public:
    CContractionCost **heapPtr;
 
    bool operator < (const CContractionCost& refcost) const;
 
#ifdef MOOTOOLS_PRIVATE_DEBUG
    void Dump() const;
#endif
};
 
#ifndef MOOTOOLS_NO_INLINE
inline bool CContractionCost::operator < (const CContractionCost& refcost) const
{
    // If priority the same, compare cost
    if (GET_CONTRACTION_PRIORITY(info) == GET_CONTRACTION_PRIORITY(refcost.info))
    {
        if (cost == refcost.cost)
        {
            if (GET_CONTRACTION_ORDER(info) == GET_CONTRACTION_ORDER(refcost.info))
            {
                if (GET_CONTRACTION_TYPE(info) == GET_CONTRACTION_TYPE(refcost.info))
                {
                    // 03/21 : #669
                    // sorting on index allow to have an optimization that remains stable between different optimization on different system (max, standalone...)
                    if (point1 == refcost.point1)
                        return point2 < refcost.point2;
 
                    return point1 < refcost.point1;
                }
 
                return GET_CONTRACTION_TYPE(info) < GET_CONTRACTION_TYPE(refcost.info); // Element that had a matrix or line contraction are first sorted
            }
 
            return GET_CONTRACTION_ORDER(info) < GET_CONTRACTION_ORDER(refcost.info); // Element that were not already moved are first sorted
        }
 
        return cost < refcost.cost;
    }
 
    // Element with lower priority are first sorted
    return GET_CONTRACTION_PRIORITY(info) < GET_CONTRACTION_PRIORITY(refcost.info);
}
#endif // MOOTOOLS_NO_INLINE
 
class C3DExtObject;
class CostHeap
{
  public:
        // Constructor, destructor, and copy assignment
    CostHeap();
    virtual ~CostHeap();
 
    void Free();
 
    void InitHeap(const CContractionCost *, unsigned int, C3DExtObject *);
 
#ifdef MOOTOOLS_PRIVATE_DEBUG
    unsigned int GetPermutation();
    void CheckOrder();
    const CostHeap &CopyForDump( const CostHeap & Rhs );
    void Dump();
#endif
 
        // Add an item maintaining heap order
    CContractionCost **Insert(CContractionCost *X);
 
    // Delete minimum item in heap
    void DeleteMin(CContractionCost *&X );
 
    // Remove an entry
    unsigned int GetSize();
    CContractionCost *GetAt(unsigned int i);
 
    void RemoveAt(CContractionCost **X );
 
    int IsEmpty() const;
    int IsFull() const;
    void MakeEmpty();
 
    // Internal routines
private:
    unsigned int MaxSize;         // Number of elements that can be stored (Allocate : MaxSize+1)
    unsigned int CurrentSize;     // Number of elements currently stored
    int OrderOK;         // Zero if heap order is not guaranteed
    CContractionCost **Array;        // Dynamically allocated array
    CContractionCost lowestVal; // The smaller possible value
 
#ifdef MOOTOOLS_PRIVATE_DEBUG
    C3DExtObject *object; // to update cost position
    unsigned int permutation;
#endif
 
    void PercolateDown( unsigned int Index );
    void GetArray( unsigned int NewMaxSize );  // Allocate array
};
 
#ifndef MOOTOOLS_NO_INLINE
inline CContractionCost *CostHeap::GetAt(unsigned int i)
{
    MOOTOOLS_PRIVATE_ASSERT(i < CurrentSize);
    return Array[i];
}
#endif // MOOTOOLS_NO_INLINE
 
END_MOOTOOLS_NAMESPACE
 
#endif // __COSTHEAP_H