# Octree Based Voxel Model for Representation of Spatial Conflicts Across Multiple Design Domains

Arun Kumar Singh, B. Gurumoorthy, Latha Christie

► To cite this version:

Arun Kumar Singh, B. Gurumoorthy, Latha Christie. Octree Based Voxel Model for Representation of Spatial Conflicts Across Multiple Design Domains. 16th IFIP International Conference on Product Lifecycle Management (PLM), Jul 2019, Moscow, Russia. pp.14-23, 10.1007/978-3-030-42250-9_2 . hal-04444736

HAL Id: hal-04444736

https://inria.hal.science/hal-04444736v1

Submitted on 7 Feb 2024

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# Octree based Voxel Model for representation of spatial conflicts across multiple design domains

Arun Kumar Singh¹, ², B. Gurumoorthy², Latha Christie¹

¹ Microwave Tube Research and Development Centre (DRDO), Bangalore - 560013, India

² Centre for Product Design and Manufacturing, Indian Institute of Science, Bangalore - 560012, India

arunsingh_aks@yahoo.com

bgm@iisc.ac.in

drchristie07@gmail.com

**Abstract.** This paper discusses use of octree based voxel model for representation of spatial conflicts across multiple design domains. A framework has been developed to create octree based voxel model linked with intended empty spaces in product, which are associated with design requirements, product lifecycle states and connected design domains. Knowledge in System Modelling Language (SysML), is used to select criteria for building octree voxel model. A case study of Coupled cavity travelling wave tube (CCTWT) Slow Wave structure (SWS) design has been taken to showcase the code capabilities. Octree voxels inside CAD platform show and represent spatial conflicts, detected by associativity modelling of Empty space blocks inside CAD along with the Product knowledge in SysML model.

**Keywords:** Octrees, Voxelization, Spatial Conflicts

## 1 Introduction

Product designs are carried out with objectives to satisfy multifunctional domain requirements. In every product design, some spaces are intentionally left empty to satisfy specific requirements of different domains. For example, space may have been provided for electrical insulation, thermal isolation, clearance for moving part, port accessibility, Electron beam transmission or Radio frequency signal travel, expansion of material, tool access, sensors, bolts accessibility, welding tools, or for removal / replacement of parts. There may be cases, where the same space is used for different purposes but in different product states. The space, which has been provided for moving parts clearance in operation state also serves the purpose for accessibility in maintenance state. That is the same space, which is used for two different purposes but in different states. Knowledge regarding these space usages for moving part clearance under operation state, may not have been documented or is not available to designer, who is searching for empty space to locate new module into the product. This may create spatial conflict with workspace of other designer in the same domain or with other domain
designers. This also incurs time wastage; if these spatial conflicts are detected and re-
solved through conventional methods of multi-domain design stakeholder reviews.
Electro-Mechanical systems exhibit more examples of these types of conflict. Design-
ers from different domains have spatial conflicts, who claim over same empty space in
coupled design iterations at different timelines.

CAD tools only hold the geometry information of the product, while beyond geometry information is not captured in CAD models. Product design information like requirements, product states, and actors involved at different product states, functional model and behavior model, is not available in CAD model. Use of tools like System Modelling Language (SysML) by incorporation of system engineering domain, provides a way to capture and to represent product’s non-geometry design knowledge.

In our earlier work for modelling Intended empty spaces for detecting multi-domain
spatial conflict, a top down approach was discussed and implemented [1]. A bulk of
empty space was detected inside CAD assembly model by Boolean operations and then
it was decomposed into smaller empty space (ES) blocks. In subsequent work, the con-
cept of modelling intended empty spaces by parametric primitive blocks was introduced
[2]. Subsequent step is modelling inter-dependencies and building associativity among
these empty spaces, product structure and other product knowledge in SysML. Further
to this, graph based and matrix based approaches were adopted to model these interde-
pendencies and relationships. Design Structure Matrix (DSM)/ Domain Mapping Ma-
trix (DMM)/ Multi-Domain Matrix (MDM) were used to detect the spatial conflicts
among multiple design domains in different product lifecycles states. Upon identifying
these conflicts, knowledge based spatial suggestions can be made for efficient assembly
and layout planning in product design. In this paper, focus is on to build an octree based
voxel model for representation and computation purpose, which uses CAD model and
ES Blocks with spatial conflicts.

## 2 Octree based Voxel model to represent CAD model

Voxel based method is an extension of the concept of pixels into 3D. Space is consid-
ered as a regular array of cells (usually cubes). Each cell is called voxel. Voxelization
provides an alternative to geometric representation for volume modelling outside CAD.
It provides a uniform, simple and robust description to synthetic and measured objects
and gives the basis of volume graphics [3]. Voxelization of 3D model is done to repre-
sent the volumetric space of geometric objects using the primitives of array of voxels
in the 3D discreet space. Voxel model approximates the shape of the model as closely
as possible. The concept of voxelization was first introduced for volume graphics in
1993 [3]. Voxelization has application in different fields as volume modelling [4], vir-
tual medicine [5], heptic rendering [6], visualization of geometric model [7], CSG Mod-
elling [8], Collision detection [9] [10] [11] and spatial analysis [12]. Voxel models are
used for geospatial applications as computational methods for voxelating spatial da-
tasets of 3D city models containing 3D surfaces, curve and point cloud data models
[13]. OctoMap is also an Octree based Voxel model, used as 3D mapping framework
for various robotic applications [14].
Goal of voxelization here is to device a method to discretize the whole product as-
sembly and empty spaces into smaller pieces and computationally model the empty
spaces available free of spatial conflicts, to make valuable knowledge based spatial
suggestions. Voxelization of 3D Solid models in CAD is one way to model volume and
have empty space representation. Voxel information can be represented in form of 3D
array data structure in cases where the CAD model space is small. Voxel enumeration
at different voxel sizes is shown in Fig 1. A moderate 3-dimensional array
1000X1000X1000 will result in 1 billion voxels. Handling associated computations and
rendering of such big number of voxel information is difficult task for any CAD soft-
ware. Once the 3D model is voxelized, Boolean operations such as union and subtrac-
tion are computationally efficient.

<figure><img src="image_3.png" /><figcaption>Fig 1. Voxel enumeration at different voxel sizes</figcaption></figure>

Voxelization of 3D model needs efficient conversion of geometry in CAD to Voxels.
Octree as data structure, enable efficient storage of 3D voxel data. Octree is a 3D gen-
eralization of a Quadtree (for 2D). Each node in an Octree has eight children as shown
in Fig 2.

<figure><img src="image_4.png" /><figcaption>Fig 2. Octree containing empty and occupied nodes</figcaption></figure>

Modelling of intended Empty space blocks as geometry items in CAD model has
been carried out in continued work earlier. Further division of these blocks in voxels
provide a way to efficiently represent and compute independent of CAD Software for
meaningful space suggestions to users. Fig 3 shows a UML class diagram of octree
based voxel model implemented. UML class diagram has been used for easy represen-
tation of the code structure. Any Octree object contains a root Octree node, which can
be further divided into eight octree nodes. Node can contain an Octree leaf object,
which are used as a condition to divide, the octree upto a user given voxel resolution.
CAD model is ray intersected using a standard ray intersection method with CAD APIs.
This results into a point cloud of CAD geometry surfaces. Individual point is added as Octree Leaf to Octree node and based on the location of Octree leaf in root octree object, the octree nodes are further sub-divided.

Every octree node is having variables for Inner node, Empty Node and associated solid body in CAD model. Every Octree Node is having an object for octree bounds to define its boundaries modelled as class in Fig 3. It has been implemented using C# language and the code interacts with CAD model using CAD APIs. Octree Voxel model visualization is done using OpenGL libraries outside CAD environment.

