g3Sharp ile Ağ Örgüsü Sadeleştirme

ORİJİNAL YAZI: http://www.gradientspace.com/tutorials/2017/8/30/mesh-simplification

(Not: Yazıyı plaza diliyle yazmak istemedim. Terimlerin Türkçe karşılıklarını kullandım. Terimlerin İngilizcelerine daha aşinaysanız en aşağıdaki terimler sözlüğüne göz atın.)

(Not2: Çeviri, doğruluk açısından orijinal yazarın ağzından, birinci şahıs ifadesi kullanılarak yapılmıştır.)

Geçenlerde bir kullanıcı, ağ örgüsü sadeleştirme örneğiyle ilgili bir Github sorunu paylaştı. Ne hikmettir ki ben de yakın zamanda Garland ve Heckbert’in İkinci Dereceden Hata Ölçümü (QEM) Sadeleştirme algoritmasını koda dökmeyi bitirmiştim. Bu teknik hakkında daha fazla bilgi edinmek istiyorsanız, orijinal makaleleri ve sonraki birkaç akademik yayını daha Michael Garland’ın internet sitesinde bulabilirsiniz. Piyasadaki diğer yayınlara göre çok okunaklılar. Konuya ana hatlarıyla az sonra giriş yapacağım ama önce ne hakkında konuştuğumuza bir bakalım. Gördüğünüz şey 13.000 üçgenden 500 üçgene otomatik indirgenmiş bir tavşan ağ örgüsü:

Bir ağ örgüsünü sadeleştirmenin ya da indirgemenin (ben bu ifadeyi kullanıyorum, çünkü… iyi bir sebebi yok ama benim kafamda öyle canlanıyor) kolay yollarından birisi ağ örgüsünün kenarlarını yinelemeli bir şekilde çökertmek. Her bir çökertme işlemi bir noktayı, bir kenarı ve o kenara bağlı iki üçgeni (ya da sınırdaysa bir üçgeni) ağ örgüsünden çıkartıyor. Hedefinizdeki üçgen sayısına düşene kadar işlemi tekrar edin, bu kadar basit. Çocuk oyuncağı!

/* Çökertmeden çıktım da Halil’im aman başım selamet. */

/* Mi acaba? */

Çökertmeye hangi kenardan başlamak gerek? Ya da bir kenarı çökerttiğimizde var olan nokta konumunu elimizde tutmaya devam etmemiz gerekir mi? Çoğu durumda en mantıklı davranış noktayı, kenarın orta noktasına kaydırmaktır. Ama akıl akıldan üstündür. İkinci Dereceden Hata Ölçümü (QEM) algoritmasının konuya dahil olduğu nokta burası. Temel olarak, Hata Ölçümü bize kenarları “puanlandırma” gibi bir imkan sunar. Böylelikle hangi kenarın çökertme işleminden sonra şekil üzerinde en az etki yaratacağını bulabiliriz. Bu da nokta için, çökertmeden sonra puanı en aza indirecek bir konum öngörmemizi sağlar.

En nihayetinde Hata Ölçümü, bir noktadan bir düzlem kümesine olan uzaklıkların toplamını bulmaya yarayan bir ölçüm aracıdır. Bir noktanın etrafına halka şeklinde dizilmiş üçgenleri düşündüğünüzde, her bir üçgen bir düzlem demektir. Başlangıçta, bu noktadan düzleme olan uzaklık sıfırdır. Ancak noktayı hareket ettirmeye başladığımızda, uzaklık artar. Böylelikle yeni nokta ile girdi düzlemler (baştaki üçgenler) arasındaki uzaklığı ölçerek bir nokta hareketini (kenar çökertmesi gibi) “puanlayabiliriz”. Her bir nokta-düzlem uzaklığı, NOKTA x MATRİS şeklinde ifade edilebildiği için ve de Ap + Bp = (A+B)p olduğu için, bütün hata ölçümlerini tek bir matris çarpımında birleştirebiliriz.

Daha da iyisi, bir kenarı çökerttikten sonra, bahsettiğimiz noktanın, kenarın iki ucundaki noktaların kendi girdi düzlemlerine göre hesaplanmış hatalarının toplamını tuttuğunu düşünebiliriz (hala tek matrisin içindeyiz ama). Yani art arda çökertme işlemleri yaparken, orijinal ağ örgüsü üçgenlerinin (geçmişte belli bir zaman diliminde) kalan noktaya bağlı bulunmuş düzlem-uzaklık fonksiyonlarını bir araya topluyoruz. Ve bunu hala tek bir matrisin içinde yapıyoruz. Yukarıda bahsettiğim sitede de bulunan 1999 tarihli makalede [PDF] Garland, QEM algoritmasının bir nevi yüzey kavisi ölçme aracı olduğunu ve en uygun üçgenleştirmeyi ürettiğini anlatıyor. Tek kelime: MÜ – KEM – MEL.

