/**************************************************************************\
 *
 *  This file is part of the Coin 3D visualization library.
 *  Copyright (C) 1998-2006 by Systems in Motion.  All rights reserved.
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License
 *  ("GPL") version 2 as published by the Free Software Foundation.
 *  See the file LICENSE.GPL at the root directory of this source
 *  distribution for additional information about the GNU GPL.
 *
 *  For using Coin with software that can not be combined with the GNU
 *  GPL, and for taking advantage of the additional benefits of our
 *  support services, please contact Systems in Motion about acquiring
 *  a Coin Professional Edition License.
 *
 *  See http://www.coin3d.org/ for more information.
 *
 *  Systems in Motion, Postboks 1283, Pirsenteret, 7462 Trondheim, NORWAY.
 *  http://www.sim.no/  sales@sim.no  coin-support@coin3d.org
 *
\**************************************************************************/

/*!
  \class SoIndexedFaceSet SoIndexedFaceSet.h Inventor/nodes/SoIndexedFaceSet.h
  \brief The SoIndexedFaceSet class is used to handle generic indexed facesets.
  \ingroup nodes

  Faces are specified using the coordIndex field. Each face must be
  terminated by a negative (-1) index. Coordinates, normals, materials
  and texture coordinates from the current state (or from the
  vertexProperty node if set), can be indexed to create triangles,
  quads or polygons.

  Here's a usage example of just about the simplest possible use of
  this node, to show a single polygon face:

  \verbatim
  #Inventor V2.1 ascii
  
  Separator {
     Coordinate3 {
        point [ 0 0 0, 1 0 0, 1 1 0 ]
     }
     IndexedFaceSet {
        coordIndex [ 0, 1, 2, -1 ]
     }
  }
  \endverbatim

  Binding PER_VERTEX_INDEXED, PER_VERTEX, PER_FACE_INDEXED, PER_FACE
  or OVERALL can be set for material, and normals. The default
  material binding is OVERALL. The default normal binding is
  PER_VERTEX_INDEXED. When PER_VERTEX_INDEXED binding is used and the
  corresponding materialIndex, normalIndex, texCoordIndex field is
  empty, the coordIndex field will be used to index material, normal
  or texture coordinate. If you do specify indices for material,
  normals or texture coordinates for PER_VERTEX_INDEXED binding, make
  sure your index array matches the coordIndex array: there should be
  a -1 wherever there is a -1 in the coordIndex field. This is done to
  make this node more easily readable for humans.


  A fairly common request when rendering facesets is how to display a
  set of faces with different colors on the backside versus the
  frontside. There is not \e direct support for this in the API, but
  it can easily be implemented by duplicating all faces in both the
  SoShapeHints::COUNTERCLOCKWISE and the SoShapeHints::CLOCKWISE
  order. Here is a simple usage example, showing the technique for a
  single polygon, using two SoFaceSet nodes for rendering the same
  polygon from both sides:

  \verbatim
  #Inventor V2.1 ascii
  
  Separator {
     Coordinate3 { point [ 0 0 0, 1 0 0, 1 1 0 ] }
  
     Separator {
        Material { diffuseColor [ 1 1 0 ] }
        ShapeHints {
           vertexOrdering COUNTERCLOCKWISE
           shapeType SOLID
        }
        FaceSet { numVertices [ 3 ] }
     }
  
     Separator {
        Material { diffuseColor [ 1 0 0 ] }
        ShapeHints {
           vertexOrdering CLOCKWISE
           shapeType SOLID
        }
        FaceSet { numVertices [ 3 ] }
     }
  }
  \endverbatim

  The same effect can also be done in the following manner, using an
  SoIndexedFaceSet to explicitly render the polygon coordinates in
  both directions (clockwise and counterclockwise):

  \verbatim
  #Inventor V2.1 ascii
  
  Separator {
     Coordinate3 { point [ 0 0 0, 1 0 0, 1 1 0 ] }
  
     Material { diffuseColor [ 1 0 0, 1 1 0 ] }
     MaterialBinding { value PER_FACE_INDEXED }
  
     ShapeHints {
        vertexOrdering COUNTERCLOCKWISE
        shapeType SOLID
     }
  
     IndexedFaceSet {
        coordIndex [ 0, 1, 2, -1, 2, 1, 0, -1 ]
        materialIndex [ 0, 1 ]
     }
  }
  \endverbatim


  Another rather rare issue that might be interesting to know about is
  that to render polygons with concave borders, you should set up an
  SoShapeHints node with SoShapeHints::faceType set to
  SoShapeHints::UNKNOWN_FACE_TYPE in the scene graph before the
  SoIndexedFaceSet (or SoFaceSet) node. This needs to be done to force
  the rendering code to tessellate the polygons properly to triangles
  before sending it off to OpenGL. Without it, the polygons will be
  sent as-is to OpenGL, and the OpenGL implementation's tessellator is
  often not able to tessellate properly. Here is an example which
  usually fails without the SoShapeHints node (try commenting it out,
  and see what happens):

  \verbatim
  #Inventor V2.1 ascii
  
  ShapeHints { faceType UNKNOWN_FACE_TYPE }
  
  Coordinate3
  {
          point [ 2 0 0,
                  1 0 0,
                  1 1 0,
                  0 1 0,
                  0 2 0,
                  1 2 0,
                  2 2 0,
                  2 1 0 ]
  }
  
  FaceSet {}
  \endverbatim

  <b>FILE FORMAT/DEFAULTS:</b>
  \code
    IndexedFaceSet {
        vertexProperty NULL
        coordIndex 0
        materialIndex -1
        normalIndex -1
        textureCoordIndex -1
    }
  \endcode

  \sa SoFaceSet, SoIndexedTriangleStripSet
*/

#include <Inventor/nodes/SoIndexedFaceSet.h>
#include <Inventor/nodes/SoSubNodeP.h>
#include <Inventor/errors/SoDebugError.h>
#include <Inventor/caches/SoConvexDataCache.h>
#include <Inventor/misc/SoState.h>
#include <Inventor/SoPrimitiveVertex.h>
#include <Inventor/details/SoFaceDetail.h>
#include <Inventor/bundles/SoMaterialBundle.h>
#include <Inventor/actions/SoGLRenderAction.h>
#include <Inventor/misc/SoGL.h>
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif // HAVE_CONFIG_H
#include <Inventor/system/gl.h>

#include <Inventor/actions/SoGetPrimitiveCountAction.h>

#include <Inventor/elements/SoModelMatrixElement.h>
#include <Inventor/elements/SoNormalBindingElement.h>
#include <Inventor/elements/SoMaterialBindingElement.h>
#include <Inventor/elements/SoCoordinateElement.h>
#include <Inventor/elements/SoShapeHintsElement.h>
#include <Inventor/elements/SoTextureCoordinateBindingElement.h>
#include <Inventor/elements/SoCacheElement.h>
#include <Inventor/elements/SoNormalElement.h>
#include <Inventor/elements/SoCreaseAngleElement.h>
#include <Inventor/elements/SoGLVBOElement.h>
#include <Inventor/elements/SoGLLazyElement.h>
#include <Inventor/caches/SoNormalCache.h>
#include <Inventor/misc/SoGL.h>
#include <assert.h>

#include <Inventor/bundles/SoTextureCoordinateBundle.h>
#include "../caches/normalcache_numcoords_hack.h"

#include "../misc/SoVertexArrayIndexer.h"
#include "../misc/SoVBO.h"

#ifdef COIN_THREADSAFE
#include <Inventor/threads/SbRWMutex.h>
#endif // COIN_THREADSAFE

// for concavestatus
#define STATUS_UNKNOWN 0
#define STATUS_CONVEX  1
#define STATUS_CONCAVE 2

#define LOCK_VAINDEXER(obj) SoBase::staticDataLock()
#define UNLOCK_VAINDEXER(obj) SoBase::staticDataUnlock()

#ifndef DOXYGEN_SKIP_THIS
class SoIndexedFaceSetP {
public:
  SoIndexedFaceSetP(void) 
#ifdef COIN_THREADSAFE
    : convexmutex(SbRWMutex::READ_PRECEDENCE)
#endif // COIN_THREADSAFE 
  { }
  SoVertexArrayIndexer * vaindexer;
  SoConvexDataCache * convexCache;
  int concavestatus;
#ifdef COIN_THREADSAFE
  SbRWMutex convexmutex;
#endif // COIN_THREADSAFE

  void readLockConvexCache(void) {
#ifdef COIN_THREADSAFE
    this->convexmutex.readLock();
#endif // COIN_THREADSAFE
  }
  void readUnlockConvexCache(void) {
#ifdef COIN_THREADSAFE
    this->convexmutex.readUnlock();
#endif // COIN_THREADSAFE
  }
  void writeLockConvexCache(void) {
#ifdef COIN_THREADSAFE
    this->convexmutex.writeLock();
#endif // COIN_THREADSAFE
  }
  void writeUnlockConvexCache(void) {
#ifdef COIN_THREADSAFE
    this->convexmutex.writeUnlock();
#endif // COIN_THREADSAFE
  }
};
#endif // DOXYGEN_SKIP_THIS

#undef THIS
#define THIS this->pimpl

SO_NODE_SOURCE(SoIndexedFaceSet);

/*!
  Constructor.
*/
SoIndexedFaceSet::SoIndexedFaceSet()
{
  THIS = new SoIndexedFaceSetP;
  THIS->vaindexer = NULL;
  THIS->convexCache = NULL;
  THIS->concavestatus = STATUS_UNKNOWN;

  SO_NODE_INTERNAL_CONSTRUCTOR(SoIndexedFaceSet);
}