<figure><img src="image_5.png" /><figcaption>**Fig 3.** UML Class Diagram for Octree based voxel model representation of CAD model and Empty Spaces</figcaption></figure>

Purpose of this representation and modeling, is to embed the knowledge available in System Modelling language (SysML) with the CAD model. SysML is the extension of
UML, which is developed to provide standard system modelling tools [15]. SysML supports capturing requirements of system and capturing structural & behavioral models. Block Definition Diagrams (BDD) and Internal Block Diagrams (IBD) are used to define classes and instances. Use of SysML tools, provides the way to capture, represent and associate the product's non-geometry information. This knowledge is stored in SysML compatible XML file for further processing along with the CAD model. Octree based voxel model is created on the fly instead of saving it in XML or other formats, whenever a representation is needed of CAD model with ES blocks associated with knowledge elements like Design requirements, Design domains and Product Lifecycle states. Octree based voxel models are compact and have an edge over array data structure for representation purpose, only when ratio of modeled space to total space, is up to 30 percent. Hence Knowledge available in the SysML, is used to choose only those Empty space blocks, which are connected to Design requirements under specific Product lifecycle state. In this particular use, where octree voxel model also needs to do computation for spatial suggestions, computational methods using Octree data structure, are preferred over arrays.

## 3 Case Study – CCTWT Slow Wave Structure (SWS) Design

Coupled Cavity Travelling wave tubes (CCTWT) are used to amplify RF signals in RADAR. Design of travelling wave tube involves multiple design domains like electromagnetics, thermal, structural, manufacturing and electrical. CCTWTs have five main sub-assemblies - Electron Gun, Slow Wave Structure (SWS), Input RF Window, Output RF window and Collector. Electron beam gets generated in Electron Gun, Which then travels through inner feature of Slow Wave Structure (SWS). RF signals enter SWS through Input RF Window and interact with Electron Beam, while travelling through SWS cavities.

<figure><img src="image_6.png" /><figcaption>Fig. 4. Slow wave structure (SWS) solid model</figcaption></figure>

SWS is an important sub-assembly of TWT and is a perfect example, where multiple design domain teams need collaboration to resolve spatial conflicts to have an efficient product design. SWS consists of alternate pattern of pole-pieces and spacers. Solid
model of typical SWS is shown in Fig. 4. SWS CAD model has been represented in Octree Voxel model in Fig. 5. Complete process of getting point cloud of representing surfaces to full voxel model not differentiating filled and empty nodes to separate Empty space leaf nodes and SWS model filled leaf nodes have been shown in Fig. 5.

<figure><img src="image_7.png" /><figcaption>**Fig. 5.** Octree Based Voxel model generated using ray intersection on CAD Model. (a) Ray Intersecting CAD model from x, y and Z direction with equal resolution. (b) Point cloud generated by standard Ray intersection method with CAD APIs. (c) Voxel model showing complete SWS with its bounding box (CAD model with Empty Spaces). (d) Empty Spaces shown with wireframe and filled octree nodes with their faces modelled. (Empty nodes visible between filled SWS). (e) Filled Nodes between surface nodes to model it as a volume (f) Surface Octree node SWS Model. (g) Octree Voxel model of Empty space (h) Octree Voxel Model of only SWS Geometry</figcaption></figure>

Design requirements for SWS with connected design domain and meant to be for particular product lifecycle states, are listed in table 1. Design mapping matrix (DMM) of ES blocks and requirements in different product lifecycle state is shown in Fig. 6. It
also shows the spatial conflicts in red color, depicting multiple usage of single ES Block in multiple design domains. This information is used to select the ES blocks shown in DMM rows, for creating the octree voxel model. Design requirements listed in table 1, are allocated to different ES blocks. SWS modelled with intended empty space blocks has been shown in Fig. 7. Empty spaces can be associated with the design requirement, which are satisfied by them.

