/*=========================================================================

Copyright (c) 1998-2005 Kitware Inc. 28 Corporate Drive, Suite 204,
Clifton Park, NY, 12065, USA.

All rights reserved. No part of this software may be reproduced,
distributed,
or modified, in any form or by any means, without permission in writing from
Kitware Inc.

IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY PARTY FOR
DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY DERIVATIVES THEREOF,
EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
INCLUDING,
BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE IS PROVIDED ON AN
"AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO
PROVIDE
MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.

=========================================================================*/
#include "vtkSeedGrowSelectionFilter.h"

#include "vtkCellData.h"
#include "vtkDiscreteModel.h"
#include "vtkDiscreteModelFace.h"
#include "vtkDiscreteModelWrapper.h"
#include "vtkIdTypeArray.h"
#include "vtkInformation.h"
#include "vtkInformationVector.h"
#include "vtkIntArray.h"
#include "vtkMath.h"
#include "vtkObjectFactory.h"
#include "vtkPolyData.h"
#include "vtkPolygon.h"
#include "vtkSelection.h"
#include "vtkSelectionNode.h"
#
#include "vtkTriangle.h"
#include <queue>
#include <set>
#

//----------------------------------------------------------------------------
class vtkSeedGrowSelectionFilter::vtkInternal
{
public:
  // Description:
  // A set of visible model faces
  std::set<vtkIdType> ModelFaceIds; //FaceIds;

  // The last element of the input array is the negative (-1).
  void updateIDs(vtkIdType thearray[])
    {
    int i=0;
    //should ModelFaceIds get reset first?
    while (thearray[i] >= 0 && i < VTK_INT_MAX)
      {
      this->ModelFaceIds.insert(thearray[i]);
      i++;
      }
    }

  bool IsModelFaceVisible(vtkIdType modelFaceId)
    {
      if(this->ModelFaceIds.find(modelFaceId) ==
         this->ModelFaceIds.end())
        {
        return 0;
        }
      return 1;
    }

  bool IsModelFaceVisible(vtkDiscreteModelGeometricEntity* modelFace)
    {
      vtkModelEntity* entity = modelFace->GetThisModelEntity();
      vtkIdType modelFaceId = entity->GetUniquePersistentId();
      return this->IsModelFaceVisible(modelFaceId);
    }
};

vtkStandardNewMacro(vtkSeedGrowSelectionFilter);
vtkCxxSetObjectMacro(vtkSeedGrowSelectionFilter, ModelWrapper, vtkDiscreteModelWrapper);

//----------------------------------------------------------------------------
vtkSeedGrowSelectionFilter::vtkSeedGrowSelectionFilter()
{
  this->FeatureAngle = 70.0;
  this->CellId = -1;
  this->ModelFaceCompositeIdx = -1;
  this->GrowMode = 0;
  this->SetNumberOfInputPorts(1);

  this->Internal = new vtkInternal();

  this->ModelWrapper = 0;
}

//----------------------------------------------------------------------------
vtkSeedGrowSelectionFilter::~vtkSeedGrowSelectionFilter()
{
  delete this->Internal;

  this->SetModelWrapper(0);
}

//----------------------------------------------------------------------------
void vtkSeedGrowSelectionFilter::SetFaceCellId(vtkIdType faceId, vtkIdType cellId)
{
  if(this->CellId == cellId && this->ModelFaceCompositeIdx == faceId)
    {
    return;
    }
  this->CellId = cellId;
  this->ModelFaceCompositeIdx = faceId;
  this->Modified();
}

//----------------------------------------------------------------------------
void vtkSeedGrowSelectionFilter::RemoveAllGrowFaceIds()
{
  this->Internal->ModelFaceIds.clear();
  this->Modified();
}

//----------------------------------------------------------------------------
void vtkSeedGrowSelectionFilter::SetGrowFaceIds(vtkIdType* faceIds)
{
  this->Internal->updateIDs(faceIds);

  this->Modified();
}

