1 /*

     1 /*

     2  * kdtree.cc: KdTree class

     2  * kdtree.cc: KdTree class

     3  *

     3  *

     4  * This file is part of Pyrit Ray Tracer.

     4  * This file is part of Pyrit Ray Tracer.

     5  *

     5  *

     7  *

     7  *

     8  * Permission is hereby granted, free of charge, to any person obtaining a copy

     8  * Permission is hereby granted, free of charge, to any person obtaining a copy

     9  * of this software and associated documentation files (the "Software"), to deal

     9  * of this software and associated documentation files (the "Software"), to deal

    10  * in the Software without restriction, including without limitation the rights

    10  * in the Software without restriction, including without limitation the rights

    11  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

    11  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

    52 // stack element for kd-tree traversal

    52 // stack element for kd-tree traversal

    53 struct StackElem

    53 struct StackElem

    54 {

    54 {

    55 	KdNode* node; /* pointer to far child */

    55 	KdNode* node; /* pointer to far child */

    56 	Float t; /* the entry/exit signed distance */

    56 	Float t; /* the entry/exit signed distance */

    58 	int prev;

    58 	int prev;

    59 };

    59 };

    60 

    60 

    61 // ----------------------------------------

    61 // ----------------------------------------

    62 

    62 

   148 

   148 

   149 #if 0

   149 #if 0

   150 // export kd-tree as .obj for visualization

   150 // export kd-tree as .obj for visualization

   151 // this would be hard to reconstruct later

   151 // this would be hard to reconstruct later

   152 	static ofstream F("kdtree.obj");

   152 	static ofstream F("kdtree.obj");

   154 	static int f=0;

   154 	static int f=0;

   155 	v.cell[axis] = node->getSplit();

   155 	v.cell[axis] = node->getSplit();

   156 	v.cell[(axis+1)%3] = bounds.L.cell[(axis+1)%3];

   156 	v.cell[(axis+1)%3] = bounds.L.cell[(axis+1)%3];

   157 	v.cell[(axis+2)%3] = bounds.L.cell[(axis+2)%3];

   157 	v.cell[(axis+2)%3] = bounds.L.cell[(axis+2)%3];

   158 	F << "v " << v.x << " " << v.y << " " << v.z << endl;

   158 	F << "v " << v.x << " " << v.y << " " << v.z << endl;

   237 

   237 

   238 	/* loop, traverse through the whole kd-tree, until an object is intersected or ray leaves the scene */

   238 	/* loop, traverse through the whole kd-tree, until an object is intersected or ray leaves the scene */

   239 	Float splitVal;

   239 	Float splitVal;

   240 	int axis;

   240 	int axis;

   241 	static const int mod3[] = {0,1,2,0,1};

   241 	static const int mod3[] = {0,1,2,0,1};

   243 	while (node)

   243 	while (node)

   244 	{

   244 	{

   245 		/* loop until a leaf is found */

   245 		/* loop until a leaf is found */

   246 		while (!node->isLeaf())

   246 		while (!node->isLeaf())

   247 		{

   247 		{

   326 

   326 

   327 	/* ray leaves the scene */

   327 	/* ray leaves the scene */

   328 	return NULL;

   328 	return NULL;

   329 }

   329 }

   330 

   330 

   331 // stack element for kd-tree traversal (packet version)

   332 // stack element for kd-tree traversal (packet version)

   332 struct StackElem4

   333 struct StackElem4

   333 {

   334 {

   334 	KdNode* node; /* pointer to far child */

   335 	KdNode* node; /* pointer to far child */

   335 	__m128 t; /* the entry/exit signed distance */

   336 	__m128 t; /* the entry/exit signed distance */

   512 		exit = stack[entry].prev;

   513 		exit = stack[entry].prev;

   513 	}

   514 	}

   514 

   515 

   515 	/* ray leaves the scene */

   516 	/* ray leaves the scene */

   516 }

   517 }

   517 

   519 

   518 ostream & operator<<(ostream &st, KdNode &node)

   520 ostream & operator<<(ostream &st, KdNode &node)

   519 {

   521 {

   520 	if (node.isLeaf())

   522 	if (node.isLeaf())

   521 	{

   523 	{