/*!
  Destructor.
*/
SoIndexedFaceSet::~SoIndexedFaceSet()
{
  delete THIS->vaindexer;
  if (THIS->convexCache) THIS->convexCache->unref();
  delete THIS;
}

// doc from parent
void
SoIndexedFaceSet::initClass(void)
{
  SO_NODE_INTERNAL_INIT_CLASS(SoIndexedFaceSet, SO_FROM_INVENTOR_1|SoNode::VRML1);
}

//
// translates current material binding into the internal Binding enum.
//
SoIndexedFaceSet::Binding
SoIndexedFaceSet::findMaterialBinding(SoState * const state) const
{
  Binding binding = OVERALL;
  SoMaterialBindingElement::Binding matbind =
    SoMaterialBindingElement::get(state);

  switch (matbind) {
  case SoMaterialBindingElement::OVERALL:
    binding = OVERALL;
    break;
  case SoMaterialBindingElement::PER_VERTEX:
    binding = PER_VERTEX;
    break;
  case SoMaterialBindingElement::PER_VERTEX_INDEXED:
    binding = PER_VERTEX_INDEXED;
    break;
  case SoMaterialBindingElement::PER_PART:
  case SoMaterialBindingElement::PER_FACE:
    binding = PER_FACE;
    break;
  case SoMaterialBindingElement::PER_PART_INDEXED:
  case SoMaterialBindingElement::PER_FACE_INDEXED:
    binding = PER_FACE_INDEXED;
    break;
  default:
#if COIN_DEBUG
    SoDebugError::postWarning("SoIndexedFaceSet::findMaterialBinding",
                              "unknown material binding setting");
#endif // COIN_DEBUG
    break;
  }
  return binding;
}


//
// translates current normal binding into the internal Binding enum.
//
SoIndexedFaceSet::Binding
SoIndexedFaceSet::findNormalBinding(SoState * const state) const
{
  Binding binding = PER_VERTEX_INDEXED;
  SoNormalBindingElement::Binding normbind =
    (SoNormalBindingElement::Binding) SoNormalBindingElement::get(state);

  switch (normbind) {
  case SoNormalBindingElement::OVERALL:
    binding = OVERALL;
    break;
  case SoNormalBindingElement::PER_VERTEX:
    binding = PER_VERTEX;
    break;
  case SoNormalBindingElement::PER_VERTEX_INDEXED:
    binding = PER_VERTEX_INDEXED;
    break;
  case SoNormalBindingElement::PER_PART:
  case SoNormalBindingElement::PER_FACE:
    binding = PER_FACE;
    break;
  case SoNormalBindingElement::PER_PART_INDEXED:
  case SoNormalBindingElement::PER_FACE_INDEXED:
    binding = PER_FACE_INDEXED;
    break;
  default:
#if COIN_DEBUG
    SoDebugError::postWarning("SoIndexedFaceSet::findNormalBinding",
                              "unknown normal binding setting");
#endif // COIN_DEBUG
    break;
  }
  return binding;
}

// Documented in superclass.
void
SoIndexedFaceSet::notify(SoNotList * list)
{
  // Overridden to invalidate convex cache.
  THIS->readLockConvexCache();
  if (THIS->convexCache) THIS->convexCache->invalidate();
  THIS->readUnlockConvexCache();
  SoField *f = list->getLastField();
  if (f == &this->coordIndex) {
    THIS->concavestatus = STATUS_UNKNOWN;
    LOCK_VAINDEXER(this);
    if (THIS->vaindexer) {
      delete THIS->vaindexer;
      THIS->vaindexer = NULL;
    }
    UNLOCK_VAINDEXER(this);
  }
  inherited::notify(list);
}

