On 8/22/2019 at 12:22 PM, JoeJ said:

 

Minor, but worth to mention: You use recursion for both traversal and build, this way the programming language manages the stack for you. I started with this too, but it may be not the best way to learn it, and it is not the most efficient way either. Managing the stack yourself lets you see what happens better. Difference between breath first / depth first becomes more clear, caching is better, dynamic allocation can be avoided.

 

First of all sorry for taking so long to respond. Your last post was very dense and it took me a while to absorb all the information. I've been pouring over it for the last few days try to make sense of it and I hope that I managed to do that because almost everything here is new to me. 

So starting with my most glaring problem, which was not sorting at every iteration, I've implemented that hopefully correctly this time.

The second thing I did was remove the root special case, and instead just generalized the function where it just takes any case.

Also rewrote some functions to be cleaner/clearer, removed the redundant float cast etc (minor things)

The major issue I had was rewriting the whole thing without using new operators and without letting the program manage the stack, this I'm still having issues with and I'm not even sure I'm doing it right. I've basically resorted to using the binary heap implementation I found online which stores the whole tree in an array (is that what you meant when you said use arrays for the trees?). So I've rewritten my generation code (hopefully correctly) using that implementation.The problem is that I'm now having some difficulties writing the traversal code, I was wondering if you can provide any sort of hint to get me going. 

This is my new generation code:

struct _heap_node
{

	//the bounding box of this volume
	_bounding_box bounding_box;

	//the list of bounding boxes of the triangles this volume encompasses
	std::vector<_bounding_box_tri> triangleBoundingBoxList;


	bool isEmpty = true;

};

std::vector<_heap_node> midpoint_split(std::vector<_bounding_box_tri>& completeBoundingBoxList, UINT unitsPerLeaf = 100)
{

	//support 7 levels of the tree
	//1st level after root is 2 nodes, 2nd level is 4 nodes, 3rd level is 8 nodes, 4th level is 16 nodes, 5th level is 32 nodes, 6th level is 64 nodes, 7th level is 128 nodes
	//2 + 4 + 8 + 16 + 32 + 64 + 128 = 256
	//256 + 2 (1st is empty and second is root) = 258
	UINT totalNumberOfNodes = 258;

	//initialize the binary heap
	_heap_node emptyNode;
	emptyNode.isEmpty = true;
	std::vector<_heap_node> tree(totalNumberOfNodes, emptyNode);


	//generate the root node
	_heap_node rootNode;


	//find the volume of all the triangles in the terrain
	rootNode.bounding_box = FindBoundingBox(completeBoundingBoxList);
	rootNode.triangleBoundingBoxList = completeBoundingBoxList;
	rootNode.isEmpty = false;

	//add the root to the tree at 1st index (since the 0th slot is always empty)
	tree[1] = rootNode;

	//start with index 1 because slot 0 is always empty
	for (UINT i = 1; i < totalNumberOfNodes; i++)
	{
		//if the number of triangles in the list is less than the set amount don't divide futher
		if (tree[i].triangleBoundingBoxList.size() <= unitsPerLeaf)
			break;

		//generate a left branch
		_heap_node leftChild;
		leftChild.isEmpty = false;

		//split the list of triangles in half (0 to 1/2 list)
		UINT parent_index = i;
		UINT start_box_index = 0;
		UINT end_box_index = UINT(tree[parent_index].triangleBoundingBoxList.size() / 2.0f + 0.5f);

		//create a sublist of triangle bounding boxes that are contained in this split
		std::vector<_bounding_box_tri>::const_iterator startIter = tree[parent_index].triangleBoundingBoxList.begin() + start_box_index;
		std::vector<_bounding_box_tri>::const_iterator endIter = tree[parent_index].triangleBoundingBoxList.begin() + end_box_index;
		std::vector<_bounding_box_tri> leftsideBoxList(startIter, endIter);

		//sort the new list of boxes
		char axis = FindLongestSide(leftChild.bounding_box);
		OrganizeListByAxis(axis, leftsideBoxList);


		//find the bounding box around that split half
		leftChild.bounding_box = FindBoundingBox(leftsideBoxList);


		//pass on the new bounding box list
		leftChild.triangleBoundingBoxList = leftsideBoxList;

		//assign child to the 2n node of the binary heap (which represents the left tree)
		tree[2 * i] = leftChild;


		//generate the right branch
		_heap_node rightChild;
		rightChild.isEmpty = false;
		

		//assign the other half to the right branch (1/2 list + 1 to end)
		parent_index = i;
		start_box_index = end_box_index + 1; //start where left box has ended, just ofset by one
		end_box_index = tree[parent_index].triangleBoundingBoxList.size(); //end at the end of the list

		//create a sublist of bounding boxes to sort
		std::vector<_bounding_box_tri>::const_iterator startIter = tree[parent_index].triangleBoundingBoxList.begin() + start_box_index;
		std::vector<_bounding_box_tri>::const_iterator endIter = tree[parent_index].triangleBoundingBoxList.begin() + end_box_index;
		std::vector<_bounding_box_tri> rightsideBoxList(startIter, endIter);

		//sort the list on the longest axis
		axis = FindLongestSide(rightChild.bounding_box);
		OrganizeListByAxis(axis, rightsideBoxList);

		//find the bounding box around that split half
		rightChild.bounding_box = FindBoundingBox(rightsideBoxList);


		//pass on the new bounding box list
		rightChild.triangleBoundingBoxList = rightsideBoxList;

		//assign child to the 2n + 1 node of the binary heap (which represents the right tree)
		tree[2 * i + 1] = rightChild;

	}


	return tree;
	
	
}

