Subversion Repositories gelsvn

Rev

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