// doc from parent
void
SoIndexedFaceSet::GLRender(SoGLRenderAction * action)
{
  if (this->coordIndex.getNum() < 3) return;
  SoState * state = action->getState();

  SbBool hasvp = FALSE;
  
  if (this->vertexProperty.getValue()) {
    hasvp = TRUE;
    state->push();
    this->vertexProperty.getValue()->GLRender(action);
  }

  if (!this->shouldGLRender(action)) {
    if (hasvp)
      state->pop();
    return;
  }

  Binding mbind = this->findMaterialBinding(state);
  Binding nbind = this->findNormalBinding(state);

  const SoCoordinateElement * coords;
  const SbVec3f * normals;
  const int32_t * cindices;
  int numindices;
  const int32_t * nindices;
  const int32_t * tindices;
  const int32_t * mindices;
  SbBool doTextures;
  SbBool normalCacheUsed;

  SoMaterialBundle mb(action);

  SoTextureCoordinateBundle tb(action, TRUE, FALSE);
  doTextures = tb.needCoordinates();
  SbBool sendNormals = !mb.isColorOnly() || tb.isFunction();

  this->getVertexData(state, coords, normals, cindices,
                      nindices, tindices, mindices, numindices,
                      sendNormals, normalCacheUsed);

  if (!sendNormals) nbind = OVERALL;
  else if (nbind == OVERALL) {
    if (normals) glNormal3fv(normals[0].getValue());
    else glNormal3f(0.0f, 0.0f, 1.0f);
  }
  else if (normalCacheUsed && nbind == PER_VERTEX) {
    nbind = PER_VERTEX_INDEXED;
  }
  else if (normalCacheUsed && nbind == PER_FACE_INDEXED) {
    nbind = PER_FACE;
  }
  if (this->getNodeType() == SoNode::VRML1) {
    // For VRML1, PER_VERTEX means per vertex in shape, not PER_VERTEX
    // on the state.
    if (mbind == PER_VERTEX) {
      mbind = PER_VERTEX_INDEXED;
      mindices = cindices;
    }
    if (nbind == PER_VERTEX) {
      nbind = PER_VERTEX_INDEXED;
      nindices = cindices;
    }
  }

  Binding tbind = NONE;
  if (doTextures) {
    if (tb.isFunction() && !tb.needIndices()) {
      tbind = NONE;
      tindices = NULL;
    }
    // FIXME: just call inherited::areTexCoordsIndexed() instead of
    // the if-check? 20020110 mortene.
    else if (SoTextureCoordinateBindingElement::get(state) ==
             SoTextureCoordinateBindingElement::PER_VERTEX) {
      tbind = PER_VERTEX;
      tindices = NULL;
    }
    else {
      tbind = PER_VERTEX_INDEXED;
      if (tindices == NULL) tindices = cindices;
    }
  }

  SbBool convexcacheused = FALSE;
  if (this->useConvexCache(action, normals, nindices, normalCacheUsed)) {
    cindices = THIS->convexCache->getCoordIndices();
    numindices = THIS->convexCache->getNumCoordIndices();
    mindices = THIS->convexCache->getMaterialIndices();
    nindices = THIS->convexCache->getNormalIndices();
    tindices = THIS->convexCache->getTexIndices();

    if (mbind == PER_VERTEX) mbind = PER_VERTEX_INDEXED;
    else if (mbind == PER_FACE) mbind = PER_FACE_INDEXED;
    if (nbind == PER_VERTEX) nbind = PER_VERTEX_INDEXED;
    else if (nbind == PER_FACE) nbind = PER_FACE_INDEXED;

    if (tbind != NONE) tbind = PER_VERTEX_INDEXED;
    convexcacheused = TRUE;
  }

  mb.sendFirst(); // make sure we have the correct material

#if 0
  fprintf(stderr,"numindices: %d, convex: %d, ncache: %d, nbind: %d, mbind: %d, tbind: %d, va: %d\n",
          numindices, convexcacheused, normalCacheUsed, nbind, mbind, tbind,
          cc_glglue_has_vertex_array(sogl_glue_instance(state)));
#endif

#ifdef COIN_NEXT_MINOR
  SoGLLazyElement * lelem = NULL;
  const uint32_t contextid = action->getCacheContext();
  SbBool dova = 
    SoVBO::shouldRenderAsVertexArrays(contextid, numindices) &&
    !convexcacheused && !normalCacheUsed &&
    ((nbind == OVERALL) || ((nbind == PER_VERTEX_INDEXED) && ((nindices == cindices) || (nindices == NULL)))) &&
    ((tbind == NONE) || ((tbind == PER_VERTEX_INDEXED) && ((tindices == cindices) || (tindices == NULL)))) &&
    ((mbind == NONE) || ((mbind == PER_VERTEX_INDEXED) && ((mindices == cindices) || (mindices == NULL)))) &&
    cc_glglue_has_vertex_array(sogl_glue_instance(state));

  const SoGLVBOElement * vboelem = SoGLVBOElement::getInstance(state);
  SoVBO * colorvbo = NULL;

  if (dova && (mbind != OVERALL)) {
    dova = FALSE;
    if ((mbind == PER_VERTEX_INDEXED) && ((mindices == cindices) || (mindices == NULL))) {
      lelem = (SoGLLazyElement*) SoLazyElement::getInstance(state);
      colorvbo = vboelem->getColorVBO();
      if (colorvbo) dova = TRUE;
      else {
        // we might be able to do VA-rendering, but need to check the
        // diffuse color type first.
        if (!lelem->isPacked() && lelem->getNumTransparencies() <= 1) {
          dova = TRUE;
        }
      }
    }
  }
  if (dova) {
    SbBool dovbo = this->startVertexArray(action,
                                          coords,
                                          (nbind != OVERALL) ? normals : NULL,
                                          doTextures,
                                          mbind != OVERALL);
    LOCK_VAINDEXER(this);
    if (THIS->vaindexer == NULL) {
      SoVertexArrayIndexer * indexer = new SoVertexArrayIndexer;
      int i = 0;
      while (i < numindices) {
        int cnt = 0;
        while (i + cnt < numindices && cindices[i+cnt] >= 0) cnt++;
        
        switch (cnt) {
        case 3:
          indexer->addTriangle(cindices[i],cindices[i+1], cindices[i+2]);
          break;
        case 4:
          indexer->addQuad(cindices[i],cindices[i+1],cindices[i+2],cindices[i+3]);
          break;
        default:
          if (cnt > 4) {
            indexer->beginTarget(GL_POLYGON);
            for (int j = 0; j < cnt; j++) {
              indexer->targetVertex(GL_POLYGON, cindices[i+j]);
            }
            indexer->endTarget(GL_POLYGON);
          }
        }
        i += cnt + 1;
      }
      indexer->close();
      if (indexer->getNumVertices()) {
        THIS->vaindexer = indexer;
      }
      else {
        delete indexer;
      }
#if 0
      fprintf(stderr,"XXX: create VertexArrayIndexer: %d\n", indexer->getNumVertices());
#endif
    }

    if (THIS->vaindexer) {
      THIS->vaindexer->render(sogl_glue_instance(state), dovbo, contextid);
    }
    UNLOCK_VAINDEXER(this);
    this->finishVertexArray(action,
                            dovbo,
                            (nbind != OVERALL),
                            doTextures,
                            mbind != OVERALL);
  }
#else // COIN_NEXT_MINOR
  if (0) { }
#endif // !COIN_NEXT_MINOR
  else {
    sogl_render_faceset((SoGLCoordinateElement *)coords,
                        cindices,
                        numindices,
                        normals,
                        nindices,
                        &mb,
                        mindices,
                        &tb,
                        tindices,
                        (int)nbind,
                        (int)mbind,
                        doTextures?1:0);
  }
  if (normalCacheUsed) {
    this->readUnlockNormalCache();
  }

  if (convexcacheused) {
    THIS->readUnlockConvexCache();
  }

  if (hasvp) {
    state->pop();
  }
  // send approx number of triangles for autocache handling
  sogl_autocache_update(state, this->coordIndex.getNum() / 4);
}

  // this macro actually makes the code below more readable  :-)
