在 3d 中表示框的排列
Representation of an arrangement of boxes in 3d
我想表示多个 3 维矩形框的排列（可能在一个更大的框...一个容器中）。一个盒子由它的长、宽、高和重量来表示。
我现在的问题是，我如何有效地表示这些框的 "placement"，以便我可以计算总排列的一些属性：
- 最大高度
- 质心
- 总体积
- 坚固性（建筑布置的整体表面有多坚固。即表面内有多少台阶和多大的台阶……与光滑表面相对应）
- ...
我不需要高效地渲染、变换、旋转、显示...数据结构，我发现的大多数解决方案都在努力改进。
两种可能的方法：
The first approach which i thought of was a list with all the boxes
and an additional given position (on the x-, y- and z-axis) within the
3d space. From this basic approach I could calculate all properties
needed, however it would be quite hard to find a suitable position for
a new box. I guess I would have to use another representation for
finding a suitable position and then transform this representation to
the discribed one.
Another idea was to think of the 3d space as voxels. Placing a box
within the space would mean assigning the voxels representing the
space the box which makes finding a new place for a box quite easy.
Once this structure is built up, calculation of the properties would
be fast and simple, however I might lack accuracy when defining too
big voxels. Increasing the amount of voxels would slow down the
calculation again and would need a lot more memory.
我已经找了好久了，还是找不到合适的表示方式。
您有任何其他想法，或者您能指出更好的解决方案，或者其中一种方法已经是一个很好的方法了吗？
在框内组织框，特别是如果您可以使用整数 space 并将尺寸表示为体素，则可以很好地适合八叉树。
https://en.wikipedia.org/wiki/Octree
尽管八叉树可用作 3D 交互的 space-dividing 方案——例如，要在大量点中快速找到最接近 3D 射线的点——您可以使用八叉树作为组织数据的起点。它不是解决问题的最佳选择，但它是一个很好的数据结构。
基本思路：
- 从要划分的 space 的整体 (x,y,z) 长方体边界开始。
- 将3D长方体分成八个子长方体（八个节点），每个子长方体占据父方框的宽、长、高的一半。 （八个节点，因此 "octree." 类似的二维结构是一个四叉树。）
- 对于每个节点，维护指向其父节点和八个子节点的指针。
- 迭代地将每个节点进一步细分为八个节点。
- 继续细分，直到算法达到 pre-defined 停止条件，例如最大深度、最小尺寸或最小体积。
又见这个问题：
Auto-balancing (or cheaply balanced) 3D datastructure
您很容易 运行 遇到细分次数过多的树的内存问题。例如，一旦超过 8^5 个节点，您可能不喜欢占用多少内存。传统使用八叉树的一个技巧是引入一个停止条件，这样如果一个特定节点为空，它就不会被细分。
八叉树可能无法解决您的问题，但如果不是针对这个特定问题，space-dividing 技术总有一天会派上用场。
此外，对于八叉树，最基本的实现没有考虑到一个对象可以跨越属于不同父节点的两个节点。为了用二维表示，假设两个正方形进一步细分为四个正方形：a、b、c、d 和 e、f、g、h:
a b e f
c d g h
虽然"d"和"g"是相邻的，但它们属于不同的父方块，"know"它们不是邻居。由于您将获得 "d" 和 "g" 的最小坐标和最大坐标，因此计算它们是否是邻居就足够简单了。
对于许多基本计算，您不需要将 3D 框表示为某种体素化 3D space，但对于 "ruggedness" 的度量，3D 数据网格是一个很好的选择方法。
如果内存不是问题，那么您可以考虑如下方案，假设您只需要处理几十个盒子，并且（可能很奇怪）这些盒子可以重叠：
- 定义一个 3D 数组（或等效数组），以整数 space 表示您需要的完整体积。这假设 1 个体素，当满的时候，可以代表一个盒子的确切边缘。 （稍后会详细介绍此假设。）
- 为每个体素分配一个 32 位或 64 位整数。
- 为每个框分配一个从 0 到 31 或 0 到 63 的索引。
- 对于每个框，遍历框中的所有像素 (x,y,z)。
- 在框内的每个体素处，将相应的位设置为 1。例如，对于基于 0 的框索引 2，将整数值设置为 ....0100。
- 对所有框重复该过程。
- 在遍历方框列表的循环中，运行 即时计算，这样您就不必再次遍历完整的 3D space：保留 运行宁计算质心；跟踪总音量的最小值和最大值；等等
遍历所有框及其尺寸后，您将得到一个 3D space，其中每个体素都定义了 presence/absence，并且每个框都分配了一个唯一 ID（可能会很方便）。
如果方框不能重叠，因为它们代表刚性长方体或真实的纸板箱，那么您可以简单地为每个体素分配一个方框索引作为十进制值。
如果为了内存而定义整数 space 但需要更高的精度，则可以使用单独的数据结构来跟踪框最外层体素的精度。因此，尽管对于某些处理，检查体素是否被占用（值 > 0）可能就足够了，但如果您需要精确地找到边缘，您可以：
- （可选）使用一位将体素标记为边缘体素，这意味着至少一个邻居的值为 0。
- 对于任何边缘体素，使用框的索引来引用框尺寸列表。例如，如果边缘体素的位值为 ...0010，则它被框索引 1 占用。框索引 1 可以定义为从 (201.3, 12.4, 13.8) 到 (304.6, 75.3, 102.8)。从 min/max 个点和边缘体素，您可以确定一个精确的位置。
分配所有框后，您遍历列表并使空体素更有意义。例如，可以为每个空体素分配一个值，指示到最近框的距离。例如，如果在最近的空体素 (x,y,z)ox 在任何方向上都是 10 体素，您可以使用负整数值 -10（作为小数）。如果最近的盒子相距 10 个体素，那么以该空体素为中心，您可以打包另一个 half-width = 9 的盒子。
根据内存限制和您的耐心，在每个空体素中，您可以在 +x、-x、+y、-y、+z 和 -z 方向（也许其他方向）。
无论您的盒子是否 axis-aligned，使用体素化 3D 方案都可以轻松计算 "ruggedness" 或粗糙度。一种简单的技术是将总体积的每一侧想象成一个深度图，或者一个二维投影，其中每个 "pixel" 是到盒子的距离。然后可以计算粗糙度如下：
- Select 要计算粗糙度的长方体面（或方向）。假设您 select XY 面，以便 Z 指向总体积。
- 在每个 XY 点，确定从框面到第一个框（如果有）的距离。将此值存储在大小适合 XY 面的二维数组中。
- 以这种方式遍历所有点。
- 估计粗糙度作为整个像素体积和 XY 面面积的度量。
您可以通过多种不同的方式计算粗糙度，具体取决于方框是否完全填满 space。例如，假设有一堆框从 XY 侧将 space 填充为 "seen"，所有框都在距 XY 面 10 - 20 体素的范围内。只要有来自表面 2D 轮廓的标准粗糙度测量值，您就可以为 3D 表面开发多种粗糙度测量值中的任何一种：
- 所有框距离的总范围（最大 - 最小）。这假定您忽略从 XY 侧看完全为空的体素列。
- 距离的标准偏差。
- 与平均距离的绝对偏差之和除以所占面积。
对于最后一个例子，想象两种情况：无论 space 被方块占据，所有方块与封闭体积的 XY 面的距离为 D。这可能是 0.0 的粗糙度，因为距离没有变化，如果目标是（比如说）在盒子上放置一个大的平面物体，这很有用。如果框之间的 space 定义 "roughness," 那么您可以执行上述简单计算或近似某些物理特性：如果将布放在框上会弯曲多少？
使用 3D 体积更容易思考问题，并且（在我看来）更容易调试。更复杂的方案也可以奏效。例如，每个框可以只是一个数据结构，带有指向其他最接近的框的指针，这些可以排列在一些相当复杂的结构中。体素 space 要求可能会通过替换单个 "supervoxels." 内连接的空体素的长方体区域而略微降低，但这些技术似乎都不是调试起来有趣的。
我想表示多个 3 维矩形框的排列（可能在一个更大的框...一个容器中）。一个盒子由它的长、宽、高和重量来表示。
我现在的问题是，我如何有效地表示这些框的 "placement"，以便我可以计算总排列的一些属性：
- 最大高度
- 质心
- 总体积
- 坚固性（建筑布置的整体表面有多坚固。即表面内有多少台阶和多大的台阶……与光滑表面相对应）
- ...
我不需要高效地渲染、变换、旋转、显示...数据结构，我发现的大多数解决方案都在努力改进。
两种可能的方法：
The first approach which i thought of was a list with all the boxes and an additional given position (on the x-, y- and z-axis) within the 3d space. From this basic approach I could calculate all properties needed, however it would be quite hard to find a suitable position for a new box. I guess I would have to use another representation for finding a suitable position and then transform this representation to the discribed one.
Another idea was to think of the 3d space as voxels. Placing a box within the space would mean assigning the voxels representing the space the box which makes finding a new place for a box quite easy. Once this structure is built up, calculation of the properties would be fast and simple, however I might lack accuracy when defining too big voxels. Increasing the amount of voxels would slow down the calculation again and would need a lot more memory.
我已经找了好久了，还是找不到合适的表示方式。
您有任何其他想法，或者您能指出更好的解决方案，或者其中一种方法已经是一个很好的方法了吗？
在框内组织框，特别是如果您可以使用整数 space 并将尺寸表示为体素，则可以很好地适合八叉树。
https://en.wikipedia.org/wiki/Octree
尽管八叉树可用作 3D 交互的 space-dividing 方案——例如，要在大量点中快速找到最接近 3D 射线的点——您可以使用八叉树作为组织数据的起点。它不是解决问题的最佳选择，但它是一个很好的数据结构。
基本思路：
- 从要划分的 space 的整体 (x,y,z) 长方体边界开始。
- 将3D长方体分成八个子长方体（八个节点），每个子长方体占据父方框的宽、长、高的一半。 （八个节点，因此 "octree." 类似的二维结构是一个四叉树。）
- 对于每个节点，维护指向其父节点和八个子节点的指针。
- 迭代地将每个节点进一步细分为八个节点。
- 继续细分，直到算法达到 pre-defined 停止条件，例如最大深度、最小尺寸或最小体积。
又见这个问题： Auto-balancing (or cheaply balanced) 3D datastructure
您很容易 运行 遇到细分次数过多的树的内存问题。例如，一旦超过 8^5 个节点，您可能不喜欢占用多少内存。传统使用八叉树的一个技巧是引入一个停止条件，这样如果一个特定节点为空，它就不会被细分。
八叉树可能无法解决您的问题，但如果不是针对这个特定问题，space-dividing 技术总有一天会派上用场。
此外，对于八叉树，最基本的实现没有考虑到一个对象可以跨越属于不同父节点的两个节点。为了用二维表示，假设两个正方形进一步细分为四个正方形：a、b、c、d 和 e、f、g、h:
a b e f
c d g h
虽然"d"和"g"是相邻的，但它们属于不同的父方块，"know"它们不是邻居。由于您将获得 "d" 和 "g" 的最小坐标和最大坐标，因此计算它们是否是邻居就足够简单了。
对于许多基本计算，您不需要将 3D 框表示为某种体素化 3D space，但对于 "ruggedness" 的度量，3D 数据网格是一个很好的选择方法。
如果内存不是问题，那么您可以考虑如下方案，假设您只需要处理几十个盒子，并且（可能很奇怪）这些盒子可以重叠：
- 定义一个 3D 数组（或等效数组），以整数 space 表示您需要的完整体积。这假设 1 个体素，当满的时候，可以代表一个盒子的确切边缘。 （稍后会详细介绍此假设。）
- 为每个体素分配一个 32 位或 64 位整数。
- 为每个框分配一个从 0 到 31 或 0 到 63 的索引。
- 对于每个框，遍历框中的所有像素 (x,y,z)。
- 在框内的每个体素处，将相应的位设置为 1。例如，对于基于 0 的框索引 2，将整数值设置为 ....0100。
- 对所有框重复该过程。
- 在遍历方框列表的循环中，运行 即时计算，这样您就不必再次遍历完整的 3D space：保留 运行宁计算质心；跟踪总音量的最小值和最大值；等等
遍历所有框及其尺寸后，您将得到一个 3D space，其中每个体素都定义了 presence/absence，并且每个框都分配了一个唯一 ID（可能会很方便）。
如果方框不能重叠，因为它们代表刚性长方体或真实的纸板箱，那么您可以简单地为每个体素分配一个方框索引作为十进制值。
如果为了内存而定义整数 space 但需要更高的精度，则可以使用单独的数据结构来跟踪框最外层体素的精度。因此，尽管对于某些处理，检查体素是否被占用（值 > 0）可能就足够了，但如果您需要精确地找到边缘，您可以：
- （可选）使用一位将体素标记为边缘体素，这意味着至少一个邻居的值为 0。
- 对于任何边缘体素，使用框的索引来引用框尺寸列表。例如，如果边缘体素的位值为 ...0010，则它被框索引 1 占用。框索引 1 可以定义为从 (201.3, 12.4, 13.8) 到 (304.6, 75.3, 102.8)。从 min/max 个点和边缘体素，您可以确定一个精确的位置。
分配所有框后，您遍历列表并使空体素更有意义。例如，可以为每个空体素分配一个值，指示到最近框的距离。例如，如果在最近的空体素 (x,y,z)ox 在任何方向上都是 10 体素，您可以使用负整数值 -10（作为小数）。如果最近的盒子相距 10 个体素，那么以该空体素为中心，您可以打包另一个 half-width = 9 的盒子。
根据内存限制和您的耐心，在每个空体素中，您可以在 +x、-x、+y、-y、+z 和 -z 方向（也许其他方向）。
无论您的盒子是否 axis-aligned，使用体素化 3D 方案都可以轻松计算 "ruggedness" 或粗糙度。一种简单的技术是将总体积的每一侧想象成一个深度图，或者一个二维投影，其中每个 "pixel" 是到盒子的距离。然后可以计算粗糙度如下：
- Select 要计算粗糙度的长方体面（或方向）。假设您 select XY 面，以便 Z 指向总体积。
- 在每个 XY 点，确定从框面到第一个框（如果有）的距离。将此值存储在大小适合 XY 面的二维数组中。
- 以这种方式遍历所有点。
- 估计粗糙度作为整个像素体积和 XY 面面积的度量。
您可以通过多种不同的方式计算粗糙度，具体取决于方框是否完全填满 space。例如，假设有一堆框从 XY 侧将 space 填充为 "seen"，所有框都在距 XY 面 10 - 20 体素的范围内。只要有来自表面 2D 轮廓的标准粗糙度测量值，您就可以为 3D 表面开发多种粗糙度测量值中的任何一种：
- 所有框距离的总范围（最大 - 最小）。这假定您忽略从 XY 侧看完全为空的体素列。
- 距离的标准偏差。
- 与平均距离的绝对偏差之和除以所占面积。
对于最后一个例子，想象两种情况：无论 space 被方块占据，所有方块与封闭体积的 XY 面的距离为 D。这可能是 0.0 的粗糙度，因为距离没有变化，如果目标是（比如说）在盒子上放置一个大的平面物体，这很有用。如果框之间的 space 定义 "roughness," 那么您可以执行上述简单计算或近似某些物理特性：如果将布放在框上会弯曲多少？
使用 3D 体积更容易思考问题，并且（在我看来）更容易调试。更复杂的方案也可以奏效。例如，每个框可以只是一个数据结构，带有指向其他最接近的框的指针，这些可以排列在一些相当复杂的结构中。体素 space 要求可能会通过替换单个 "supervoxels." 内连接的空体素的长方体区域而略微降低，但这些技术似乎都不是调试起来有趣的。