GraphTriangulation.cpp

Go to the documentation of this file.

// *****************************************************************
// Filename:    GraphProcessor.cpp
// Copyright:   Kai Welke, Chair Prof. Dillmann (IAIM),
//              Institute for Computer Science and Engineering (CSE),
//              University of Karlsruhe. All rights reserved.
// Author:      Kai Welke
// Date:        12.06.2007
// *****************************************************************
 
 
// *****************************************************************
// includes
// *****************************************************************
// local includes
#include "GraphTriangulation.h"
 
#include "Base/Math/MathTools.h"
#include "Base/Tools/DebugMemory.h"
#include "GraphProcessor.h"
 
void
GraphTriangulation::delaunayTriangulationQuadratic(CSphericalGraph* pGraph)
{
    TC3DNodeList* pC3DNodeList = new TC3DNodeList();
    int nNodes = (int)pGraph->getNodes()->size();
 
    for (int i = 0; i < nNodes; i++)
    {
        // project point to polar coordinates
        Vec3d cartesian_point;
        MathTools::convert(pGraph->getNode(i)->getPosition(), cartesian_point);
 
        CC3DNode* pC3DNode = new CC3DNode(cartesian_point);
        pC3DNodeList->push_back(pC3DNode);
    }
 
    // generate the delaunay triangulation by computing the
    // convex hull of the sphere
    CCHGiftWrap giftWrapping = CCHGiftWrap(pC3DNodeList);
    CSphericalGraph* pCopy = new CSphericalGraph();
    giftWrapping.generateConvexHull(pCopy);
 
    // add edges from triangulated graph to pGraph
    TEdgeList* pEdges = pCopy->getEdges();
 
    for (int e = 0; e < pEdges->size(); e++)
    {
        pGraph->addEdge(pEdges->at(e)->nIndex1, pEdges->at(e)->nIndex2);
    }
 
    delete pCopy;
}
 
void
GraphTriangulation::triangulationQuadraticSpherical(CSphericalGraph* pGraph)
{
    int nNumberViews = (int)pGraph->getNodes()->size();
 
    // create graph with nodes and nodes + 360
    CSphericalGraph* pDoubleGraph = doubleNodes(pGraph);
 
    // do triangulation on the double size graph
    //triangulationQuadratic(pDoubleGraph);
    triangulationQuartic(pDoubleGraph);
 
    // insert detrmined edges in original graph
    int nIndex1, nIndex2;
    CSGEdge* pCurrentEdge;
 
    for (int e = 0; e < int(pDoubleGraph->getEdges()->size()); e++)
    {
        pCurrentEdge = pDoubleGraph->getEdges()->at(e);
        nIndex1 = pCurrentEdge->nIndex1;
        nIndex2 = pCurrentEdge->nIndex2;
 
        // HACK: delete outer edges
        if ((pDoubleGraph->getNode(nIndex1)->getPosition().fTheta < 30.0) ||
            (pDoubleGraph->getNode(nIndex1)->getPosition().fTheta > 690.0))
        {
            continue;
        }
 
        if ((pDoubleGraph->getNode(nIndex2)->getPosition().fTheta < 30.0) ||
            (pDoubleGraph->getNode(nIndex2)->getPosition().fTheta > 690.0))
        {
            continue;
        }
 
        /*      if( (pDoubleGraph->getNode(nIndex1)->getPosition().fPhi < 30.0) || (pDoubleGraph->getNode(nIndex1)->getPosition().fPhi > 330.0))
                    continue;
                if( (pDoubleGraph->getNode(nIndex2)->getPosition().fPhi < 30.0) || (pDoubleGraph->getNode(nIndex2)->getPosition().fPhi > 330.0))
                    continue;
                if( (pDoubleGraph->getNode(nIndex1)->getPosition().fPhi < 180.0) && (pDoubleGraph->getNode(nIndex2)->getPosition().fPhi > 180.0))
                    continue;
                if( (pDoubleGraph->getNode(nIndex2)->getPosition().fPhi < 180.0) && (pDoubleGraph->getNode(nIndex1)->getPosition().fPhi > 180.0))
                    continue;
        */
        // eliminate virtual nodes
        if (nIndex1 >= nNumberViews)
        {
            nIndex1 %= nNumberViews;
        }
 
        if (nIndex2 >= nNumberViews)
        {
            nIndex2 %= nNumberViews;
        }
 
        // update graph
        if (nIndex1 != nIndex2)
            if (!GraphProcessor::isEdgePresent(pGraph, nIndex1, nIndex2))
            {
                pGraph->addEdge(nIndex1, nIndex2);
            }
    }
 
    delete pDoubleGraph;
}
 