And this is as far as I've gotten with my traversal code. Since you said that the bounding boxes will intersect, I'm not even sure how to find the bounding volumes of the point anymore, do I just have to search every node? Anyways, here how I start it:

std::vector<_bounding_box_tri> FindPointInTree(XMVECTOR point, std::vector<_heap_node> tree)
{

	//begin iteration at 2nd element since 1st element (slot 0) is always empty
	for (UINT i = 1; i < tree.size(); i++)
	{
		//check if the point is in the node at all 
		if (IsPointInBox(point, tree[i].bounding_box) == false)
			break;


		//check if the point belong in the left side of the tree
		if (IsPointInBox(point, tree[2*i].bounding_box))
			//what do I do here? Start a new loop and go into the 2*i tree?

		//check if the point belong in the right side of the tree
		if (IsPointInBox(point, tree[2 * i + 1].bounding_box))
			//what do I do here? Start a new loop and go into the 2*i + 1 tree?


	}
                                     
    
}

And thank you for all your help so far, this is has been really helpful for this issue and in general as these concepts (representing trees as arrays and using arrays instead of recursion) are new areas for me which I have not previously explored. So either way I've learned a bunch already, and ironing out the remainders to get the BVH to work would just be icing on the cake at this point.

1 hour ago, VanillaSnake21 said:

First of all sorry for taking so long to respond. Your last post was very dense and it took me a while to absorb all the information. I've been pouring over it for the last few days try to make sense of it and I hope that I managed to do that because almost everything here is new to me. 

No problem, and i may push a lot or too qickly. It would be enough to just keep those things in mind for the next time when you implement this again. For me this took decades, improved over time just when there was a need for it.

Your building looks much better now, but:

1 hour ago, VanillaSnake21 said:

//support 7 levels of the tree //1st level after root is 2 nodes, 2nd level is 4 nodes, 3rd level is 8 nodes, 4th level is 16 nodes, 5th level is 32 nodes, 6th level is 64 nodes, 7th level is 128 nodes //2 + 4 + 8 + 16 + 32 + 64 + 128 = 256 //256 + 2 (1st is empty and second is root) = 258

