Subversion Repositories gelsvn

Rev

Rev 309 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 309 Rev 595
- 
 
 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 
 
1 
#include "build_bbtree.h"
 7 
#include "build_bbtree.h"
2 
#include "HMesh/VertexCirculator.h"
 - 
 
3 
#include "HMesh/FaceCirculator.h"
 - 
 
4 
 
 8 
 
- 
 
 9 
#include <HMesh/Manifold.h>
5 
 
 10 
 
6 
using namespace CGLA;
 11 
using namespace CGLA;
7 
using namespace std;
 12 
using namespace std;
8 
using namespace HMesh;
 13 
using namespace HMesh;
9 
 
 14 
 
10 
namespace
 15 
namespace
11 
{
 16 
{
12 
	const float EDGE_MIN_SQ_LENGTH = CGLA::MINUTE;
 17 
    const float EDGE_MIN_SQ_LENGTH = CGLA::MINUTE;
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 
 
 18 
 
- 
 
 19 
    inline bool degenerate_edge(const Manifold& m, HalfEdgeID h)
- 
 
 20 
    {
- 
 
 21 
		Walker w = m.walker(h);
- 
 
 22 
        if(sqr_length(m.pos(w.vertex()) - m.pos(w.opp().vertex())) < 1e-8)
23 
namespace Geometry
 23 
            return true;
- 
 
 24 
        return false;
24 
{
 25 
    }
25 
 
 26 
 
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));
 - 
 
151 
			else
 - 
 
152 
					cout << "Killing degenerate triangle" << endl;
 - 
 
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 
}
 27 
}
176 
 
 28 
 
177 
void build_OBBTree(HMesh::Manifold& m, OBBTree& tree)
 29 
namespace Geometry
178 
{
 30 
{
179 
	build_tree_robust<OBBTree>(m, tree);
 - 
 
180 
}
 - 
 
181 
 
 31 
 
- 
 
 32 
    template<class BBTree>
182 
void build_AABBTree(HMesh::Manifold& m, AABBTree& tree)
 33 
    void build_tree_robust(Manifold& m, BBTree& tree)
- 
 
 34 
    {
- 
 
 35 
        vector<Triangle> triangle_vec;
- 
 
 36 
 
- 
 
 37 
        for(FaceIDIterator fi=m.faces_begin(); fi != m.faces_end();++fi)
- 
 
 38 
        {
- 
 
 39 
            Vec3d face_normal = normal(m, *fi);
- 
 
 40
- 
 
 41 
            Walker w = m.walker(*fi);
- 
 
 42 
 
- 
 
 43 
            Vec3f v0,v1,v2;
- 
 
 44 
            Vec3f vn0,vn1,vn2;
- 
 
 45 
            Vec3f en0,en1,en2;
- 
 
 46 
 
- 
 
 47 
            v0  = Vec3f(m.pos(w.vertex()));
- 
 
 48 
            vn0 = Vec3f(normal(m, w.vertex()));
- 
 
 49 
            en0 = Vec3f(normalize(face_normal + normal(m, w.next().opp().face())));
- 
 
 50
- 
 
 51 
            w = w.next();
- 
 
 52 
 
- 
 
 53 
            v1  = Vec3f(m.pos(w.vertex()));
- 
 
 54 
            vn1 = Vec3f(normal(m, w.vertex()));
- 
 
 55 
            en1 = Vec3f(normalize(face_normal + normal(m, w.next().opp().face())));
- 
 
 56 
 
- 
 
 57
- 
 
 58 
            w = w.next();
- 
 
 59 
 
- 
 
 60 
            v2  = Vec3f(m.pos(w.vertex()));
- 
 
 61 
            vn2 = Vec3f(normal(m, w.vertex()));
- 
 
 62 
            en2 = Vec3f(normalize(face_normal + normal(m, w.next().opp().face())));
- 
 
 63
- 
 
 64 
            if(sqr_length(v0-v1)>EDGE_MIN_SQ_LENGTH &&
- 
 
 65 
                sqr_length(v1-v2)>EDGE_MIN_SQ_LENGTH &&
- 
 
 66 
                sqr_length(v2-v0)>EDGE_MIN_SQ_LENGTH)
- 
 
 67 
                triangle_vec.push_back(Triangle(v0,v1,v2,vn0,vn1,vn2,en0,en1,en2));
- 
 
 68 
            else
- 
 
 69 
                cout << "Killing degenerate triangle" << endl;
- 
 
 70 
        }
- 
 
 71 
 
- 
 
 72 
        tree.build(triangle_vec);
- 
 
 73 
    }
183 
{
 74 
 
- 
 
 75 
    void build_OBBTree(HMesh::Manifold& m, OBBTree& tree)
- 
 
 76 
    {
184 
	build_tree_robust<AABBTree>(m, tree);
 77 
        build_tree_robust<OBBTree>(m, tree);
- 
 
 78 
    }
185 
}
 79 
 
- 
 
 80 
    void build_AABBTree(HMesh::Manifold& m, AABBTree& tree)
- 
 
 81 
    {
- 
 
 82 
        build_tree_robust<AABBTree>(m, tree);
- 
 
 83 
    }
186 
 
 84 
 
187 
}
 85 
}
188 
 
 86