void
GraphTriangulation::triangulationQuartic(CSphericalGraph* pGraph, float fThreshold)
{
    TNodeList* pNodes = pGraph->getNodes();
 
    int nNumberPoints = int(pNodes->size());
    bool bPointFree;
    int i, j, k, l;
 
    for (i = 0; i < nNumberPoints - 2; i++)
    {
        printf("Round %d / %d\n", i, nNumberPoints - 2);
 
        for (j = i + 1; j < nNumberPoints - 1; j++)
        {
            if (j != i)
            {
                for (k = j + 1; k < nNumberPoints; k++)
                {
                    if (k != i && k != j)
                    {
 
                        // check if this rectangle is point free
                        bPointFree = true;
 
                        for (l = 0; l < nNumberPoints; l++)
                        {
                            // only if not one of the triangle points
                            if (l != i && l != j && l != k)
                            {
                                bool bInside;
 
                                if (!GraphProcessor::insideCircumcircle(
                                        pGraph, i, j, k, l, bInside))
                                {
                                    bPointFree = false;
                                    break;
                                }
 
                                if (bInside)
                                {
                                    bPointFree = false;
                                    break;
                                }
                            }
                        }
 
                        if (bPointFree)
                        {
                            TSphereCoord p_i, p_j, p_k;
                            p_i = pNodes->at(i)->getPosition();
                            p_j = pNodes->at(j)->getPosition();
                            p_k = pNodes->at(k)->getPosition();
 
                            // add triangle
                            if (MathTools::getDistanceOnArc(p_i, p_j) < fThreshold)
                            {
                                pGraph->addEdge(i, j);
                            }
 
                            if (MathTools::getDistanceOnArc(p_i, p_k) < fThreshold)
                            {
                                pGraph->addEdge(i, k);
                            }
 
                            if (MathTools::getDistanceOnArc(p_k, p_j) < fThreshold)
                            {
                                pGraph->addEdge(k, j);
                            }
                        }
                    }
                }
            }
        }
    }
}
 
void
GraphTriangulation::triangulationQuadratic(CSphericalGraph* pGraph)
{
    TEdgeList* pEdges = pGraph->getEdges();
 
    int nCurrentEdge;
    int nFaces = 0;
    int s = 0, t = 0;
 
    // find two closest neighbours and add edge to triangulation.
    GraphProcessor::findClosestNeighbours(pGraph, s, t);
 
    // Create seed edge
    int nEdgeIndex = pGraph->addEdge(s, t, -1, -1);
 
    nCurrentEdge = 0;
 
    while (nCurrentEdge < int(pEdges->size()))
    {
        if (pEdges->at(nCurrentEdge)->nLeftFace == -1)
        {
            completeFacet(pGraph, nCurrentEdge, nFaces);
        }
 
        if (pEdges->at(nCurrentEdge)->nRightFace == -1)
        {
            completeFacet(pGraph, nCurrentEdge, nFaces);
        }
 
        nCurrentEdge++;
    }
}
 
void
GraphTriangulation::completeFacet(CSphericalGraph* pGraph, int nEdgeIndex, int nFaces)
{
    TNodeList* pNodes = pGraph->getNodes();
    TEdgeList* pEdges = pGraph->getEdges();
    int s, t, u;
 
    // Cache s and t.
    if (pEdges->at(nEdgeIndex)->nLeftFace == -1)
    {
        s = pEdges->at(nEdgeIndex)->nIndex1;
        t = pEdges->at(nEdgeIndex)->nIndex2;
    }
    else if (pEdges->at(nEdgeIndex)->nRightFace == -1)
    {
        s = pEdges->at(nEdgeIndex)->nIndex2;
        t = pEdges->at(nEdgeIndex)->nIndex1;
    }
    else
    {
        // Edge already completed.
        return;
    }
 
 
    // Find a point on left of edge.
    for (u = 0; u < int(pNodes->size()); u++)
    {
        if (u == s || u == t)
        {
            continue;
        }
 
        // check side
        float fAngle = MathTools::CalculateCrossProductFromDifference(pNodes->at(s)->getPosition(),
                                                                      pNodes->at(t)->getPosition(),
                                                                      pNodes->at(u)->getPosition());
 
        if (fAngle > 0.0)
        {
            break;
        }
    }
 
    // Find best point on left of edge.
    int nBestPoint = u;
    float fCp;
 
    if (nBestPoint < int(pNodes->size()))
    {
        TSphereCoord center;
        float fRadius;
        GraphProcessor::getCircumcircle(pGraph, s, t, nBestPoint, center, fRadius);
 
        for (u = nBestPoint + 1; u < int(pNodes->size()); u++)
        {
            if (u == s || u == t)
            {
                continue;
            }
 
            fCp = MathTools::CalculateCrossProductFromDifference(pNodes->at(s)->getPosition(),
                                                                 pNodes->at(t)->getPosition(),
                                                                 pNodes->at(u)->getPosition());
 
            if (fCp > 0.0)
            {
                bool bInside;
 
                if (GraphProcessor::insideCircumcircle(pGraph, s, t, nBestPoint, u, bInside))
                {
                    if (bInside)
                    {
                        nBestPoint = u;
                    }
                }
            }
        }
    }
 
    // Add new triangle or update edge info if s-t is on hull.
    if (nBestPoint < int(pNodes->size()))
    {
        // Update face information of edge being completed.
        updateLeftFace(pGraph, nEdgeIndex, s, t, nFaces);
        nFaces++;
 
        // Add new edge or update face info of old edge.
        nEdgeIndex = GraphProcessor::findEdge(pGraph, nBestPoint, s);
 
        if (nEdgeIndex == -1)
        {
            // New edge.
            nEdgeIndex = pGraph->addEdge(nBestPoint, s, nFaces, -1);
        }
        else
        {
            // Old edge.
            updateLeftFace(pGraph, nEdgeIndex, nBestPoint, s, nFaces);
        }
 
        // Add new edge or update face info of old edge.
        nEdgeIndex = GraphProcessor::findEdge(pGraph, t, nBestPoint);
 
        if (nEdgeIndex == -1)
        {
            // New edge.
            nEdgeIndex = pGraph->addEdge(t, nBestPoint, nFaces, -1);
        }
        else
        {
            // Old edge.
            updateLeftFace(pGraph, nEdgeIndex, t, nBestPoint, nFaces);
        }
    }
    else
    {
        updateLeftFace(pGraph, nEdgeIndex, s, t, -2);
    }
}
 