#define DO_VERTEX(idx) \
  if (mbind == PER_VERTEX) {                  \
    pointDetail.setMaterialIndex(matnr);      \
    vertex.setMaterialIndex(matnr++);         \
  }                                           \
  else if (mbind == PER_VERTEX_INDEXED) {     \
    pointDetail.setMaterialIndex(*mindices); \
    vertex.setMaterialIndex(*mindices++); \
  }                                         \
  if (nbind == PER_VERTEX) {                \
    pointDetail.setNormalIndex(normnr);     \
    currnormal = &normals[normnr++];        \
    vertex.setNormal(*currnormal);          \
  }                                         \
  else if (nbind == PER_VERTEX_INDEXED) {   \
    pointDetail.setNormalIndex(*nindices);  \
    currnormal = &normals[*nindices++];     \
    vertex.setNormal(*currnormal);          \
  }                                        \
  if (tb.isFunction()) {                 \
    vertex.setTextureCoords(tb.get(coords->get3(idx), *currnormal)); \
    if (tb.needIndices()) pointDetail.setTextureCoordIndex(tindices ? *tindices++ : texidx++); \
  }                                         \
  else if (tbind != NONE) {                      \
    pointDetail.setTextureCoordIndex(tindices ? *tindices : texidx); \
    vertex.setTextureCoords(tb.get(tindices ? *tindices++ : texidx++)); \
  }                                         \
  vertex.setPoint(coords->get3(idx));        \
  pointDetail.setCoordinateIndex(idx);      \
  this->shapeVertex(&vertex);

