GraphGenerator.cpp

Go to the documentation of this file.

// *****************************************************************
// Filename:    GraphGenerator.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:        08.07.2008
// *****************************************************************
 
#include "GraphGenerator.h"
 
vector<Vec3d> CGraphGenerator::m_Vertices;
vector<Face> CGraphGenerator::m_Faces;
 
 
void CGraphGenerator::generateGraph(CSphericalGraph* pPlainGraph, EPolyhedronType nBaseType, int nLevels, float fRadius)
{
    initBasePolyhedron(nBaseType);
    projectToSphere(fRadius);
 
    for (int L = 0 ; L < nLevels ; L++)
    {
        subDivide();
        projectToSphere(fRadius);
    }
 
    buildNodesAndEdges(pPlainGraph);
}
 
void CGraphGenerator::initBasePolyhedron(EPolyhedronType nBaseType)
{
    m_Vertices.clear();
    m_Faces.clear();
 
    switch (nBaseType)
    {
        case eTetrahedron:
            generateTetrahedron();
            break;
 
        case eOctahedron:
            generateOctahedron();
            break;
 
        case eIcosahedron:
            generateIcosahedron();
            break;
 
        default:
            printf("Wrong base type\n");
            break;
    }
}
 
void CGraphGenerator::generateTetrahedron()
{
    // vertices of a tetrahedron
    float fSqrt3 = sqrt(3.0);
    Vec3d v[4];
 
    Math3d::SetVec(v[0], fSqrt3, fSqrt3, fSqrt3);
    Math3d::SetVec(v[1], -fSqrt3, -fSqrt3, fSqrt3);
    Math3d::SetVec(v[2], -fSqrt3, fSqrt3, -fSqrt3);
    Math3d::SetVec(v[3], fSqrt3, -fSqrt3, -fSqrt3);
 
    for (int i = 0 ; i < 4 ; i++)
    {
        m_Vertices.push_back(v[i]);
    }
 
    // structure describing a tetrahedron
    Face f[4];
    f[0].set(1, 2, 3);
    f[1].set(1, 4, 2);
    f[2].set(3, 2, 4);
    f[3].set(4, 1, 3);
 
    for (int i = 0 ; i < 4 ; i++)
    {
        f[i].m_n1--;
        f[i].m_n2--;
        f[i].m_n3--;
        m_Faces.push_back(f[i]);
    }
}
 
void CGraphGenerator::generateOctahedron()
{
    // Six equidistant points lying on the unit sphere
    Vec3d v[6];
    Math3d::SetVec(v[0], 1, 0, 0);
    Math3d::SetVec(v[1], -1, 0, 0);
    Math3d::SetVec(v[2], 0, 1, 0);
    Math3d::SetVec(v[3], 0, -1, 0);
    Math3d::SetVec(v[4], 0, 0, 1);
    Math3d::SetVec(v[5], 0, 0, -1);
 
    for (int i = 0 ; i < 6 ; i++)
    {
        m_Vertices.push_back(v[i]);
    }
 
    // Join vertices to create a unit octahedron
    Face f[8];
    f[0].set(1, 5, 3);
    f[1].set(3, 5, 2);
    f[2].set(2, 5, 4);
    f[3].set(4, 5, 1);
    f[4].set(1, 3, 6);
    f[5].set(3, 2, 6);
    f[6].set(2, 4, 6);
    f[7].set(4, 1, 6);
 
    for (int i = 0 ; i < 8 ; i++)
    {
        f[i].m_n1--;
        f[i].m_n2--;
        f[i].m_n3--;
        m_Faces.push_back(f[i]);
    }
}
 
void CGraphGenerator::generateIcosahedron()
{
    // Twelve vertices of icosahedron on unit sphere
    float tau = 0.8506508084;
    float one = 0.5257311121;
 
    Vec3d v[12];
 
    Math3d::SetVec(v[0], tau, one, 0);
    Math3d::SetVec(v[1], -tau, one, 0);
    Math3d::SetVec(v[2], -tau, -one, 0);
    Math3d::SetVec(v[3], tau, -one, 0);
    Math3d::SetVec(v[4], one, 0, tau);
    Math3d::SetVec(v[5], one, 0, -tau);
    Math3d::SetVec(v[6], -one, 0, -tau);
    Math3d::SetVec(v[7], -one, 0, tau);
    Math3d::SetVec(v[8], 0, tau, one);
    Math3d::SetVec(v[9], 0, -tau, one);
    Math3d::SetVec(v[10], 0, -tau, -one);
    Math3d::SetVec(v[11], 0, tau, -one);
 
    for (int i = 0 ; i < 12 ; i++)
    {
        m_Vertices.push_back(v[i]);
    }
 
 
    // Structure for unit icosahedron
    Face f[20];
    f[0].set(5,  8,  9);
    f[1].set(5, 10,  8);
    f[2].set(6, 12,  7);
    f[3].set(6,  7, 11);
    f[4].set(1,  4,  5);
    f[5].set(1,  6,  4);
    f[6].set(3,  2,  8);
    f[7].set(3,  7,  2);
    f[8].set(9, 12,  1);
    f[9].set(9,  2, 12);
    f[10].set(10,  4, 11);
    f[11].set(10, 11, 3);
    f[12].set(9,  1,  5);
    f[13].set(12,  6,  1);
    f[14].set(5,  4, 10);
    f[15].set(6, 11,  4);
    f[16].set(8,  2,  9);
    f[17].set(7, 12,  2);
    f[18].set(8, 10, 3);
    f[19].set(7,  3, 11);
 
    for (int i = 0 ; i < 20 ; i++)
    {
        f[i].m_n1--;
        f[i].m_n2--;
        f[i].m_n3--;
        m_Faces.push_back(f[i]);
    }
}
 