I see i pushed you too much. You try to keep things together, and you end up assuming a complete tree where every node that could exist does exist, even if empty. This would meake sense for soemting like a multi level grid, but in a tree you can not predict indexing - the indexing is actually what you calculate when building a tree.

I think this can be done with some changes:

struct _heap_node
{
	int childIndices[2];

	//the bounding box of this volume
	_bounding_box bounding_box;

	//the list of bounding boxes of the triangles this volume encompasses
	std::vector<_bounding_box_tri> triangleBoundingBoxList; /// why does the type differ from _bounding_box? Node and triangle could use the same?


	_heap_node()
	{
		childIndices[0] = -1;
		childIndices[1] = -1;
	}
};

std::vector<_heap_node> midpoint_split(const std::vector<_bounding_box_tri>& completeBoundingBoxList, const UINT unitsPerLeaf = 100)
{

	std::vector<_heap_node> tree;


	//generate the root node
	_heap_node rootNode;


	//find the volume of all the triangles in the terrain
	rootNode.bounding_box = FindBoundingBox(completeBoundingBoxList);
	rootNode.triangleBoundingBoxList = completeBoundingBoxList;


	//add the root to the tree
	tree.push_back(rootNode);

	std::vector<int> stack;
	if (rootNode.triangleBoundingBoxList.size() > unitsPerLeaf) 
		stack.push_back(0); // process the root node
	
	for (UINT i = 0; i < stack.size(); i++)
	{
		UINT parent_index = stack[i];

		//sort the new list of boxes
		/// you need to do this before splitting the list, which can be done only after determinating the axis. I guess your logic would have worked if you had done this once before.
		std::vector<_bounding_box_tri> sortedParentCopy = tree[parent_index].triangleBoundingBoxList;
		char axis = FindLongestSide(leftChild.bounding_box);
		OrganizeListByAxis(axis, sortedParentCopy); /// i assume the list is sorted along axis after that. Now we can find the split.


		//generate a left branch
		_heap_node leftChild;
		
		//split the list of triangles in half (0 to 1/2 list)
		UINT start_box_index = 0;
		UINT end_box_index = UINT(sortedParentCopy.size() / 2);

		//create a sublist of triangle bounding boxes that are contained in this split
		std::vector<_bounding_box_tri>::const_iterator startIter = sortedParentCopy.begin() + start_box_index;
		std::vector<_bounding_box_tri>::const_iterator endIter = sortedParentCopy.begin() + end_box_index;
		std::vector<_bounding_box_tri> leftsideBoxList(startIter, endIter);

		if (leftsideBoxList.size()) /// avoid empty nodes
		{
			/// if left child has too many many triangles, push it to the stack for future subdivision
			if (leftChild.triangleBoundingBoxList.size() > unitsPerLeaf) 
				stack.push_back(tree.size());

			//find the bounding box around that split half
			leftChild.bounding_box = FindBoundingBox(leftsideBoxList);

			//pass on the new bounding box list
			leftChild.triangleBoundingBoxList = leftsideBoxList;

			/// link parent to left child and add it to the tree
			tree[parent_index].childIndices[0] = tree.size();
			tree.push_back(leftChild);
		}


		//generate the right branch
		_heap_node rightChild;

		//assign the other half to the right branch (1/2 list + 1 to end)
		start_box_index = end_box_index + 1; //start where left box has ended, just ofset by one
		end_box_index = sortedParentCopy.size(); //end at the end of the list

		//create a sublist of bounding boxes to sort
		std::vector<_bounding_box_tri>::const_iterator startIter = sortedParentCopy.begin() + start_box_index;
		std::vector<_bounding_box_tri>::const_iterator endIter = sortedParentCopy.begin() + end_box_index;
		std::vector<_bounding_box_tri> rightsideBoxList(startIter, endIter);

		if (rightsideBoxList.size()) 
		{
			/// if right child has too many many triangles, push it to the stack for future subdivision
			if (rightChild.triangleBoundingBoxList.size() > unitsPerLeaf) 
				stack.push_back(tree.size());

			//find the bounding box around that split half
			rightChild.bounding_box = FindBoundingBox(rightsideBoxList);

			//pass on the new bounding box list
			rightChild.triangleBoundingBoxList = rightsideBoxList;

			/// link parent to right child and add it to the tree
			tree[parent_index].childIndices[1] = tree.size();
			tree.push_back(rightChild);
		}

	}


	return tree;
	
	
}

