Track.cpp

Go to the documentation of this file.

/* Copyright © 2009, 2010 James Legg.
    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 3 of the License, or
    (at your option) any later version.
*/
#include "Track.h"

#include "stream_loader.h"
#include "FormErrors.h"

#include <Debug.h>

/* gcc >= 4.3 Depreciates hash_set & hash_map, causing warnings to be emited when
 * including boost graph library headers.
 * We don't need the hash-based storage selectors anyway, so turn them off.
 */
#define BOOST_NO_HASH
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#undef BOOST_NO_HASH

#include <cmath>

const unsigned int track_newest_version = 3;

namespace Track
{

Track::Track(std::istream & source, const Theme & theme, bool editor_in)
    :   file_version(int_from_stream(source))
    ,   theme(theme)
    ,   path(source, theme, this, editor_in)
    ,   editor(editor_in)
{
    if (file_version == 0) throw CorruptedError();
    if (file_version == 3) m_lighting = Lighting(source);
    if (file_version > track_newest_version) throw NewVersionError();
    // version 1 contained some extra information, but we can ignore it
    // since it would have been at the end of the file.
    scan_theme();
}

Track::Track(const Theme & theme, bool editor_in)
    :   file_version(0)
    ,   theme(theme)
    ,   path(theme, this, editor_in)
    ,   editor(editor_in)
{
    scan_theme();
}


Track::~Track()
{
    
}

const Path & Track::get_path() const
{
    return path;
}

Path & Track::get_path()
{
    return path;
}

std::ostream & operator<<(std::ostream & destination, const Track & track)
{
    destination << track_newest_version << ' ';
    destination << track.path << ' ' << track.get_lighting() << ' ';
    // the space at the end of the file prevents an error reading the last
    // number. end of file is not end of number, apparently.
    return destination;
}

const Theme & Track::get_theme() const
{
    return theme;
}

template <class A>
class CollisionDeallocator
{
    public:
        CollisionDeallocator(A *mesh)
            :   m_mesh(mesh)
            {};
        template <class T>
        void operator ()(T shape)
        {
            delete shape;
            delete m_mesh;
        }
    private:
        A *m_mesh;
    
};

boost::shared_ptr<btCollisionShape> Track::get_collision_shape() const
{
    btTriangleMesh *  shape = new btTriangleMesh;
    path.add_collision_faces(*shape);
    
    boost::shared_ptr<btCollisionShape> result(new btBvhTriangleMeshShape(shape, true),
                                               CollisionDeallocator<btTriangleMesh>(shape));
    return result;
}

boost::shared_ptr<btCollisionShape> Track::get_floor_shape() const
{
    btTriangleMesh * shape = new btTriangleMesh;
    path.add_floor_faces(*shape);
    boost::shared_ptr<btCollisionShape> result(new btBvhTriangleMeshShape(shape, true),
                                               CollisionDeallocator<btTriangleMesh>(shape));
    return result;
}

const MeshFaces & Track::get_ai_mesh() const
{
    return m_ai_mesh;
}

void Track::update_ai_mesh()
{
    // reset incase this was used before a change.
    DEBUG_MESSAGE("Finding AI navigation mesh.");
    m_ai_mesh = MeshFaces();
    path.add_ai_faces(m_ai_mesh);
    // Merge vertices near each other, so the mesh can be navigated cleanly
    // by the AI cars.
    m_ai_mesh.merge_doubles();
    
    // Find the connectivity graph.
    scan_ai_graph();
    m_ai_graph = m_ai_mesh.get_connectivity();
}

struct EdgeProperties
{
    float distance;
};

void Track::scan_ai_graph()
{
    /* We want to set the u texture coordinate to a number indicating how far
     * into a lap a position is. This number is called lap_position.
     * 0.0 means the start of the lap. lap_position should vary linearly with
     * distance from the start.
     * We create a graph related to the navigation graph to run dijkstra's
     * algorithm on. We use the minimum distances assigned to each node as the
     * lap_position.
     * The new graph is a variation on the graph of connected vertices on the
     * ai mesh. The vertices along the starting plane are split so that faces
     * on either side of the starting plane are not connected across the
     * starting plane.
     * A source node is created which has 0 distance to all vertices along the
     * starting plane connecting with faces infront of it. Similarly, a sink
     * node is created with 0 distance to the nodes in the starting plane
     * connecting with faces behind it. This way position along the starting
     * plane doesn't matter, and it doesn't mess with ordering cars near the
     * starting plane.
     *
     * A possible improvement to this algorithm would take note of splits
     * where the paths are very different lengths. Currently this sort of
     * thing could happen:
     *  |  6  |
     *  |5 ^ 7| < goes backwards here. The long path should be scaled down so
     *  | | \8\                        that lap_position varies between
     *  |4|  \8\                       the values at the start and end of the
     *  | |   \7\                      split section.
     *  |3|    \6\
     *  | |    /5/
     *  |2|   /4/
     *  | |  /3/
     *  |1| /2/
     *  |  _ 1|
     *  |0   0|
     * 
     *  You could say this would be bad level design, but if the short path
     *  requires going much slower than the long path, or the long path
     *  provides an additional benifit (e.g. pit lane), the track could be
     *  well balanced and still suffer from this.
     * 
     * This could be done with a graph layout algorithm, though care must be
     * taken to insure the starting vertices stay at 0 and the ending vertices
     * have the largest value.
     */
    DEBUG_MESSAGE("scan_ai_graph: Getting vertex graph");
    MeshFaces::VertexGraph graph = m_ai_mesh.get_vertex_graph();
    // Add source and sink.
    MeshFaces::VertexGraph::vertex_descriptor source_descriptor;
    {
        source_descriptor = boost::add_vertex(graph);
        DEBUG_MESSAGE("Source node is " << source_descriptor);
    }
    MeshFaces::VertexGraph::vertex_descriptor sink_descriptor;
    {
        sink_descriptor = boost::add_vertex(graph);
        DEBUG_MESSAGE("Sink node is " << sink_descriptor);
    }
    
    // split start and end vertices, which lie along the start/finish plane.
    // First, what is the plane?
    btVector3 start_point = path.find_start_position();
    btVector3 start_plane_normal;
    btScalar start_plane_distance;
    path.find_start_plane(start_plane_normal, start_plane_distance);
    // Find the vertices we want.
    std::vector<MeshFaces::VertexGraph::vertex_descriptor> start_vertices;
    std::pair<MeshFaces::VertexGraph::vertex_iterator,
              MeshFaces::VertexGraph::vertex_iterator> its;
    for (its = boost::vertices(graph); its.first != its.second; its.first++)
    {
        MeshFaces::VertexGraph::vertex_descriptor vertex = *(its.first);
        btVector3 position = graph[vertex];
        // find distance from plane.
        btScalar to_plane = start_plane_normal.dot(position) + start_plane_distance;
        if (std::abs(to_plane) < 0.001)
        {
            // close enough to start plane to be in it.
            // Is it near enough to the start, or is it somewhere in the distance?
            if (start_point.distance2(position) < 289.0)
            {
                // It will do.
                start_vertices.push_back(vertex);
                DEBUG_MESSAGE("Vertex " << vertex << " is on the start plane, distance^2=" << to_plane << ".");
            }
        }
    }
    // add copies of the vertices found to the graph.
    std::vector<MeshFaces::VertexGraph::vertex_descriptor> finish_vertices;
    for (std::vector<MeshFaces::VertexGraph::vertex_descriptor>::iterator it = start_vertices.begin();
         it != start_vertices.end();
         it++)
    {
        finish_vertices.push_back(boost::add_vertex(graph[*it], (graph)));
        DEBUG_MESSAGE("Vertex " << finish_vertices.back() << " is the end of track equivalent to vertex " << *it);
    }
    // now work out which edges should be moved from start to finish.
    std::vector<MeshFaces::VertexGraph::vertex_descriptor>::iterator start_it, finish_it;
    for (start_it = start_vertices.begin(), finish_it = finish_vertices.begin();
         start_it != start_vertices.end();
         start_it++, finish_it++)
    {
        typedef MeshFaces::VertexGraph::out_edge_iterator OutEdgeIterator;
        std::pair<OutEdgeIterator, OutEdgeIterator> its;
        for (its = boost::out_edges(*start_it, graph);
             its.first != its.second;
             its.first++)
        {
            // which side of the plane does this edge take it?
            MeshFaces::VertexGraph::vertex_descriptor target = boost::target(*(its.first), graph);
            // which side of the plane?
            btScalar plane_distance = start_plane_normal.dot(graph[target]) + start_plane_distance;
            if (plane_distance < -0.001)
            {
                // behind the plane. Move the edge to the other side.
                DEBUG_MESSAGE("Moving edge " << *(its.first) << " from start vertex " << *start_it << " to finish vertex " << *finish_it << ".");
                boost::add_edge(*finish_it, target, graph[*(its.first)], graph);
                boost::remove_edge(*(its.first), graph);
                // edge iterators invalidated. Start again.
                its = boost::out_edges(*start_it, graph);
            }
        }
    }
    // Link up start to source vertex.
    for (std::vector<MeshFaces::VertexGraph::vertex_descriptor>::iterator it = start_vertices.begin();
         it != start_vertices.end();
         it++)
    {
        // Use a large length to prevent the shortest path of nearby nodes
        // going backwards.
        boost::add_edge(source_descriptor, *it, MeshFaces::FaceEdgePointers(0, 0, 0, 100.0), graph);
    }
    // Link up finish to sink vertex.
    for (std::vector<MeshFaces::VertexGraph::vertex_descriptor>::iterator it = finish_vertices.begin();
         it != finish_vertices.end();
         it++)
    {
        boost::add_edge(sink_descriptor, *it, MeshFaces::FaceEdgePointers(0, 0, 0, 0.0), graph);
    }
    
    /* Now we have the graph we want. Lets find the minimal distance to each
     * vertex from the sink node.
     */
    std::vector<MeshFaces::VertexGraph::vertex_descriptor> predecessors(boost::num_vertices(graph));
    std::vector<btScalar> distances(boost::num_vertices(graph));
    boost::dijkstra_shortest_paths(graph, sink_descriptor,
        boost::weight_map(get(&MeshFaces::FaceEdgePointers::length, graph)).
        predecessor_map(&predecessors[0]).distance_map(&distances[0])
        );
    // The length of the lap is the shortest distance from end to finish,
    // without the 100m length of the connections to the source node.
    m_lap_length = distances[source_descriptor] - 100.0;
    /* Now we want to put the distances back into the mesh.
     * We use the u coordinate for face vertices.
     * The same vertex will appear on multiple faces. Normally each vertex has
     * only one value, but the vertices in start_vertices get 0 for the faces
     * infront of the start plane and distances[sink_descriptor] behind it.
     */
    // For each edge, set the right distances on each end.
    std::pair<MeshFaces::VertexGraph::edge_iterator,
              MeshFaces::VertexGraph::edge_iterator> edge_its;
    btScalar end_cut_off = m_lap_length / 2.0;
    for (edge_its = boost::edges(graph); edge_its.first != edge_its.second; edge_its.first++)
    {
        MeshFaces::VertexGraph::edge_descriptor edge = *(edge_its.first);
        MeshFaces::FaceEdgePointers & fep = graph[edge];
        // Each face vertex is set twice due to the edges both sides of it.
        if (fep.source)
        {
            if ((    boost::source(edge, graph) > sink_descriptor
                  || boost::target(edge, graph) > sink_descriptor)
                && distances[fep.source->vertex_index] > end_cut_off)
            {
                // Must be a copy of a starting vertex placed on the end.
                // This edge connects to the end of the course.
                fep.source->texture_coord_u = m_lap_length;
            }
            else
            {
                fep.source->texture_coord_u = m_lap_length - distances[fep.source->vertex_index];
            }
        }
        if (fep.target)
        {
            if ((   boost::target(edge, graph) > sink_descriptor
                  || boost::source(edge, graph) > sink_descriptor)
                && distances[fep.target->vertex_index] > end_cut_off)
            {
                // Must be a copy of a starting vertex placed on the end.
                // This edge connects to the end of the course.
                fep.target->texture_coord_u = m_lap_length;
            }
            else
            {
                fep.target->texture_coord_u = m_lap_length - distances[fep.target->vertex_index];
            }
        }
    }
    DEBUG_MESSAGE("Track is " << m_lap_length << "m long.");
}

const MeshFaces::Graph & Track::get_ai_graph() const
{
    return m_ai_graph;
}

btScalar Track::get_lap_length() const
{
    return m_lap_length;
}

void Track::set_filename(std::string filename_in)
{
    filename = filename_in;
}

std::string Track::get_filename() const
{
    return filename;
}

void Track::scan_theme()
{
    if (!editor) return;
    std::size_t range = theme.get_number_of_segments();
    for (std::size_t index = 0; index < range; index++)
    {
        const_cast<DrawableMesh&>(theme.get_segment(index).get_graphics_mesh().get_faces()).set_render_mode(DrawableMesh::RM_WIREFRAME);
    }
}

const Lighting & Track::get_lighting() const
{
    return m_lighting;
}

void Track::set_lighting(const Lighting & lighting)
{
    m_lighting = lighting;
}

};

---

Generated at Mon Sep 6 00:41:12 2010 by Doxygen version 1.4.7 for Racer version svn335.