AnimaL

Tutorial

Documentation

---

Documentation

• Overview
• Modules
• Namespace List
• Class Hierarchy
• Alphabetical List
• Compound List
• File List
• Namespace Members
• Compound Members
• File Members
• Examples

---

Octree.cpp

Go to the documentation of this file.

/***************************************************************************
                          x3d_octree.cpp  -  description
                             -------------------
    begin                : Tue Mar 23 2004
    copyright            : (C) 2004 by Mathieu Coquerelle
    email                : mathieu.coquerelle@imag.fr
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   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.                                   *
 *                                                                         *
 ***************************************************************************/


#include "Octree.h"
#include "ConstrainedVertex.h"
#include "SFVec3fCellConstrained.h"
//#include "ParametersCalculus.h"
// #include "Vec3.h"
// #include "ConstrainedVertex.h"
// #include "fastoctreedeformableconstrained.cpp"

#include <set>
using std::set
    ;


#include "DirectManipulation.h"


namespace animal
{
namespace octree
{
// //template class FastOc
// template class FastOctree<OctreeVertex,OctreeData,Vec3d>
// ;

static int _globalPositionMethod;


Vec3d getFirstVertexParametersInCell( Cell *cStart, Cell *cEnd )
{
    Cell *curCell = cStart;
    Vec3d params;

    while( curCell != cEnd )
    {
        if( (curCell->fatherPos()%2) != 0 )
            params[0] += 1.0;
        if( (curCell->fatherPos()%4) >= 2 )
            params[1] += 1.0;
        if( curCell->fatherPos() >= 4 )
            params[2] += 1.0;

        params /= 2.0;

        curCell = curCell->father();
    }

    return params;
}





unsigned short getVertexPositionInCell( ConstrainedVertex *cv, Cell *cell )
{
    unsigned short vId;
    for( vId=0 ; vId<8 ; ++vId )
    {
        if( cell->vertex(vId) == cv )
        {
            break;
        }
    }
    Require( vId != 8 );

    return vId;
}



Cell* getVertexFreeCell( Cell* cStart, const ConstrainedVertex* cv )
{
    Require( cStart->isLeaf() );
    Require( cv->isFree() );

    //std::cerr << "getVert exFreeCell : searching for " << cv->getMainCellVertexId() << " in cell " << *cStart << "\n";

    bool stop = false;

    Cell * cell = cStart;

    while( !stop )
    {
        //std::cerr << "\tCell = " << *cell << "\n";
        Require( cell != NULL );

        //std::cerr << "\tCell is   " << *cell << "\n";

        unsigned short vId;
        for( vId=0 ; vId<8 ; ++vId )
        {
            //std::cerr << "\tvId = " << vId << " and vertex is : " << cell->vertex(vId) << "\n";
            if( cell->vertex(vId) == cv )
            {
                break;
            }
        }

        if( vId == 8 )
        {
            //continue to father's cell
            cell = cell->father();
        }
        else
        {
            Cell *neighbours[3];
            std::vector<unsigned short> nonNullNeighbourDir;

            // Ok we've find it, but look if's it's a "free cell"
            unsigned short dir;
            for( dir=0 ; dir<3 ; ++dir )
            {
                neighbours[dir] = cell->uncleSharingFace( TempOctree::verticesConnectedFaces[vId][dir] );
                if( neighbours[dir] != NULL )
                {
                    nonNullNeighbourDir.push_back( dir );
                    if( neighbours[dir]->getData()._depth < cell->getData()._depth )
                    {
                        // It's constrained
                        break;
                    }
                }
            }

            if( dir == 3 )
            {
                // Ok, wee got every non NULL neighbours at the same depth
                if( nonNullNeighbourDir.size() <= 1 )
                {
                    // Ok it's a free cell
                    stop = true;
                }
                else if( nonNullNeighbourDir.size() == 2 )
                {
                    // Get the diagonal neighbour
                    Cell *dNeighbour = neighbours[ nonNullNeighbourDir[0] ]->uncleSharingFace( TempOctree::verticesConnectedFaces[ Cell::connectedVertices[vId][nonNullNeighbourDir[0]] ][nonNullNeighbourDir[1]] );
                    if( dNeighbour->getData()._depth == cell->getData()._depth )
                    {
                        stop = true;
                    }
                    else
                    {
                        cell = cell->father();
                    }
                }
                else
                {
                    // we have 3 diagonal cells, test each of them
                    Cell *dNeighbours[3];
                    dNeighbours[0] = neighbours[ 0 ]->uncleSharingFace( TempOctree::verticesConnectedFaces[ Cell::connectedVertices[vId][0] ][1] );
                    dNeighbours[1] = neighbours[ 0 ]->uncleSharingFace( TempOctree::verticesConnectedFaces[ Cell::connectedVertices[vId][0] ][2] );
                    dNeighbours[2] = neighbours[ 1 ]->uncleSharingFace( TempOctree::verticesConnectedFaces[ Cell::connectedVertices[vId][1] ][2] );
                    if( dNeighbours[0]->getData()._depth == cell->getData()._depth &&
                            dNeighbours[1]->getData()._depth == cell->getData()._depth &&
                            dNeighbours[2]->getData()._depth == cell->getData()._depth
                      )
                    {
                        stop = true;
                    }
                    else
                    {
                        cell = cell->father();
                    }
                }
            }
            else
            {
                cell = cell->father();
            }
        }
        //std::cerr << "Next iteration\n";
    }

    Ensure( cell != NULL );
    return cell;
}





std::map<ConstrainedVertex*,Vec3d> getWeightsHash( Cell *cell, ConstrainedVertex *vertex, unsigned short vId )
{
    //std::cerr << "Cell is " << *cell << " and vId is " << vId << "\n";

    std::map<ConstrainedVertex*,Vec3d> resMap;

    // Make the local cell parameters coordinates
    resMap[vertex] = Vec3d(0,0,0);
    for( unsigned short dir=0 ; dir<3 ; ++dir )
    {
        Vec3d val(0,0,0);
        val[dir] = 1;
        resMap[cell->vertex(TempOctree::Cell::connectedVertices[vId][dir])] = val;
    }
    resMap[cell->vertex(7-vId)] = Vec3d(1,1,1);
    for( unsigned short dir=0 ; dir<3 ; ++dir )
    {
        Vec3d val(1,1,1);
        val[dir] = 0;
        resMap[cell->vertex(TempOctree::Cell::connectedVertices[7-vId][dir])] = val;
    }

    if( cell->isLeaf() )
    {
        return resMap;
    }


    /*
     * vertexChildPos[v][0] gives our associated father's child position for the vertex v
     * vertexChildPos[v][1] gives the ID of the vertex in vertexChildPos[v][0] father's child
     */

    static const unsigned short vertexChildPos[27][2] =
        {
            {
                0,0
            }
            , {0,1}, {1,1}, {0,2}, {0,3}, {1,3}, {2,2}, {2,3}, {3,3},
            {0,4}, {0,5}, {1,5}, {0,6}, {0,7}, {1,7}, {2,6}, {2,7}, {3,7},
            {4,4}, {4,5}, {5,5}, {4,6}, {4,7}, {5,7}, {6,6}, {6,7}, {7,7}
        };



    /*
     * vertexOnEdge[e][4] gives :
     *     [0] : the Id of the point in 0..26
     *     [1] : the direction of the edge (0,1 or 2)
     *     [2] : the Id of its father1
     *     [3] : the Id of its father2
     */
    static const unsigned short vertexOnEdge[12][4] =
        {
            {
                1,0,0,2
            }
            , {7,0,6,8},    {19,0,18,20},   {25,0,24,26},
            {3,1,0,6}, {5,1,2,8},   {21,1,18,24},   {23,1,20,26},
            {9,2,0,18}, {11,2,2,20}, {15,2,6,24},{17,2,8,26}
        };

    static const unsigned short vertexOnFace[6][6] =
        {
            {
                4,2,1,3,5,7
            }
            , {22,2,19,21,23,25},
            {12,0,3,21,9,15}, {14,0,5,23,11,17},
            {10,1,1,19,9,11}, {16,1,7,25,15,17}
        };



    //std::cerr << "Cell is " << *cell << " vId is " << vId << " and vertex : " << vertex << "\n";




    //std::cerr << "Cell is " << *cell << " vId is " << vId << " and vertex : " << vertex << "\n";
    /*
    for( unsigned short i=0 ; i<8 ; ++i )
    {
        std::cerr << "\tfor vertex " << i << " val is " << resMap[cell->vertex(i)] << "\n";
    }
    */

    std::list<Cell*> cellQueue;
    cellQueue.push_back(cell);

    {
        ConstrainedVertex *vertices[27];

        for( unsigned short i=0 ; i<27 ; ++i )
        {
            vertices[i] = cell->child( vertexChildPos[i][0] )->vertex( vertexChildPos[i][1] );
        }

        Cell *it = cellQueue.front();
        cellQueue.pop_front();

        Require( !it->isLeaf() );
        // Compute the parameters for the children's vertices

        // First the edges
        for( unsigned short e=0 ; e<12 ; ++e )
        {
            //std::cerr << "\tOn edge " << e << " vertex is " << vertexOnEdge[e][0] << "\n";
            unsigned short vEId = vertexOnEdge[e][0];
            ConstrainedVertex *cv = vertices[vEId];

            ConstrainedVertex *father1 = vertices[ vertexOnEdge[e][2] ];
            ConstrainedVertex *father2 = vertices[ vertexOnEdge[e][3] ];

            //std::cerr << "\t\tFathers are : " << vertexOnEdge[e][2] << " and " << vertexOnEdge[e][3] << "\n";
            //std::cerr << "\t\t for values : " << resMap[father1] << " and " << resMap[father2] << "\n";

            resMap[cv] = 0.5*(resMap[father1]+resMap[father2]);

            if( cv->isFree() )
            {
                resMap[cv][vertexOnEdge[e][1]] = 1;
            }
            else
            {
            }

            //std::cerr << "\t\tRes : " << resMap[cv] << "\n";
        }

        // Then the faces
        for( unsigned short f=0 ; f<6 ; ++f )
        {
            unsigned short vFId = vertexOnFace[f][0];
            ConstrainedVertex *cv = vertices[vFId];

            //std::cerr << "\tOn face " << f << " vertex is " << vertexOnFace[f][0] << "\n";
            if( cv->isFree() )
            {
                resMap[cv] = Vec3d(1,1,1);
            }
            else
            {
                ConstrainedVertex *fathers[4];

                for( unsigned short i=0 ; i<4 ; ++i )
                {
                    fathers[i] = vertices[ vertexOnFace[f][2+i] ];
                }

                resMap[cv] = 0.25 * (resMap[fathers[0]]+resMap[fathers[1]]+resMap[fathers[2]]+resMap[fathers[3]]);
            }
            //std::cerr << "\t\tRes : " << resMap[cv] << "\n";
        }

        // Always free !
        resMap[ it->child(0)->vertex(7) ] = Vec3d(1,1,1);

        for( unsigned short c=0 ; c<8 ; ++c )
        {
            if( !it->child(c)->isLeaf() )
            {
                cellQueue.push_back(it->child(c));
            }
        }
    }


    //std::cerr << "Cell is " << *cell << "\n";
    while( !cellQueue.empty() )
    {
        Cell *it = cellQueue.front();
        cellQueue.pop_front();
        Require( !it->isLeaf() );

        //std::cerr << "\tnew cell : " << *it << "\n";

        ConstrainedVertex *vertices[27];

        for( unsigned short i=0 ; i<27 ; ++i )
        {
            vertices[i] = it->child( vertexChildPos[i][0] )->vertex( vertexChildPos[i][1] );
        }

        //std::cerr << "\tcomputing for cell " << *it << "\n";

        // Compute the parameters for the children's vertices

        // First the edges
        for( unsigned short e=0 ; e<12 ; ++e )
        {

            unsigned short vEId = vertexOnEdge[e][0];
            ConstrainedVertex *cv = vertices[vEId];

            //std::cerr << "\tOn edge " << e << " vertex is " << vertexOnEdge[e][0] << " (ptr " << cv << ")\n";
            ConstrainedVertex *father1 = vertices[ vertexOnEdge[e][2] ];
            ConstrainedVertex *father2 = vertices[ vertexOnEdge[e][3] ];

            resMap[cv] = 0.5*(resMap[father1]+resMap[father2]);

            if( cv->isFree() )
            {
                resMap[cv][vertexOnEdge[e][1]] = 1;
            }

        }

        // Then the faces
        // First the edges
        for( unsigned short f=0 ; f<6 ; ++f )
        {
            unsigned short vFId = vertexOnFace[f][0];
            ConstrainedVertex *cv = vertices[vFId];

            if( cv->isFree() )
            {
                resMap[cv] = Vec3d(1,1,1);
            }
            else
            {
                ConstrainedVertex *fathers[4];

                for( unsigned short i=0 ; i<4 ; ++i )
                {
                    fathers[i] = vertices[ vertexOnFace[f][2+i] ];
                }

                resMap[cv] = 0.25 * (resMap[fathers[0]]+resMap[fathers[1]]+resMap[fathers[2]]+resMap[fathers[3]]);
            }
        }

        // Always free !
        resMap[ it->child(0)->vertex(7) ] = Vec3d(1,1,1);

        for( unsigned short c=0 ; c<8 ; ++c )
        {
            if( !it->child(c)->isLeaf() )
            {
                cellQueue.push_back(it->child(c));
            }
        }

    }

    //std::cerr << "Cell is " << *cell << " and vId is " << vId << "End\n\n";

    return resMap;
}






void printOctree( Cell *cell, unsigned int depth )
{
    char pref[depth+1];
    for( unsigned int i=0 ; i<depth ; ++i )
    {
        pref[i] = '\t';
    }
    pref[depth] = '\0';

    std::cerr << pref << "Cell=" << *cell << "\n";
    for( unsigned int i=0;i<8 ; ++i )
    {
        std::cerr << pref << "\tvertex[" << i << "] is ";
        if( !cell->vertex(i)->isFree() )
            std::cerr << "not ";
        std::cerr << "free\n";
    }

    if( !cell->isLeaf() )
    {
        for( unsigned int i=0 ; i<8 ; ++i )
            printOctree( cell->child(i), depth+1 );
    }
}




































Octree::Octree( Vec3d bboxMin, Vec3d bboxMax, MFVec3f *points, MFVec3f normals, unsigned int nMaxPointsPerCell ) :
        TempOctree( bboxMin, bboxMax.x-bboxMin.x, bboxMax.y-bboxMin.y, bboxMax.z-bboxMin.z),
        _nMaxPointsPerCell(nMaxPointsPerCell),
        _optionPositionMethod( LINEAR ),
    _freeFrames(false),
    _DMMethod(OCTREE_DM_NOTHING)
{
    Require( getNMaxPointsPerCell() != 0 );

    std::cerr << "There are " << points->size() << " points to put in the octree\n";

    std::deque<SFVec3f*> pointsPointers;
    for( MFVec3f::iterator it = points->begin() ; it != points->end() ; ++it )
    {
        pointsPointers.push_back( &(*it) );
    }



    root()->getData()._depth = 0; // depth 0
    root()->getData()._initialSize = bboxMax - bboxMin;

    //      updateFrames(root());

    //
    // Now add the vertices in the cell
    //
    int vertexID = 0;

    MFVec3f::iterator itN = normals.begin();
    for(    std::deque<SFVec3f*>::iterator it = pointsPointers.begin() ;
            it != pointsPointers.end() ;
            ++it, ++itN
       )
    {
        root()->getData()._points.push_back( new SFVec3fCellConstrained(*it,root(),vertexID,*itN) );

        for( unsigned short i=0 ; i<8 ; ++i )
        {
            root()->getData()._points.back()->setRelativeWeight( root()->vertex(i), SFVec3fCellConstrained::computeWeight( root()->getData()._points.back()->getParameters(i), LOCAL_SKINNING ) );
            root()->getData()._points.back()->setInitNormalRelativeWeight( root()->vertex(i), SFVec3fCellConstrained::computeWeight( root()->getData()._points.back()->getInitNormalParameters(i), LOCAL_SKINNING ) );
        }

        vertexID++;
    }

    /*
    //
    // Now subdivide the octree if necessary
    //
    */

    int nCells;
    nCells = createOctree( root() );
    std::cerr << "There are " << nCells << " cells in the octree\n";

    structureChangedRecLeaves( root() );
    updateVertexInformations( root() );


}

Octree::~Octree( )
{
    std::cerr << "~Octree()\n";
}



void Octree::setDMMethod( int method )
{
    std::cerr << "Octree::setDMMethod( " << method << " )\n";
    Require( (method == OCTREE_DM_NOTHING) || (method == OCTREE_DM_VERTICES) || (method == OCTREE_DM_FRAMES) || (method == (OCTREE_DM_FRAMES|OCTREE_DM_VERTICES)) );
    _DMMethod = method;
}

void Octree::setFreeFrames( bool b )
{
    _freeFrames = b;
}






/*
 * The depth information is allready filled for cell
 */
int Octree::createOctree( Cell *cell )
{

    if( cell->getData()._points.size() <= getNMaxPointsPerCell() )
    {
        return 1;
    }
    else
    {
        subdivideDeformed( cell );

        int acc = 0;
        for( unsigned int i=0 ; i<8 ; ++i )
        {
            acc += createOctree( cell->child(i) );
        }

        return acc;
    }
}




unsigned int Octree::getNMaxPointsPerCell()
{
    return _nMaxPointsPerCell;
}

void Octree::setNMaxPointsPerCell(unsigned int n)
{
    Require( n != 0 );
    _nMaxPointsPerCell = n;
    this->updateHierarchy( root() );
}




void Octree::updateHierarchy( Cell *cell )
{

    unsigned nPoints = cell->getData()._points.size();

    if( cell->isLeaf() && (nPoints > getNMaxPointsPerCell()) )
    {
        this->subdivideDeformed( cell );

        for( unsigned int i=0 ; i<8 ; ++i )
        {
            updateHierarchy( cell->child(i) );
        }

    }
    else if( !cell->isLeaf() && (nPoints <= getNMaxPointsPerCell()) )
    {
        //          std::cerr << "Simplyfing : " << nPoints << " for max " << getNMaxPointsPerCell() << "\n";
        cell->simplify();
    }
    else if( !cell->isLeaf() )
    {
        for( unsigned int i=0 ; i<8 ; ++i )
        {
            updateHierarchy( cell->child(i) );
        }
    }
}



void Octree::setPositionMethod( int m )
{
    _optionPositionMethod = m;

    // Clear some informations due to some techniques
    for( Cell::vertex_width_iterator it(root()) ; !it.empty() ; )
    {
        ConstrainedVertex *cv = ++it;
        cv->setDelta( Vec3d(0,0,0) );
    }
}
int Octree::getPositionMethod() const
{
    return _optionPositionMethod;
}










void Octree::subdivideDeformed( Cell *cell )
{
    Require( cell->isLeaf() );

    cell->subdivide();
    Ensure( !cell->isLeaf() );
    
 // Now make the depth data
    for( unsigned int i=0 ; i<8 ; ++i )
    {
        // Update the depth data
        cell->child(i)->getData()._depth = cell->getData()._depth + 1;
        cell->child(i)->getData()._initialSize = cell->getData()._initialSize / 2.0;
    }
        
    {
        static const float childNodesParams[19][3] =
    {
        // z-
        { 0.5, 0.0, 0.0 },
        { 0.0, 0.5, 0.0 },
        { 0.5, 0.5, 0.0 },
        { 1.0, 0.5, 0.0 },
        { 0.5, 1.0, 0.0 },
        
        // z = 0
        { 0.0, 0.0, 0.5 },
        { 0.5, 0.0, 0.5 },
        { 1.0, 0.0, 0.5 },
        { 0.0, 0.5, 0.5 },
        { 0.5, 0.5, 0.5 },
        { 1.0, 0.5, 0.5 },
        { 0.0, 1.0, 0.5 },
        { 0.5, 1.0, 0.5 },
        { 1.0, 1.0, 0.5 },
        
        // z+
        { 0.5, 0.0, 1.0 },
        { 0.0, 0.5, 1.0 },
        { 0.5, 0.5, 1.0 },
        { 1.0, 0.5, 1.0 },
        { 0.5, 1.0, 1.0 }
    };
    
    static const unsigned short cellsChildrenVertices[19][2] =
        {
        {0,1}, {0,2}, {0,3}, {1,3}, {2,3},
                {0,4}, {0,5}, {1,5}, {0,6}, {0,7}, {1,7}, {2,6}, {2,7}, {3,7},
                {4,5}, {4,6}, {4,7}, {5,7}, {6,7}
            };
    
    SFVec3fCellConstrained vec = **(cell->getData()._points.begin());
    for( unsigned int i=0 ; i<19 ; ++i )
    {
        unsigned short childId = cellsChildrenVertices[i][0];
        unsigned short vertId = cellsChildrenVertices[i][1];

        cell->child(childId)->vertex(vertId)->_lastConstrainedDepth = cell->child(childId)->vertex(vertId)->getMainCell()->getData()._depth-1;
        
        if( haveFreeFrames() && cell->child(childId)->vertex(vertId)->isFree() )
        {
            Vec3d v;
            
            vec.setParams( Vec3d( childNodesParams[i][0], childNodesParams[i][1], childNodesParams[i][2]) );
            vec.updateSkinningInformations( cell->getData()._influence );
            v = vec.computePosition( LOCAL_SKINNING );
            
            
            cell->child(childId)->vertex(vertId)->setPosition( v );
            v = cell->child(childId)->vertex(vertId)->getPosition();
            
            std::vector<Vec3d> frameVecs = vec.computeDerivative();
            
//          std::cerr << "For point " << i << " and params " << vec.getLocalParams() << " frames are :\n";
//          std::cerr << "\t" << frameVecs[0] << "\n";
//          std::cerr << "\t" << frameVecs[1] << "\n";
//          std::cerr << "\t" << frameVecs[2] << "\n";
            float factor = 1.0;
            cell->child(childId)->vertex(vertId)->getFrame() = Frame( v, frameVecs[0]/factor, frameVecs[1]/factor, frameVecs[2]/factor );
            
            
            
//          std::cerr << "For point " << i << " got depth " << cell->child(childId)->vertex(vertId)->_lastConstrainedDepth << "\n";
        }
    }
    
    }
    
    

   

    // Now put each point in an OctreeDataPoints structur for children
    for( OctreeDataPoints::iterator it = cell->getData()._points.begin() ; it != cell->getData()._points.end() ; ++it )
    {
        Vec3d initParams = (*it)->getLocalParams();

        /*
         * Put it in the good child
         */
        unsigned int childPos = 0;
        if( initParams[0] > 0.5 )
        {
            childPos += 1;
            initParams[0] = (initParams[0] - 0.5)*2.0;
        }
        else
            initParams[0] *= 2.0;

        if( initParams[1] > 0.5 )
        {
            childPos += 2;
            initParams[1] = (initParams[1] - 0.5)*2.0;
        }
        else
            initParams[1] *= 2.0;

        if( initParams[2] > 0.5 )
        {
            childPos += 4;
            initParams[2] = (initParams[2] - 0.5)*2.0;
        }
        else
        {
            initParams[2] *= 2.0;
        }

        cell->child(childPos)->getData()._points.push_back( new SFVec3fCellConstrained( (*it)->getSFVec3f() , cell->child(childPos), initParams, (*it)->getVertexID(), (*it)->getInitNormal() ) );
    }
    
}


void Octree::subdivideRecDeformed( Cell *cell )
{
    for( dfs_leaf_iterator it( cell ) ; !it.empty() ; )
    {
        Cell *tmpCell = ++it;

        if( tmpCell->isLeaf() && tmpCell->getData()._points.size() != 0 )
        {
            subdivideDeformed( tmpCell );
        }
    }

    structureChangedRecLeaves(root());
    movedRecLeaves(root());
    

}







void Octree::movedRecLeaves( Cell *cell )
{
    if( !haveFreeFrames() )
    {
        updateFrames(cell);
    }
    if( this->getPositionMethod() == GLOBAL_LINEAR )
    {
        SFVec3fCellConstrained::globalLinearUpdatePositions( cell );
    }
    else
    {
        _globalPositionMethod = this->getPositionMethod();
        for( dfs_leaf_iterator it( cell, moved ) ; !it.empty() ; ++it )
            ;
    }
}
void Octree::moved( Cell *cell )
{
    OctreeDataPoints *points = &(cell->getData()._points);
    for( OctreeDataPoints::iterator it = points->begin() ; it != points->end() ; ++it )
    {
        (*it)->updatePosition( _globalPositionMethod );
    }
}





void Octree::structureChangedRecLeaves( Cell *cell )
{
/*    updateFrames(cell);*/
    if( !haveFreeFrames() )
    {
        updateFrames(cell);
        
        Cell::vertex_width_iterator it( cell );
        
        while( !it.empty() )
        {
            Vertex* v= ++it;
            if( v->isFree() )
            {
                v->_lastConstrainedDepth = v->getConstrainedDepth();
            }
        }
    }
    else
    {
        Cell::vertex_width_iterator it( cell );
        
        while( !it.empty() )
        {
            Vertex* v= ++it;
            if( v->isFree() )
            {
                float factor = 1.0;
                float depthFactor = 2.0;
                
                Frame &f = v->getFrame();
                
                unsigned int cDepth = v->getConstrainedDepth();
//              std::cerr << "For vertex " << *(v->getMainCell()) << " Id " << v->getMainCellVertexId() <<
//                  " depth was " << v->_lastConstrainedDepth << " got : " << cDepth << "\n";
                if( cDepth < v->_lastConstrainedDepth )
                {
                    factor = pow( depthFactor, (v->_lastConstrainedDepth-cDepth) );
                }
                else if( cDepth > v->_lastConstrainedDepth )
                {
                    factor = 1.0 / pow( depthFactor, (cDepth-v->_lastConstrainedDepth) );
                }
                 v->_lastConstrainedDepth = cDepth;
                
                f.setOrigin( v->getPosition() );
                f.setVector( 0, f.getVector(0)*factor);
                f.setVector( 1, f.getVector(1)*factor );
                f.setVector( 2, f.getVector(2)*factor );
            }
        }   
    }
    
    for( dfs_leaf_iterator it( cell, structureChanged ) ; !it.empty() ; ++it )
        ;
}
void Octree::structureChanged( Cell *cell )
{
    //updateFrame(cell);
    updateInfluenceMaps( cell );
    updateVertexInformations( cell );
}










void Octree::updateVertexInformationsRec( Cell *cell )
{
    for( dfs_iterator it( cell, NULL, updateVertexInformations, NULL ) ; !it.empty() ; ++it )
        ;
}

void Octree::updateVertexInformationsRecLeaves( Cell *cell )
{
    for( dfs_leaf_iterator it( cell, updateVertexInformations ) ; !it.empty() ; ++it )
        ;
}


void Octree::updateVertexInformations( Cell *cell )
{
    for( OctreeDataPoints::iterator it=cell->getData()._points.begin() ; it!=cell->getData()._points.end() ; ++it )
    {
        (*it)->updateSkinningInformations( cell->getData()._influence );
    }
}





void Octree::simplify( Cell *cell )
{
    if( !cell->isLeaf() )
    {
        cell->simplify();

        structureChangedRecLeaves( root() );

//         updateFrame( root() );
//  if( !haveFreeFrames() )
//  {
//      updateFrame( root() );
//  }

        updateInfluenceMapsRecLeaves( root() );
        updateVertexInformationsRecLeaves( root() );
        movedRecLeaves( root() );
    }
}







void Octree::updateFrame( Cell *cell )
{
    for( unsigned short i=0 ; i<8 ; ++i )
    {
        cell->vertex(i)->updateFrame();
    }
}



void Octree::updateFrames( Cell *cell )
{
    Cell::vertex_width_iterator it( cell );

    while( !it.empty() )
    {
        Vertex* v= ++it;
        if( v->isFree() )
        {
            v->updateFrame();
        }
    }
}





void Octree::updateFrames( ConstrainedVertex* vertex, Cell *cell, unsigned int vPos  )
{
    Cell::vertex_width_neighbours_iterator it( vertex, cell, vPos );

    // Do remove this
    set <Cell*> cellList;

    while( !it.empty() )
    {
        Vertex* v= ++it;
        v->updateFrame();

        for( unsigned int i=0 ; i<v->nConnectedCells() ; ++i )
        {
            if( v->connectedCell(i)->getData()._depth == v->getDepth() )
            {
                cellList.insert(v->connectedCell(i));
            }
        }
    }
    /*
    for( set<Cell*>::iterator it=cellList.begin() ; it != cellList.end() ; ++it )
    {
        this->updateCellsData( *it );
    }
    */
}





void Octree::updateCellsData( Cell *cell )
{
    std::cerr << "Don't iuse this\n";
    exit(0);
    if( cell->isLeaf() )
    {
        //std::cerr << "Ok leaf\n";
        OctreeDataPoints *points = &(cell->getData()._points);
        unsigned int nPoints=0;
        for( OctreeDataPoints::iterator it = points->begin() ; it != points->end() ; ++it )
        {
            (*it)->updatePosition( this->getPositionMethod() );
            nPoints++;
        }
        //std::cerr << "Have updated " << nPoints << " points\n";
    }
    else
    {
        for( unsigned int i=0 ; i < 8 ; ++i )
            updateCellsData( cell->child(i) );
    }
}












void Octree::updateInfluenceMapsRecLeaves( Cell *cell )
{
    for( dfs_leaf_iterator it( cell, updateInfluenceMaps ) ; !it.empty() ; ++it )
        ;
}



void Octree::updateInfluenceMaps( Cell *cell )
{
    // First get the list of freeVertices
    //
    std::set
        <ConstrainedVertex*> freeVertices = ConstrainedVertex::getFreeParentVertices( cell );

    //
    // Now fill the influencemaps
    //
    CellInfluenceData cid;
    unsigned int nfreeVertices = freeVertices.size();

    cid.influenceMaps.resize(nfreeVertices);
    cid.vertices.resize(nfreeVertices);
    cid.verticesId.resize(nfreeVertices);
    cid.parents.resize(nfreeVertices);
    cid.firstCellVertexParameters.resize(nfreeVertices);

    //std::cerr << "\n\nUPDATECELL : " << *cell << "\n";

    unsigned int i=0;
    // Now freeVertices contains the list of intereting vertices
    // Find the _cell's parent cell that is of same depth of each free vertex
    // And compute the parameters in this cell
    for( std::set
                <ConstrainedVertex*>::iterator it=freeVertices.begin() ; it!=freeVertices.end() ; ++it )
        {
            //std::cerr << "\tI is " << i << " and vertex is " << *it << "\n";
            cid.vertices[i] = *it;
            cid.parents[i] = (void*)getVertexFreeCell( cell, (*it) );

            /*
            std::cerr << "Gloppy\n";
            cid.parents[i] = (void*)getVertexFreeCell( (*it)->getMainCell(), (*it) );
            std::cerr << "the cell is " << *(Cell*) cid.parents[i] << "\n";
            std::cerr << "the cell would be " << *getVertexFreeCell( cell, (*it) ) << "\n";
            */

            cid.verticesId[i] = getVertexPositionInCell(*it,(Cell*)cid.parents[i]);

            //std::cerr << "\tVertex id is " << cid.verticesId[i] << " and cell : " << *((Cell*)cid.parents[i])<< "\n";

            // Now get the parameter of "cell's" vertex(0) in the parent cell
            cid.firstCellVertexParameters[i] = getFirstVertexParametersInCell( cell, (Cell*)cid.parents[i] );

            cid.influenceMaps[i] = getWeightsHash( (Cell*)cid.parents[i], *it, cid.verticesId[i] );

            i++;
        }

    cell->getData()._influence = cid;
}





void Octree::directManipulation( SFVec3fCellConstrained* vertex, Vec3d newPosition )
{
    Cell *cell = vertex->getCell();
    std::vector<FloatingPointType> weights;
    
    X3DTK::SFVec3f *sf = vertex->getSFVec3f();
    Vec3d deltaQ = newPosition - Vec3d( sf->x, sf->y, sf->z );
    
    std::vector<Vec3d> deltaP;
    
//  std::cerr << "Moving vertex " << Vec3d( sf->x, sf->y, sf->z ) << " at position " << newPosition << "\n";
//  std::cerr << "Delta Q is " << deltaQ << "\n";

    switch( this->getPositionMethod() )
    {
        case LINEAR:
        {
            Vec3d localParams = vertex->getLocalParams();
            
            for( unsigned int i=0 ; i<8 ; ++i )
            {
                weights.push_back( vertex->computeWeight( vertex->getParameters(i), LINEAR ) );
            }
            
            deltaP = computeDirectManipulationResultPseudoInverse( weights, deltaQ );
            
            for( unsigned int i=0 ; i<8 ; ++i )
            {
                cell->vertex(i)->setPositionAndPropagate( cell->vertex(i)->getPosition()+deltaP[i] );
            }
        }
        break;
        
        case LOCAL_SKINNING:
        {
            std::vector<ConstrainedVertex*> framesVertices;
            std::vector<Vec3d> relPos;
            
            CellInfluenceData cid = cell->getData()._influence;
            
            for( unsigned int i=0 ; i<cid.vertices.size() ; ++i )
                    {
                weights.push_back( vertex->getRelativeWeight( cid.vertices[i] ) );
                relPos.push_back( vertex->getRelativePosition(cid.vertices[i]) );
                framesVertices.push_back( cid.vertices[i] );
            }
            
            if( _DMMethod == OCTREE_DM_VERTICES )
            {
                if( !haveFreeFrames() )
                {
                    
                    // results stored here
                    vector<ConstrainedVertex*> verticesToMove;
        
                    computeDirectManipulationSkinning(
                        deltaQ, weights, relPos, framesVertices, // in data
                        verticesToMove, deltaP ); // results here
                
                    unsigned int i=0;
                    for( vector<ConstrainedVertex*>::iterator it=verticesToMove.begin() ;
                        it!=verticesToMove.end() ;
                        ++it )
                    {
                        (*it)->setPositionAndPropagate( (*it)->getPosition() + deltaP[i] );
                        ++i;
                    }
                }
                else
                {
                    // results stored here
                    // Will have <dPi>
                    std::vector< Vec3d > deltas;
        
                    computeDirectManipulationSkinningVertices(
                        deltaQ, weights, relPos, framesVertices, // in data
                        deltas ); // results here
                    
                    unsigned int i=0;
                    for( vector<ConstrainedVertex*>::iterator it=framesVertices.begin() ;
                        it!=framesVertices.end() ;
                        ++it )
                    {
                        Frame &f = (*it)->getFrame();
                        f.setOrigin( f.getOrigin()+ deltas[i++] );
                        (*it)->setPositionAndPropagate( f.getOrigin() );
                    }
                }
            }
            else if( _DMMethod == OCTREE_DM_FRAMES )
            {
                Require( haveFreeFrames() );
                
                // results stored here
                // <Ui' Vi' Wi'>
                // for each frames of the "framesVertices" vector
                std::vector< std::vector<Vec3d> > deltaFrames;
    
                computeDirectManipulationSkinningFrames(
                    deltaQ, weights, relPos, framesVertices, // in data
                    deltaFrames ); // results here
            
                unsigned int i=0;
                for( vector<ConstrainedVertex*>::iterator it=framesVertices.begin() ;
                    it!=framesVertices.end() ;
                    ++it )
                {
                    Frame &f = (*it)->getFrame();
                    f.setVector( 0, f.getVector(0) + deltaFrames[i][0] );
                    f.setVector( 1, f.getVector(1) + deltaFrames[i][1] );
                    f.setVector( 2, f.getVector(2) + deltaFrames[i][2] );
                    ++i;
                }
                
            }
            else if( (_DMMethod&OCTREE_DM_FRAMES)&&(_DMMethod&OCTREE_DM_VERTICES) )
            {   
                Require( haveFreeFrames() );
                
                // results stored here
                // Will have <dPi' dUi' dVi' dWi'>
                // for each frames of the "framesVertices" vector
                std::vector< Vec3d > deltas;
    
                computeDirectManipulationSkinningVerticesAndFrames(
                    deltaQ, weights, relPos, framesVertices, // in data
                    deltas ); // results here
                
                unsigned int i=0;
                for( vector<ConstrainedVertex*>::iterator it=framesVertices.begin() ;
                    it!=framesVertices.end() ;
                    ++it )
                {
                    Frame &f = (*it)->getFrame();
                    f.setOrigin( f.getOrigin()+ deltas[i++] );
                    (*it)->setPositionAndPropagate( f.getOrigin() );
                    f.setVector( 0, f.getVector(0) + deltas[i++] );
                    f.setVector( 1, f.getVector(1) + deltas[i++] );
                    f.setVector( 2, f.getVector(2) + deltas[i++] );
                }
                
            }
            
            movedRecLeaves( root() );
            
//          std::vector<ConstrainedVertex*> framesVertices;
//          std::vector<Vec3d> relPos;
//          
//          CellInfluenceData cid = cell->getData()._influence;
//          
//          for( unsigned int i=0 ; i<cid.vertices.size() ; ++i )
//                  {
//              weights.push_back( vertex->getRelativeWeight( cid.vertices[i] ) );
//              relPos.push_back( vertex->getRelativePosition(cid.vertices[i]) );
//              framesVertices.push_back( cid.vertices[i] );
//          }
//          
//          vector<ConstrainedVertex*> verticesToMove;
//          
//          //
//          // iterative scheme
//          //
//          const double eps = 10e-8;
//          const double maxErr = 10e-4;
//          double err = INFINITY;
//          double precErr = INFINITY;
//          
//          std::vector<Vec3d> oldPositions;
//          
//          unsigned int nIt = 0;
//          do
//          {
//              precErr = err;
//              
//              computeDirectManipulationSkinning(
//                  deltaQ, weights, relPos, framesVertices, // in data
//                  verticesToMove, deltaP ); // results here
//          
//              oldPositions.clear();
//              unsigned int i=0;
//              for( vector<ConstrainedVertex*>::iterator it=verticesToMove.begin() ;
//                  it!=verticesToMove.end() ;
//                  ++it )
//              {
//                  oldPositions.push_back( (*it)->getPosition() );
//                  (*it)->setPositionAndPropagate( (*it)->getPosition() + deltaP[i] );
//                  ++i;
//              }
//              
//              movedRecLeaves( root() );
//              SFVec3f sfPos = *(vertex->getSFVec3f());
//              Vec3d curPos(sfPos.x,sfPos.y,sfPos.z);
//              
//              err = (newPosition - curPos) * (newPosition - curPos);
// //               std::cerr << "DM: for iteration " << nIt << " got err " << err << "\n";
//              
//              nIt++;
//          }
//          while( (err > eps) && (err<precErr) && (err<maxErr) );
//          
//          if( (err > precErr) || (err>maxErr) )
//          {
//              std::cerr << "\tStopping because diverging\n";
//              unsigned int i=0;
//              for( vector<ConstrainedVertex*>::iterator it=verticesToMove.begin() ;
//                  it!=verticesToMove.end() ;
//                  ++it )
//              {
//                  (*it)->setPositionAndPropagate( oldPositions[i] );
//                  ++i;
//              }   
//              
//          }
        }
        break;
    }
}






std::vector<Vec3d> Octree::getNormals() const
{
    Cell *cell = root();

    std::vector<Vec3d> result( cell->getData()._points.size() );

    unsigned int i=0;
    for( OctreeDataPoints::iterator it = cell->getData()._points.begin() ; it != cell->getData()._points.end() ; ++it )
    {
        result[i] = (*it)->getInitNormal();
        ++i;
    }

    return result;
}

OctreeDataPoints& Octree::getMeshVertices()
{
    return root()->getData()._points;
}

} // X3D

} // X3DTK

---