// doc from parent
void
SoIndexedFaceSet::generatePrimitives(SoAction *action)
{
  if (this->coordIndex.getNum() < 3) return;

  SoState * state = action->getState();

  if (this->vertexProperty.getValue()) {
    state->push();
    this->vertexProperty.getValue()->doAction(action);
  }

  Binding mbind = this->findMaterialBinding(state);
  Binding nbind = this->findNormalBinding(state);

  const SoCoordinateElement * coords;
  const SbVec3f * normals;
  const int32_t * cindices;
  int numindices;
  const int32_t * nindices;
  const int32_t * tindices;
  const int32_t * mindices;
  SbBool doTextures;
  SbBool sendNormals;
  SbBool normalCacheUsed;

  sendNormals = TRUE; // always generate normals

  getVertexData(state, coords, normals, cindices,
                nindices, tindices, mindices, numindices,
                sendNormals, normalCacheUsed);

  SoTextureCoordinateBundle tb(action, FALSE, FALSE);
  doTextures = tb.needCoordinates();

  if (!sendNormals) nbind = OVERALL;
  else if (normalCacheUsed && nbind == PER_VERTEX) {
    nbind = PER_VERTEX_INDEXED;
  }
  else if (normalCacheUsed && nbind == PER_FACE_INDEXED) {
    nbind = PER_FACE;
  }

  if (this->getNodeType() == SoNode::VRML1) {
    // For VRML1, PER_VERTEX means per vertex in shape, not PER_VERTEX
    // on the state.
    if (mbind == PER_VERTEX) {
      mbind = PER_VERTEX_INDEXED;
      mindices = cindices;
    }
    if (nbind == PER_VERTEX) {
      nbind = PER_VERTEX_INDEXED;
      nindices = cindices;
    }
  }

  Binding tbind = NONE;
  if (doTextures) {
    if (tb.isFunction() && !tb.needIndices()) {
      tbind = NONE;
      tindices = NULL;
    }
    // FIXME: just call inherited::areTexCoordsIndexed() instead of
    // the if-check? 20020110 mortene.
    else if (SoTextureCoordinateBindingElement::get(state) ==
             SoTextureCoordinateBindingElement::PER_VERTEX) {
      tbind = PER_VERTEX;
      tindices = NULL;
    }
    else {
      tbind = PER_VERTEX_INDEXED;
      if (tindices == NULL) tindices = cindices;
    }
  }

  if (nbind == PER_VERTEX_INDEXED && nindices == NULL) {
    nindices = cindices;
  }
  if (mbind == PER_VERTEX_INDEXED && mindices == NULL) {
    mindices = cindices;
  }

  SbBool convexcacheused = FALSE;
  if (this->useConvexCache(action, normals, nindices, normalCacheUsed)) {
    cindices = THIS->convexCache->getCoordIndices();
    numindices = THIS->convexCache->getNumCoordIndices();
    mindices = THIS->convexCache->getMaterialIndices();
    nindices = THIS->convexCache->getNormalIndices();
    tindices = THIS->convexCache->getTexIndices();

    if (mbind == PER_VERTEX) mbind = PER_VERTEX_INDEXED;
    else if (mbind == PER_FACE) mbind = PER_FACE_INDEXED;
    if (nbind == PER_VERTEX) nbind = PER_VERTEX_INDEXED;
    else if (nbind == PER_FACE) nbind = PER_FACE_INDEXED;

    if (tbind != NONE) tbind = PER_VERTEX_INDEXED;
    convexcacheused = TRUE;
  }

  int texidx = 0;
  TriangleShape mode = POLYGON;
  TriangleShape newmode;
  const int32_t *viptr = cindices;
  const int32_t *viendptr = viptr + numindices;
  int32_t v1, v2, v3, v4, v5 = 0; // v5 init unnecessary, but kills a compiler warning.

  SoPrimitiveVertex vertex;
  SoPointDetail pointDetail;
  SoFaceDetail faceDetail;

  vertex.setDetail(&pointDetail);

  SbVec3f dummynormal(0,0,1);
  const SbVec3f *currnormal = &dummynormal;
  if (normals) currnormal = normals;
  vertex.setNormal(*currnormal);

  int matnr = 0;
  int normnr = 0;

  while (viptr + 2 < viendptr) {
    v1 = *viptr++;
    v2 = *viptr++;
    v3 = *viptr++;
    if (v1 < 0 || v2 < 0 || v3 < 0) {
#if COIN_DEBUG
      SoDebugError::postInfo("SoIndexedFaceSet::generatePrimitives",
                             "Polygon with less than three vertices detected. "
                             "Aborting current shape.");
#endif // COIN_DEBUG
      
      break;
    } 
    v4 = viptr < viendptr ? *viptr++ : -1;
    if (v4  < 0) newmode = TRIANGLES;
    else {
      v5 = viptr < viendptr ? *viptr++ : -1;
      if (v5 < 0) newmode = QUADS;
      else newmode = POLYGON;
    }
    if (newmode != mode) {
      if (mode != POLYGON) this->endShape();
      mode = newmode;
      this->beginShape(action, mode, &faceDetail);
    }
    else if (mode == POLYGON) this->beginShape(action, POLYGON, &faceDetail);

    // vertex 1 can't use DO_VERTEX
    if (mbind == PER_VERTEX || mbind == PER_FACE) {
      pointDetail.setMaterialIndex(matnr);
      vertex.setMaterialIndex(matnr++);
    }
    else if (mbind == PER_VERTEX_INDEXED || mbind == PER_FACE_INDEXED) {
      pointDetail.setMaterialIndex(*mindices);
      vertex.setMaterialIndex(*mindices++);
    }
    if (nbind == PER_VERTEX || nbind == PER_FACE) {
      pointDetail.setNormalIndex(normnr);
      currnormal = &normals[normnr++];
      vertex.setNormal(*currnormal);
    }
    else if (nbind == PER_FACE_INDEXED || nbind == PER_VERTEX_INDEXED) {
      pointDetail.setNormalIndex(*nindices);
      currnormal = &normals[*nindices++];
      vertex.setNormal(*currnormal);
    }

    if (tb.isFunction()) {
      vertex.setTextureCoords(tb.get(coords->get3(v1), *currnormal));
      if (tb.needIndices()) pointDetail.setTextureCoordIndex(tindices ? *tindices++ : texidx++); 
    }
    else if (tbind != NONE) {
      pointDetail.setTextureCoordIndex(tindices ? *tindices : texidx);
      vertex.setTextureCoords(tb.get(tindices ? *tindices++ : texidx++));
    }
    pointDetail.setCoordinateIndex(v1);
    vertex.setPoint(coords->get3(v1));
    this->shapeVertex(&vertex);

    DO_VERTEX(v2);
    DO_VERTEX(v3);

    if (mode != TRIANGLES) {
      DO_VERTEX(v4);
      if (mode == POLYGON) {
        DO_VERTEX(v5);
        v1 = viptr < viendptr ? *viptr++ : -1;
        while (v1 >= 0) {
          DO_VERTEX(v1);
          v1 = viptr < viendptr ? *viptr++ : -1;
        }
        this->endShape();
      }
    }
    faceDetail.incFaceIndex();
    if (mbind == PER_VERTEX_INDEXED) {
      mindices++;
    }
    if (nbind == PER_VERTEX_INDEXED) {
      nindices++;
    }
    if (tindices) tindices++;
  }
  if (mode != POLYGON) this->endShape();

  if (normalCacheUsed) {
    this->readUnlockNormalCache();
  }
  if (convexcacheused) {
    THIS->readUnlockConvexCache();
  }

  if (this->vertexProperty.getValue()) {
    state->pop();
  }
}

