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

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).