Talk:Octree

What is an MX octtree?

This article mentions an "MX octtree". Unfortunately, no where are such trees explained.

This article also mentions that PR octtrees can represent "infinite" space. To me, this is somewhat vague. Perhaps the word "unbounded" would be more appropriate? In any case, I do not quite see how it is possible for an octtree to keep track of things which may be arbitrarily far away from some center. This relates to my first question, because this seems to be where the difference lies between PR and MX varieties of octtrees.

MX Octree and PR Octree are by analogy to those terms for quadtrees; googling will turn up more information. I don't know where the terminology originates, but it's popularized in Samet's spatial data structure books. And yes, by "infinite" I meant "unbounded". Consider your classic binary tree: the tree represents arbitrary points (by inserting them) from some essentially unbounded space. If a new element is inserted outside the range of the existing elements, there's no problem, the tree can "grow" appropriately. Normally we don't think very explicitly about a binary tree partitioning space, but it is doing so implicitly. A PR quadtree/octree works the same way; you insert specific data items and they go somewhere in the tree and divide the space correspondingly. In an MX quadtree/octree, you define a finite space to be partitioned, and each partitioning step halves it. 71.141.227.19 01:14, 17 September 2007 (UTC)[reply]

I've also never seen the MX and PR nomenclature. It looks like it is specific to that particular author. In any case, what it describes is a detail that should not be present in this article, or at least be moved way down the page. BTW, PR trees as you describe them sound awfully similar to K-D trees. And K-D trees aren't octrees even if they're three dimensional. Nomis80 (talk) 05:42, 24 February 2008 (UTC)[reply]

Picture

Does the picture look messed up to anyone else? Mainly the right hand side.

There is a new image now. Arthena^(talk) 16:44, 28 October 2007 (UTC)[reply]

linear octrees

this article could mention linear octrees (storing an octree as a list of gargantini-coded nodes, instead of a pointer-based tree), and the relatively easy set-operations(union, intersection, difference) which the linear representation makes possible. —Preceding unsigned comment added by 89.27.71.155 (talk) 08:43, 10 April 2010 (UTC)[reply]

Why should an octree be a BSP-Tree variant?

According to the tree overview at bottom of this article the octree is a BSP-Tree. But where should be the binary part in this structure? Each cell is not subdivided or subdivided in exactly 8 children. There is nothing binary to my mind.

Does anyone share my point of view? -- 139.30.216.151 (talk) 07:28, 6 June 2011 (UTC)[reply]

I guess quadtrees and octrees are considered BSP-trees because each dimension is divided by two (binary) as you go deeper into the tree. In quadtrees a given cell can have 2^2 sub-cells; in octrees it's 2^3. Leblanc kevin (talk) 14:56, 3 September 2012 (UTC)[reply]

As Leblanc kevin said, quadtrees and octrees are very similar to BPS trees, since you very easily can construct corresponding tree structures using BSP trees. The main difference that separates BSP trees from quadtrees and octrees is that in BSP trees, two and three levels respectively are required to represent the same parent–child connections that exist over one level in quadtrees and octrees. Therefore, quadtrees and octrees cannot really be considered to be special cases of the BSP tree (although some people might think so anyway), although very close, and they can definitely be considered to be variants of it.

Besides, in BSP trees, you also usually explicitly store the hyperplanes that separate the different subspaces. For quadtrees and octrees however, it is already given what those hyperplanes are, so there is no need to store them explicitly. —Kri (talk) 19:20, 4 September 2012 (UTC)[reply]

History and Don Meagher Patent

Disclaimer : I worked in the same company as Don Meagher (Phoenix Data Systems) when he was building (and patented) the Octree. I'll start with a 1-line statement linking to the patent, and then I'll dig up some WP:RS links to expand on it. I referenced his first report. I also put 3d graphics in "common uses" Alanf777 (talk) 20:19, 20 September 2012 (UTC)[reply]

Where did the pictures go?

The article describes pictures, but there don't seem to be any on the page. Where did they go? Yitz (talk) 04:53, 14 June 2023 (UTC)[reply]