#undef DO_VERTEX

// doc from parent
void
SoIndexedFaceSet::getPrimitiveCount(SoGetPrimitiveCountAction *action)
{
  if (!this->shouldPrimitiveCount(action)) return;

  int n = this->coordIndex.getNum();
  if (n < 3) return;

  if (action->canApproximateCount()) {
    action->addNumTriangles(n/4);
  }
  else {
    const int32_t * ptr = coordIndex.getValues(0);
    const int32_t * endptr = ptr + n;
    int cnt = 0;
    int add = 0;
    while (ptr < endptr) {
      if (*ptr++ >= 0) cnt++;
      else {
        add += cnt-2;
        cnt = 0;
      }
    }
    // in case index array wasn't terminated with a -1
    if (cnt >= 3) add += cnt-2;
    action->addNumTriangles(add);
  }
}

//
// internal method which checks if convex cache needs to be
// used or (re)created. Returns TRUE if convex cache must be
// used. this->convexCache is then guaranteed to be != NULL.
//
SbBool
SoIndexedFaceSet::useConvexCache(SoAction * action,
                                 const SbVec3f * normals,
                                 const int32_t * nindices,
                                 const SbBool normalsfromcache)
{
  SoState * state = action->getState();
  if (SoShapeHintsElement::getFaceType(state) == SoShapeHintsElement::CONVEX)
    return FALSE;
  
  if (THIS->concavestatus == STATUS_UNKNOWN) {
    const int32_t * ptr = this->coordIndex.getValues(0);
    const int32_t * endptr = ptr + this->coordIndex.getNum();
    int cnt = 0;
    THIS->concavestatus = STATUS_CONVEX;
    while (ptr < endptr) {
      if (*ptr++ >= 0) cnt++;
      else {
        if (cnt > 3) { THIS->concavestatus = STATUS_CONCAVE; break; }
        cnt = 0;
      }
    }
  }
  if (THIS->concavestatus == STATUS_CONVEX) return FALSE;

  THIS->readLockConvexCache();

  if (THIS->convexCache && THIS->convexCache->isValid(state))
    return TRUE;

  THIS->readUnlockConvexCache();
  THIS->writeLockConvexCache();

  if (THIS->convexCache) THIS->convexCache->unref();
  SbBool storedinvalid = SoCacheElement::setInvalid(FALSE);

  // need to send matrix if we have some weird transformation
  SbMatrix modelmatrix = SoModelMatrixElement::get(state);
  if (modelmatrix[3][0] == 0.0f &&
      modelmatrix[3][1] == 0.0f &&
      modelmatrix[3][2] == 0.0f &&
      modelmatrix[3][3] == 1.0f) modelmatrix = SbMatrix::identity();

  // push to create cache dependencies
  state->push();
  THIS->convexCache = new SoConvexDataCache(state);
  THIS->convexCache->ref();
  SoCacheElement::set(state, THIS->convexCache);
  if (this->vertexProperty.getValue()) this->vertexProperty.getValue()->doAction(action);
  const SoCoordinateElement * coords;
  const SbVec3f * dummynormals;
  const int32_t * cindices;
  int numindices;
  const int32_t * dummynindices;
  const int32_t * tindices;
  const int32_t * mindices;
  SbBool dummy;

  // normals was included as parameters to this function (to avoid
  // a double readLock on the normal cache), so tell getVertexData()
  // not to return normals.
  this->getVertexData(state, coords, dummynormals, cindices,
                      dummynindices, tindices, mindices, numindices,
                      FALSE, dummy);
  
  // force a cache-dependency on SoNormalElement
  (void) SoNormalElement::getInstance(state);

  Binding mbind = this->findMaterialBinding(state);
  Binding nbind = this->findNormalBinding(state);

  if (this->getNodeType() == SoNode::VRML1) {
    // For VRML1, PER_VERTEX means per vertex in shape, not PER_VERTEX
    // on the state.
    if (mbind == PER_VERTEX) {
      mbind = PER_VERTEX_INDEXED;
      mindices = cindices;
    }
    if (nbind == PER_VERTEX) {
      nbind = PER_VERTEX_INDEXED;
      nindices = cindices;
    }
  }

  if (normalsfromcache && nbind == PER_VERTEX) {
    nbind = PER_VERTEX_INDEXED;
  }

  Binding tbind = NONE;
  // FIXME: just call inherited::areTexCoordsIndexed() instead of
  // the if-check? 20020110 mortene.
  if (SoTextureCoordinateBindingElement::get(state) ==
      SoTextureCoordinateBindingElement::PER_VERTEX) {
    tbind = PER_VERTEX;
  }
  else {
    tbind = PER_VERTEX_INDEXED;
    if (tindices == NULL) tindices = cindices;
  }

  if (nbind == PER_VERTEX_INDEXED && nindices == NULL) {
    nindices = cindices;
  }
  if (mbind == PER_VERTEX_INDEXED && mindices == NULL) {
    mindices = cindices;
  }
  THIS->convexCache->generate(coords, modelmatrix,
                              cindices, numindices,
                              mindices, nindices, tindices,
                              (SoConvexDataCache::Binding)mbind,
                              (SoConvexDataCache::Binding)nbind,
                              (SoConvexDataCache::Binding)tbind);

  THIS->writeUnlockConvexCache();

  state->pop();
  SoCacheElement::setInvalid(storedinvalid);

  THIS->readLockConvexCache();

  return TRUE;
}