//----------------------------------------------------------------------------
void vtkSeedGrowSelectionFilter::GrowFromCell(const DiscreteMesh *mesh, vtkIntArray* marked, vtkIdType inputCellId,
  vtkIdTypeArray* outSelectionList)
{
  vtkDiscreteModel* model = this->ModelWrapper->GetModel();
  vtkDiscreteModel::ClassificationType& classified =
                            model->GetMeshClassification();
  std::queue<vtkIdType> cellQueue;
  cellQueue.push(inputCellId);
  outSelectionList->InsertNextValue(inputCellId);

  vtkIdList* edgePts = vtkIdList::New();
  edgePts->SetNumberOfIds(2);
  vtkIdList* neighbors = vtkIdList::New();
  vtkIdList* pts = vtkIdList::New();
  vtkIdList* otherPts = vtkIdList::New();
  double normal[3];
  while(!cellQueue.empty())
    {
    vtkIdType cellId = cellQueue.front();
    cellQueue.pop();
    mesh->GetCellPointIds(cellId, pts);
    this->ComputeNormal(pts, mesh, normal);
    const int numberOfPoints = pts->GetNumberOfIds();
    for(int i=0;i<numberOfPoints;i++)
      {
      edgePts->SetId(0, pts->GetId(i));
      edgePts->SetId(1, pts->GetId((i+1)%numberOfPoints));
      mesh->GetCellNeighbors(cellId, edgePts, neighbors);
      // may have multiple edge neighbors for non-manifold mesh
      const vtkIdType numberOfNeighbors = neighbors->GetNumberOfIds();
      for(vtkIdType id=0;id<numberOfNeighbors;id++)
        {
        vtkIdType otherId = neighbors->GetId(id);
        // first check if marked
        if(marked->GetValue(otherId) == 0)
          {
          vtkDiscreteModelGeometricEntity* modelFace =
                                              classified.GetEntity(otherId);
          if(this->Internal->IsModelFaceVisible(modelFace))
            {
            // also needs to be visible in order to grow to the cell
            double otherNormal[3];
            mesh->GetCellPointIds(otherId, otherPts);
            this->ComputeNormal(otherPts, mesh, otherNormal);
            double dotprod = vtkMath::Dot(normal, otherNormal);
            if(!this->AreCellNormalsConsistent(
                 edgePts->GetId(0), edgePts->GetId(1), otherPts))
              {
              dotprod = -dotprod;
              }
            if(dotprod > this->FeatureAngleCosine )
              {
              marked->SetValue(otherId, 1);
              outSelectionList->InsertNextValue(otherId);
              cellQueue.push(otherId);
              }
            }
          }
        }
      }
    }
  edgePts->Delete();
  neighbors->Delete();
  pts->Delete();
  otherPts->Delete();
}

//----------------------------------------------------------------------------
void vtkSeedGrowSelectionFilter::GrowAndRemoveFromSelection(
  const DiscreteMesh *mesh, vtkIntArray* marked, vtkIdType inputCellId,
  vtkIdTypeArray* outSelectionList, vtkSelection* inSelection)
{
  if(!inSelection)
    {
    return;
    }
  vtkIdTypeArray* selIdArray = vtkIdTypeArray::SafeDownCast(
    inSelection->GetNode(0)->GetSelectionList());
  if(!selIdArray || selIdArray->GetNumberOfTuples()==0)
    {
    return;
    }
  vtkIdType inIdx = selIdArray->LookupValue(inputCellId);
  if(inIdx<0)
    {
    outSelectionList->DeepCopy(selIdArray);
    //this->MergeGrowSelection(selection, marked);
    return;
    }

  int numRemIds = 0;
  std::queue<vtkIdType> cellQueue;
  cellQueue.push(inputCellId);
  //selIdArray->RemoveTuple(inIdx);
  selIdArray->SetValue(inIdx, -1);
  numRemIds++;
  //outSelectionList->InsertNextValue(inputCellId);

  vtkIdList* edgePts = vtkIdList::New();
  edgePts->SetNumberOfIds(2);
  vtkIdList* neighbors = vtkIdList::New();
  vtkIdList* pts = vtkIdList::New();
  vtkIdList* otherPts = vtkIdList::New();
  double normal[3];
  while(!cellQueue.empty())
    {
    vtkIdType cellId = cellQueue.front();
    cellQueue.pop();
    mesh->GetCellPointIds(cellId, pts);
    this->ComputeNormal(pts, mesh, normal);
    const int numberOfPoints = pts->GetNumberOfIds();
    for(int i=0;i<numberOfPoints;i++)
      {
      edgePts->SetId(0, pts->GetId(i));
      edgePts->SetId(1, pts->GetId((i+1)%numberOfPoints));
      mesh->GetCellNeighbors(cellId, edgePts, neighbors);
      // may have multiple edge neighbors for non-manifold mesh
      const vtkIdType numberOfNeighbors = neighbors->GetNumberOfIds();
      for(vtkIdType id=0;id<numberOfNeighbors;id++)
        {
        vtkIdType otherId = neighbors->GetId(id);
        // first check if marked
        if(marked->GetValue(otherId) ==0)
          {
          inIdx = selIdArray->LookupValue(otherId);
          if(inIdx<0)
            {
            continue;
            }
          double otherNormal[3];
          mesh->GetCellPointIds(otherId, otherPts);
          this->ComputeNormal(otherPts, mesh, otherNormal);
          double dotprod = vtkMath::Dot(normal, otherNormal);
          if(!this->AreCellNormalsConsistent(
               edgePts->GetId(0), edgePts->GetId(1), otherPts))
            {
            dotprod = -dotprod;
            }
          if(dotprod > this->FeatureAngleCosine )
            {
            selIdArray->SetValue(inIdx, -1);
            numRemIds++;
            marked->SetValue(otherId, 1);
            //(*numCells)++;
            cellQueue.push(otherId);
            }
          }
        }
      }
    }

  int numSelIds = selIdArray->GetNumberOfTuples();
  if(numRemIds < numSelIds)
    {
    vtkIdType selId;
    for(int idx=0; idx<numSelIds; idx++)
      {
      selId = selIdArray->GetValue(idx);
      if( selId != -1)
        {
        outSelectionList->InsertNextValue(selId);
        }
      }
    }
  otherPts->Delete();
  edgePts->Delete();
  neighbors->Delete();
  pts->Delete();
}

