//<copyright>
//
// Copyright (c) 1996
// Institute for Information Processing and Computer Supported New Media (IICM),
// Graz University of Technology, Austria.
//
// This file is part of VRweb.
//
// VRweb 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, or (at your option)
// any later version.
//
// VRweb 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 VRweb; see the file LICENCE. If not, write to the
// Free Software Foundation, Inc., 59 Temple Place - Suite 330,
// Boston, MA 02111-1307, USA.
//
// Note that the GNU General Public License does not permit incorporating
// the Software into proprietary or commercial programs. Such usage
// requires a separate license from IICM.
//
//</copyright>

//<file>
//
// Name:        asmooth.C
//
// Purpose:     autosmoothing (vertex normal generation)
//
// Created:     16 Apr 96   Peter Zemljic
//
// Changed:      3 Jun 96   Peter Zemljic
//
// Changed:     14 Jun 96   Michael Pichler
//
// $Id: asmooth.C,v 1.6 1997/02/25 16:59:31 mpichler Exp $
//
//</file>



#include "vrmlscene.h"
#include "scene3d.h"
#include "vecutil.h"
#include "arrays.h"

#include <vrml/QvIndexedFaceSet.h>

#include <ge3d/vectors.h>
#include <iostream.h>
#include <math.h>

#include <hyperg/utils/verbose.h>


// equal
// test two vectors for equality (missing in ge3d/vectors.h)

inline int equal (const vector3D& a, const vector3D& b)
{
  return (a.x == b.x && a.y == b.y && a.z == b.z);
}


// calcnormvec
// calculate averaged normal vector at current vertex based on crease_angle
// input normal data should be normalized, vertnormal normalized by caller

static void calcnormvec (
  const vector3D* facenormals, int facenum,
  const IntArray& faceNormalIndpV, float threash_value,  // cos (crease_angle)
  vector3D& vertnormal  // out
)
{
  // start with face normal vector
  const vector3D* facenormal = facenormals + facenum;
  vertnormal = *facenormal;

  int lastelement = faceNormalIndpV.count ();
  int currentface;
  float skalarpr;

  for (int i = 0; i < lastelement; i++)
  {
    currentface = faceNormalIndpV [i];
    if (facenum != currentface)
    {
      const vector3D& curfnormal = facenormals [currentface];
      skalarpr = dot3D (curfnormal, *facenormal);
      if (skalarpr > threash_value)
      {
        inc3D (vertnormal, curfnormal);
      }
    }
  }
} // calcnormvec


// normalize
// ensure that vectors have unit length

inline void normalize (vector3D& normal)
{
  float norm = dot3D (normal, normal);
  if (norm > 0.0)
  {
    norm = 1/sqrt (norm);
    scl3D (normal, norm);
  }
}


// autosmooth
// generate vertex normal vectors based on crease_angle;
// when there are N vertexindices in total (length of coordIndex array) and
// each vertex belongs up to k vertices, this algorithm runs in O(k*N) time;
// typically k is a small constant (4 on quad meshes, 6 on tri. meshes),
// so it runs in linear time in N (which can grow fairly large);
// to save space, identical normals at vertices are detected (typical
// smoothing case) as well as identical normals on successive vertices of a
// (flat) face


