Sanal heykeltraşlıkta optimize edilmiş hash-temelli octree veri yapısının kullanılması

Abstract

Sanal heykeltıraşlık, kullanıcılara sanat, tasarım ve hızlı prototipleme alanlarında sanal gerçeklik donanım ve yazılımları tarafından sağlanan bir sanal dünya içerisinde yeni 3B katı nesne oluşturma veya mevcut nesneleri değiştirebilme imkânı sağlayan 3B bir modelleme işlemidir. Bu tez çalışmasında haptic kuvvet geri-beslemesi ile voksel-temelli bir sanal heykeltıraşlık uygulaması için optimize edilmiş hash-temelli bir octree veri yapısı kullanımı önerilmektedir. Amaç, hacim voksel veri kümesini saklamak için gerekli hafızayı ve hesaplama maliyetini düşürmek, aynı zamanda da gerçek-zamanda etkileşim esnasında gerçekleşen octree kullanımından doğan ağaç dolanım süresini azaltarak model yüzeyinin lokal olarak yeniden oluşturulma süresini kısaltmaktır. İlk önce, üzerinde çalışılan sanal ham maddeye ait hacim verisi daha az hafıza kullanarak saklayabilmek ve gerçek-zamanda yontabilmek amacıyla vokselleştirilerek optimize-edilmiş hash-temelli bir octree veri yapısına dönüştürülmektedir. Daha sonra, küre olarak tasarlanan sanal araç tarafından heykelin hangi voksellerine dokunulduğu belirlenerek bu vokseller veri yapısından çıkarılmaktadır. Sonuç verisine gerçekçi bir görüntü verebilmek amacıyla üçgen kafes modelini yeniden oluşturmak için Marching Cubes algoritması kullanılmaktadır. Tüm hacim için hesaplama maliyeti yüksek olduğundan dolayı bu çalışmada sadece yontma işleminden sonra modifiye edilen vokseller tarafından etkilenen eş yüzey yeniden hesaplanarak lokal güncelleme gerçekleştirildi. İkinci olarak, önerilen sanal heykeltıraşlık sistemine, sanal yontma aracının üç-boyutlu kontrolünü sağlamak ve kullanıcıların yontma işlemi sırasında heykel üzerinde uyguladıkları kuvvete karşı meydana gelen direnci hissedebilmelerine imkan sağlamak amacıyla bir haptic cihazı yolu ile haptic kuvvet-geri beslemesi entegre edilmiştir. Sanal heykeltıraşlıkta hafıza optimizasyonu ve gerçek-zaman etkileşimi üzerine odaklanılan bu çalışmada, önerilen optimize edilmiş hash-temelli octree veri yapısının performansını test etmek amacıyla hafıza maliyetleri ve çalışma süreleri, işaretçi-temelli ve hash temelli veri yapıları ile karşılaştırılmıştır. Sonuç olarak, bu yeni optimize edilmiş hash-temelli octree veri yapısının hem ön-işleme zamanında hem de gerçek zamanda hafıza maliyetleri ve çalışma sürelerindeki düşüşler gösterilmiştir. Anahtar kelimeler: Sanal Heykeltaşlık, Haptics, Vokselleştirme, Octree, Hashing

Virtual sculpting is a 3D modelling process which allows users to create new 3D solid models or modify existing objects provided by virtual reality software and hardware in art, design and rapid prototyping areas. In this thesis, an optimized hash-based octree data structure in a voxel-based virtual sculpting application with haptic force feedback is proposed. The goal is to reduce the memory and computation costs to store volumetric voxel dataset and also to reduce the local surface reconstruction times of the model by decreasing tree traversal time caused by octree during real-time interaction. First, in order to store with less memory and carve in real-time, volumetric data of virtual workpiece is converted into an optimized hash-based octree data structure by voxelizing them. Then, voxels collided with the carving tool that is designed as a sphere are removed from this data structure. Marching Cubes algorithm is used to reconstruct the triangular mesh model in order to give a realistic display of the voxel data. Since the computational cost is very high for the whole volume, in this study, local update is performed by reconstructing the isosurface affected from the modified voxels after carving process. Afterwards, by the way of a haptic device, a haptic force feedback is integrated in the proposed virtual sculpting application in order to provide 3D control of the virtual tool and allow to feel the resistance against the applied force on the sculpture object. This study focused on memory optimization and real-time interaction, memory costs and runtimes of the proposed optimized hash-based octree data structure are compared with the pointer-based and hash-based ones in order to test the performance. Consequently, memory cost and working time decreases on both pre-processing and runtime of this new optimized hash-based octree data structure are shown. Keywords: Virtual Sculpting, Haptics, Voxelization, Octree, Hashing