156 lines
3.0 KiB
C++
156 lines
3.0 KiB
C++
/* -----------------------------------------------------------------------------
|
|
GSFramework
|
|
Copyright 2001-2013 Emmanuel Julien. All Rights Reserved.
|
|
----------------------------------------------------------------------------- */
|
|
|
|
|
|
#ifndef __nPathKdtree__
|
|
#define __nPathKdtree__
|
|
|
|
|
|
#include "core/geometry_tree.h"
|
|
#include "container/narray.h"
|
|
#include "container/narray_list.h"
|
|
#include "memory/nshared_ptr.h"
|
|
|
|
|
|
namespace GS {
|
|
namespace Render { class Renderer; }
|
|
|
|
struct nMSegment : public SharedObject
|
|
{
|
|
Vector4 a,b;
|
|
float a_t, b_t;
|
|
MinMax bounding_box;
|
|
|
|
MinMax GetBoundingBox()
|
|
{
|
|
Vector4 min;
|
|
Vector4 max;
|
|
if(a.x > b.x)
|
|
{
|
|
min.x = b.x;
|
|
max.x = a.x;
|
|
}
|
|
else
|
|
{
|
|
min.x = a.x;
|
|
max.x = b.x;
|
|
}
|
|
if(a.y > b.y)
|
|
{
|
|
min.y = b.y;
|
|
max.y = a.y;
|
|
}
|
|
else
|
|
{
|
|
min.y = a.y;
|
|
max.y = b.y;
|
|
}
|
|
if(a.z > b.z)
|
|
{
|
|
min.z = b.z;
|
|
max.z = a.z;
|
|
}
|
|
else
|
|
{
|
|
min.z = a.z;
|
|
max.z = b.z;
|
|
}
|
|
|
|
bounding_box = MinMax(min, max);
|
|
return bounding_box;
|
|
}
|
|
};
|
|
|
|
/*!
|
|
@short Geometry polygon KD-tree.
|
|
@author Thomas Simonnet (thomas@movida-mail.com)
|
|
*/
|
|
class PathKdtree
|
|
{
|
|
private:
|
|
|
|
struct KDTreeNode
|
|
{
|
|
char m_KDTREE_NODE_TYPE_SPLIT;
|
|
int m_KDTREE_NODE_ID_ROPE[6];
|
|
float m_KDTREE_NODE_AABB[6];
|
|
float m_KDTREE_NODE_VALUE_SPLIT;
|
|
int m_KDTREE_NODE_ID;
|
|
int m_KDTREE_NODE_ID_CHILD_LEFT;
|
|
int m_KDTREE_NODE_ID_CHILD_RIGHT;
|
|
bool m_KDTREE_NODE_IS_LEAF;
|
|
int m_KDTREE_NODE_COUNT_SEGMENT;
|
|
int* m_KDTREE_NODE_ID_SEGMENT;
|
|
|
|
KDTreeNode();
|
|
~KDTreeNode(){delete []m_KDTREE_NODE_ID_SEGMENT;};
|
|
};
|
|
|
|
#define KDTREE_X_AXIS 0
|
|
#define KDTREE_Y_AXIS 1
|
|
#define KDTREE_Z_AXIS 2
|
|
|
|
#define KDTREE_SIDE_LEFT 0
|
|
#define KDTREE_SIDE_RIGHT 1
|
|
#define KDTREE_SIDE_BOTTOM 2
|
|
#define KDTREE_SIDE_TOP 3
|
|
#define KDTREE_SIDE_BACK 4
|
|
#define KDTREE_SIDE_FRONT 5
|
|
|
|
int m_count_bih;
|
|
float * m_TempFloatBih;
|
|
|
|
KDTreeNode* m_NodeTree;
|
|
int m_SizeTree;
|
|
|
|
protected:
|
|
|
|
void DrawKdtreeNode(Render::Renderer &render, int _CurrentNode, Matrix4& m);
|
|
void IncreaseSizeNodeKdtreeBuffer(int _IncreaseSize);
|
|
void CreateNodeKdtree(int &_CurrentNode, int *_IdSegment, int _CountSegment, int _CurrentDepth, bool _ForceCreateLeaf=false);
|
|
|
|
public:
|
|
|
|
SharedArrayList<nMSegment*> segment_list;
|
|
|
|
void draw_scene_debug(Render::Renderer &render, Matrix4& m);
|
|
|
|
/*!
|
|
@name KD-Tree specific functions.
|
|
@{
|
|
*/
|
|
/// Retrieve the index of the closest KD-tree node to a given location in world space.
|
|
int InsideKdTreeNode(const Vector4 &p, bool CheckInside=false);
|
|
bool InsideKdTree(const Vector4 &p);
|
|
|
|
/// @}
|
|
|
|
/*!
|
|
@name Interface core functions.
|
|
@{
|
|
*/
|
|
/// Raytrace the geometry tree.
|
|
void NearestQuadtreeTreeNode(Vector4 p, SharedArrayList<nMSegment*> &list_segment);
|
|
|
|
void BuildQuadtree();
|
|
|
|
/// add object to the quadtree.
|
|
virtual bool AddSegment(nMSegment* segment);
|
|
virtual bool AddSegment(SharedArrayList<nMSegment*> segment_list);
|
|
|
|
/// Free all internal structures.
|
|
virtual void Free();
|
|
/// @}
|
|
|
|
PathKdtree();
|
|
~PathKdtree()
|
|
{ Free(); }
|
|
};
|
|
|
|
} // GS
|
|
|
|
|
|
#endif // __nPathKdtree__
|