//----------------------------------------------------------------------------
void vtkSeedGrowSelectionFilter::ComputeNormal(
  vtkIdList* ptids, const DiscreteMesh* mesh, double* normal)
{
  switch(ptids->GetNumberOfIds())
    {
    case 3:
    case 4:
    double pts0[3], pts1[3], pts2[3];
    mesh->GetPoint(ptids->GetId(0), pts0);
    mesh->GetPoint(ptids->GetId(1), pts1);
    mesh->GetPoint(ptids->GetId(2), pts2);
    vtkTriangle::ComputeNormal(pts0, pts1, pts2, normal);
    return;

    default:
    vtkIdType numberOfPoints = ptids->GetNumberOfIds();
    std::vector<double> pts(numberOfPoints*3);
    for(vtkIdType i=0;i<numberOfPoints;i++)
      {
      mesh->GetPoint(ptids->GetId(i), &(pts[3*i]));
      }
    vtkPolygon::ComputeNormal(numberOfPoints, &(pts[0]), normal);
    }
}

//----------------------------------------------------------------------------
bool vtkSeedGrowSelectionFilter::AreCellNormalsConsistent(
  vtkIdType pointId1, vtkIdType pointId2, vtkIdList * neighborCellIds)
{
  vtkIdType numberOfPoints = neighborCellIds->GetNumberOfIds();
  for(vtkIdType i=0;i<numberOfPoints;i++)
    {
    if(pointId1 == neighborCellIds->GetId(i) &&
       pointId2 == neighborCellIds->GetId((i+1)%numberOfPoints))
      {
      return false;
      }
    }
  return true;
}

//----------------------------------------------------------------------------
void vtkSeedGrowSelectionFilter::SetSelectionConnection(
  vtkAlgorithmOutput* algOutput)
{
  this->SetInputConnection(0, algOutput);
}

//----------------------------------------------------------------------------
void vtkSeedGrowSelectionFilter::MergeGrowSelection(
  vtkSelection* selection, vtkIntArray* marked,
  vtkIdTypeArray* outSelectionList)
{
  vtkIdTypeArray* array = NULL;
  vtkSelectionNode* selNode = NULL;
  for(unsigned int ui=0;ui<selection->GetNumberOfNodes();ui++)
    {
    selNode = selection->GetNode(ui);
    array = vtkIdTypeArray::SafeDownCast(
      selNode->GetSelectionList());
    if(!array)
      {
      continue;
      }
    for(int i=0;i<array->GetNumberOfTuples();i++)
      {
      int selId = array->GetValue(i);;  // add in ids here to marked
      if(marked->GetValue(selId)==0)
        {
        // no need for this since marked is not used after this
        //marked->SetValue(selId, 1);
        outSelectionList->InsertNextValue(selId);
        }
      }
    }
}

