Subversion Repositories gelsvn

Rev

Rev 291 | Go to most recent revision | Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
290 jrf 1 
#include <cfloat>
2 
#include <queue>
3 
#include <algorithm>
4 
#include <vector>
5 
#include <GL/gl.h>
6 
#include "AABox.h"
7 
#include "OBox.h"
8 
#include "BoundingTree.h"
9 
 
10 
using namespace std;
11 
using namespace CGLA;
12 
 
13 
 
14 
namespace
15 
{
16 
	template <class _Tp>
17 
	inline const _Tp& my_min(const _Tp& __a, const _Tp& __b)
18 
	{
19 
		return __b < __a ? __b : __a;
20 
	}
21 
	template <class _Tp>
22 
	inline const _Tp& my_max(const _Tp& __a, const _Tp& __b)
23 
	{
24 
		return  __a < __b ? __b : __a;
25 
	}
26 
 
27 
}
28 
 
29 
template<class BoxType>
30 
bool BoundingTree<BoxType>::intersect(const CGLA::Vec3f& p , const CGLA::Vec3f& dir,
31 
																float& tmin) const
32 
{
33 
	return root->intersect(p,dir,tmin);
34 
}
35 
 
36 
template<class BoxType>
37 
int BoundingTree<BoxType>::intersect_cnt(const CGLA::Vec3f& p,
38 
																	 const CGLA::Vec3f& dir) const
39 
{
40 
	return root->intersect_cnt(p,dir);
41 
}
42 
 
43 
template<class BoxType>
44 
void BoundingTree<BoxType>::draw(int lmax)
45 
 
46 
{
47 
	root->draw(0,lmax);
48 
}
49 
 
50 
template<class BoxType>
51 
void BoundingTree<BoxType>::build(std::vector<Triangle>& triangles)
52 
{
53 
	delete root;
54 
	root = Node::build(triangles);
55 
}
56 
 
57 
 
58 
template<class Node>
59 
class HE
60 
{
61 
	const Node* node;
62 
	float sq_dist_min;
63 
	float sq_dist_max;
64 
	float sgn;
65 
 
66 
public:
67 
 
68 
	HE() {}
69 
 
70 
	HE(const Vec3f& p, const Node*_node):
71 
		node(_node), sq_dist_min(FLT_MAX), sq_dist_max(FLT_MAX), sgn(0)
72 
 
73 
	{
74 
		node->sq_distance(p,sq_dist_min,sq_dist_max, sgn);
75 
	}
76 
 
77 
	float get_sq_dist_min() const {return sq_dist_min;}
78 
	float get_sq_dist_max() const {return sq_dist_max;}
79 
 
80 
	float get_dist() const {return sgn * sqrt(sq_dist_min);}
81 
 
82 
	const Node* get_node() const
83 
	{
84 
		return node;
85 
	}
86 
 
87 
	bool operator<(const HE<Node>& r)
88 
	{
89 
		return r.sq_dist_min< sq_dist_min;
90 
	}
91 
 
92 
};
93 
 
94 
 
95 
 
96 
template<class BoxType>
97 
float BoundingTree<BoxType>::compute_signed_distance(const CGLA::Vec3f& p,
98 
																										 float minmax) const
99 
{
100 
	int N=100;
101 
	vector<HE<Node> > Q(N);
102 
	Q[0] = HE<Node>(p,root);
103 
 
104 
	HE<Node> *Q_beg = &Q[0];
105 
	int Q_end = 1;
106 
	int pushes = 1;
107 
	while(const IntNode* n = dynamic_cast<const IntNode*>(Q[0].get_node()))
108 
		{
109 
			float q0_max= Q[0].get_sq_dist_max();
110 
			float q0_min= Q[0].get_sq_dist_min();
111 
			pop_heap(Q_beg, Q_beg + Q_end);
112 
			--Q_end;
113 
 
114 
 
115 
			HE<Node> hl(p,n->get_left());
116 
			if(hl.get_sq_dist_min() < (minmax + DIST_THRESH))
117 
				{
118 
					if(hl.get_sq_dist_max() < minmax)
119 
							minmax = hl.get_sq_dist_max();
120 
 
121 
					Q[Q_end++] = hl;
122 
					push_heap(Q_beg, Q_beg + Q_end);
123 
					if(Q_end == N)
124 
						{
125 
							Q.resize(N=2*N);
126 
							Q_beg = &Q[0];
127 
						}
128 
					++pushes;
129 
				}
130 
 
131 
			HE<Node> hr(p,n->get_right());
132 
			if(hr.get_sq_dist_min() < (minmax + DIST_THRESH))
133 
				{
134 
					if(hr.get_sq_dist_max() < minmax)
135 
							minmax = hr.get_sq_dist_max();
136 
 
137 
					Q[Q_end++] = hr;
138 
					push_heap(Q_beg, Q_beg + Q_end);
139 
					if(Q_end == N)
140 
						{
141 
							Q.resize(N=2*N);
142 
							Q_beg = &Q[0];
143 
						}
144 
					++pushes;
145 
				}
146 
 
147 
//  			if((hr.get_sq_dist_min() > (q0_max + DIST_THRESH)) &&
148 
// 				 (hl.get_sq_dist_min() > (q0_max + DIST_THRESH)) )
149 
// 				{
150 
// 					cout.precision(4);
151 
// 					cout << q0_min << " " << q0_max << endl;
152 
// 					cout << hl.get_sq_dist_min() << endl;
153 
// 					cout << hr.get_sq_dist_min() << endl;
154 
// 					cout << typeid(*n).name() << endl;
155 
// 					if(const LeafNode* ll =dynamic_cast<const LeafNode*>(hl.get_node()))
156 
// 						{
157 
// 							ll->get_tri().print();
158 
// 							cout << sqr_length(p-ll->get_tri().get_v0()) << endl;
159 
// 							cout << sqr_length(p-ll->get_tri().get_v1()) << endl;
160 
// 							cout << sqr_length(p-ll->get_tri().get_v2()) << endl;
161 
// 							float d=FLT_MAX, s;
162 
// 							ll->get_tri().signed_distance(p,d,s);
163 
// 							cout << "Dist " << d << endl;
164 
// 						}
165 
// 					if(const LeafNode* lr =dynamic_cast<const LeafNode*>(hr.get_node()))
166 
// 						{
167 
// 							lr->get_tri().print();
168 
// 							cout << sqr_length(p-lr->get_tri().get_v0()) << endl;
169 
// 							cout << sqr_length(p-lr->get_tri().get_v1()) << endl;
170 
// 							cout << sqr_length(p-lr->get_tri().get_v2()) << endl;
171 
// 							float d=FLT_MAX, s;
172 
// 							lr->get_tri().signed_distance(p,d,s);
173 
// 							cout << "Dist " << d << endl;
174 
// 						}
175 
// 					cout << "P=" << p<< endl;
176 
// 				}
177 
 
178 
 			assert((hr.get_sq_dist_min() < (q0_max + DIST_THRESH)) ||
179 
 						 (hl.get_sq_dist_min() < (q0_max + DIST_THRESH)) );
180 
			assert(Q_end > 0);
181 
			assert(Q_end <=N);
182 
		}
183 
	return Q[0].get_dist();
184 
}
185 
 
186 
template BoundingTree<AABox>;
187 
template BoundingTree<OBox>;