Subversion Repositories gelsvn

Rev

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

Rev Author Line No. Line
290 jrf 1 
#include "build_bbtree.h"
2 
#include "HMesh/VertexCirculator.h"
3 
#include "HMesh/FaceCirculator.h"
4 
 
5 
 
6 
using namespace CGLA;
7 
using namespace std;
8 
using namespace HMesh;
9 
 
10 
namespace
11 
{
12 
	const float EDGE_MIN_SQ_LENGTH = 1e-10;
13 
 
14 
	inline bool degenerate_edge(HalfEdgeIter he)
15 
	{
16 
		if(sqr_length(he->vert->pos-he->opp->vert->pos)<1e-8)
17 
			return true;
18 
		return false;
19 
	}
20 
 
21 
}
22 
 
23 
template<class BBTree>
24 
void build_tree_robust(Manifold& m, BBTree& tree)
25 
{
26 
#ifdef COMPUTE_SIGN
27 
	vector<Vec3f> face_normals(m.no_faces());
28 
 
29 
	int i=0;
30 
	for(FaceIter fi=m.faces_begin(); fi != m.faces_end();++fi,++i)
31 
		{
32 
			face_normals[i] = normal(fi);
33 
			fi->touched = i;
34 
		}
35 
 
36 
	for(HalfEdgeIter ei=m.halfedges_begin(); ei != m.halfedges_end();++ei)
37 
		ei->touched = -1;
38 
 
39 
	i=0;
40 
	vector<Vec3f> edge_normals(0);
41 
	for(HalfEdgeIter ei=m.halfedges_begin(); ei != m.halfedges_end();++ei)
42 
		{
43 
			if(ei->touched == -1)
44 
				{
45 
					Vec3f n_a = face_normals[ei->face->touched];
46 
					Vec3f n_b = n_a;
47 
					if(ei->opp->face != NULL_FACE_ITER)
48 
						n_b = face_normals[ei->opp->face->touched];
49 
 
50 
					edge_normals.push_back(normalize(n_a+n_b));
51 
					ei->touched = i;
52 
					ei->opp->touched = i;
53 
					++i;
54 
				}
55 
		}
56 
 
57 
	for(VertexIter vi=m.vertices_begin(); vi != m.vertices_end(); ++vi)
58 
		vi->touched = -1;
59 
 
60 
	int vertex_cluster_number=0;
61 
	vector<Vec3f> vertex_normals(m.no_vertices());
62 
	for(VertexIter vi=m.vertices_begin(); vi != m.vertices_end(); ++vi)
63 
		{
64 
			if(vi->touched == -1)
65 
				{
66 
					int cluster_size=0;
67 
					Vec3f nsum(0);
68 
					vector<VertexIter> cluster(1,vi);
69 
					while(!cluster.empty())
70 
						{
71 
							cluster_size ++;
72 
							VertexIter vert_iter = cluster.back();
73 
							cluster.pop_back();
74 
							vert_iter->touched = vertex_cluster_number;
75 
 
76 
							vector<VertexIter> nbrs;
77 
							VertexCirculator vc(vert_iter);
78 
							for(;!vc.end();++vc)
79 
								nbrs.push_back(vc.get_vertex());
80 
 
81 
							int N = vc.no_steps();
82 
							Vec3f p = vert_iter->pos;
83 
							for(int j=0;j<N;++j)
84 
								{
85 
									Vec3f va = nbrs[(j+1)%N]->pos - p;
86 
									Vec3f vb = nbrs[j]->pos - p;
87 
									if(sqr_length(vb) > EDGE_MIN_SQ_LENGTH)
88 
										{
89 
											if(sqr_length(va) > EDGE_MIN_SQ_LENGTH)
90 
												{
91 
													va.normalize();
92 
													vb.normalize();
93 
													float a = acos(dot(va,vb));
94 
													nsum += a*normalize(cross(va,vb));
95 
												}
96 
										}
97 
 									else
98 
 										{
99 
 											if(nbrs[j]->touched != vertex_cluster_number)
100 
 												{
101 
 													assert(nbrs[j]->touched == -1);
102 
 													cluster.push_back(nbrs[j]);
103 
 												}
104 
 										}
105 
								}
106 
						}
107 
					vertex_normals[vertex_cluster_number] = normalize(nsum);
108 
					++vertex_cluster_number;
109 
 					if(cluster_size > 1) cout << "Cluster Size "
110 
 																		<< cluster_size << " normal "
111 
																		<< normalize(nsum) << endl;
112 
				}
113 
		}
114 
 
115 
	vector<Triangle> triangle_vec;
116 
 
117 
	i=0;
118 
	for(FaceIter fi=m.faces_begin(); fi != m.faces_end();++fi,++i)
119 
		{
120 
			Vec3f fn = face_normals[fi->touched];
121 
 
122 
			FaceCirculator fc(fi);
123 
 
124 
			Vec3f v0,v1,v2;
125 
			Vec3f vn0,vn1,vn2;
126 
			Vec3f en0,en1,en2;
127 
 
128 
			v0  = fc.get_vertex()->pos;
129 
			vn0 = vertex_normals[fc.get_vertex()->touched];
130 
			en0 = edge_normals[fc.get_halfedge()->touched];
131 
 
132 
			++fc;
133 
 
134 
			v1  = fc.get_vertex()->pos;
135 
			vn1 = vertex_normals[fc.get_vertex()->touched];
136 
			en1 = edge_normals[fc.get_halfedge()->touched];
137 
 
138 
			++fc;
139 
 
140 
			v2  = fc.get_vertex()->pos;
141 
			vn2 = vertex_normals[fc.get_vertex()->touched];
142 
			en2 = edge_normals[fc.get_halfedge()->touched];
143 
 
144 
			if(sqr_length(v0-v1)>EDGE_MIN_SQ_LENGTH &&
145 
				 sqr_length(v1-v2)>EDGE_MIN_SQ_LENGTH &&
146 
				 sqr_length(v2-v0)>EDGE_MIN_SQ_LENGTH)
147 
					triangle_vec.push_back(Triangle(v0,v1,v2,vn0,vn1,vn2,en0,en1,en2));
148 
			// 			else
149 
			// 				cout << "Killing degenerate triangle" << endl;
150 
		}
151 
#else
152 
	vector<Triangle> triangle_vec;
153 
	int i=0;
154 
	for(FaceIter fi=m.faces_begin(); fi != m.faces_end();++fi,++i)
155 
		{
156 
			FaceCirculator fc(fi);
157 
			Vec3f v0,v1,v2;
158 
			Vec3f dmy(0);
159 
			v0  = fc.get_vertex()->get_pos();
160 
			++fc;
161 
			v1  = fc.get_vertex()->get_pos();
162 
			++fc;
163 
			v2  = fc.get_vertex()->get_pos();
164 
			if(sqr_length(v0-v1)>EDGE_MIN_SQ_LENGTH &&
165 
				 sqr_length(v1-v2)>EDGE_MIN_SQ_LENGTH &&
166 
				 sqr_length(v2-v0)>EDGE_MIN_SQ_LENGTH)
167 
					triangle_vec.push_back(Triangle(v0,v1,v2,dmy,dmy,dmy,dmy,dmy,dmy));
168 
		}
169 
#endif
170 
 
171 
	tree.build(triangle_vec);
172 
}
173 
 
174 
void build_OBBTree(HMesh::Manifold& m, OBBTree& tree)
175 
{
176 
	build_tree_robust<OBBTree>(m, tree);
177 
}
178 
 
179 
void build_AABBTree(HMesh::Manifold& m, AABBTree& tree)
180 
{
181 
	build_tree_robust<AABBTree>(m, tree);
182 
}
183 
 
184