//----------------------------------------------------------------------------
int vtkSeedGrowSelectionFilter::RequestData(
  vtkInformation* vtkNotUsed(request),
  vtkInformationVector** inputVector,
  vtkInformationVector* outputVector)
{
  vtkSelection* output = vtkSelection::GetData(outputVector);
  vtkSelectionNode* selNode = vtkSelectionNode::New();
  vtkInformation* oProperties = selNode->GetProperties();
  oProperties->Set(vtkSelectionNode::CONTENT_TYPE(),
                   vtkSelectionNode::INDICES);
  oProperties->Set(vtkSelectionNode::FIELD_TYPE(), vtkSelectionNode::CELL);
  output->AddNode(selNode);
  selNode->Delete();

  vtkSelection* inSelection = 0;
  if(this->GetNumberOfInputPorts() > 0 && this->GrowMode > 0)
    {
    vtkInformation *selInfo = inputVector[0]->GetInformationObject(0);
    if ( selInfo )
      {
      inSelection = vtkSelection::SafeDownCast(
        selInfo->Get(vtkDataObject::DATA_OBJECT()));
      }
    }

  if(!this->ModelWrapper)
    {
    vtkErrorMacro("Must set ModelWrapper.");
    return 0;
    }
  vtkDiscreteModel* Model = this->ModelWrapper->GetModel();
  if(Model->HasInValidMesh())
    {
    vtkErrorMacro("Could not get mesh from model.");
    return 0;
    }

  vtkIdType numCells = Model->GetMesh().GetNumberOfFaces();

  // the CellId we have now is the Id from the Model Face that it is
  // associated with, we need to get this cell's Id on the master poly data...
  // need to skip the root index for selection in composite data
  unsigned int cur_index = static_cast<unsigned int>(this->ModelFaceCompositeIdx);
  vtkIdType faceId;
  if (!this->ModelWrapper->GetEntityIdByChildIndex(cur_index, faceId))
    {
    vtkErrorMacro("Could not find the model face from the composite index." << this->ModelFaceCompositeIdx);
    return 0;
    }

  vtkDiscreteModelFace* Face = vtkDiscreteModelFace::SafeDownCast(
    Model->GetModelEntity(vtkModelFaceType, faceId));
  if(!Face)
    {
    vtkErrorMacro("Could not get model face with Id " << faceId);
    return 0;
    }
  vtkIdType MasterCellId = Face->GetMasterCellId(this->CellId);
  if (MasterCellId<0 || MasterCellId>=numCells)
    {
    vtkErrorMacro("No cell found by given cellId and faceId!");
    return 0;
    }

  vtkIntArray* marked = vtkIntArray::New();
  marked->SetNumberOfComponents(1);
  marked->SetNumberOfTuples(numCells);
  int i;
  for(i=0;i<numCells;i++)
    {
    marked->SetValue(i, 0);
    }
  marked->SetValue(MasterCellId, 1);

  //get the vtkPolydata from the mesh
  const DiscreteMesh &mesh = Model->GetMesh();

  vtkIdList* pts = vtkIdList::New();
  mesh.GetCellPointIds(MasterCellId, pts);
  double normal[3];
  this->ComputeNormal(pts, &mesh, normal);
  this->FeatureAngleCosine = cos(
    vtkMath::RadiansFromDegrees(this->FeatureAngle));

  // Create the selection list
  vtkIdTypeArray* outSelectionList = vtkIdTypeArray::New();
  outSelectionList->SetNumberOfComponents(1);

  if(this->GrowMode == 0 || this->GrowMode == 1) // Grow and/or Merge
    {
    this->GrowFromCell(&mesh, marked, MasterCellId, outSelectionList);
    if(inSelection && this->GrowMode == 1) // Merge
      {
      this->MergeGrowSelection(inSelection, marked, outSelectionList);
      }
    }
  else if (this->GrowMode == 2) // grow and remove
    {
    this->GrowAndRemoveFromSelection(&mesh, marked, MasterCellId,
                                     outSelectionList, inSelection);
    }

  selNode->SetSelectionList(outSelectionList);
  outSelectionList->Delete();

  oProperties->Set(vtkSelectionNode::CONTAINING_CELLS(),1);

  oProperties->Set(vtkSelectionNode::INVERSE(),0);

  if (selNode->GetSelectionList())
    {
    selNode->GetSelectionList()->SetName("IDs");
    }

  pts->Delete();
  marked->Delete();

  return 1;
}

//----------------------------------------------------------------------------
int vtkSeedGrowSelectionFilter::FillInputPortInformation(
  int /*port*/, vtkInformation *info)
{
  info->Set(vtkAlgorithm::INPUT_REQUIRED_DATA_TYPE(), "vtkSelection");
  info->Set(vtkAlgorithm::INPUT_IS_OPTIONAL(), 1);

  return 1;
}

//----------------------------------------------------------------------------
void vtkSeedGrowSelectionFilter::PrintSelf(ostream& os, vtkIndent indent)
{
  this->Superclass::PrintSelf(os, indent);
  os << indent << "FeatureAngle: " << this->FeatureAngle << "\n";
  os << indent << "CellId: " << this->CellId << "\n";
  os << indent << "ModelFaceCompositeIdx: " << this->ModelFaceCompositeIdx << "\n";
  os << indent << "GrowMode: " << this->GrowMode << "\n";
}

