Context Navigation

← Previous Revision
Latest Revision
Next Revision →
Blame
Revision Log

ktbtrav.cpp @ 2582

Revision 2582, 27.2 KB checked in by bittner, 17 years ago (diff)
Havran Ray Caster compiles and links, but still does not work

Line
1	// ===================================================================
2	// $Id: $
3	//
4	// ktbtrav.cpp
5	//
6	// class: CKTBTraversal
7	//
8	// REPLACEMENT_STRING
9	//
10	// Copyright by Vlastimil Havran, 2007 - email to "vhavran AT seznam.cz"
11	// Initial coding by Vlasta Havran, February 2007 (copy from kdrtrav.cpp)
12
13	// GOLEM headers
14	#include "ktbtrav.h"
15	#include "Intersectable.h"
16
17	namespace GtpVisibilityPreprocessor {
18
19	//------------------------------------------------------------------
20	// Robust statistically optimized algorithm for CKTB ray-traversal
21	// original version 025. This algorithm was published at Journal of
22	// Graphics Tools, 1997, Havran et al.
23
24	// the depth of traversal when kd-trees are nested. The global (the highest
25	// level) kd-tree is at the depth 0.
26	int
27	CKTBTraversal::traversalDepth = 0;
28
29	// sets the stack pointers that are used for the traversal.
30	void
31	CKTBTraversal::GetStackPointers(struct SStackElem *&entryPointer,
32	struct SStackElem *&exitPointer)
33	{
34	assert(traversalDepth < MAX_NESTING);
35
36	int index = traversalDepth * MAX_HEIGHT;
37	entryPointer = &(stack[index]);
38	exitPointer = &(stack[index + 1]);
39
40	traversalDepth++;
41	return;
42	}
43
44	// sets the stack pointers that are used for the traversal.
45	void
46	CKTBTraversal::RestoreStackPointers()
47	{
48	assert(traversalDepth >= 0);
49	traversalDepth--;
50	return;
51	}
52
53
54	// default constructor
55	CKTBTraversal::CKTBTraversal()
56	{
57	bbox = AxisAlignedBox3(Vector3(MAXFLOAT),
58	Vector3(-MAXFLOAT));
59	root = 0;
60	epsilon = 0;
61
62	#ifdef __TRAVERSAL_STATISTICS
63	_allNodesTraversed = 0L;
64	_fullLeavesTraversed = 0L;
65	_emptyLeavesTraversed = 0L;
66	#endif
67	}
68
69	// Here we find the node (preferably minbox node) containing
70	// the point
71	const SKTBNodeT*
72	CKTBTraversal::Locate(const Vector3 &position)
73	{
74	const SKTBNodeT current, next = root;
75	const SKTBNodeT *returnNode = 0;
76
77	do {
78	current = next;
79	switch (GetNodeType(current)) {
80	// -------------------------------------------------
81	case CKTBAxes::EE_X_axis: {
82	if (position[CKTBAxes::EE_X_axis] < current->splitPlane)
83	next = GetLeft(current);
84	else
85	next = GetRight(current);
86	break;
87	}
88	case CKTBAxes::EE_Y_axis: {
89	if (position[CKTBAxes::EE_Y_axis] < current->splitPlane)
90	next = GetLeft(current);
91	else
92	next = GetRight(current);
93	break;
94	}
95	case CKTBAxes::EE_Z_axis: {
96	if (position[CKTBAxes::EE_Z_axis] < current->splitPlane)
97	next = GetLeft(current);
98	else
99	next = GetRight(current);
100	break;
101	}
102	case CKTBAxes::EE_X_axisBox: {
103	if (position[CKTBAxes::EE_X_axis] < current->splitPlane)
104	next = GetLeft(current);
105	else
106	next = GetRight(current);
107	returnNode = current;
108	break;
109	}
110	case CKTBAxes::EE_Y_axisBox: {
111	if (position[CKTBAxes::EE_Y_axis] < current->splitPlane)
112	next = GetLeft(current);
113	else
114	next = GetRight(current);
115	returnNode = current;
116	break;
117	}
118	case CKTBAxes::EE_Z_axisBox: {
119	if (position[CKTBAxes::EE_Z_axis] < current->splitPlane)
120	next = GetLeft(current);
121	else
122	next = GetRight(current);
123	returnNode = current;
124	break;
125	}
126	case CKTBAxes::EE_Leaf: {
127	next = 0; // finishing
128	break;
129	}
130	case CKTBAxes::EE_Link:{
131	next = GetLinkNode(current);
132	// cout << "Link node was accessed" << endl;
133	break;
134	}
135	} // switch
136	}
137	while (next != NULL);
138
139	if (returnNode)
140	return returnNode;
141
142	// return the last (leaf node) visited on the path
143	return current;
144	}
145
146	#ifdef TRV000
147	int
148	CKTBTraversal::FindNearestI(const SimpleRay &ray)
149	{
150	// passing through parameters
151	float tmin, tmax;
152
153	// test if the whole CKTB tree is missed by the input ray
154	if ( (!root) \|\|
155	(!bbox.ComputeMinMaxT(ray.mOrigin, ray.mDirection, &tmin, &tmax)) \|\|
156	(tmin >= tmax) \|\|
157	(tmax < 0.f)
158	) {
159	SimpleRay::IntersectionRes[0].intersectable = 0;
160	return 0; // no object can be intersected
161	}
162
163	//#define _DEBUGKTB
164	#ifdef _DEBUGKTB
165	int ib = 0;
166	int depth = 0;
167	#endif
168
169	#ifdef __TRAVERSAL_STATISTICS
170	int allNodesTraversed = 0L;
171	int fullLeavesTraversed = 0L;
172	int emptyLeavesTraversed = 0L;
173	#endif // __TRAVERSAL_STATISTICS
174
175	#ifdef _COMPUTE_INVERTED_DIR_KTB
176	Vector3 invertedDir;
177	invertedDir.x = 1.0f / ray.mDirection.x;
178	invertedDir.y = 1.0f / ray.mDirection.y;
179	invertedDir.z = 1.0f / ray.mDirection.z;
180	#endif // _COMPUTE_INVERTED_DIR_KTB
181
182	// start from the root node
183	SKTBNodeT *currNode = root;
184
185	struct SStackElem entp, extp;
186	GetStackPointers(entp, extp);
187	//struct SStackElem *entp = &(stack[0]);
188	//struct SStackElem *extp = &(stack[1]);
189
190	// exit point setting for the box and the ray
191	extp->x = ray.mOrigin.x + ray.mDirection.x * tmax;
192	extp->y = ray.mOrigin.y + ray.mDirection.y * tmax;
193	extp->z = ray.mOrigin.z + ray.mDirection.z * tmax;
194	extp->nodep = NULL;
195	extp->prev = NULL;
196	extp->t = tmax;
197
198	// entry point setting for the box and the ray
199	entp->nodep = NULL;
200	entp->prev = NULL;
201	if (tmin > 0.0) { // external node
202	entp->x = ray.mOrigin.x + ray.mDirection.x * tmin;
203	entp->y = ray.mOrigin.y + ray.mDirection.y * tmin;
204	entp->z = ray.mOrigin.z + ray.mDirection.z * tmin;
205	entp->t = tmin;
206	}
207	else { // internal node
208	entp->x = ray.mOrigin.x;
209	entp->y = ray.mOrigin.y;
210	entp->z = ray.mOrigin.z;
211	entp->t = 0.0;
212	}
213	SKTBNodeT *farChild;
214
215	// DEBUG << "A: c= " << currNode << "\n" << flush ;
216
217	// traverse through whole CKTB tree
218	for (;;) {
219	#ifndef _ALLOC_EMPTY_LEAVES
220	for (;;) {
221	// label for continuing the traversal
222	#else
223	// we have to check the node
224	// current node is not the leaf, empty leaves are NULL pointers
225	while (currNode) {
226	#endif
227
228	#ifdef _DEBUGKTB
229	cout << "i = " << ib << " node = " << (void*)currNode
230	<< " depth=" << depth << endl;
231	ib++;
232	#endif
233
234	#ifdef __TRAVERSAL_STATISTICS
235	allNodesTraversed++;
236	#endif // __TRAVERSAL_STATISTICS
237	// the position of the splitting plane
238	float splitVal = GetSplitValue(currNode);
239	// decision based on the axis given by splitting plane
240	switch (GetNodeType(currNode) & 0x7) {
241	// -------------------------------------------------
242	case CKTBAxes::EE_X_axis: {
243	#ifdef _DEBUGKTB
244	cout << "X-axis v=" << splitVal << endl;
245	depth++;
246	#endif
247	if (entp->x <= splitVal) {
248	if (extp->x <= splitVal) {
249	currNode = GetLeft(currNode);
250	// cases N1,N2,N3,P5,Z2,Z3
251	continue;
252	}
253	// case N4
254	farChild = GetRight(currNode);
255	currNode = GetLeft(currNode);
256	}
257	else {
258	if (splitVal <= extp->x) {
259	currNode = GetRight(currNode);
260	continue; // cases P1,P2,P3,N5,Z1
261	}
262	farChild = GetLeft(currNode); // case P4
263	currNode = GetRight(currNode);
264	}
265	#ifdef _DEBUGKTB
266	cout << "X-Push right node = " << farChild << endl;
267	#endif
268	// case N4 or P4
269	#ifdef _COMPUTE_INVERTED_DIR_KTB
270	float tdist = (splitVal - ray.mOrigin.x) * invertedDir.x;
271	#else // _COMPUTE_INVERTED_DIR_KTB
272	float tdist = (splitVal - ray.mOrigin.x) / ray.mDirection.x;
273	#endif // _COMPUTE_INVERTED_DIR_KTB
274
275	struct SStackElem *tmp = extp;
276	if (++extp == entp)
277	extp++;
278	#if defined(_KTBEXTSTACK) && defined(_DEBUGKTB)
279	extp->dummy = depth+1;
280	#endif
281	extp->prev = tmp;
282	extp->nodep = farChild;
283	extp->t = tdist;
284	extp->x = splitVal;
285	extp->y = ray.mOrigin.y + tdist * ray.mDirection.y;
286	extp->z = ray.mOrigin.z + tdist * ray.mDirection.z;
287	continue;
288	}
289	// -------------------------------------------------
290	case CKTBAxes::EE_Y_axis: {
291	#ifdef _DEBUGKTB
292	cout << "Y-axis v=" << splitVal << endl;
293	depth++;
294	#endif
295	if (entp->y <= splitVal) {
296	if (extp->y <= splitVal) {
297	currNode = GetLeft(currNode);
298	//case N1,N2,N3,P5,Z2,Z3
299	continue;
300	}
301	// case N4
302	farChild = GetRight(currNode);
303	currNode = GetLeft(currNode);
304	}
305	else {
306	if (splitVal <= extp->y) {
307	currNode = GetRight(currNode);
308	continue; // case P1,P2,P3,N5
309	}
310	farChild = GetLeft(currNode); // case P4
311	currNode = GetRight(currNode);
312	}
313	#ifdef _DEBUGKTB
314	cout << "Y-Push right node = " << farChild << endl;
315	#endif
316	// case N4 or P4
317	#ifdef _COMPUTE_INVERTED_DIR_KTB
318	float tdist = (splitVal - ray.mOrigin.y) * invertedDir.y;
319	#else // _COMPUTE_INVERTED_DIR_KTB
320	float tdist = (splitVal - ray.mOrigin.y) / ray.mDirection.y;
321	#endif // _COMPUTE_INVERTED_DIR_KTB
322
323	struct SStackElem *tmp = extp;
324	if (++extp == entp)
325	extp++;
326	#if defined(_KTBEXTSTACK) && defined(_DEBUGKTB)
327	extp->dummy = depth+1;
328	#endif
329	extp->prev = tmp;
330	extp->nodep = farChild;
331	extp->t = tdist;
332	extp->x = ray.mOrigin.x + tdist * ray.mDirection.x;
333	extp->y = splitVal;
334	extp->z = ray.mOrigin.z + tdist * ray.mDirection.z;
335	continue;
336	}
337	// -------------------------------------------------
338	case CKTBAxes::EE_Z_axis: {
339	#ifdef _DEBUGKTB
340	cout << "Z-axis v=" << splitVal << endl;
341	depth++;
342	#endif
343	if (entp->z <= splitVal) {
344	if (extp->z <= splitVal) {
345	currNode = GetLeft(currNode);
346	//case N1,N2,N3,P5,Z2,Z3
347	continue;
348	}
349	// case N4
350	farChild = GetRight(currNode);
351	currNode = GetLeft(currNode);
352	}
353	else {
354	if (splitVal <= extp->z) {
355	currNode = GetRight(currNode);
356	continue; // case P1,P2,P3,N5
357	}
358	farChild = GetLeft(currNode); // case P4
359	currNode = GetRight(currNode);
360	}
361	#ifdef _DEBUGKTB
362	cout << "Z-Push right node = " << farChild << endl;
363	#endif
364	// case N4 or P4
365	#ifdef _COMPUTE_INVERTED_DIR_KTB
366	float tdist = (splitVal - ray.mOrigin.z) * invertedDir.z;
367	#else // _COMPUTE_INVERTED_DIR_KTB
368	float tdist = (splitVal - ray.mOrigin.z) / ray.mDirection.z;
369	#endif // _COMPUTE_INVERTED_DIR_KTB
370
371	struct SStackElem *tmp = extp;
372	if (++extp == entp)
373	extp++;
374	#if defined(_KTBEXTSTACK) && defined(_DEBUGKTB)
375	extp->dummy = depth+1;
376	#endif
377
378	extp->prev = tmp;
379	extp->nodep = farChild;
380	extp->t = tdist;
381	extp->x = ray.mOrigin.x + tdist * ray.mDirection.x;
382	extp->y = ray.mOrigin.y + tdist * ray.mDirection.y;
383	extp->z = splitVal;
384	continue;
385	}
386	case CKTBAxes::EE_Leaf:
387	{ // test objects for intersection
388	#ifdef _DEBUGKTB
389	cout << "Leaf " << endl;
390	depth++;
391	#endif
392	goto TEST_OBJECTS;
393	}
394	case CKTBAxes::EE_Link:{
395	#ifdef _DEBUGKTB
396	cout << "Link " << endl;
397	#endif
398	currNode = GetLinkNode(currNode);
399	// cout << "Link node was accessed" << endl;
400	continue;
401	}
402	case CKTBAxes::EE_X_axisBox: {
403	#ifdef _DEBUGKTB
404	cout << "X-axis Box v=" << splitVal << endl;
405	depth++;
406	#endif
407	if (entp->x <= splitVal) {
408	if (extp->x <= splitVal) {
409	currNode = GetLeftMinBox(currNode);
410	// cases N1,N2,N3,P5,Z2,Z3
411	continue;
412	}
413	// case N4
414	farChild = GetRight(currNode);
415	currNode = GetLeftMinBox(currNode);
416	}
417	else {
418	if (splitVal <= extp->x) {
419	currNode = GetRight(currNode);
420	continue; // cases P1,P2,P3,N5,Z1
421	}
422	farChild = GetLeftMinBox(currNode); // case P4
423	currNode = GetRight(currNode);
424	}
425	#ifdef _DEBUGKTB
426	cout << "X-Push (Box) right node = " << farChild << endl;
427	#endif
428	// case N4 or P4
429	#ifdef _COMPUTE_INVERTED_DIR_KTB
430	float tdist = (splitVal - ray.mOrigin.x) * invertedDir.x;
431	#else // _COMPUTE_INVERTED_DIR_KTB
432	float tdist = (splitVal - ray.mOrigin.x) / ray.mDirection.x;
433	#endif // _COMPUTE_INVERTED_DIR_KTB
434
435	struct SStackElem *tmp = extp;
436	if (++extp == entp)
437	extp++;
438	#if defined(_KTBEXTSTACK) && defined(_DEBUGKTB)
439	extp->dummy = depth+1;
440	#endif
441	extp->prev = tmp;
442	extp->nodep = farChild;
443	extp->t = tdist;
444	extp->x = splitVal;
445	extp->y = ray.mOrigin.y + tdist * ray.mDirection.y;
446	extp->z = ray.mOrigin.z + tdist * ray.mDirection.z;
447	continue;
448	}
449	// -------------------------------------------------
450	case CKTBAxes::EE_Y_axisBox: {
451	#ifdef _DEBUGKTB
452	cout << "Y-axis Box v=" << splitVal << endl;
453	depth++;
454	#endif
455	if (entp->y <= splitVal) {
456	if (extp->y <= splitVal) {
457	currNode = GetLeftMinBox(currNode);
458	//case N1,N2,N3,P5,Z2,Z3
459	continue;
460	}
461	// case N4
462	farChild = GetRight(currNode);
463	currNode = GetLeftMinBox(currNode);
464	}
465	else {
466	if (splitVal <= extp->y) {
467	currNode = GetRight(currNode);
468	continue; // case P1,P2,P3,N5
469	}
470	farChild = GetLeftMinBox(currNode); // case P4
471	currNode = GetRight(currNode);
472	}
473	#ifdef _DEBUGKTB
474	cout << "Y-Push (Box) right node = " << farChild << endl;
475	#endif
476	// case N4 or P4
477	#ifdef _COMPUTE_INVERTED_DIR_KTB
478	float tdist = (splitVal - ray.mOrigin.y) * invertedDir.y;
479	#else // _COMPUTE_INVERTED_DIR_KTB
480	float tdist = (splitVal - ray.mOrigin.y) / ray.mDirection.y;
481	#endif // _COMPUTE_INVERTED_DIR_KTB
482
483	struct SStackElem *tmp = extp;
484	if (++extp == entp)
485	extp++;
486	#if defined(_KTBEXTSTACK) && defined(_DEBUGKTB)
487	extp->dummy = depth+1;
488	#endif
489	extp->prev = tmp;
490	extp->nodep = farChild;
491	extp->t = tdist;
492	extp->x = ray.mOrigin.x + tdist * ray.mDirection.x;
493	extp->y = splitVal;
494	extp->z = ray.mOrigin.z + tdist * ray.mDirection.z;
495	continue;
496	}
497	// -------------------------------------------------
498	case CKTBAxes::EE_Z_axisBox: {
499	#ifdef _DEBUGKTB
500	cout << "Z-axis Box v=" << splitVal << endl;
501	depth++;
502	#endif
503	if (entp->z <= splitVal) {
504	if (extp->z <= splitVal) {
505	currNode = GetLeftMinBox(currNode);
506	//case N1,N2,N3,P5,Z2,Z3
507	continue;
508	}
509	// case N4
510	farChild = GetRight(currNode);
511	currNode = GetLeftMinBox(currNode);
512	}
513	else {
514	if (splitVal <= extp->z) {
515	currNode = GetRight(currNode);
516	continue; // case P1,P2,P3,N5
517	}
518	farChild = GetLeftMinBox(currNode); // case P4
519	currNode = GetRight(currNode);
520	}
521	#ifdef _DEBUGKTB
522	cout << "Z-Push (Box) right node = " << farChild << endl;
523	#endif
524	// case N4 or P4
525	#ifdef _COMPUTE_INVERTED_DIR_KTB
526	float tdist = (splitVal - ray.mOrigin.z) * invertedDir.z;
527	#else // _COMPUTE_INVERTED_DIR_KTB
528	float tdist = (splitVal - ray.mOrigin.z) / ray.mDirection.z;
529	#endif // _COMPUTE_INVERTED_DIR_KTB
530
531	struct SStackElem *tmp = extp;
532	if (++extp == entp)
533	extp++;
534	#if defined(_KTBEXTSTACK) && defined(_DEBUGKTB)
535	extp->dummy = depth+1;
536	#endif
537
538	extp->prev = tmp;
539	extp->nodep = farChild;
540	extp->t = tdist;
541	extp->x = ray.mOrigin.x + tdist * ray.mDirection.x;
542	extp->y = ray.mOrigin.y + tdist * ray.mDirection.y;
543	extp->z = splitVal;
544	continue;
545	}
546	} // switch
547	} // while current node is not the leaf
548
549	// leaf can be empty or full at this point
550	TEST_OBJECTS:
551
552	#ifdef _DEBUGKTB
553	DEBUG << "currNode = " << currNode << " entp.t = " << entp->t
554	<< " extp.t = " << extp->t << endl;
555	#endif
556
557	if (!IsEmptyLeaf_(currNode)) {
558	#ifdef _DEBUGKTB
559	cout << "Full leaf at depth= " << depth << endl;
560	#endif
561
562	#ifdef __TRAVERSAL_STATISTICS
563	fullLeavesTraversed++;
564	#endif // __TRAVERSAL_STATISTICS
565	// test the objects in the full leaf against the ray
566
567	SimpleRay::IntersectionRes[0].maxt = extp->t;
568	if (TestFullLeaf(ray, currNode)) {
569	#ifdef _DEBUGKTB
570	cout << "Full leaf HIT " << endl;
571	#endif
572
573	#ifdef __TRAVERSAL_STATISTICS
574	_allNodesTraversed += allNodesTraversed;
575	_fullLeavesTraversed += fullLeavesTraversed;
576	_emptyLeavesTraversed += emptyLeavesTraversed;
577	#endif // __TRAVERSAL_STATISTICS
578
579	// signed distance should be already set in TestFullLeaf
580	// the first object intersected was found
581	RestoreStackPointers();
582	return 1;
583	}
584	}
585	#ifdef __TRAVERSAL_STATISTICS
586	else {
587	#ifdef _DEBUGKTB
588	cout << "Empty leaf at depth= " << depth << endl;
589	#endif
590	emptyLeavesTraversed++;
591	}
592	#endif // __TRAVERSAL_STATISTICS
593
594
595	#ifdef _DEBUGKTB
596	cout << "Pop the node" << endl;
597	#endif
598
599	// pop farChild from the stack
600	// restore the current values
601	entp = extp;
602	currNode = entp->nodep;
603	#ifdef _DEBUGKTB
604	#ifdef _KTBEXTSTACK
605	depth = entp->dummy;
606	cout << "Popped node at depth = " << depth << endl;
607	#endif
608	#endif
609
610	// DEBUG << "Pop c= " << currNode << "\n" << flush ;
611	if (currNode == NULL) {
612	#ifdef _DEBUGKTB
613	cout << "NO HIT - EXIT " << endl;
614	#endif
615
616	#ifdef __TRAVERSAL_STATISTICS
617	_allNodesTraversed += allNodesTraversed;
618	_fullLeavesTraversed += fullLeavesTraversed;
619	_emptyLeavesTraversed += emptyLeavesTraversed;
620	#endif // __TRAVERSAL_STATISTICS
621
622	// no objects found along the ray path
623	RestoreStackPointers();
624	return 0;
625	}
626	extp = extp->prev;
627	} // for(;;)
628	} // FindNearestI
629	#endif // TRV000
630
631	#ifdef TRV001
632	int
633	CKTBTraversal::FindNearestI(const SimpleRay &ray)
634	{
635	// passing through parameters
636	float tmin, tmax;
637
638	// test if the whole CKTB tree is missed by the input ray
639	if ( (!root) \|\|
640	(!bbox.ComputeMinMaxT(ray.mOrigin, ray.mDirection, &tmin, &tmax)) \|\|
641	(tmin >= tmax) \|\|
642	(tmax <= 0.f)
643	) {
644	SimpleRay::IntersectionRes[0].intersectable = 0;
645	return 0; // no object can be intersected
646	}
647
648	//#define _DEBUGKTB
649	#ifdef _DEBUGKTB
650	int ib = 0;
651	int depth = 0;
652	#endif
653
654	#ifdef __TRAVERSAL_STATISTICS
655	int allNodesTraversed = 0L;
656	int fullLeavesTraversed = 0L;
657	int emptyLeavesTraversed = 0L;
658	#endif // __TRAVERSAL_STATISTICS
659
660	#ifdef _COMPUTE_INVERTED_DIR_KTB
661	Vector3 invertedDir;
662	invertedDir.x = 1.0f / ray.mDirection.x;
663	invertedDir.y = 1.0f / ray.mDirection.y;
664	invertedDir.z = 1.0f / ray.mDirection.z;
665	#endif // _COMPUTE_INVERTED_DIR_KTB
666
667	// start from the root node
668	SKTBNodeT *currNode = root;
669
670	struct SStackElem entp, extp;
671	GetStackPointers(entp, extp);
672	//struct SStackElem *entp = &(stack[0]);
673	//struct SStackElem *extp = &(stack[1]);
674
675	// exit point setting for the box and the ray
676	extp->x = ray.mOrigin.x + ray.mDirection.x * tmax;
677	extp->y = ray.mOrigin.y + ray.mDirection.y * tmax;
678	extp->z = ray.mOrigin.z + ray.mDirection.z * tmax;
679	extp->nodep = NULL;
680	extp->prev = NULL;
681	extp->t = tmax;
682
683	// entry point setting for the box and the ray
684	entp->nodep = NULL;
685	entp->prev = NULL;
686	if (tmin > 0.0) { // external node
687	entp->x = ray.mOrigin.x + ray.mDirection.x * tmin;
688	entp->y = ray.mOrigin.y + ray.mDirection.y * tmin;
689	entp->z = ray.mOrigin.z + ray.mDirection.z * tmin;
690	entp->t = tmin;
691	}
692	else { // internal node
693	entp->x = ray.mOrigin.x;
694	entp->y = ray.mOrigin.y;
695	entp->z = ray.mOrigin.z;
696	entp->t = 0.0;
697	}
698	SKTBNodeT *farChild;
699
700	// DEBUG << "A: c= " << currNode << "\n" << flush ;
701
702	// traverse through whole CKTB tree
703	for (;;) {
704	#ifndef _ALLOC_EMPTY_LEAVES
705	for (;;) {
706	// label for continuing the traversal
707	#else
708	// we have to check the node
709	// current node is not the leaf, empty leaves are NULL pointers
710	while (currNode) {
711	#endif
712
713	#ifdef _DEBUGKTB
714	cout << "i = " << ib << " node = " << (void*)currNode
715	<< " depth=" << depth << endl;
716	ib++;
717	#endif
718
719	#ifdef __TRAVERSAL_STATISTICS
720	allNodesTraversed++;
721	#endif // __TRAVERSAL_STATISTICS
722	// the position of the splitting plane
723	float splitVal = GetSplitValue(currNode);
724	// decision based on the axis given by splitting plane
725	switch (GetNodeType(currNode) & 0x07) {
726	// -------------------------------------------------
727	case CKTBAxes::EE_X_axis: {
728	#ifdef _DEBUGKTB
729	cout << "X-axis v=" << splitVal << endl;
730	depth++;
731	#endif
732	if (entp->x <= splitVal) {
733	if (extp->x <= splitVal) {
734	currNode = GetLeft(currNode);
735	// cases N1,N2,N3,P5,Z2,Z3
736	continue;
737	}
738	// case N4
739	farChild = GetRight(currNode);
740	currNode = GetLeft(currNode);
741	}
742	else {
743	if (splitVal <= extp->x) {
744	currNode = GetRight(currNode);
745	continue; // cases P1,P2,P3,N5,Z1
746	}
747	farChild = GetLeft(currNode); // case P4
748	currNode = GetRight(currNode);
749	}
750	#ifdef _DEBUGKTB
751	cout << "X-Push right node = " << farChild << endl;
752	#endif
753	// case N4 or P4
754	#ifdef _COMPUTE_INVERTED_DIR_KTB
755	float tdist = (splitVal - ray.mOrigin.x) * invertedDir.x;
756	#else // _COMPUTE_INVERTED_DIR_KTB
757	float tdist = (splitVal - ray.mOrigin.x) / ray.mDirection.x;
758	#endif // _COMPUTE_INVERTED_DIR_KTB
759
760	struct SStackElem *tmp = extp;
761	if (++extp == entp)
762	extp++;
763	#if defined(_KTBEXTSTACK) && defined(_DEBUGKTB)
764	extp->dummy = depth+1;
765	#endif
766	extp->prev = tmp;
767	extp->nodep = farChild;
768	extp->t = tdist;
769	extp->x = splitVal;
770	extp->y = ray.mOrigin.y + tdist * ray.mDirection.y;
771	extp->z = ray.mOrigin.z + tdist * ray.mDirection.z;
772	continue;
773	}
774	// -------------------------------------------------
775	case CKTBAxes::EE_Y_axis: {
776	#ifdef _DEBUGKTB
777	cout << "Y-axis v=" << splitVal << endl;
778	depth++;
779	#endif
780	if (entp->y <= splitVal) {
781	if (extp->y <= splitVal) {
782	currNode = GetLeft(currNode);
783	//case N1,N2,N3,P5,Z2,Z3
784	continue;
785	}
786	// case N4
787	farChild = GetRight(currNode);
788	currNode = GetLeft(currNode);
789	}
790	else {
791	if (splitVal <= extp->y) {
792	currNode = GetRight(currNode);
793	continue; // case P1,P2,P3,N5
794	}
795	farChild = GetLeft(currNode); // case P4
796	currNode = GetRight(currNode);
797	}
798	#ifdef _DEBUGKTB
799	cout << "Y-Push right node = " << farChild << endl;
800	#endif
801	// case N4 or P4
802	#ifdef _COMPUTE_INVERTED_DIR_KTB
803	float tdist = (splitVal - ray.mOrigin.y) * invertedDir.y;
804	#else // _COMPUTE_INVERTED_DIR_KTB
805	float tdist = (splitVal - ray.mOrigin.y) / ray.mDirection.y;
806	#endif // _COMPUTE_INVERTED_DIR_KTB
807
808	struct SStackElem *tmp = extp;
809	if (++extp == entp)
810	extp++;
811	#if defined(_KTBEXTSTACK) && defined(_DEBUGKTB)
812	extp->dummy = depth+1;
813	#endif
814	extp->prev = tmp;
815	extp->nodep = farChild;
816	extp->t = tdist;
817	extp->x = ray.mOrigin.x + tdist * ray.mDirection.x;
818	extp->y = splitVal;
819	extp->z = ray.mOrigin.z + tdist * ray.mDirection.z;
820	continue;
821	}
822	// -------------------------------------------------
823	case CKTBAxes::EE_Z_axis: {
824	#ifdef _DEBUGKTB
825	cout << "Z-axis v=" << splitVal << endl;
826	depth++;
827	#endif
828	if (entp->z <= splitVal) {
829	if (extp->z <= splitVal) {
830	currNode = GetLeft(currNode);
831	//case N1,N2,N3,P5,Z2,Z3
832	continue;
833	}
834	// case N4
835	farChild = GetRight(currNode);
836	currNode = GetLeft(currNode);
837	}
838	else {
839	if (splitVal <= extp->z) {
840	currNode = GetRight(currNode);
841	continue; // case P1,P2,P3,N5
842	}
843	farChild = GetLeft(currNode); // case P4
844	currNode = GetRight(currNode);
845	}
846	#ifdef _DEBUGKTB
847	cout << "Z-Push right node = " << farChild << endl;
848	#endif
849	// case N4 or P4
850	#ifdef _COMPUTE_INVERTED_DIR_KTB
851	float tdist = (splitVal - ray.mOrigin.z) * invertedDir.z;
852	#else // _COMPUTE_INVERTED_DIR_KTB
853	float tdist = (splitVal - ray.mOrigin.z) / ray.mDirection.z;
854	#endif // _COMPUTE_INVERTED_DIR_KTB
855
856	struct SStackElem *tmp = extp;
857	if (++extp == entp)
858	extp++;
859	#if defined(_KTBEXTSTACK) && defined(_DEBUGKTB)
860	extp->dummy = depth+1;
861	#endif
862
863	extp->prev = tmp;
864	extp->nodep = farChild;
865	extp->t = tdist;
866	extp->x = ray.mOrigin.x + tdist * ray.mDirection.x;
867	extp->y = ray.mOrigin.y + tdist * ray.mDirection.y;
868	extp->z = splitVal;
869	continue;
870	}
871	case CKTBAxes::EE_Leaf:
872	{ // test objects for intersection
873	#ifdef _DEBUGKTB
874	cout << "Leaf " << endl;
875	depth++;
876	#endif
877	goto TEST_OBJECTS;
878	}
879	case CKTBAxes::EE_Link:{
880	#ifdef _DEBUGKTB
881	cout << "Link " << endl;
882	#endif
883	currNode = GetLinkNode(currNode);
884	// cout << "Link node was accessed" << endl;
885	continue;
886	}
887	} // switch
888	} // while current node is not the leaf
889
890	// leaf can be empty or full at this point
891	TEST_OBJECTS:
892
893	#ifdef _DEBUGKTB
894	DEBUG << "currNode = " << currNode << " entp.t = " << entp->t
895	<< " extp.t = " << extp->t << endl;
896	#endif
897
898	if (!IsEmptyLeaf_(currNode)) {
899	#ifdef _DEBUGKTB
900	cout << "Full leaf at depth= " << depth << endl;
901	#endif
902
903	#ifdef __TRAVERSAL_STATISTICS
904	fullLeavesTraversed++;
905	#endif // __TRAVERSAL_STATISTICS
906	// test the objects in the full leaf against the ray
907
908	SimpleRay::IntersectionRes[0].maxt = extp->t;
909	if (TestFullLeaf(ray, currNode)) {
910	#ifdef _DEBUGKTB
911	cout << "Full leaf HIT " << endl;
912	#endif
913
914	#ifdef __TRAVERSAL_STATISTICS
915	_allNodesTraversed += allNodesTraversed;
916	_fullLeavesTraversed += fullLeavesTraversed;
917	_emptyLeavesTraversed += emptyLeavesTraversed;
918	#endif // __TRAVERSAL_STATISTICS
919
920	// signed distance should be already set in TestFullLeaf
921	// the first object intersected was found
922	RestoreStackPointers();
923	return 1;
924	}
925	}
926	#ifdef __TRAVERSAL_STATISTICS
927	else {
928	#ifdef _DEBUGKTB
929	cout << "Empty leaf at depth= " << depth << endl;
930	#endif
931	emptyLeavesTraversed++;
932	}
933	#endif // __TRAVERSAL_STATISTICS
934
935
936	#ifdef _DEBUGKTB
937	cout << "Pop the node" << endl;
938	#endif
939
940	// pop farChild from the stack
941	// restore the current values
942	entp = extp;
943	currNode = entp->nodep;
944	#ifdef _DEBUGKTB
945	#ifdef _KTBEXTSTACK
946	depth = entp->dummy;
947	cout << "Popped node at depth = " << depth << endl;
948	#endif
949	#endif
950
951	// DEBUG << "Pop c= " << currNode << "\n" << flush ;
952	if (currNode == NULL) {
953	#ifdef _DEBUGKTB
954	cout << "NO HIT - EXIT " << endl;
955	#endif
956
957	#ifdef __TRAVERSAL_STATISTICS
958	_allNodesTraversed += allNodesTraversed;
959	_fullLeavesTraversed += fullLeavesTraversed;
960	_emptyLeavesTraversed += emptyLeavesTraversed;
961	#endif // __TRAVERSAL_STATISTICS
962
963	// no objects found along the ray path
964	RestoreStackPointers();
965	return 0;
966	}
967	extp = extp->prev;
968	} // for(;;)
969	} // FindNearestI
970
971	#endif // TRV001
972
973	#if defined(TRV000)\|\|defined(TRV001)\|\|defined(TRV002)\|\|defined(TRV003)\|\|defined(TRV004)\|\|defined(TRV007)
974	int
975	CKTBTraversal::FindNearestI_16oneDir(SimpleRayContainer &rays)
976	{
977	assert("NYI");
978	}
979	#endif
980
981	#if defined(TRV000)\|\|defined(TRV001)\|\|defined(TRV002)\|\|defined(TRV003)\|\|defined(TRV004)\|\|defined(TRV006)\|\|defined(TRV007)\|\|defined(TRV00F)
982	int
983	CKTBTraversal::FindNearestI_16twoDir(SimpleRayContainer &rays)
984	{
985	assert("NYI");
986	return 0;
987	}
988	#endif
989
990	#ifdef __SSE__
991	#if defined(TRV000)\|\|defined(TRV001)\|\|defined(TRV002)\|\|defined(TRV003)\|\|defined(TRV004)\|\|defined(TRV005)
992	// The same operations for packets of rays, if implemented by
993	// a particular ASDS, otherwise it is emulated by decomposition
994	// of a packet to individual rays and traced individually.
995	void
996	CKTBTraversal::FindNearestI(RayPacket2x2 &raypack)
997	{
998	for (int i = 0; i < 4; i++) {
999	cout << " orig = " << raypack.GetLoc(i) << " dir = "
1000	<< raypack.GetDir(i) << endl;
1001	}
1002	// cout << "Not yet implemented" << endl;
1003	}
1004	#endif
1005	#endif // __SSE__
1006
1007	} // namespace
1008

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

Context Navigation

source: GTP/trunk/Lib/Vis/Preprocessing/src/havran/ktbtrav.cpp @ 2582

Download in other formats: