/// /// Creates a new quad tree node. /// This function is iterative, unless the node is a leaf. /// /// /// /// /// private void CreateQuadTreeNode(BoundingBox bounds, uint parentID, uint id, ref uint nextAvailableBlockIndex) { //If we have a zero size, we overflowed, return if (bounds.Max.X == bounds.Min.X) return; TerrainQuadTreeNodeType type; //This will be integer, since whole terrain size is POW/2, //along with the blocks float edgeWidth = bounds.Max.X - bounds.Min.X; float halfEdgeWidth = edgeWidth / 2.0f; float nodeHeight = bounds.Max.Y - bounds.Min.Y; float blockWidth = (float)this.SideLength / (float)this.NumBlocksInternal; if (edgeWidth == blockWidth) { type = TerrainQuadTreeNodeType.LEAF; this.QuadTreeNodeListInternal[id].BoundsInternal = bounds; this.QuadTreeNodeListInternal[id].ParentIDInternal = parentID; this.QuadTreeNodeListInternal[id].IDInternal = id; this.QuadTreeNodeListInternal[id].TypeInternal = type; //now we know this is a leaf, and needs to be associated with a block //Use the next avilable block slot and add a terrain block using //the bounds dimensions. The block index buffers themselves //have been created, we just need to fill them with vertices. this.QuadTreeNodeListInternal[id].blockIndexInternal = this.NumLeavesAddedInternal; this.NumLeavesAddedInternal++; this.BlocksInternal[nextAvailableBlockIndex].FillBlock(bounds, this.NumBlocksInternal); //advanced the block index for the next call of this method nextAvailableBlockIndex++; return; } else { type = TerrainQuadTreeNodeType.NODE; this.QuadTreeNodeListInternal[id].BoundsInternal = bounds; this.QuadTreeNodeListInternal[id].ParentIDInternal = parentID; this.QuadTreeNodeListInternal[id].IDInternal = id; this.QuadTreeNodeListInternal[id].TypeInternal = type; //child 0 bounds Vector3 boundMax = bounds.Min + new Vector3(halfEdgeWidth, nodeHeight, halfEdgeWidth); BoundingBox child0Bounds = new BoundingBox(bounds.Min, boundMax); this.CurrentTreeNodeIDInternal++; this.QuadTreeNodeListInternal[id].ChildInternal[0] = this.CurrentTreeNodeIDInternal; this.CreateQuadTreeNode(child0Bounds, id, this.CurrentTreeNodeIDInternal, ref nextAvailableBlockIndex); Vector3 boundMin = bounds.Min + new Vector3(halfEdgeWidth, 0, 0); boundMax = boundMin + new Vector3(halfEdgeWidth, nodeHeight, halfEdgeWidth); BoundingBox child1Bounds = new BoundingBox(boundMin, boundMax); this.CurrentTreeNodeIDInternal++; this.QuadTreeNodeListInternal[id].ChildInternal[1] = this.CurrentTreeNodeIDInternal; this.CreateQuadTreeNode(child1Bounds, id, this.CurrentTreeNodeIDInternal, ref nextAvailableBlockIndex); boundMin = bounds.Min + new Vector3(0, 0, halfEdgeWidth); boundMax = boundMin + new Vector3(halfEdgeWidth, nodeHeight, halfEdgeWidth); BoundingBox child2Bounds = new BoundingBox(boundMin, boundMax); this.CurrentTreeNodeIDInternal++; this.QuadTreeNodeListInternal[id].ChildInternal[2] = this.CurrentTreeNodeIDInternal; this.CreateQuadTreeNode(child2Bounds, id, this.CurrentTreeNodeIDInternal, ref nextAvailableBlockIndex); boundMin = bounds.Min + new Vector3(halfEdgeWidth, 0, halfEdgeWidth); boundMax = boundMin + new Vector3(halfEdgeWidth, nodeHeight, halfEdgeWidth); BoundingBox child3Bounds = new BoundingBox(boundMin, boundMax); this.CurrentTreeNodeIDInternal++; this.QuadTreeNodeListInternal[id].ChildInternal[3] = this.CurrentTreeNodeIDInternal; this.CreateQuadTreeNode(child3Bounds, id, this.CurrentTreeNodeIDInternal, ref nextAvailableBlockIndex); } return; }