mesh.cpp

Go to the documentation of this file.

/*
    toxic - A Global Illumination Renderer
    Copyright (C) 2003-2004 Francois Beaune
    Contact: http://toxicengine.sourceforge.net/

    This file is part of toxic.

    toxic 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.

    toxic is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with toxic; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

#include "mesh.h"   // include first
#include "context.h"
#include "framebuffer.h"
#include "icamera.h"
#include "intersecttriangle.h"
#include "ray.h"
#include "statistics.h"
#include "triboxoverlap.h"

#include <cassert>
#include <limits>

using namespace sheep;
using namespace std;
using namespace toxic;

Mesh::Mesh(const Matrix4 &m,
           const ISurfaceShader *surface_shader,
           IntersectionMask intersection_mask /*= INTERSECT_ALL_RAYS*/) :
    IAreaLight(m, surface_shader, intersection_mask),
    m_octree(0)
{
}

Mesh::~Mesh() {
    delete m_octree;
}

Mesh::FeatureId Mesh::AppendVertex(const Point3 &v) {
    m_vertices.push_back(v);

    return static_cast<FeatureId>(m_vertices.size() - 1);
}

Mesh::FeatureId Mesh::AppendNormal(const Vector3 &n) {
    assert(n.IsUnitLength());

    m_normals.push_back(n);

    return static_cast<FeatureId>(m_normals.size() - 1);
}

Mesh::FeatureId Mesh::AppendTexCoord(const Vector2 &vt) {
    m_texcoords.push_back(vt);

    return static_cast<FeatureId>(m_texcoords.size() - 1);
}

Mesh::FeatureId Mesh::AppendTriangle(FeatureId v0, FeatureId v1, FeatureId v2) {
    triangle tri;

    tri.m_v0 = v0;
    tri.m_v1 = v1;
    tri.m_v2 = v2;

    tri.m_n0 = tri.m_n1 = tri.m_n2 = -1;    // no normals yet
    tri.m_t0 = tri.m_t1 = tri.m_t2 = -1;    // no texture coordinates yet

    m_triangles.push_back(tri);

    return static_cast<FeatureId>(m_triangles.size() - 1);
}

void Mesh::SetTriangleNormals(FeatureId tri, FeatureId n0, FeatureId n1, FeatureId n2) {
    assert(tri >= 0 && tri < static_cast<FeatureId>(m_triangles.size()));

    m_triangles[tri].m_n0 = n0;
    m_triangles[tri].m_n1 = n1;
    m_triangles[tri].m_n2 = n2;
}

void Mesh::SetTriangleTexCoords(FeatureId tri, FeatureId t0, FeatureId t1, FeatureId t2) {
    assert(tri >= 0 && tri < static_cast<FeatureId>(m_triangles.size()));

    m_triangles[tri].m_t0 = t0;
    m_triangles[tri].m_t1 = t1;
    m_triangles[tri].m_t2 = t2;
}

void Mesh::Finalize(const Context &context) {
    finalize_geometry();

    IAreaLight::Finalize(context);

    // Transform all vertices to world space. Normals are kept in object space.
    for(vertex_vector_it i = m_vertices.begin(), e = m_vertices.end(); i != e; ++i) {
        *i = TransformToWorld(*i);
    }

    // Minimum number of triangles to use an octree.
    const int TRIANGLES_THRESHOLD = 8;

    if(m_triangles.size() >= TRIANGLES_THRESHOLD) {
        m_octree = new octree();

        for(triangle_vector_const_it i = m_triangles.begin(), e = m_triangles.end(); i != e; ++i) {
            AABB3 aabb;

            aabb.Include(m_vertices[i->m_v0]);
            aabb.Include(m_vertices[i->m_v1]);
            aabb.Include(m_vertices[i->m_v2]);

            aabb.Extend(OBJECT_AABB_EXTENSION);

            m_octree->Insert(&(*i), aabb);
        }

        // Maximum number of subdivisions.
        const int MAX_SUBDIV = 6;   // at most 8^6 = 262,144 cells

        triangle_voxel_intersector tvi(m_vertices);
        m_octree->Subdivide(TRIANGLES_THRESHOLD, MAX_SUBDIV, tvi);

        //!\todo This is probably incorrect...
        m_aabb = m_octree->GetAABB();
    } else {
        assert(m_octree == 0);

        m_aabb.Invalidate();

        // Compute AABB from vertices.
        for(vertex_vector_const_it i = m_vertices.begin(), e = m_vertices.end(); i != e; ++i) {
            m_aabb.Include(*i);
        }

        // Enlarge the object bounding box to avoid numerical instabilities.
        m_aabb.Extend(OBJECT_AABB_EXTENSION);
    }
}

