source: trunk/VUT/GtpVisibilityPreprocessor/src/Mesh.cpp @ 162

#include "ray.h"
#include "Mesh.h"

int MeshInstance::mailID = 21843194198;

void
Mesh::Preprocess()
{
  mBoundingBox.Initialize();

  VertexContainer::const_iterator vi = mVertices.begin();
  for (; vi != mVertices.end(); vi++) {
    mBoundingBox.Include(*vi);
  }
  
  mIsConvex = false;
}


int
Mesh::CastRay(
              Ray &ray,
              MeshInstance *instance
              )
{
  FaceContainer::const_iterator fi;
  int faceIndex = 0;
  int hits = 0;
  float nearestT = MAX_FLOAT;
  float nearestFace;

  if (ray.GetType() == Ray::LOCAL_RAY && ray.intersections.size())
    nearestT = ray.intersections[0].mT;

  
  for ( ;
        faceIndex < mFaces.size();
        faceIndex++) {
    float t;
    if (RayFaceIntersection(faceIndex, ray, t, nearestT) == Ray::INTERSECTION) {
      switch (ray.GetType()) {
      case Ray::GLOBAL_RAY:
        ray.intersections.push_back(Ray::RayIntersection(t, instance, faceIndex));
        hits++;
        break;
      case Ray::LOCAL_RAY:
        hits++;
        nearestT = t;
        nearestFace = faceIndex;
        break;
      }
    }
  }
  
  if ( hits && ray.GetType() == Ray::LOCAL_RAY ) {
    if (ray.intersections.size())
      ray.intersections[0] = Ray::RayIntersection(nearestT, instance, nearestFace);
    else
      ray.intersections.push_back(Ray::RayIntersection(nearestT, instance, nearestFace));
  }
  
  return hits;
}


// int_lineseg returns 1 if the given line segment intersects a 2D
// ray travelling in the positive X direction.  This is used in the
// Jordan curve computation for polygon intersection.
inline int
int_lineseg(float px,
            float py,
            float u1,
            float v1,
            float u2,
            float v2)
{
  float t;
  float ydiff;

  u1 -= px; u2 -= px;     // translate line
  v1 -= py; v2 -= py;

  if ((v1 > 0 && v2 > 0) ||
      (v1 < 0 && v2 < 0) ||
      (u1 < 0 && u2 < 0))
    return 0;

  if (u1 > 0 && u2 > 0)
    return 1;

  ydiff = v2 - v1;
  if (fabs(ydiff) < Limits::Small) {      // denominator near 0
    if (((fabs(v1) > Limits::Small) ||
         (u1 > 0) || (u2 > 0)))
      return 0;
    return 1;
  }

  t = -v1 / ydiff;                // Compute parameter

  return (u1 + t * (u2 - u1)) > 0;
}



// intersection with the polygonal face of the mesh
int
Mesh::RayFaceIntersection(const int faceIndex,
                          const Ray &ray,
                          float &t,
                          const float nearestT
                          )
{
  Face *face  = mFaces[faceIndex];

  Plane3 plane = GetFacePlane(faceIndex);
  float dot = DotProd(plane.mNormal, ray.GetDir());
  
  // Watch for near-zero denominator
  // ONLY single sided polygons!!!!!
  if (dot > -Limits::Small)
    //  if (fabs(dot) < Limits::Small)
    return Ray::NO_INTERSECTION;
  
  t = (-plane.mD - DotProd(plane.mNormal, ray.GetLoc())) / dot;
  
  if (t <= Limits::Small)
    return Ray::INTERSECTION_OUT_OF_LIMITS;
  
  if (t >= nearestT) {
    return Ray::INTERSECTION_OUT_OF_LIMITS; // no intersection was found
  }
  
  int count = 0;
  float u, v, u1, v1, u2, v2;
  int i;

  int paxis = plane.mNormal.DrivingAxis();

  // Project the intersection point onto the coordinate plane
  // specified by which.
  ray.Extrap(t).ExtractVerts(&u, &v, paxis);


  mVertices[face->mVertexIndices[face->mVertexIndices.size() - 1]].
    ExtractVerts(&u1, &v1, paxis );

  if (mIsConvex) {
    // assume a convex face
    for (i = 0; i < face->mVertexIndices.size(); i++) {
      mVertices[face->mVertexIndices[i]].ExtractVerts(&u2, &v2, paxis);
      // line u1, v1, u2, v2
      if ((v2 - v1)*(u1 - u) > (u2 - u1)*(v1 - v))
        return Ray::NO_INTERSECTION;
      u1 = u2;
      v1 = v2;
    }
    
    return Ray::INTERSECTION;
  }
  
  // We're stuck with the Jordan curve computation.  Count number
  // of intersections between the line segments the polygon comprises
  // with a ray originating at the point of intersection and
  // travelling in the positive X direction.
  for (i = 0; i < face->mVertexIndices.size(); i++) {
    mVertices[face->mVertexIndices[i]].ExtractVerts(&u2, &v2, paxis);
    count += (int_lineseg(u, v, u1, v1, u2, v2) != 0);
    u1 = u2;
    v1 = v2;
  }

  // We hit polygon if number of intersections is odd.
  return (count & 1) ? Ray::INTERSECTION : Ray::NO_INTERSECTION;
}


int
MeshInstance::CastRay(
                      Ray &ray
                      )
{
  int res = mMesh->CastRay(ray, this);
  return res;
}


Plane3
Mesh::GetFacePlane(const int faceIndex)
{
  Face *face = mFaces[faceIndex];
  return Plane3(mVertices[face->mVertexIndices[0]],
                mVertices[face->mVertexIndices[1]],
                mVertices[face->mVertexIndices[2]]);
}

int
MeshTransformedInstance::CastRay(
                                 Ray &ray
                                 )
{
  ray.ApplyTransform(Invert(mWorldTransform));
  int res = mMesh->CastRay(ray, this);
  ray.ApplyTransform(mWorldTransform);
  
  return res;
}