Added BKE_freestyle_lineset_delete() by generalizing FRS_delete_active_lineset().
[blender.git] / source / blender / blenkernel / BKE_bvhutils.h
index dd9ea61f24b0b539d69aab085b7eb12533583268..4bc8fc44bb4617c5562c5fe7c58dc352caf78e91 100644 (file)
@@ -1,7 +1,4 @@
-/**
- *
- * $Id$
- *
+/*
  * ***** BEGIN GPL LICENSE BLOCK *****
  *
  * This program is free software; you can redistribute it and/or
@@ -16,7 +13,7 @@
  *
  * You should have received a copy of the GNU General Public License
  * along with this program; if not, write to the Free Software Foundation,
- * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  *
  * The Original Code is Copyright (C) 2006 by NaN Holding BV.
  * All rights reserved.
  *
  * ***** END GPL LICENSE BLOCK *****
  */
-#ifndef BKE_BVHUTILS_H
-#define BKE_BVHUTILS_H
+#ifndef __BKE_BVHUTILS_H__
+#define __BKE_BVHUTILS_H__
+
+/** \file BKE_bvhutils.h
+ *  \ingroup bke
+ */
 
 #include "BLI_kdopbvh.h"
 
@@ -43,24 +44,28 @@ struct MFace;
 /*
  * struct that kepts basic information about a BVHTree build from a mesh
  */
-typedef struct BVHTreeFromMesh
-{
+typedef struct BVHTreeFromMesh {
        struct BVHTree *tree;
 
        /* default callbacks to bvh nearest and raycast */
        BVHTree_NearestPointCallback nearest_callback;
-       BVHTree_RayCastCallback      raycast_callback;
-
-       /* Mesh represented on this BVHTree */
-       struct DerivedMesh *mesh; 
+       BVHTree_RayCastCallback raycast_callback;
 
        /* Vertex array, so that callbacks have instante access to data */
        struct MVert *vert;
+       struct MEdge *edge;     /* only used for BVHTreeFromMeshEdges */
        struct MFace *face;
+       bool vert_allocated;
+       bool face_allocated;
+       bool edge_allocated;
 
        /* radius for raycast */
        float sphere_radius;
 
+       /* Private data */
+       void *em_evil;  /* var only for snapping */
+       bool cached;
+
 } BVHTreeFromMesh;
 
 /*
@@ -69,12 +74,12 @@ typedef struct BVHTreeFromMesh
  *
  * The tree is build in mesh space coordinates, this means special care must be made on queries
  * so that the coordinates and rays are first translated on the mesh local coordinates.
- * Reason for this is that later bvh_from_mesh_* might use a cache system and so it becames possible to reuse
+ * Reason for this is that later bvh_from_mesh_* might use a cache system and so it becomes possible to reuse
  * a BVHTree.
  * 
  * free_bvhtree_from_mesh should be called when the tree is no longer needed.
  */
-void bvhtree_from_mesh_verts(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
+BVHTree *bvhtree_from_mesh_verts(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
 
 /*
  * Builds a bvh tree where nodes are the faces of the given mesh.
@@ -82,17 +87,62 @@ void bvhtree_from_mesh_verts(struct BVHTreeFromMesh *data, struct DerivedMesh *m
  *
  * The tree is build in mesh space coordinates, this means special care must be made on queries
  * so that the coordinates and rays are first translated on the mesh local coordinates.
- * Reason for this is that later bvh_from_mesh_* might use a cache system and so it becames possible to reuse
+ * Reason for this is that later bvh_from_mesh_* might use a cache system and so it becomes possible to reuse
  * a BVHTree.
+ *
+ * The returned value is the same as in data->tree, its only returned to make it easier to test
+ * the success 
  * 
  * free_bvhtree_from_mesh should be called when the tree is no longer needed.
  */
-void bvhtree_from_mesh_faces(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
+BVHTree *bvhtree_from_mesh_faces(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
+
+BVHTree *bvhtree_from_mesh_edges(struct BVHTreeFromMesh *data, struct DerivedMesh *mesh, float epsilon, int tree_type, int axis);
 
 /*
  * Frees data allocated by a call to bvhtree_from_mesh_*.
  */
 void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data);
 
+/*
+ * Math functions used by callbacks
+ */
+float bvhtree_ray_tri_intersection(const BVHTreeRay *ray, const float m_dist, const float v0[3], const float v1[3], const float v2[3]);
+float nearest_point_in_tri_surface_squared(const float v0[3], const float v1[3], const float v2[3], const float p[3], int *v, int *e, float nearest[3]);
+
+/*
+ * BVHCache
+ */
+
+//Using local coordinates
+#define BVHTREE_FROM_FACES      0
+#define BVHTREE_FROM_VERTICES   1
+#define BVHTREE_FROM_EDGES      2
+
+#define BVHTREE_FROM_FACES_EDITMESH  3
+
+typedef struct LinkNode *BVHCache;
+
+
+/*
+ * Queries a bvhcache for the cache bvhtree of the request type
+ */
+BVHTree *bvhcache_find(BVHCache *cache, int type);
+
+/*
+ * Inserts a BVHTree of the given type under the cache
+ * After that the caller no longer needs to worry when to free the BVHTree
+ * as that will be done when the cache is freed.
+ *
+ * A call to this assumes that there was no previous cached tree of the given type
+ */
+void bvhcache_insert(BVHCache *cache, BVHTree *tree, int type);
+
+/*
+ * inits and frees a bvhcache
+ */
+void bvhcache_init(BVHCache *cache);
+void bvhcache_free(BVHCache *cache);
+
 #endif