SoIntersectionDetectionAction.h

/*=======================================================================
 *** THE CONTENT OF THIS WORK IS PROPRIETARY TO FEI S.A.S, (FEI S.A.S.),            ***
 ***              AND IS DISTRIBUTED UNDER A LICENSE AGREEMENT.                     ***
 ***                                                                                ***
 ***  REPRODUCTION, DISCLOSURE,  OR USE,  IN WHOLE OR IN PART,  OTHER THAN AS       ***
 ***  SPECIFIED  IN THE LICENSE ARE  NOT TO BE  UNDERTAKEN  EXCEPT WITH PRIOR       ***
 ***  WRITTEN AUTHORIZATION OF FEI S.A.S.                                           ***
 ***                                                                                ***
 ***                        RESTRICTED RIGHTS LEGEND                                ***
 ***  USE, DUPLICATION, OR DISCLOSURE BY THE GOVERNMENT OF THE CONTENT OF THIS      ***
 ***  WORK OR RELATED DOCUMENTATION IS SUBJECT TO RESTRICTIONS AS SET FORTH IN      ***
 ***  SUBPARAGRAPH (C)(1) OF THE COMMERCIAL COMPUTER SOFTWARE RESTRICTED RIGHT      ***
 ***  CLAUSE  AT FAR 52.227-19  OR SUBPARAGRAPH  (C)(1)(II)  OF  THE RIGHTS IN      ***
 ***  TECHNICAL DATA AND COMPUTER SOFTWARE CLAUSE AT DFARS 52.227-7013.             ***
 ***                                                                                ***
 ***                   COPYRIGHT (C) 1996-2024 BY FEI S.A.S,                        ***
 ***                        BORDEAUX, FRANCE                                        ***
 ***                      ALL RIGHTS RESERVED                                       ***
**=======================================================================*/
/*=======================================================================
** Author      : Sebastien Dedieu (Jul 1997)
**=======================================================================*/
 
 
#ifndef _SO_INTERSECTION_DETECTION_ACTION_
#define _SO_INTERSECTION_DETECTION_ACTION_
 
 
//------------------------------------------------------------------------------
// Includes
 
#include <Inventor/actions/SoAction.h>
#include <Inventor/actions/SoSubAction.h>
#include <Inventor/SoType.h>
#include <Inventor/SbViewportRegion.h>
#include <Inventor/SoPrimitiveVertex.h>
 
//------------------------------------------------------------------------------
// Types declaration
 
 
//------------------------------------------------------------------------------
// Types definition
typedef SbBool SoIntersectionFilterCB(void *userData, 
                                      const SoPath *p1, 
                                      const SoPath *p2);
 
struct SoIntersectingPrimitive {
  enum PrimitiveType {
    SEGMENT = 2,
    LINE_SEGMENT = 2,
    TRIANGLE = 3
  };
  SoPath *path;
  PrimitiveType type;
  SbVec3f vertex[3];
  SbVec3f xf_vertex[3];
};
 
class  SoIntersectionDetectionAction : public SoAction
{
  SO_ACTION_HEADER(SoIntersectionDetectionAction);
 
public:
 
  // Types definitions ---------------------------------------------------------
  enum Resp {
    NEXT_PRIMITIVE,
    NEXT_SHAPE,
    ABORT
  };
 
  typedef Resp SoIntersectionCB(void *userData,
                                const SoIntersectingPrimitive *,
                                const SoIntersectingPrimitive *);
 
  SoIntersectionDetectionAction ();
  ~SoIntersectionDetectionAction();
 
  // Applying the action -------------------------------------------------------
  void apply(SoNode *node);
  void apply(SoPath *path);
  void apply(const SoPathList &pathList, SbBool obeysRules = FALSE);
 
  void setFilterCallback(SoIntersectionFilterCB *newFilterCB, void *data=NULL);
 
  void addIntersectionCallback (SoIntersectionCB* f, void* userData = NULL);
 
  void removeIntersectionCallback(SoIntersectionCB* f, void* userData = NULL);
 
  // Computing types -----------------------------------------------------------
  enum Axis {
    X_AXIS = 1,
    Y_AXIS = 2,
    Z_AXIS = 4
  };
 
  enum Position {
    BEGIN,
    END
  };
#ifndef HIDDEN_FROM_DOC
  struct ShapeInformationItem {
    SoPath *path;
    float xMin, yMin, zMin;
    float xMax, yMax, zMax;
  };
 
  struct CoupleTableItem {
    int overlapFlags;
    float xMin, yMin, zMin;
    float xMax, yMax, zMax;
  };
  
  struct ActiveListItem {
    int shapeIndex;
    enum Position position;
    SbBool toRemove;
    float x, y, z;
  };
  static float m_fIntersectEpsilon;
#endif // HIDDEN_FROM_DOC
 
  static void setIntersectEpsilon(float epsilon);
 
  static  float getIntersectEpsilon();
 
private:
 
  static void initClass();
  static void exitClass();
 
private : 
  friend class SoCollisionManager;
 
  // General data --------------------------------------------------------------
  
  // Flags ---------------------------------------------------------------------
  SbBool m_new_test;
  SbBool m_new_shapes;
 
  // Managing callbacks --------------------------------------------------------
  SoIntersectionFilterCB*  filterCB;
  void*                    userDataFilterCB;
  SoIntersectionCB*        intersectionCB;
  void*                    userDataIntersectionCB;
  void*                    m_callback_list;
  Resp                     response;
  Resp invokeCallbacks (const SoIntersectingPrimitive* p1,
                        const SoIntersectingPrimitive* p2);
 
  // Computing variables -------------------------------------------------------
  int                      shapeCount;
  SbViewportRegion         viewportRegion;
  int                      shapeInformationSize;
  int                      shapeInformationReservedSize;
  ShapeInformationItem*    shapeInformation;
  int                      coupleTableSize;
  int                      coupleTableReservedSize;
  CoupleTableItem*         coupleTable;
  int                      activeListSize;
  int                      activeListReservedSize;
  ActiveListItem*          activeList;
  int                      primitiveTableSize;
  int                      primitiveTableReservedSize;
  SoIntersectingPrimitive* primitiveTable;
  int                      currentShapeIndex1;
  int                      currentShapeIndex2;
  CoupleTableItem*         currentCouple;
 
  // Computing functions -------------------------------------------------------
  void seek (SoSearchAction* search);
  //void shapeInformationBuild(SoNode *root);
  void shapeInformationDestroy();
  void shapeInformationClear();
  void shapeInformationAddItem(SoPath *path);
  //void coupleTableBuild();
  void coupleTableDestroy();
  void coupleTableClear();
  CoupleTableItem * coupleTableGetItem(int shapeIndex1, int shapeIndex2);
  void coupleTableSetOverlaping(int shapeIndex1, int shapeIndex2, 
                                Axis axis);
  void coupleTableUpdate(enum Axis axis);
  //void activeListBuild();
  void activeListDestroy();
  void activeListClear();
  void activeListAddItem(int shapeIndex);
  void activeListSort(int (*compareFunction)(void const *, void const *));
  static int activeListXCompare(void const *pointer1, void const *pointer2);
  static int activeListYCompare(void const *pointer1, void const *pointer2);
  static int activeListZCompare(void const *pointer1, void const *pointer2);
  void activeListClean();
  void primitiveTableBuild();
  void primitiveTableDestroy();
  void primitiveTableClear();
  void primitiveTableReserveSpace();
  void primitiveTableAddTriangle (SoCallbackAction *action,
                                  const SoPrimitiveVertex *vertex1,
                                  const SoPrimitiveVertex *vertex2,
                                  const SoPrimitiveVertex *vertex3);
  void primitiveTableAddLineSegment(SoCallbackAction *action,
                                    const SoPrimitiveVertex *vertex1,
                                    const SoPrimitiveVertex *vertex2);
  void shapesCollisionTest(int shapeIndex1, int shapeIndex2);
 
  void triangleCollisionTest(SoCallbackAction *action,
                             const SoPrimitiveVertex *vertex1,
                             const SoPrimitiveVertex *vertex2,
                             const SoPrimitiveVertex *vertex3);
  void lineSegmentCollisionTest(SoCallbackAction *action,
                                const SoPrimitiveVertex *vertex1,
                                const SoPrimitiveVertex *vertex2);
  static SbBool isTriangleIntersectSegment(const SbVec3f &A,
                                           const SbVec3f &B,
                                           const SbVec3f &C,
                                           const SbVec3f &D, 
                                           const SbVec3f &E);
  static SbBool isTriangleIntersectTriangle (const SoIntersectingPrimitive &triangle1,
                                             const SoIntersectingPrimitive &triangle2);
  static SbBool isSegmentIntersectSegment (const SbVec3f &A,
                                           const SbVec3f &B,
                                           const SbVec3f &C,
                                           const SbVec3f &D);
  
  // Real callbacks ------------------------------------------------------------
  static void primitiveTableAddTriangleCB (void *userData,
                                           SoCallbackAction *action,
                                           const SoPrimitiveVertex *vertex1,
                                           const SoPrimitiveVertex *vertex2,
                                           const SoPrimitiveVertex *vertex3)
  { ((SoIntersectionDetectionAction*) userData)->
      primitiveTableAddTriangle (action, vertex1, vertex2, vertex3); }
  static void primitiveTableAddLineSegmentCB (void *userData,
                                              SoCallbackAction *action,
                                              const SoPrimitiveVertex *vertex1,
                                              const SoPrimitiveVertex *vertex2)
  { ((SoIntersectionDetectionAction*) userData)->
      primitiveTableAddLineSegment (action, vertex1, vertex2); }
  static void triangleCollisionTestCB (void *userData,
                                       SoCallbackAction *action,
                                       const SoPrimitiveVertex *vertex1,
                                       const SoPrimitiveVertex *vertex2,
                                       const SoPrimitiveVertex *vertex3)
  { ((SoIntersectionDetectionAction*) userData)->
      triangleCollisionTest (action, vertex1, vertex2, vertex3); }
  static void lineSegmentCollisionTestCB (void *userData,
                                          SoCallbackAction *action,
                                          const SoPrimitiveVertex *vertex1,
                                          const SoPrimitiveVertex *vertex2)
  { ((SoIntersectionDetectionAction*) userData)->
      lineSegmentCollisionTest (action, vertex1, vertex2); }
 
  // Miscelaneous --------------------------------------------------------------
  void quickSort(void *array, int nElm, int elmSize,
                 int (*compare)(void const *, void const *),
                 char *tmp);
  void sort(void *array, int nElm, int elmSize,
            int (*compare)(void const *, void const *));
 
  static SbThreadMutex classMutex;
};
 
 
#endif // _SO_INTERSECTION_DETECTION_ACTION_