<table><caption>**Table 1.** Design Requirements table</caption><thead><tr><th>ID</th><th>Requirement</th><th>Design Domain</th><th>Product Lifecycle States</th></tr></thead><tbody><tr><td>R6</td><td>Electron Beam Transmission</td><td>Electromagnetic</td><td>Testing, Operation</td></tr><tr><td>R7</td><td>RF Signal and Electron Beam Interaction</td><td>Electromagnetic</td><td>Testing, Operation</td></tr><tr><td>R8</td><td>Space for Magnet Placements in assembly</td><td>Electromagnetic</td><td>Assembly, Testing</td></tr><tr><td>R9</td><td>Cooling channel for thermal management</td><td>Thermal</td><td>All States</td></tr><tr><td>R10</td><td>Holes to align pole-pieces of SWS stack in Assembly and Brazing</td><td>Manufacturing</td><td>Manufacturing, Assembly</td></tr><tr><td>R11</td><td>Brazing of Cooling Channels</td><td>Manufacturing</td><td>Manufacturing, Assembly</td></tr><tr><td>R12</td><td>Magnetic Tuning for increasing electron beam transmission</td><td>Electromagnetic</td><td>Testing</td></tr><tr><td>R13</td><td>Coolant flow inside pole-piece cooling channels</td><td>Thermal</td><td>Testing, Operation</td></tr><tr><td>R14</td><td>Cooling of Pole-piece Cavities to avoid degassing</td><td>Thermal</td><td>Testing, Operation</td></tr><tr><td>R15</td><td>Magnetic field to compress electron beam</td><td>Electromagnetic</td><td>Testing, Operation</td></tr><tr><td>R16</td><td>Structure to sustain Ultra High Vacuum level inside TWT</td><td>Structural</td><td>All States</td></tr><tr><td>R17</td><td>Materials to sustain brazing temperatures</td><td>Structural</td><td>Assembly</td></tr><tr><td>R18</td><td>Materials to sustain temperatures under processing</td><td>Structural</td><td>Assembly</td></tr><tr><td>R19</td><td>RF Power Gain requirement</td><td>Electromagnetic</td><td>Testing, Operation</td></tr><tr><td>R20</td><td>RF Frequency Bandwidth requirement</td><td>Electromagnetic</td><td>Testing, Operation</td></tr></tbody></table>

3D solid model of SWS empty space blocks and Cut-sectional model views of intended empty spaces of SWS for different requirements, have been shown in Fig. 8(a) and (b). This method enables us to correctly differentiate and demarcate spaces inside SWS like for RF Signal and Electron beam. ES Blocks depicting multi-domain spatial conflicts in CAD model are shown in Fig. 8c. ES block list is computed from DMM shown in Fig. 6 for different product lifecycle states. This list in addition with Product structure, is the criteria, used to model octree Voxel model shown in Fig. 8(d).
<figure><img src="image_8.png" /><figcaption>Fig. 6. DMM of ES Blocks and Design Requirements for Slow Wave structure for each product lifecycle state showing multiple usage of single ES Block within Single domain and in multiple design domains depicting spatial conflict</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 7. SWS Empty spaces decomposed into intended empty space blocks showing allocated design requirements</figcaption></figure>
<figure><img src="image_10.png" /><figcaption>**Fig. 8.** a) 3D solid model of SWS Empty spaces b) Cut sectional model of SWS's bulk empty space decomposed into intended Empty space blocks to be allocated to different design requirements. c) ES Blocks depicting multi-domain spatial conflicts in CAD model d) Multi-domain spatial conflict representation using Octree Voxel model by rendering conflicting ES blocks in red with wireframe SWS octree voxel model outside CAD environment using OpenGL.</figcaption></figure>

## 4 Conclusion

This paper discusses use of octree based voxel model for representation of spatial conflicts across multiple design domains. A framework has been developed to create octree based voxel model linked with intended empty spaces in product, which are associated with design requirements, product lifecycle states and are also connected with functional design domains. Knowledge in SysML, which was elaborated in our earlier work [1], is used to select criteria for building octree voxel model. A case study of Coupled cavity travelling wave tube (CCTWT) Slow Wave structure (SWS) design has been taken to showcase the code capabilities and showcase Octree voxels outside CAD platform representing spatial conflicts detected by associativity modelling of Empty space blocks along with the Product knowledge in SysML model.