void VRMLScene::autosmooth (QvIndexedFaceSet* faceSet, float crease_angle)
{
  int nv;
  const int* vertindices;
  const vector3D* facenormals;

  if (!doautosmooth_ || !faceSet || !crease_angle)
    return;

  DEBUGNL ("autosmooth for faceSet " << (void*) faceSet << " ...");

  // operate on triangulated faces in case confexify was called
  if (faceSet->convexCoordIndex.num == 1)  // convexify wasn't called
  { nv = faceSet->numvertinds_;
    vertindices = faceSet->vertindices_;
    facenormals = faceSet->facenormals_;
  }
  else  // convexify was called
  { nv = faceSet->convexCoordIndex.num;
    vertindices = (const int*) faceSet->convexCoordIndex.values;
    facenormals = (const vector3D*) faceSet->convexFaceNormals_.values;
  }

  // mpi-TODO: store normal indices elsewhere to prevent writing them to file on saving
  // determine normal index for each vertex of each face
  // normalIndex array is overwritten with indices to normal vectors created by smoothing (normalList_)
  faceSet->normalIndex.allocValues (nv);

  // find highest vertexindex
  int maxvert = 0;
  int i = nv;
  const int* vi = vertindices;
  while (i--)
  {
    if (*vi > maxvert)
      maxvert = *vi;
    vi++;
  }
  DEBUGNL ("maximum vertex index: " << maxvert);

  // For each vertex (value of index) store the indices of all faces to which the vertex belongs to
  // On the first position of each list (index 0) the number of elements, stored in the list is given.
  IntArray* faceNormalIndperVertex = new IntArray [maxvert+1];  // [0..maxvert]

  // For each vertex (value of index) store the indices of all smoothed normals that have already been calculated.
  IntArray* vertNormalIndperVertex = new IntArray [maxvert+1];  // [0..maxvert]
  // length accessible via count (), no need to store it at index 0

  int facenum = 0;
  for (i = nv, vi = vertindices;  i--;  vi++)
  {
    if (*vi >= 0)
      faceNormalIndperVertex [*vi].append (facenum);
    else  // next face
      facenum++;
  }


  facenum = 0;
  int curindex;
  int j;
  int found;
  int same_normal = 0;  // well defined when found

  // worst case: all normal vectors different (totally faceted)
  faceSet->normalList_.allocValues (nv);  // make room for nv normal vectors (vec3f)
  vector3D* normallist = (vector3D*) faceSet->normalList_.values;
  int normal_index = 0;  // next free index in normallist

  float threash_value = cos (crease_angle);


  for (i = 0; i < nv; i++)
  {
    curindex = vertindices[i];
    if (curindex >= 0)
    {
      calcnormvec (facenormals, facenum,
        faceNormalIndperVertex [curindex], threash_value, normallist [normal_index]);
      normalize (normallist [normal_index]);

      IntArray& vertNormalIndpV = vertNormalIndperVertex [curindex];  // normals generated for this vertex

      found = 0;
      for (j = 0;  j < vertNormalIndpV.count () && !found;  j++)
      {
        same_normal = vertNormalIndpV [j];
        found = equal (normallist [same_normal], normallist [normal_index]);
      }
      if (found)  // Normal already exists for same vertex in another face (because of smoothing)
        faceSet->normalIndex.values [i] = same_normal;
      else if ((normal_index > 0) && equal (normallist [normal_index], normallist [normal_index - 1]))
      { // this normal happens to be identical with the previously calculated normal
        faceSet->normalIndex.values [i] = normal_index - 1;
      }
      else
      {
        faceSet->normalIndex.values [i] = normal_index;
        vertNormalIndpV.append (normal_index);
        normal_index++;
      }
    }
    else  // next face
    {
      facenum++;
      faceSet->normalIndex.values[i] = -1;
    }
  }


  faceSet->normalindices_ = (const int*) faceSet->normalIndex.values;
  faceSet->numnormalinds_ = nv;
  faceSet->normalList_.allocValues (normal_index);  // shrink array to no. of used elements
  faceSet->normallist_ = (const vector3D*) faceSet->normalList_.values;
  delete[] faceNormalIndperVertex;
  delete[] vertNormalIndperVertex;

  DEBUGNL (normal_index << " smooth normals for " << facenum << " faces, " << nv << " vertex indices");

//  cerr << "Creaseangle :   " << crease_angle  << endl;
//  cerr << "nv                   : " <<  nv                            << endl;
//  cerr << "numvertinds_         : " <<  faceSet->numvertinds_         << endl;
//  cerr << "coordIndex.num       : " <<  faceSet->coordIndex.num       << endl;
//  cerr << "convexCoordIndex.num : " <<  faceSet->convexCoordIndex.num << endl;
//  cerr << "numconvexinds_       : " <<  faceSet->numconvexinds_       << endl;
//  cerr << "numnormalinds_       : " <<  faceSet->numnormalinds_       << endl;
//  cerr << "normalIndex.num      : " <<  faceSet->normalIndex.num      << endl;
//  cerr << endl;

  DEBUGNL ("... finished autosmooth");

} // autosmooth