I have added a child ponters to the node, changed sorting logic and made sure no empty nodes are added to the tree (requiring a stack to maintain necessary work), see comments.

Can't say if it still has bugs, but otherwise i would only criticize the std::vector in the node. This still leads to fragmented memory in the end, when each vector contains only a small list of content. It would be possible to have just one list of content (source list), and a second list of the same size (destination list). When splitting (and sorting) you move the content from one list to the other with the new order, and after one level of tree has been processed the source becomes destination for the next step. So using both lists in a ping-pong manner while building one level of the tree after the other. Constant memory, no allocation and no fragmentation. My usage of the stack here already ensures the tree is built per level, but to determinate start / end indices you would need to add an additional step after one level is done, adding complexity. (This is what you want to  if you have to update the tree in real time.)

Alternative: After the tree has been build as above or in any other way, traverse it once and write the nodes to linear memory as they appear and all is perfect. This also works if you had generated the tree in some bad order you want to change. (e.g. change breadth to depth first order if you would decide to use stackless traversal at a later point.) However, this alternative requires to update the pointers in the tree, which is a bit error prone to get right, just to mention. (This is what you often do when you built the tree offline.)

But we can skip over this for now and make it work first.

1 hour ago, VanillaSnake21 said:

do I just have to search every node?

No. You check all children of the current node and traverse only those that contain the point. So a child that does not contain the point may have 1000 nodes in its subtree (or 'branch'), you you do not touch any of them.

My example from the last post does exacly that. Only if the point is in the bound, it writes the child index to the stack. So in future interations, only nodes that contain the point are popped from the stack. If your tree has 10 levels, and there would be no overlaps, you would process at most 10 nodes and never more. (But there might be (10-1)*2 point in box tests)

I try to rewrite your function, but using recursion this time. At the end you should be able to implement it either way, but initally one is enough and does not matter which:

void FindPointInTree(std::vector<_bounding_box_tri> &intersectingNodes, const XMVECTOR &point, const &std::vector<_heap_node> &tree, const int parent)
{
  		for (int n=0; n<2; n++) // process both children
        {
  			int child = tree[parent].childIndices[n]; // this time assuming each node has 2 child indices, so can have any order in memory
          	if (child == -1) continue;
          
            if (IsPointInBox(point, tree[child].bounding_box))
            {
                intersectingNodes.push_back(child); // likely we want only leaf nodes, but store them all far now
                FindPointInTree(intersectingNodes, point, tree, child); // make child the parent for the next step
            }  
        }
}

Now you need to test it, which works best by visualizing a query point and intersectiong bounding boxes...

... oops, forgot to clear the vector of triangles in the parent box, but do not dare to edit the code because this sometimes causes mess.

So we could change this to become a reference, not a copy:

	std::vector<_bounding_box_tri> &sortedParentCopy = tree[parent_index].triangleBoundingBoxList;
	

It does not matter to mess it up with sorting, because we don't need it anyways after the children have been made.

Then delete it after that:

	if (rightsideBoxList.size()) {.....}
	sortedParentCopy.clear();
	

Otherwise we would duplicate triangles like crazy

3 hours ago, JoeJ said:

... oops, forgot to clear the vector of triangles in the parent box, but do not dare to edit the code because this sometimes causes mess.

 So we could change this to become a reference, not a copy:

 

	std::vector<_bounding_box_tri> &sortedParentCopy = tree[parent_index].triangleBoundingBoxList;
	

 