void
GraphTriangulation::updateLeftFace(CSphericalGraph* pGraph,
                                   int nEdgeIndex,
                                   int nIndex1,
                                   int nIndex2,
                                   int nFace)
{
    //  vector<TView*>* pViews = &pGraph->getAspectPool()->m_Views;
    vector<CSGEdge*>* pEdges = pGraph->getEdges();
 
    bool bValid = false;
 
    if ((pEdges->at(nEdgeIndex)->nIndex1 == nIndex1) &&
        (pEdges->at(nEdgeIndex)->nIndex2 == nIndex2))
    {
        bValid = true;
    }
 
    if ((pEdges->at(nEdgeIndex)->nIndex1 == nIndex2) &&
        (pEdges->at(nEdgeIndex)->nIndex2 == nIndex1))
    {
        bValid = true;
    }
 
    if (!bValid)
    {
        printf("updateLeftFace: adj. matrix and edge table mismatch\n");
    }
 
    if ((pEdges->at(nEdgeIndex)->nIndex1 == nIndex1) && (pEdges->at(nEdgeIndex)->nLeftFace == -1))
    {
        pEdges->at(nEdgeIndex)->nLeftFace = nFace;
    }
    else if ((pEdges->at(nEdgeIndex)->nIndex2 == nIndex1) &&
             (pEdges->at(nEdgeIndex)->nRightFace == -1))
    {
        pEdges->at(nEdgeIndex)->nRightFace = nFace;
    }
}
 
CSphericalGraph*
GraphTriangulation::doubleNodes(CSphericalGraph* pSourceGraph)
{
    // list to source views
    TNodeList* pNodes = pSourceGraph->getNodes();
    int nNumberSourceNodes = (int)pNodes->size();
 
    // add views to aspectpool
    vector<TSphereCoord> coordinates;
 
 
    for (int i = 0; i < nNumberSourceNodes; i++)
    {
        coordinates.push_back(pNodes->at(i)->getPosition());
    }
 
    TSphereCoord shiftedCoord;
 
    for (int i = 0; i < nNumberSourceNodes; i++)
    {
        shiftedCoord = pNodes->at(i)->getPosition();
        shiftedCoord.fTheta += 360.0f;
        coordinates.push_back(shiftedCoord);
    }
 
    /*  TSphereCoord shifted2Coord, shifted3Coord;
        for(int i = 0 ; i < nNumberSourceNodes ; i++)
        {
            shifted2Coord = pNodes->at(i)->getPosition();
            shifted2Coord.fPhi += 180.0f;
            coordinates.push_back(shifted2Coord);
        }
 
        for(int i = 0 ; i < nNumberSourceNodes ; i++)
        {
            shifted3Coord = pNodes->at(i)->getPosition();
            shifted3Coord.fPhi += 180.0f;
            shifted3Coord.fTheta += 360.0f;
            coordinates.push_back(shifted3Coord);
        }
    */
    CSphericalGraph* pTmpGraph = new CSphericalGraph();
 
    for (int i = 0; i < 2 * nNumberSourceNodes; i++)
    {
        CSGNode* pNode = new CSGNode(coordinates.at(i));
        pTmpGraph->addNode(pNode);
    }
 
    return pTmpGraph;
}