In future work, it has been planned to use Octree based voxel model for knowledge based spatial suggestions in CAD for assembly and layout planning. Spatial conflict across multiple design domains are detected using different approaches in our earlier work. Subsequently in this paper, an octree based voxel model was generated using CAD model and selected Empty space blocks, which have requirements allocated from multiple design domains / states and showcases spatial conflicts. This gives us spaces available free from conflicts, which are planned to be used for locating new parts in assembly and carry out layout planning.

## 5 Acknowledgement

The First author is thankful to Director, Microwave Tube Research & Development Centre (MTRDC) for providing the opportunity and encouragement in carrying out the work presented in the paper.
6 References

1. A. K. Singh, B. Gurumoorthy and L. Christie, "Empty Space Modelling for Detecting Spatial Conflicts Across Multiple Design Domains," in Product Lifecycle Management and the Industry of the Future, Springer International Publishing, 2017, pp. 223-230.

2. A. K. Singh, B. Gurumoorthy and L. Christie, "Empty Space modelling using Primitive Shapes and Associated constraints for detecting spatial conflicts across multiple design domains," in Proceedings of the International Conference on Product Lifecycle Modelling, Synthesis & Simulations (PLMSS) - 2017.

3. A. Kaufman, D. Cohen and R. Yagel, "Volume graphics," Computer, vol. 26, pp. 51-64, 7 1993.

4. S. W. Wang and A. E. Kaufman, "Volume-sampled 3D modeling," IEEE Computer Graphics and Applications, vol. 14, pp. 26-32, 9 1994.

5. K. Kreeger and A. Kaufman, "Mixing Translucent Polygons with Volumes," in Proceedings of the Conference on Visualization '99: Celebrating Ten Years, CA, USA, 1999.

6. W. A. McNeely, K. D. Puterbaugh and J. J. Troy, "Six degree-of-freedom haptic rendering using voxel sampling," in Proceedings of the 26th annual conference on Computer graphics and interactive techniques - SIGGRAPH 99, 1999.

7. R. Westermann, O. Sommer and T. Ertl, "Decoupling Polygon Rendering from Geometry using Rasterization Hardware," in Eurographics, Springer Vienna, 1999, pp. 45-56.

8. D. Liao and S. Fang, "Fast CSG Voxelization by Frame Buffer Pixel Mapping," in 2000 IEEE Symposium on Volume Visualization (VV 2000), 2000.

9. T. He and A. Kaufman, "Collision Detection for Volumetric Objects," in Proceedings of the 8th Conference on Visualization '97, Los Alamitos, CA, USA, 1997.

10. M. Boyles and S. Fang, "Slicing-Based Volumetric Collision Detection," Journal of Graphics Tools, vol. 4, pp. 23-32, 1 1999.

11. N. Gagvani and D. Silver, "Shape-based volumetric collision detection," in Proceedings of the 2000 IEEE symposium on Volume visualization - VVS 00, 2000.

12. S. Beckhaus, J. Wind, F. Imk. Ve and T. Strothotte, "Hardware-Based Voxelization for 3D Spatial Analysis," 7 2002.

13. Nourian, P.; Gonçalves, R.; Zlatanova, S.; Ohori, K. A. & Vo, A. V., "Voxelization algorithms for geospatial applications", Elsevier BV, 3, 69-86, 2016.

14. A. Hornung, K. M. Wurm, M. Bennewitz, C. Stachniss and W. Burgard, "OctoMap: an efficient probabilistic 3D mapping framework based on octrees," *Autonomous Robots*, vol. 34, pp. 189-206, 2 2013.

15. O. M. G. OMG, “OMG Systems modelling Language Specifications,” 2015. [Online]. Available: http://www.omg.org/spec/SysML/1.4/.