Subversion Repositories gelsvn

Rev

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