Ama, tabii, siz herhalde sadece kod için buradasınız, değil mi?

g3Sharp kütüphanesini kullanabilmeniz için öncelikle ağ örgünüzü DMesh3 formatına çevirmeniz gerek. Nasıl yapıldığını öğrenmek için önceki yazıma göz atın. Sonrasında Reducer nesnesi oluşturmak için birkaç satır daha ekleyip sadeleştirmeyi çalıştırmanız yeterli:

    DMesh3 mesh = load_my_mesh_somehow();
    Reducer r = new Reducer(mesh);
    r.ReduceToTriangleCount(500);

Yukarıdaki kodda, hedef üçgen sayısı 500. Çalışması göz açıp kapayıncaya kadar sürüyor. Kapsamlı bir inceleme yapmadım ama nispeten hızlı bir bilgisayarda 350.000 üçgene sahip bir ağ örgüsünü 100.000 üçgene düşürmek 2-3 saniyemi alıyor. Yani bundan hızlısı mezarda.

Ağ Örgüsü Sağlamlık Denetimi

g3Sharp içerisindeki birçok ağ örgüsü işleme algoritması, girdi olarak verilen ağ örgülerinin manifold olmasını gerektiriyor. Bu terimin birçok anlamı var ancak bizim konumuzla alakalı kısımda, her bir kenarın en az 1 ya da 2 üçgene bağlı olması gerektiği anlamına geliyor. DMesh3 içerisinde üçgen kenarları, bir Index2i nesnesi içerisinde saklanıyor. Dolayısıyla DMesh3, manifold olmayan bir kenarı gösteremez bile. Aynı şekilde, birçok durumda papyon noktaların da bulunmaması gerekir. Papyon nokta, ayrışık iki üçgenin kesişiminde bulunan tek noktaya verilen isimdir (adı üstünde: papyon).

Bu gereksinimler sağlanmadığı takdirde, kenar çökertme gibi bazı ağ örgüsü işlemleri belirsiz sonuçlar doğurabilir, kuraldışılık hataları verebilir, vs. Bu yüzden, ağ örgünüzün sağlamlığını test etmek için DMesh3.CheckValidity() fonksiyonunu kullanabilirsiniz. Bu fonksiyonun ağ örgüsünün geçerli olmadığı durumlarda nasıl tepki vereceğini yapılandırabilirsiniz: belirtim yapabilir, kuraldışılık hatası verebilir, yalnızca false değeri döndürebilir, vs. Fonksiyon, varsayılan olarak papyon noktaları geçersiz olarak dikkate alır. Bu davranışı değiştirmek için AllowNonManifoldVertices argümanını yapılandırabilirsiniz.

Aklınızda bulunsun: bu fonksiyon, ağ örgüsü içerisindeki bütün veri yapılarının sağlamlığıyla ilgili titiz bir test işlemi yapıyor. Bu fonksiyonu kullanmak performans açısından pahalıya mal olabileceğinden dolayı üretim kodu içerisinde sık kullanmamanızı öneririm. Bir istisna, dosyadan ağ örgüsü okuduğunuz zaman olabilir. Ağ örgüsünü okuduktan hemen sonra sağlamlığını test etmek, sizi daha sonra büyük baş ağrılarından kurtarabilir.

Sınırları Koruma

Sınırlara sahip ağ örgüleriyle çalıştığınız bazı durumlarda, sınır döngülerini olduğu gibi korumanız gerekebilir. Büyük bir ağ örgüsünün sadece belli bir kısmının üçgen sayısını azaltma durumu ya da ağ örgüsünün UV sınırları boyunca ayrılmış olma durumu, buna örnek olarak verilebilir. Bunu halletmek için ReduceToTriangleCount() fonksiyonunu çağırmadan önce birkaç satır eklemeniz yeterli:

    r.SetExternalConstraints(new MeshConstraints());
    MeshConstraintUtil.FixAllBoundaryEdges(r.Constraints, mesh);

Yukarıdaki kodda bulunan MeshConstraints nesnesi aslında çok kaslı bir abimizdir. Çünkü sınır kenarlarından daha fazlasını kısıtlamamızı sağlar. Bu veri yapısını ya da MeshConstraintUtil yardımcı sınıfını biraz kurcalayarak daha fazla bilgi edinebilirsiniz. Aşağıdaki görsellerde, sınırlara sahip bir tavşan modelini 500 üçgene sadeleştirirken sınırları korumadığımız (solda) ve koruduğumuz (sağda) durumları karşılaştırabilirsiniz.

