Subversion Repositories gelsvn

Rev

Rev 595 | Details | Compare with Previous | Last modification | View Log | RSS feed

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