Context Navigation

source: trunk/VUT/GtpVisibilityPreprocessor/src/Mesh.cpp @ 340

Revision 340, 9.2 KB checked in by bittner, 19 years ago (diff)
mesh cleanup added

Line
1	#include "Ray.h"
2	#include "Mesh.h"
3	#include "MeshKdTree.h"
4	#include "Triangle3.h"
5
6	int Intersectable::sMailId = 21843194198;
7
8	void
9	Mesh::Preprocess()
10	{
11	Cleanup();
12
13	mBox.Initialize();
14	VertexContainer::const_iterator vi = mVertices.begin();
15	for (; vi != mVertices.end(); vi++) {
16	mBox.Include(*vi);
17	}
18
19	/** true if it is a watertight convex mesh */
20	mIsConvex = false;
21
22	if (mFaces.size() > MeshKdTree::mTermMinCost) {
23	mKdTree = new MeshKdTree(this);
24	MeshKdLeaf root = (MeshKdLeaf )mKdTree->GetRoot();
25	for (int i = 0; i < mFaces.size(); i++)
26	root->mFaces.push_back(i);
27	cout<<"KD";
28	mKdTree->Construct();
29
30	if (mKdTree->GetRoot()->IsLeaf()) {
31	cout<<"d";
32	delete mKdTree;
33	mKdTree = NULL;
34	}
35	}
36	}
37
38	AxisAlignedBox3
39	Mesh::GetFaceBox(const int faceIndex)
40	{
41	Face *face = mFaces[faceIndex];
42	AxisAlignedBox3 box;
43	box.SetMin( mVertices[face->mVertexIndices[0]] );
44	box.SetMax(box.Min());
45	for (int i = 1; i < face->mVertexIndices.size(); i++) {
46	box.Include(mVertices[face->mVertexIndices[i]]);
47	}
48	return box;
49	}
50
51	int
52	Mesh::CastRayToFace(
53	const int faceIndex,
54	Ray &ray,
55	float &nearestT,
56	int &nearestFace,
57	Intersectable *instance
58	)
59	{
60	float t;
61	int hit = 0;
62	if (RayFaceIntersection(faceIndex, ray, t, nearestT) == Ray::INTERSECTION) {
63	switch (ray.GetType()) {
64	case Ray::GLOBAL_RAY:
65	ray.intersections.push_back(Ray::Intersection(t, instance, faceIndex));
66	hit++;
67	break;
68	case Ray::LOCAL_RAY:
69	nearestT = t;
70	nearestFace = faceIndex;
71	hit++;
72	break;
73	case Ray::LINE_SEGMENT:
74	if (t <= 1.0f) {
75	ray.intersections.push_back(Ray::Intersection(t, instance, faceIndex));
76	hit++;
77	}
78	break;
79	}
80	}
81	return hit;
82	}
83
84	int
85	Mesh::CastRay(
86	Ray &ray,
87	MeshInstance *instance
88	)
89	{
90	if (mKdTree) {
91	return mKdTree->CastRay(ray, instance);
92	}
93
94	int faceIndex = 0;
95	int hits = 0;
96	float nearestT = MAX_FLOAT;
97	int nearestFace = -1;
98
99	if (ray.GetType() == Ray::LOCAL_RAY && ray.intersections.size())
100	nearestT = ray.intersections[0].mT;
101
102	for ( ;
103	faceIndex < mFaces.size();
104	faceIndex++) {
105	hits += CastRayToFace(faceIndex, ray, nearestT, nearestFace, instance);
106	if (mIsConvex && nearestFace != -1)
107	break;
108	}
109
110	if ( hits && ray.GetType() == Ray::LOCAL_RAY ) {
111	if (ray.intersections.size())
112	ray.intersections[0] = Ray::Intersection(nearestT, instance, nearestFace);
113	else
114	ray.intersections.push_back(Ray::Intersection(nearestT, instance, nearestFace));
115	}
116
117	return hits;
118	}
119
120	int
121	Mesh::CastRayToSelectedFaces(
122	Ray &ray,
123	const vector<int> &faces,
124	Intersectable *instance
125	)
126	{
127	vector<int>::const_iterator fi;
128	int faceIndex = 0;
129	int hits = 0;
130	float nearestT = MAX_FLOAT;
131	int nearestFace = -1;
132
133	if (ray.GetType() == Ray::LOCAL_RAY && ray.intersections.size())
134	nearestT = ray.intersections[0].mT;
135
136	for ( fi = faces.begin();
137	fi != faces.end();
138	fi++) {
139	hits += CastRayToFace(*fi, ray, nearestT, nearestFace, instance);
140	if (mIsConvex && nearestFace != -1)
141	break;
142	}
143
144	if ( hits && ray.GetType() == Ray::LOCAL_RAY ) {
145	if (ray.intersections.size())
146	ray.intersections[0] = Ray::Intersection(nearestT, instance, nearestFace);
147	else
148	ray.intersections.push_back(Ray::Intersection(nearestT, instance, nearestFace));
149	}
150
151	return hits;
152	}
153
154
155	// int_lineseg returns 1 if the given line segment intersects a 2D
156	// ray travelling in the positive X direction. This is used in the
157	// Jordan curve computation for polygon intersection.
158	inline int
159	int_lineseg(float px,
160	float py,
161	float u1,
162	float v1,
163	float u2,
164	float v2)
165	{
166	float t;
167	float ydiff;
168
169	u1 -= px; u2 -= px; // translate line
170	v1 -= py; v2 -= py;
171
172	if ((v1 > 0 && v2 > 0) \|\|
173	(v1 < 0 && v2 < 0) \|\|
174	(u1 < 0 && u2 < 0))
175	return 0;
176
177	if (u1 > 0 && u2 > 0)
178	return 1;
179
180	ydiff = v2 - v1;
181	if (fabs(ydiff) < Limits::Small) { // denominator near 0
182	if (((fabs(v1) > Limits::Small) \|\|
183	(u1 > 0) \|\| (u2 > 0)))
184	return 0;
185	return 1;
186	}
187
188	t = -v1 / ydiff; // Compute parameter
189
190	return (u1 + t * (u2 - u1)) > 0;
191	}
192
193
194
195	// intersection with the polygonal face of the mesh
196	int
197	Mesh::RayFaceIntersection(const int faceIndex,
198	const Ray &ray,
199	float &t,
200	const float nearestT
201	)
202	{
203	Face *face = mFaces[faceIndex];
204
205	Plane3 plane = GetFacePlane(faceIndex);
206	float dot = DotProd(plane.mNormal, ray.GetDir());
207
208	// Watch for near-zero denominator
209	// ONLY single sided polygons!!!!!
210	if (dot > -Limits::Small)
211	// if (fabs(dot) < Limits::Small)
212	return Ray::NO_INTERSECTION;
213
214	t = (-plane.mD - DotProd(plane.mNormal, ray.GetLoc())) / dot;
215
216	if (t <= Limits::Small)
217	return Ray::INTERSECTION_OUT_OF_LIMITS;
218
219	if (t >= nearestT) {
220	return Ray::INTERSECTION_OUT_OF_LIMITS; // no intersection was found
221	}
222
223	int count = 0;
224	float u, v, u1, v1, u2, v2;
225	int i;
226
227	int paxis = plane.mNormal.DrivingAxis();
228
229	// Project the intersection point onto the coordinate plane
230	// specified by which.
231	ray.Extrap(t).ExtractVerts(&u, &v, paxis);
232
233
234	int size = face->mVertexIndices.size();
235
236	mVertices[face->mVertexIndices[size - 1]].
237	ExtractVerts(&u1, &v1, paxis );
238
239	if (0 && size <= 4) {
240	// assume a convex face
241	for (i = 0; i < size; i++) {
242	mVertices[face->mVertexIndices[i]].ExtractVerts(&u2, &v2, paxis);
243	// line u1, v1, u2, v2
244	if ((v2 - v1)(u1 - u) > (u2 - u1)(v1 - v))
245	return Ray::NO_INTERSECTION;
246	u1 = u2;
247	v1 = v2;
248	}
249
250	return Ray::INTERSECTION;
251	}
252
253	// We're stuck with the Jordan curve computation. Count number
254	// of intersections between the line segments the polygon comprises
255	// with a ray originating at the point of intersection and
256	// travelling in the positive X direction.
257	for (i = 0; i < size; i++) {
258	mVertices[face->mVertexIndices[i]].ExtractVerts(&u2, &v2, paxis);
259	count += (int_lineseg(u, v, u1, v1, u2, v2) != 0);
260	u1 = u2;
261	v1 = v2;
262	}
263
264	// We hit polygon if number of intersections is odd.
265	return (count & 1) ? Ray::INTERSECTION : Ray::NO_INTERSECTION;
266	}
267
268
269	void
270	Mesh::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal)
271	{
272	int faceIndex = RandomValue(0, mFaces.size()-1);
273
274	// assume the face is convex and generate a convex combination
275	//
276	Face *face = mFaces[faceIndex];
277	point = Vector3(0,0,0);
278	float sum = 0.0f;
279	for (int i = 0; i < face->mVertexIndices.size(); i++) {
280	float r = RandomValue(0,1);
281	sum += r;
282	point += mVertices[face->mVertexIndices[i]]*r;
283	}
284	point *= 1.0f/sum;
285
286	normal = GetFacePlane(faceIndex).mNormal;
287	}
288
289
290	int
291	MeshInstance::CastRay(
292	Ray &ray
293	)
294	{
295	int res = mMesh->CastRay(ray, this);
296	return res;
297	}
298
299	int
300	MeshInstance::CastRay(
301	Ray &ray,
302	const vector<int> &faces
303	)
304	{
305	return mMesh->CastRayToSelectedFaces(ray, faces, this);
306	}
307
308
309
310	void
311	MeshInstance::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal)
312	{
313	mMesh->GetRandomSurfacePoint(point, normal);
314	}
315
316	void
317	TransformedMeshInstance::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal)
318	{
319	mMesh->GetRandomSurfacePoint(point, normal);
320	point = mWorldTransform*point;
321	normal = TransformNormal(mWorldTransform, normal);
322	}
323
324	Plane3
325	Mesh::GetFacePlane(const int faceIndex)
326	{
327	Face *face = mFaces[faceIndex];
328	return Plane3(mVertices[face->mVertexIndices[0]],
329	mVertices[face->mVertexIndices[1]],
330	mVertices[face->mVertexIndices[2]]);
331	}
332
333	bool
334	Mesh::ValidateFace(const int i)
335	{
336	Face *face = mFaces[i];
337
338	Plane3 plane = Plane3(mVertices[face->mVertexIndices[0]],
339	mVertices[face->mVertexIndices[1]],
340	mVertices[face->mVertexIndices[2]]);
341
342	if (!eq(Magnitude(plane.mNormal), 1.0f))
343	return false;
344	}
345
346	void
347	Mesh::Cleanup()
348	{
349	int toRemove = 0;
350	FaceContainer newFaces;
351	for (int i=0; i < mFaces.size(); i++)
352	if (ValidateFace(i)) {
353	newFaces.push_back(mFaces[i]);
354	} else {
355	cout<<"d";
356	delete mFaces[i];
357	toRemove++;
358	}
359
360	if (toRemove) {
361	mFaces = newFaces;
362	}
363
364	// cleanup vertices??
365	}
366
367	int
368	TransformedMeshInstance::CastRay(
369	Ray &ray
370	)
371	{
372	ray.ApplyTransform(Invert(mWorldTransform));
373	int res = mMesh->CastRay(ray, this);
374	ray.ApplyTransform(mWorldTransform);
375
376	return res;
377	}
378
379
380	void
381	Mesh::AddTriangle(const Triangle3 &triangle)
382	{
383	int index = mVertices.size();
384
385	for (int i=0; i < 3; i++) {
386	mVertices.push_back(triangle.mVertices[i]);
387	}
388
389	AddFace(new Face(index + 0, index + 1, index + 2) );
390	}
391
392	void
393	Mesh::AddRectangle(const Rectangle3 &rect)
394	{
395	int index = mVertices.size();
396
397	for (int i=0; i < 4; i++) {
398	mVertices.push_back(rect.mVertices[i]);
399	}
400
401	AddFace(new Face(index + 0, index + 1, index + 2, index + 3) );
402	}

Note: See TracBrowser for help on using the repository browser.

Download in other formats: