src/kdtree.cc
branchpyrit
changeset 7 bf17f9f84c91
parent 0 3547b885df7e
child 9 3239f749e394
equal deleted inserted replaced
6:d8d596d26f25 7:bf17f9f84c91
     1 #include "kdtree.cc"
     1 #include <algorithm>
     2 
     2 
     3 void KdTree::KdTree(ShapeList &shapelist):
     3 #include "kdtree.h"
       
     4 
       
     5 void Container::addShape(Shape* aShape)
       
     6 {
       
     7 	shapes.push_back(aShape);
       
     8 	if (shapes.size() == 0) {
       
     9 		/* initialize bounding box */
       
    10 		bbox = aShape->get_bbox();
       
    11 	} else {
       
    12 		/* adjust bounding box */
       
    13 		BBox shapebb = aShape->get_bbox();
       
    14 		if (shapebb.L.x < bbox.L.x)  bbox.L.x = shapebb.L.x;
       
    15 		if (shapebb.L.y < bbox.L.y)  bbox.L.y = shapebb.L.y;
       
    16 		if (shapebb.L.z < bbox.L.z)  bbox.L.z = shapebb.L.z;
       
    17 		if (shapebb.R.x > bbox.R.x)  bbox.R.x = shapebb.R.x;
       
    18 		if (shapebb.R.y > bbox.R.y)  bbox.R.y = shapebb.R.y;
       
    19 		if (shapebb.R.z > bbox.R.z)  bbox.R.z = shapebb.R.z;
       
    20 	}
       
    21 };
       
    22 
       
    23 void KdNode::subdivide(BBox bbox, int depth, int count)
       
    24 {
       
    25 	int axis;
       
    26 	float pos;
       
    27 
       
    28 	//if (stopcriterionmet()) return
       
    29 
       
    30 	// choose split axis
       
    31 	axis = 0;
       
    32 	if (bbox.R.y - bbox.L.y > bbox.R.x - bbox.L.x)
       
    33 		axis = 1;
       
    34 	if (bbox.R.z - bbox.L.z > bbox.R.y - bbox.L.y)
       
    35 		axis = 2;
       
    36 
       
    37 	// *** find optimal split position
       
    38 	SortableShapeList sslist(shapes, axis);
       
    39 	sort(sslist.begin(), sslist.end());
       
    40 
       
    41 	SplitList splitlist = SplitList();
       
    42 
       
    43 	SortableShapeList::iterator sh;
       
    44 	for (sh = sslist.begin(); sh != sslist.end(); sh++)
       
    45 	{
       
    46 		splitlist.push_back(SplitPos(sh->bbox.L.cell[axis]));
       
    47 		splitlist.push_back(SplitPos(sh->bbox.R.cell[axis]));
       
    48 	}
       
    49 	sort(splitlist.begin(), splitlist.end());
       
    50 
       
    51 	// find all posible splits
       
    52 	SplitList::iterator split;
       
    53 	int rest;
       
    54 	for (split = splitlist.begin(); split != splitlist.end(); split++)
       
    55 	{
       
    56 		for (sh = sslist.begin(), rest = sslist.size(); sh != sslist.end(); sh++, rest--)
       
    57 		{
       
    58 			if (sh->hasMark())
       
    59 				continue;
       
    60 			// if shape is on left side of split plane
       
    61 			if (sh->bbox.R.cell[axis] <= split->pos)
       
    62 			{
       
    63 				sh->setMark();
       
    64 				split->lnum++;
       
    65 			}
       
    66 			// if shape is completely contained in split plane
       
    67 			if (sh->bbox.L.cell[axis] == sh->bbox.R.cell[axis] == split->pos)
       
    68 			{
       
    69 				if (split->pos - bbox.L.cell[axis] < bbox.R.cell[axis] - split->pos)
       
    70 				{
       
    71 					// left subcell is smaller -> if not empty, put shape here
       
    72 					if (split->lnum)
       
    73 						split->lnum++;
       
    74 					else
       
    75 						split->rnum++;
       
    76 				} else {
       
    77 					// right subcell is smaller
       
    78 					if (split->rnum)
       
    79 						split->rnum++;
       
    80 					else
       
    81 						split->lnum++;
       
    82 				}
       
    83 			}
       
    84 			// if shape is on right side of split plane
       
    85 			if (sh->bbox.L.cell[axis] >= split->pos)
       
    86 			{
       
    87 				split->rnum += rest;
       
    88 				break;
       
    89 			}
       
    90 			// if shape occupies both sides of split plane
       
    91 			if (sh->bbox.L.cell[axis] < split->pos && sh->bbox.R.cell[axis] > split->pos)
       
    92 			{
       
    93 				split->lnum++;
       
    94 				split->rnum++;
       
    95 			}
       
    96 		}
       
    97 	}
       
    98 
       
    99 	// choose best split pos
       
   100 	// ... //
       
   101 
       
   102 	KdNode *children = new KdNode[2];
       
   103 
       
   104 	ShapeList::iterator shape;
       
   105 	for (shape = shapes.begin(); shape != shapes.end(); shape++)
       
   106 	{
       
   107 		if (((Triangle*)*shape)->A.cell[axis-1] < pos
       
   108 		|| ((Triangle*)*shape)->B.cell[axis-1] < pos
       
   109 		|| ((Triangle*)*shape)->C.cell[axis-1] < pos)
       
   110 			children[0].addShape(*shape);
       
   111 		if (((Triangle*)*shape)->A.cell[axis-1] >= pos
       
   112 		|| ((Triangle*)*shape)->B.cell[axis-1] >= pos
       
   113 		|| ((Triangle*)*shape)->C.cell[axis-1] >= pos)
       
   114 			children[1].addShape(*shape);
       
   115 	}
       
   116 
       
   117 	bbox.R[axis-1] = pos;
       
   118 	children[0].subdivide(bbox, depth+1, children[0].shapes.size());
       
   119 
       
   120 	bbox.L[axis-1] = pos;
       
   121 	children[1].subdivide(bbox, depth+1, children[1].shapes.size());
       
   122 }
       
   123 
       
   124 void KdTree::build()
     4 {
   125 {
     5 	root = new KdNode();
   126 	root = new KdNode();
     6 	shapes = new vector<Shape*>();
   127 	root->shapes = shapes;
     7 	ShapeList::iterator shape;
   128 	root->subdivide(bbox, 0, shapes.size());
     8 	for (shape = shapelist.begin(); shape != shapes.end(); shape++)
       
     9 		addShape(*shape);
       
    10 
       
    11 	rebuild();
       
    12 }
   129 }
    13 
       
    14 void KdTree::Subdivide(KdNode* node, AABB& bbox, int depth, int count)
       
    15 {
       
    16 	
       
    17 	/*if (stopcriterionmet()) return
       
    18 	splitpos = findoptimalsplitposition()
       
    19 	leftnode = new Node()
       
    20 	rightnode = new Node()
       
    21 	for (all primitives in node)
       
    22 	{
       
    23 		if (node->intersectleftnode()) leftnode->addprimitive( primitive )
       
    24 		if (node->intersectrightnode()) rightnode->addprimitive( primitive )
       
    25 	}
       
    26 	buildkdtree( leftnode )
       
    27 		buildkdtree( rightnode )*/
       
    28 }
       
    29 
       
    30 void KdTree::rebuild()
       
    31 {
       
    32 	int count = shapes->size();
       
    33 	AABB bbox = shapes->extends();
       
    34 
       
    35 	Subdivide(root, bbox, 0, count);
       
    36 }