REPRESENTATION AND STORAGE OF VOXEL TERRAIN FOR DESIGNING VIRTUAL REALITY SYSTEMS

In this paper, we develop methods for representing and storing volumetric (voxel) data. These methods can be used for modeling voxel terrains with sharp features that are necessary for representing human-made parts of the terrain in architectural CAD and virtual reality systems with destructible environments. We propose that each editable chunk of the voxel terrain be stored in a form of ray-representation augmented with surface normals and materials, or as a set of points with implicit connectivity. In the first case, a 3D object is encoded as a set of solid intervals along the three principal directions. In the second case, the object is described as a dense 3D array of voxels (serving as material indices), and a sparse point cloud, where points are stored only inside heterogeneous cells (where materials at corner voxels differ). Both representations allow to perform boolean operations, support multiple materials and store information for reconstructing sharp features of the surface, while the ray representation is used in CAD/CAM/CAE software for geometric modeling. We evaluate the proposed volumetric representations in a test environment and emphasize their advantages and limitations. This enables the reader to choose the best strategy according to the number of specific requirements for a CAD or a virtual reality system.The reported study was funded by RFBR according to the research project № 19-07-01200

1. Lengyel E. Voxel-Based Terrain for Real-Time Virtual Simulations // PhD diss., University of California at Davis. — 2010. — 95 P.

2. Forstmann S. Research on Improving Methods for Visualizing Common Elements in Video Game Applications // PhD diss., Waseda University. — 2013. — 168 P.

3. Voxel Farm [Electronic resource] / Access mode: http://voxelfarm.com/ Access date: 01/29/2019

4. A Survey on Implicit Surface Polygonization // ACM Computing Surveys. 2015. Vol. 47, Iss. 4. — P. 1-39.

5. Ju T., Losasso F., Schaefer S., Warren J. Dual Contouring of Hermite Data // ACM Transactions on Graphics, 21(3). — 2002. — P. 339–346.

6. Shakaev, V. View-Dependent Level of Detail for Real-Time Rendering of Large Isosurfaces / V. Shakaev, N.P. Sadovnikova, D.S. Parygin // Creativity in Intelligent Technologies and Data Science. Second Conference, CIT&DS 2017 – (Ser. Communications in Computer and Information Science ; Vol. 754) – P. 501-516.

7. Schaefer S, Warren J. Dual marching cubes: primal contouring of dual grids // Computer Graphics Forum, 24(2). —2005. — P. 195–201.

8. Ho C.-C., Wu F.-C., Chen B.-Y., Chuang Y.-Y., Ouhyoung M. Cubical marching squares: Adaptive feature preserving surface extraction from volume data // EUROGRAPHICS 2005, 24, 3. — 2005. — P. 537–545.

9. Frisken S.F., Perry R.N. Designing with distance fields // Proceedings of the International Conference on Shape Modeling and Applications 2005 (SMI '05), IEEE Computer Society. — 2005, Washington, DC, USA. – P. 58–59

10. Menon J., Marisa R., Zagajac J. More powerful solid modeling through ray representations // IEEE Computer Graphics and Applications, 14. — 1994. — P. 22–35.

11. Rocchini C., Cignoni P., Ganovelli F., Montani C., Pingi P., Scopigno R. Marching Intersections: an Efficient Resampling Algorithm // Shape Modeling International, IEEE Computer Society. — 2001. – P. 296–305.

12. Benouamer M.O., Michelucci D. Bridging the Gap between CSG and Brep via a Triple Ray Representation // Proceedings of the fourth ACM symposium on Solid modeling and applications (SMA '97), ACM. — 1997, New York, NY, USA. — P. 68–79.

13. Wang C.C.L., Chen Y. Layered Depth-Normal Images: a Sparse Implicit Representation of Solid Models // Technical Report, The Chinese University of Hong Kong. — 2007.

14. Wang C.C.L., Leung Y.-S., Chen Y., Solid modeling of polyhedral objects by Layered Depth-Normal Images on the GPU // Computer-Aided Design, Vol. 42, Iss. 6. — 2010. — P. 535–544.

15. Zhao H., Wang C.C.L., Chen Y., Jin X. Parallel and efficient Boolean on polygonal solids // The Visual Computer, Vol. 27, Iss. 6–8. — 2011. — P. 507–517.

16. Vorontsov G.V. Quickly build a BVH tree on GPGPU. / Vorontsov G.V., Preobrazhensky A.P., Choporov O.N. / / Modeling, optimization and information technology. 2018. Vol. 6. No. 2 (21). Pp. 24-34.

17. Wang C.C.L., Chen Y. Regulating complex geometries using layered depthnormal images for rapid prototyping and manufacturing // Rapid Prototyping Journal, Vol. 19, Iss. 4. — 2013. — P. 253–268.

18. Kwok T.-H., Chen Y., Wang C.C.L. Geometric Analysis and Computation Using Layered Depth-Normal Images for Three-Dimensional Microfabrication // Three-Dimensional Microfabrication Using Two-photon Polymerization (Micro and Nano Technologies), William A. Publishing. — 2016. — P. 119–147.

19. Ho C.-C., Tu C.-H., Ouhyoung M. Detail sculpting using cubical marching squares // Proceedings of the 2005 international conference on Augmented tele-existence (ICAT '05). — 2005, NY, USA. — P. 10–15.

20. Nooruddin F., Turk, G. Simplification and Repair of Polygonal Models Using Volumetric Techniques // ACM Transactions on Visualization and Computer Graphics, Vol. 9, Iss. 2. — 2003. — P. 191–205.

21. Lefebvre S. IceSL: A GPU Accelerated CSG Modeler and Slicer // AEFA'13, 18th European Forum on Additive Manufacturing. — 2013, Paris, France.

22. Zhang N., Qu H., Kaufman A. CSG Operations on Point Models with Implicit Connectivity // Computer Graphics International 2005. — 2005. — P. 87–93.

23. Lorensen W., Cline H. Marching Cubes: a high-resolution 3D surface construction algorithm // Computer Graphics (SIGGRAPH 87 Proceedings). — 1987. — P. 163–169.

24. Gibson S. Constrained elastic surface nets: Generating smooth surfaces from binary segmented data // Proceedings of the First International Conference on Medical Image Computing and Computer-Assisted Intervention, MICCAI 1998. — 1998. — P. 888–898.