// Documented in superclass.
SbBool
SoIndexedFaceSet::generateDefaultNormals(SoState *, SoNormalBundle *)
{
  // Normals are generated in normal cache.
  return FALSE;
}

// Documented in superclass.
SbBool
SoIndexedFaceSet::generateDefaultNormals(SoState * state,
                                       SoNormalCache * nc)
{
  SbBool ccw = TRUE;
  if (SoShapeHintsElement::getVertexOrdering(state) ==
      SoShapeHintsElement::CLOCKWISE) ccw = FALSE;

  const SbVec3f * coords = SoCoordinateElement::getInstance(state)->getArrayPtr3();
  assert(coords);

  normalcache_set_num_coords_hack(nc, SoCoordinateElement::getInstance(state)->getNum());

  SoNormalBindingElement::Binding normbind =
    SoNormalBindingElement::get(state);

  switch (normbind) {
  case SoNormalBindingElement::PER_VERTEX:
  case SoNormalBindingElement::PER_VERTEX_INDEXED:
    nc->generatePerVertex(coords,
                          coordIndex.getValues(0),
                          coordIndex.getNum(),
                          SoCreaseAngleElement::get(state, this->getNodeType() == SoNode::VRML1),
                          NULL,
                          ccw);
    break;
  case SoNormalBindingElement::PER_FACE:
  case SoNormalBindingElement::PER_FACE_INDEXED:
  case SoNormalBindingElement::PER_PART:
  case SoNormalBindingElement::PER_PART_INDEXED:
    nc->generatePerFace(coords,
                        coordIndex.getValues(0),
                        coordIndex.getNum(),
                        ccw);
    break;
  default:
    break;
  }
  return TRUE;
}

#undef THIS
#undef STATUS_UNKNOWN
#undef STATUS_CONVEX
#undef STATUS_CONCAVE
#undef LOCK_VAINDEXER
#undef UNLOCK_VAINDEXER