It does not matter to mess it up with sorting, because we don't need it anyways after the children have been made.

Then delete it after that:

 

	if (rightsideBoxList.size()) {.....}
	sortedParentCopy.clear();
	

 

Otherwise we would duplicate triangles like crazy

 

 

 

Oh my God, thank you that is a brilliant implementation. It just seems so elegant and beautiful the way you reuse the indices from tree to stack and yet I just can't seem to write my own routine without looking that would convert your recursive traversal implantation (above) to the iterative approach. I ended up just peeking at the solution you provided at the previous page where you provided the implementation. 

I'm going to keep looking at this until I can successfully write my own routine, but do you happen to know if there are any resources that can help me get this down? For example I see you use the word "tail" in the solution on the previous page, I looked it up and came to a "tail call", so there must be a whole area of study that deals with things like that. Should I just look up like general "recursion" chapter in a comp sci book or something? In particularly I'd like to focus on this manual stack management, and maybe do a few exercises of converting recursion to manual loops, like we did here.

And if you don't mind, just give me a day or two, I'm going to try to study this and re-write the whole thing from scratch once I feel comfortable enough because I just want to have this really under my belt. I know I can probably just use what you provided, at this point you pretty much wrote the whole thing for me (thanks ), but I _really_ feel like this is a great opportunity for me to actually improve my coding and learn an area that I'm obviously completely oblivious to. And I'd really like to finally finish this BVH implementation too (heh, I feel like at this point it's like a secondary objective ?). Thanks again, I really appreciate how much you've helped so far!!

4 hours ago, VanillaSnake21 said:

but do you happen to know if there are any resources that can help me get this down? For example I see you use the word "tail" in the solution on the previous page

No, i don't know resources because i learned this myself. (It's not brilliant, but just how it works. But thinking it is brilliant or beautyful means you're on you'r way to get it.) Maybe the word 'tail' means something different usually, i just use 'head' for the current position in the stack, and 'tail' for it's position at the end where new stuff can be added. Can't rmember why using those terms.

I remember Michael Abrashs Graphics Programming Blackbook talking about traversal without recursion in BSP trees,

and the resulting traversal is the same as BFS search in graphs: https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/ (but there is no need for a visited flag if your graph is just a tree like here.)

4 hours ago, VanillaSnake21 said:

In particularly I'd like to focus on this manual stack management, and maybe do a few exercises of converting recursion to manual loops, like we did here.

Some tutorials about this would be useful. Tree tutorials never cover this it seems. One way to do it yourself is to understand how a recursively written function works under hood, mainly in what exact order it processes the data. Doing this in detail is often more involved than it seems.

As an example look at our recursive function and how it differs from the iterative solution:

void Recursive (parent, ...)

{

printf (textfile, "node: %i level %i", parentIndex, parent.treeLevel);

If (parent.leftChild.Intersects(query)) Recursive (leftChild...)

// imagine a lot of processing happens from this function call, how many variables need to be stored on the stack managed by C++, and only after that we can come back to this and continue:

If (parent.rightChild.Intersects(query)) Recursive (rightChild...)

}

If you run this and later look at the log file, you see the traversal runs from root towards a leaf decreasing the level each step. Advantage can be: If we process the closer children first, there is a chance we rarely need to touch the other children.

In contrast the iterative version processes the root, then all its children at level 1, then all nodes from level 2, then level 3 etc. Advantage can be: As we store all children compacted in memory, we utlize the cache better when accessing them.

So even both methods just work, it is good to know exactly how, if we ever need to optimize. What is better depends on what you do with the tree most of the time, and if you do it serially or in parallel.

I remember this takes some time to get it all. You don't need to learn this all the first time you use a tree! But it surely helps in the future to have heard about this (which i had not).