Real Mesh::ComputeSurfaceArea() const {
    //!\todo Implement.
//  assert(!"Not implemented yet.");
    return 0.0;
}

void Mesh::EvaluateSurface(const Point2 &input,
                           Point3 *point,
                           Vector3 *geometric_normal) const
{
    assert(point);
    assert(geometric_normal);

    //!\todo Implement.
    assert(!"Not implemented yet.");
}

bool Mesh::Intersect(const Context &context,
                     const Ray &ray,    //!< 'ray' is expressed in world space.
                     Hit *hit /*= 0*/) const
{
    // Test whether this object intersects with this type of ray.
    if(!(m_intersection_mask & ray.GetType()))
        return false;

    ++context.m_statistics->m_tested_intersections;

    if(m_octree) {
        if(hit) {
            octree_full_visitor visitor(m_vertices, context, ray);
            m_octree->Trace(ray.m_origin, ray.m_direction, visitor);

            if(visitor.m_t < std::numeric_limits<Real>::max()) {
                ++context.m_statistics->m_intersections_found;

                const Real k = 1.0 - visitor.m_u - visitor.m_v;

                hit->m_object = this;
                hit->m_abscissa = visitor.m_t;  // world space
                hit->m_geometric_normal = visitor.m_triangle->m_geometric_normal;   // object space

                const Vector3 &n0 = m_normals[visitor.m_triangle->m_n0];
                const Vector3 &n1 = m_normals[visitor.m_triangle->m_n1];
                const Vector3 &n2 = m_normals[visitor.m_triangle->m_n2];

                const Vector2 &t0 = m_texcoords[visitor.m_triangle->m_t0];
                const Vector2 &t1 = m_texcoords[visitor.m_triangle->m_t1];
                const Vector2 &t2 = m_texcoords[visitor.m_triangle->m_t2];

                // Compute shading normal.
                //!\todo Interpolate vertex normals using spherical interpolation.
                hit->m_shading_normal = k * n0 + visitor.m_u * n1 + visitor.m_v * n2;

                // Compute texture coordinates.
                hit->m_u = k * t0.m_x + visitor.m_u * t1.m_x + visitor.m_v * t2.m_x;
                hit->m_v = k * t0.m_y + visitor.m_u * t1.m_y + visitor.m_v * t2.m_y;

//!\todo Hack...
hit->m_u = fmod(hit->m_u, 1.0);
if(hit->m_u < 0.0)
    hit->m_u += 1.0;

hit->m_v = fmod(hit->m_v, 1.0);
if(hit->m_v < 0.0)
    hit->m_v += 1.0;

                // Normals will be made unit-length later, when absolutely necessary.

                return true;
            } else return false;
        } else {
            octree_test_visitor visitor(m_vertices, context, ray);
            m_octree->Trace(ray.m_origin, ray.m_direction, visitor);

            if(visitor.m_found) {
                ++context.m_statistics->m_intersections_found;
                return true;
            } else return false;
        }
    } else {
        if(hit) {
            Real nearest_t = std::numeric_limits<Real>::max();
            Real nearest_u, nearest_v;
            const triangle *nearest_triangle;

            for(triangle_vector_const_it i = m_triangles.begin(), e = m_triangles.end(); i != e; ++i) {
                const Point3 &v0 = m_vertices[i->m_v0];
                const Point3 &v1 = m_vertices[i->m_v1];
                const Point3 &v2 = m_vertices[i->m_v2];

                Real t, u, v;

                if(intersect_triangle(ray, v0, v1, v2, &t, &u, &v))
                    if(t > 0.0 && t < nearest_t) {
                        nearest_t = t;
                        nearest_u = u;
                        nearest_v = v;
                        nearest_triangle = &(*i);
                    }
            }

            if(nearest_t < std::numeric_limits<Real>::max()) {
                ++context.m_statistics->m_intersections_found;

                const Real k = 1.0 - nearest_u - nearest_v;

                hit->m_object = this;
                hit->m_abscissa = nearest_t;    // world space
                hit->m_geometric_normal = nearest_triangle->m_geometric_normal; // object space

                const Vector3 &n0 = m_normals[nearest_triangle->m_n0];
                const Vector3 &n1 = m_normals[nearest_triangle->m_n1];
                const Vector3 &n2 = m_normals[nearest_triangle->m_n2];

                const Vector2 &t0 = m_texcoords[nearest_triangle->m_t0];
                const Vector2 &t1 = m_texcoords[nearest_triangle->m_t1];
                const Vector2 &t2 = m_texcoords[nearest_triangle->m_t2];

                // Compute shading normal.
                //!\todo Interpolate normals with a spherical interpolation.
                hit->m_shading_normal = k * n0 + nearest_u * n1 + nearest_v * n2;

                // Compute texture coordinates.
                hit->m_u = k * t0.m_x + nearest_u * t1.m_x + nearest_v * t2.m_x;
                hit->m_v = k * t0.m_y + nearest_u * t1.m_y + nearest_v * t2.m_y;

//!\todo Hack...
hit->m_u = fmod(hit->m_u, 1.0);
if(hit->m_u < 0.0)
    hit->m_u += 1.0;

hit->m_v = fmod(hit->m_v, 1.0);
if(hit->m_v < 0.0)
    hit->m_v += 1.0;

                // Normals will be made unit-length later, when absolutely necessary.

                return true;
            } else return false;
        } else {
            for(triangle_vector_const_it i = m_triangles.begin(), e = m_triangles.end(); i != e; ++i) {
                const Point3 &v0 = m_vertices[i->m_v0];
                const Point3 &v1 = m_vertices[i->m_v1];
                const Point3 &v2 = m_vertices[i->m_v2];

                Real t, u, v;   // not used

                if(intersect_triangle(ray, v0, v1, v2, &t, &u, &v))
                    if(t > 0.0) {
                        ++context.m_statistics->m_intersections_found;
                        return true;
                    }
            }

            return false;
        }
    }
}

namespace {
    void line(const ICamera *camera,
              Framebuffer *framebuffer,
              const Point3 &p0,
              const Point3 &p1,
              const Color3 &color)
    {
        int x0, y0, x1, y1;

        framebuffer->ConvertFromNDC(camera->Project(p0), &x0, &y0);
        framebuffer->ConvertFromNDC(camera->Project(p1), &x1, &y1);

        framebuffer->PlotLine(x0, y0, x1, y1, color);
    }
}

void Mesh::Annotate(const Context &context,
                    const ICamera *camera,
                    Framebuffer *framebuffer) const
{
    int n = 0;

    for(triangle_vector_const_it i = m_triangles.begin(), e = m_triangles.end(); i != e; ++i) {
//      if(n++ % 50 != 0)
//          continue;

        const Point3 &v0 = m_vertices[i->m_v0];
        const Point3 &v1 = m_vertices[i->m_v1];
        const Point3 &v2 = m_vertices[i->m_v2];

        const Vector3 n0 = TransformNormalToWorld(m_normals[i->m_n0]);
        const Vector3 n1 = TransformNormalToWorld(m_normals[i->m_n1]);
        const Vector3 n2 = TransformNormalToWorld(m_normals[i->m_n2]);

        assert(n0.IsUnitLength());
        assert(n1.IsUnitLength());
        assert(n2.IsUnitLength());

        const Real SCALE = 1.0e-2;
        const Color3 COLOR(1.0, 0.0, 0.0);

//      line(camera, framebuffer, v0, v0 + SCALE * n0, COLOR);
//      line(camera, framebuffer, v1, v1 + SCALE * n1, COLOR);
//      line(camera, framebuffer, v2, v2 + SCALE * n2, COLOR);

        const Point3 p = (v0 + v1 + v2) / 3;
        const Vector3 n = SCALE * (n0 + n1 + n2).Normalized();

        line(camera, framebuffer, p, p + 0.9 * n, COLOR);
        line(camera, framebuffer, p + 0.9 * n, p + n, Color3(1.0, 1.0, 0.0));
    }
}

inline
Mesh::triangle::triangle()
#ifdef USE_MAILBOXES
    : m_mailbox_ray_id(Ray::GetInvalidId())
#endif  // USE_MAILBOXES
{
}

inline
bool Mesh::triangle_voxel_intersector::Intersect(const triangle *tri,
                                                 const AABB3 &voxel) const
{
    assert(tri);

    const Point3 boxcenter = voxel.GetCenter();
    const Vector3 boxhalfsize = voxel.m_max - boxcenter;
    const Point3 &v0 = m_vertices[tri->m_v0];
    const Point3 &v1 = m_vertices[tri->m_v1];
    const Point3 &v2 = m_vertices[tri->m_v2];

    return tri_box_overlap(boxcenter, boxhalfsize, v0, v1, v2);
}

inline
Mesh::octree_test_visitor::octree_test_visitor(const vertex_vector &vertices,
                                               const Context &context,
                                               const Ray &ray) :
    m_vertices(vertices),   
    m_context(context),
    m_ray(ray),
    m_found(false)
{
}

bool Mesh::octree_test_visitor::Trace(const octree_node *node,
                                      Real /*t0*/, Real /*t1*/)
{
    assert(node);

    for(octree_node::ItemVectorConstIt i = node->m_items.begin(), e = node->m_items.end(); i != e; ++i) {
        //!\todo Optimize: use a simplified routine that does not compute
        //! and report t, u and v, because we really don't care here.

        const triangle *tri = *i;

        const Point3 &v0 = m_vertices[tri->m_v0];
        const Point3 &v1 = m_vertices[tri->m_v1];
        const Point3 &v2 = m_vertices[tri->m_v2];

        Real t, u, v;   // not used

        if(intersect_triangle(m_ray, v0, v1, v2, &t, &u, &v))
            if(t > 0.0) {
                m_found = true;
                return true;    // terminate octree traversal
            }
    }

    return false;   // continue octree traversal
}

inline
Mesh::octree_full_visitor::octree_full_visitor(const vertex_vector &vertices,
                                               const Context &context,
                                               const Ray &ray) :
    m_vertices(vertices),
    m_context(context),
    m_ray(ray),
    m_t(std::numeric_limits<Real>::max())
{
}

bool Mesh::octree_full_visitor::Trace(const octree_node *node,
                                      Real t0, Real t1)
{
    assert(node);

    for(octree_node::ItemVectorConstIt i = node->m_items.begin(), e = node->m_items.end(); i != e; ++i) {
        const triangle *tri = *i;

#ifdef USE_MAILBOXES
        if(tri->m_mailbox_ray_id != m_ray.GetId()) {
#endif  // USE_MAILBOXES
            const Point3 &v0 = m_vertices[tri->m_v0];
            const Point3 &v1 = m_vertices[tri->m_v1];
            const Point3 &v2 = m_vertices[tri->m_v2];

            Real t, u, v;

            if(intersect_triangle(m_ray, v0, v1, v2, &t, &u, &v)) {
                if(t > 0.0 && t < m_t) {
                    m_t = t;
                    m_u = u;
                    m_v = v;
                    m_triangle = tri;
                }
            }

#ifdef USE_MAILBOXES
            tri->m_mailbox_ray_id = m_ray.GetId();
        }
#endif  // USE_MAILBOXES
    }

    //!\todo Make sure the <= and >= are correct.
    if(m_t >= t0 && m_t <= t1)
        return true;    // terminate octree traversal
    else return false;  // continue octree traversal
}

void Mesh::finalize_geometry() {
    int dummy_tid = -1;

    for(triangle_vector_it i = m_triangles.begin(), e = m_triangles.end(); i != e; ++i) {
        triangle &tri = *i;

        const Point3 &v0 = m_vertices[tri.m_v0];
        const Point3 &v1 = m_vertices[tri.m_v1];
        const Point3 &v2 = m_vertices[tri.m_v2];

        // Compute geometric normal to the triangle surface.
        const Vector3 e0 = v1 - v0; // object space
        const Vector3 e1 = v2 - v0; // object space
        tri.m_geometric_normal = (e0 ^ e1).Normalized();    // object space

        // Set missing vertex normals.
        if(tri.m_n0 == -1 || tri.m_n1 == -1 || tri.m_n2 == -1) {
            m_normals.push_back(tri.m_geometric_normal);
            tri.m_n0 = tri.m_n1 = tri.m_n2 = static_cast<FeatureId>(m_normals.size() - 1);
        }

        // Set missing texture coordinates.
        if(tri.m_t0 == -1 || tri.m_t1 == -1 || tri.m_t2 == -1) {
            if(dummy_tid == -1) {
                m_texcoords.push_back(Vector2(0.0));
                dummy_tid = m_texcoords.size() - 1;
            }

            tri.m_t0 = tri.m_t1 = tri.m_t2 = dummy_tid;
        }
    }
}

---