Burada da tavşanın patileri çevresindeki sınırların yakın çekimini görüyorsunuz. Solda gördüğünüz üzere sınır döngüsü boyunca gözden kaçmayan kısa kenarlar var, çünkü sınırları koruduk. Amma ve lakin, biraz daha yakından bakarsanız, ön-sol patide birkaç tane çok ince üçgenler oluşmuş. Sınır koruma işleminin tavan kalitesi şimdilik bu kadar. Arada sırada, sınıra yakın bölgelerde böyle çirkin sonuçlar doğurabiliyor.

/* Sınıra yakın bölgelerde çirkin sonuç görmemiş bu arkadaş. Belli ki Türkiye’ye hiç gelmemiş. */

Umut ediyorum ki ilerleyen zamanlardaki bir güncellemede bu konuda bazı geliştirmeler yapacağız.

Hedefe Yansıtma

Son olarak, ağ örgüsünü sadeleştirirken yapmak isteyebileceğiniz bir şey daha var. Varsayılan olarak, kenar çökertme işleminden sonra oluşan “yeni” noktanın konumu, o nokta için QEM hatasının en aza indirilmesiyle hesaplanıyor. Kenar orta noktaları gibi durumlarla kıyaslandığında, daha güzel sonuçlar çıkartıyor ve de algoritmanın çok daha hızlı çalışmasını sağlıyor. Amma ve lakin, bazı durumlarda bu nokta konumlarının orijinal ağ örgüsü üzerinde kalmasına gerek duyabilirsiniz. Bu özelliği de destekliyoruz.

Öncelikle, Mekansal Sorgu yazısında oluşturduğumuz DMeshAABBTree3 gibi bir mekansal veri yapısı oluşturuyorsunuz. Sonra Reducer içerisinde “yansıtma hedefi” olarak atamasını yapıyorsunuz. Bu işlem, nokta konumlarının girdi ağ örgüsü yüzeyindeki en yakın noktalara eşlenmesini sağlıyor. Aha bu da kodu:

    DMeshAABBTree3 tree = new DMeshAABBTree3(new DMesh3(mesh));
    tree.Build();
    MeshProjectionTarget target = new MeshProjectionTarget(tree.Mesh, tree);
    r.SetProjectionTarget(target);
    r.ProjectionMode = Reducer.TargetProjectionMode.Inline;

Son satır isteğe bağlı. Bu satır, Reducer nesnesini, nokta için her QEM hatası hesaplaması gerektiğinde yansıtma yapacağı şekilde yapılandırıyor. Bu yöntem mantıksal olarak daha doğru ama noktaların birçoğu önünde sonunda sistemden atılacağı için aynı zamanda işgücü israfı anlamına geliyor (yansıtma işlemleri performans yönünden pahalı çünkü). Eğer bu satırı hariç tutarsanız, yansıtma işlemi Reducer işini hallettikten sonra hesaplanır. Bu da en sonunda sistemde kalacak olan noktalar için hesaplanması demek. Aşağıdaki görselde, yansıtma yapılmamış (solda) ve hizalı yansıtma yapılmış (sağda) ağ örgülerinin orijinal ağ örgüsünün (koyu gri) üzerine bindirilerek karşılaştırılmalarını görüyorsunuz. Sadeleştirilmiş ağ örgüleri aslında çok da farklı görünmüyor ama sağda gördüğünüz gibi, ağ örgüsünün çoğu orijinal ağ örgüsünün içinde kalıyor. Öte yandan, soldaki ağ örgüsü ise orijinal ağ örgüsünün yarı içinde/yarı dışında.

Aklınızda bulunması gerekir ki, ince kısımlar üzerinde yansıtma yaparken, yansıma kolay bir şekilde “yanlış” tarafta oluşabilir. Aslına bakarsanız, birçok sadeleştirme sorununu çözerken böyle bir şeye belki ihtiyaç bile duymayacaksınız. Bu da işinize gelir çünkü bu durumda algoritma nispeten yavaş çalışıyor.

Şimdi, de hayde gidin çökertme yapıverin gari. Sonraki durağımız Yeniden Örgüleme. Hemen hemen aynı mantıkla çalışan bir sistem ama aynı zamanda da tam bir Arap saçı…

Terimler Sözlüğü

Ağ örgüsü	Mesh
Nokta	Vertex
Kenar	Edge
İkinci Dereceden Hata Ölçümü	Quadratic Error Metric
Yinelemeli	Iteratively
Çökertme	Collapse
Düzlem	Plane
Girdi	Input
Kuraldışılık hatası	Exception
Belirtim	Assertion
Veri yapısı	Data structure
Sınır döngüsü	Boundary loop
Yansıtma	Projection
Orta nokta	Mid-point
Mekansal sorgu	Spatial query
Eşlenme	Mapping
Hizalı	Inline
Yeniden Örgüleme	Remesh