void CGraphGenerator::subDivide()
{
    // buffer new faces
    vector<Face> faces;
 
    // gp through all faces and subdivide
    for (int f = 0 ; f < int(m_Faces.size()) ; f++)
    {
        // get the triangle vertex indices
        int nA = m_Faces.at(f).m_n1;
        int nB = m_Faces.at(f).m_n2;
        int nC = m_Faces.at(f).m_n3;
 
        // get the triangle vertex coordinates
        Vec3d a = m_Vertices.at(nA);
        Vec3d b = m_Vertices.at(nB);
        Vec3d c = m_Vertices.at(nC);
 
        // Now find the midpoints between vertices
        Vec3d a_m, b_m, c_m;
        Math3d::AddVecVec(a, b, a_m);
        Math3d::MulVecScalar(a_m, 0.5, a_m);
        Math3d::AddVecVec(b, c, b_m);
        Math3d::MulVecScalar(b_m, 0.5, b_m);
        Math3d::AddVecVec(c, a, c_m);
        Math3d::MulVecScalar(c_m, 0.5, c_m);
        /*      printf("a: %f,%f,%f\n", a.x,a.y,a.z);
                printf("b: %f,%f,%f\n", b.x,b.y,b.z);
                printf("c: %f,%f,%f\n", c.x,c.y,c.z);
 
                printf("a<->b: %f,%f,%f\n", a_m.x,a_m.y,a_m.z);
                printf("b<->c: %f,%f,%f\n", b_m.x,b_m.y,b_m.z);
                printf("c<->a: %f,%f,%f\n", c_m.x,c_m.y,c_m.z);*/
 
        // add vertices
        int nA_m, nB_m, nC_m;
 
        int nIndex;
        nIndex = findVertex(a_m, 0.01);
 
        if (nIndex == -1)
        {
            m_Vertices.push_back(a_m);
            nA_m = m_Vertices.size() - 1;
        }
        else
        {
            nA_m = nIndex;
        }
 
        nIndex = findVertex(b_m, 0.01);
 
        if (nIndex == -1)
        {
            m_Vertices.push_back(b_m);
            nB_m = m_Vertices.size() - 1;
        }
        else
        {
            nB_m = nIndex;
        }
 
        nIndex = findVertex(c_m, 0.01);
 
        if (nIndex == -1)
        {
            m_Vertices.push_back(c_m);
            nC_m = m_Vertices.size() - 1;
        }
        else
        {
            nC_m = nIndex;
        }
 
        // Create new faces with orig vertices plus midpoints
        Face f[4];
        f[0].set(nA, nA_m, nC_m);
        f[1].set(nA_m, nB, nB_m);
        f[2].set(nC_m, nB_m, nC);
        f[3].set(nA_m, nB_m, nC_m);
 
        for (int i = 0 ; i < 4 ; i++)
        {
            faces.push_back(f[i]);
        }
    }
 
    // assign new faces
    m_Faces = faces;
}
 
void CGraphGenerator::projectToSphere(float fRadius)
{
    TSphereCoord coord;
    Vec3d point;
    coord.fDistance = 1.0f;
 
    for (int v = 0 ; v < int(m_Vertices.size()) ; v++)
    {
        float X = m_Vertices.at(v).x;
        float Y = m_Vertices.at(v).y;
        float Z = m_Vertices.at(v).z;
 
        float x, y, z;
 
        // Convert Cartesian X,Y,Z to spherical (radians)
        float theta = atan2(Y, X);
        float phi   = atan2(sqrt(X * X + Y * Y), Z);
 
        // Recalculate X,Y,Z for constant r, given theta & phi.
        x = fRadius * sin(phi) * cos(theta);
        y = fRadius * sin(phi) * sin(theta);
        z = fRadius * cos(phi);
 
        m_Vertices.at(v).x = x;
        m_Vertices.at(v).y = y;
        m_Vertices.at(v).z = z;
    }
}
 
void CGraphGenerator::buildNodesAndEdges(CSphericalGraph* pGraph)
{
    // add nodes
    TSphereCoord coord;
 
    for (int v = 0 ; v < int(m_Vertices.size()) ; v++)
    {
        //      printf("Vertex: %f,%f,%f\n", m_Vertices.at(v).x, m_Vertices.at(v).y, m_Vertices.at(v).z);
        MathTools::convert(m_Vertices.at(v), coord);
        CSGNode* pNode = pGraph->getNewNode();
        pNode->setPosition(coord);
        pGraph->addNode(pNode);
    }
 
    // add edges
    // go through all faces (assumes check for duplicate edges in spherical graph!?)
    for (int f = 0 ; f < int(m_Faces.size()) ; f++)
    {
        //      printf(" %d,%d,%d\n", m_Faces.at(f).m_n1, m_Faces.at(f).m_n2, m_Faces.at(f).m_n3);
        pGraph->addEdge(m_Faces.at(f).m_n1, m_Faces.at(f).m_n2);
        pGraph->addEdge(m_Faces.at(f).m_n2, m_Faces.at(f).m_n3);
        pGraph->addEdge(m_Faces.at(f).m_n3, m_Faces.at(f).m_n1);
    }
}
 
int CGraphGenerator::findVertex(Vec3d position, float fEpsilon)
{
    float fDistance;
    float fMinDistance = FLT_MAX;
    int nIndex = -1;
 
    for (int v = 0 ; v < int(m_Vertices.size()) ; v++)
    {
        fDistance = Math3d::Angle(position, m_Vertices.at(v));
 
        if (fDistance < fMinDistance)
        {
            fMinDistance = fDistance;
            nIndex = v;
        }
    }
 
    if (fMinDistance > fEpsilon)
    {
        nIndex = -1;
    }
 
    return nIndex;
}