Context Navigation

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

Revision 376, 10.4 KB checked in by bittner, 19 years ago (diff)
vsspreprocessor kdtree meshkdtree optimization

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
103	for ( ;
104	faceIndex < mFaces.size();
105	faceIndex++) {
106	hits += CastRayToFace(faceIndex, ray, nearestT, nearestFace, instance);
107	if (mIsConvex && nearestFace != -1)
108	break;
109	}
110
111	if ( hits && ray.GetType() == Ray::LOCAL_RAY ) {
112	if (ray.intersections.size())
113	ray.intersections[0] = Ray::Intersection(nearestT, instance, nearestFace);
114	else
115	ray.intersections.push_back(Ray::Intersection(nearestT, instance, nearestFace));
116	}
117
118	return hits;
119	}
120
121	int
122	Mesh::CastRayToSelectedFaces(
123	Ray &ray,
124	const vector<int> &faces,
125	Intersectable *instance
126	)
127	{
128	vector<int>::const_iterator fi;
129	int faceIndex = 0;
130	int hits = 0;
131	float nearestT = MAX_FLOAT;
132	int nearestFace = -1;
133
134	if (ray.GetType() == Ray::LOCAL_RAY && ray.intersections.size())
135	nearestT = ray.intersections[0].mT;
136
137	for ( fi = faces.begin();
138	fi != faces.end();
139	fi++) {
140	hits += CastRayToFace(*fi, ray, nearestT, nearestFace, instance);
141	if (mIsConvex && nearestFace != -1)
142	break;
143	}
144
145	if ( hits && ray.GetType() == Ray::LOCAL_RAY ) {
146	if (ray.intersections.size())
147	ray.intersections[0] = Ray::Intersection(nearestT, instance, nearestFace);
148	else
149	ray.intersections.push_back(Ray::Intersection(nearestT, instance, nearestFace));
150	}
151
152	return hits;
153	}
154
155
156	// int_lineseg returns 1 if the given line segment intersects a 2D
157	// ray travelling in the positive X direction. This is used in the
158	// Jordan curve computation for polygon intersection.
159	inline int
160	int_lineseg(float px,
161	float py,
162	float u1,
163	float v1,
164	float u2,
165	float v2)
166	{
167	float t;
168	float ydiff;
169
170	u1 -= px; u2 -= px; // translate line
171	v1 -= py; v2 -= py;
172
173	if ((v1 > 0 && v2 > 0) \|\|
174	(v1 < 0 && v2 < 0) \|\|
175	(u1 < 0 && u2 < 0))
176	return 0;
177
178	if (u1 > 0 && u2 > 0)
179	return 1;
180
181	ydiff = v2 - v1;
182	if (fabs(ydiff) < Limits::Small) { // denominator near 0
183	if (((fabs(v1) > Limits::Small) \|\|
184	(u1 > 0) \|\| (u2 > 0)))
185	return 0;
186	return 1;
187	}
188
189	t = -v1 / ydiff; // Compute parameter
190
191	return (u1 + t * (u2 - u1)) > 0;
192	}
193
194
195
196	// intersection with the polygonal face of the mesh
197	int
198	Mesh::RayFaceIntersection(const int faceIndex,
199	const Ray &ray,
200	float &t,
201	const float nearestT
202	)
203	{
204	Face *face = mFaces[faceIndex];
205
206	Plane3 plane = GetFacePlane(faceIndex);
207	float dot = DotProd(plane.mNormal, ray.GetDir());
208
209	// Watch for near-zero denominator
210	// ONLY single sided polygons!!!!!
211	if (dot > -Limits::Small)
212	// if (fabs(dot) < Limits::Small)
213	return Ray::NO_INTERSECTION;
214
215	t = (-plane.mD - DotProd(plane.mNormal, ray.GetLoc())) / dot;
216
217	if (t <= Limits::Small)
218	return Ray::INTERSECTION_OUT_OF_LIMITS;
219
220	if (t >= nearestT) {
221	return Ray::INTERSECTION_OUT_OF_LIMITS; // no intersection was found
222	}
223
224	int count = 0;
225	float u, v, u1, v1, u2, v2;
226	int i;
227
228	int paxis = plane.mNormal.DrivingAxis();
229
230	// Project the intersection point onto the coordinate plane
231	// specified by which.
232	ray.Extrap(t).ExtractVerts(&u, &v, paxis);
233
234
235	int size = face->mVertexIndices.size();
236
237	mVertices[face->mVertexIndices[size - 1]].
238	ExtractVerts(&u1, &v1, paxis );
239
240	if (0 && size <= 4) {
241	// assume a convex face
242	for (i = 0; i < size; i++) {
243	mVertices[face->mVertexIndices[i]].ExtractVerts(&u2, &v2, paxis);
244	// line u1, v1, u2, v2
245	if ((v2 - v1)(u1 - u) > (u2 - u1)(v1 - v))
246	return Ray::NO_INTERSECTION;
247	u1 = u2;
248	v1 = v2;
249	}
250
251	return Ray::INTERSECTION;
252	}
253
254	// We're stuck with the Jordan curve computation. Count number
255	// of intersections between the line segments the polygon comprises
256	// with a ray originating at the point of intersection and
257	// travelling in the positive X direction.
258	for (i = 0; i < size; i++) {
259	mVertices[face->mVertexIndices[i]].ExtractVerts(&u2, &v2, paxis);
260	count += (int_lineseg(u, v, u1, v1, u2, v2) != 0);
261	u1 = u2;
262	v1 = v2;
263	}
264
265	// We hit polygon if number of intersections is odd.
266	return (count & 1) ? Ray::INTERSECTION : Ray::NO_INTERSECTION;
267	}
268
269	int
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	return faceIndex;
289	}
290
291	int
292	Mesh::GetRandomVisibleSurfacePoint(Vector3 &point,
293	Vector3 &normal,
294	const Vector3 &viewpoint,
295	const int maxTries
296	)
297	{
298	Plane3 plane;
299	int faceIndex = RandomValue(0, mFaces.size()-1);
300	int tries;
301	for (tries = 0; tries < maxTries; tries++) {
302	Face *face = mFaces[faceIndex];
303	plane = GetFacePlane(faceIndex);
304
305	if (plane.Side(viewpoint) > 0) {
306	point = Vector3(0,0,0);
307	float sum = 0.0f;
308	// pickup a point inside this triangle
309	for (int i = 0; i < face->mVertexIndices.size(); i++) {
310	float r = RandomValue(0,1);
311	sum += r;
312	point += mVertices[face->mVertexIndices[i]]*r;
313	}
314	point *= 1.0f/sum;
315	break;
316	}
317	}
318
319	normal = plane.mNormal;
320	return (tries < maxTries) ? faceIndex + 1 : 0;
321	}
322
323
324	int
325	MeshInstance::CastRay(
326	Ray &ray
327	)
328	{
329	int res = mMesh->CastRay(ray, this);
330	return res;
331	}
332
333	int
334	MeshInstance::CastRay(
335	Ray &ray,
336	const vector<int> &faces
337	)
338	{
339	return mMesh->CastRayToSelectedFaces(ray, faces, this);
340	}
341
342
343
344	int
345	MeshInstance::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal)
346	{
347	return mMesh->GetRandomSurfacePoint(point, normal);
348	}
349
350	int
351	MeshInstance::GetRandomVisibleSurfacePoint(Vector3 &point,
352	Vector3 &normal,
353	const Vector3 &viewpoint,
354	const int maxTries
355	)
356	{
357	return mMesh->GetRandomVisibleSurfacePoint(point, normal, viewpoint, maxTries);
358	}
359
360
361	int
362	TransformedMeshInstance::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal)
363	{
364	int index = mMesh->GetRandomSurfacePoint(point, normal);
365	point = mWorldTransform*point;
366	normal = TransformNormal(mWorldTransform, normal);
367	return index;
368	}
369
370	Plane3
371	Mesh::GetFacePlane(const int faceIndex)
372	{
373	Face *face = mFaces[faceIndex];
374	return Plane3(mVertices[face->mVertexIndices[0]],
375	mVertices[face->mVertexIndices[1]],
376	mVertices[face->mVertexIndices[2]]);
377	}
378
379	bool
380	Mesh::ValidateFace(const int i)
381	{
382	Face *face = mFaces[i];
383
384	Plane3 plane = Plane3(mVertices[face->mVertexIndices[0]],
385	mVertices[face->mVertexIndices[1]],
386	mVertices[face->mVertexIndices[2]]);
387
388	if (!eq(Magnitude(plane.mNormal), 1.0f))
389	return false;
390
391	return true;
392	}
393
394	void
395	Mesh::Cleanup()
396	{
397	int toRemove = 0;
398	FaceContainer newFaces;
399	for (int i=0; i < mFaces.size(); i++)
400	if (ValidateFace(i)) {
401	newFaces.push_back(mFaces[i]);
402	} else {
403	cout<<"d";
404	delete mFaces[i];
405	toRemove++;
406	}
407
408	if (toRemove) {
409	mFaces = newFaces;
410	}
411
412	// cleanup vertices??
413	}
414
415	int
416	TransformedMeshInstance::CastRay(
417	Ray &ray
418	)
419	{
420	ray.ApplyTransform(Invert(mWorldTransform));
421	int res = mMesh->CastRay(ray, this);
422	ray.ApplyTransform(mWorldTransform);
423
424	return res;
425	}
426
427
428	void
429	Mesh::AddTriangle(const Triangle3 &triangle)
430	{
431	int index = mVertices.size();
432
433	for (int i=0; i < 3; i++) {
434	mVertices.push_back(triangle.mVertices[i]);
435	}
436
437	AddFace(new Face(index + 0, index + 1, index + 2) );
438	}
439
440	void
441	Mesh::AddRectangle(const Rectangle3 &rect)
442	{
443	int index = mVertices.size();
444
445	for (int i=0; i < 4; i++) {
446	mVertices.push_back(rect.mVertices[i]);
447	}
448
449	AddFace(new Face(index + 0, index + 1, index + 2, index + 3) );
450	}

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

Download in other formats: