Mesh editleri için quad’lar kullanışlı olsa da ekran kartı günün sonunda ekrana trisleri basacak. Bu sebepten ötürü elimizdeki quad’ları güzel bir şekilde ekrana basmamızı sağlayacak bir algoritma yazmamız lazım.
İlk başta bu çok kolay görünebilir:
ABCD quad’ımızı ABC ve ACD olmak üzere 2 tris’e bölebiliriz. Düzlemsel olup kare, dikdörtgen, yamuk gibi şekillere benzeyen quadlar için bu yeterli olacaktır…
Fakat her zaman quad’ımız bu şekillerde düzgün olmaz. Misal aşağıdaki görsele bakalım. ABC tris’i gayet ince uzun bir üçgen olmuş. B, D’ye yaklaştıkça üçgenin alanı 0’a yaklaşır ve bu durum bize çeşitli konularda problem yaratabilir.
Çözüm olarak AC’yi diagonal olarak seçmek yerine BD’yi diagonal olarak seçebiliriz. Bariz olarak
- |BD| : BD’nin uzunluğu
- |AC| : AC’nin uzunluğu
- |BD| < |AC|
Yani aslında kısa diagonal’ı seçmemiz bu durumda bizim problemimizi çözecektir.
Bu yaklaşım çok pratik olsa da her durum için yeterli değildir. A ve C’yi birbirine yaklaştırdığımızı düşünelim. Belli bir noktadan sonra
- |AC| < |BD|
durumu gerçekleşecektir ve triangulation için AC diagonal’ı seçilecektir. Bu bizim istediğimiz bir durum değil çünkü halen ABC üçgeninin dar ve uzun, alanı ufak. Biz daha dengeli bir dağılım istiyoruz. Bunun için diagonal uzunluğa bakmak yerine oluşacak üçgenlerin iç açılarına bakabaliriz.
- AC diagonal’ına göre quad’ı 2 tris’e böl. Aynısını BD diagonal’ı için de yap
- Açılarını hesapla, her üçgenin en küçük iç açısını bul
- En küçük açılı tris’i oluşturmayan diagonal’ı seç.
Farkedeceğiniz üzere bu yol biraz daha çetrefilli olsa da daha iyi sonuç verir. Lakin aynı algoritmanın aşağıdaki quad benzerleri için çalışıp çalışmayacağından emin değilim.
Görüldüğü üzere farklı durumlar için farklı çözüm yolları var ve bu sebepten ötürü algoritmamızı basit bir mantığa sığdıramıyoruz. Farklı durumları düşünmemiz ve çözüm yolları üretememiz lazım.
Şuana kadar yaptığımız örnekler hep Düzlemsel yüzeyler üzerineydi yani bir nevi 2D uzayda çalıştık. Fakat mesh’ler genelde 3D uzayda olur. Böyle olunca planar olması ihtimali çok düşük yani muhtemelen quad’ımız non-planar olacak.
Maksadımız mümkün olduğunca en düz geometriyi oluşturan triangulation’ı yapmak.
- Üçgenlerin normallerini hesapla
- Normallerin dot product’ını al
- Sonuç 1 ise bu 2 üçgenin normali birbirine paraleldir.
- Maksadımız en paralel olan triangulation’ı yapmak
// Üçgenin yüzey normalini hesaplar
glm::vec3 EMesh::trisNormal(const glm::vec3 &A, const glm::vec3 &B, const glm::vec3 &C)
{
constexpr float GeometryEpsilon = 1e-6f;
glm::vec3 AB = B-A;
glm::vec3 AC = C-A;
glm::vec3 n = glm::cross(AB, AC);
// Eğer cross product sıfıra yakın ise
if(glm::dot(n, n) < GeometryEpsilon*GeometryEpsilon)
return glm::vec3(0.0f);
return glm::normalize(n);
}
// bir üçgenin içindeki en küçük açıyı radian cinsinden döndürür.
float EMesh::trisMinAngle(const glm::vec3 &A, const glm::vec3 &B, const glm::vec3 &C)
{
// A
// / \
// / \
// B-----C
// CAB açısının hesaplanması:
// theta = arccos((AB•AC) / (|AB||AC|))
glm::vec3 AB = glm::normalize(B-A);
glm::vec3 AC = glm::normalize(C-A);
glm::vec3 BC = glm::normalize(C-B);
glm::vec3 BA = -AB;
glm::vec3 CA = -AC;
glm::vec3 CB = -BC;
// arccos öncesi numerik hataları önlemek için clamp yapmalıyız:
float dotCAB = glm::clamp( glm::dot(AB,AC), -1.0f, 1.0f );
float dotABC = glm::clamp( glm::dot(BC,BA), -1.0f, 1.0f );
float dotBCA = glm::clamp( glm::dot(CA,CB), -1.0f, 1.0f );
float CAB = acos(dotCAB);
float ABC = acos(dotABC);
float BCA = acos(dotBCA);
return std::min({CAB, ABC, BCA});
}
// Verilen quad'ı triangulate etmek için en iyi diagonalı hesaplar.
// - Eğer en iyi diagonal AC ise true,
// - En iyi diagonal BD ise false döndürür.
// A -- D
// | \ |
// | \ |
// B -- C
bool EMesh::useDiagonalAC(const glm::vec3 &A, const glm::vec3 &B, const glm::vec3 &C, const glm::vec3 &D)
{
const float CoplanarThreshold = 1 - 0.1; // 1 -> maks value; 0.1 ->delta value
// İki üçgenin kırılma açısını buluyoruz. Yani tris normallerinin arasındaki açı
glm::vec3 abcNormal = trisNormal(A,B,C);
glm::vec3 acdNormal = trisNormal(A,C,D);
glm::vec3 abdNormal = trisNormal(A,B,D);
glm::vec3 bcdNormal = trisNormal(B,C,D);
float dotAC = glm::dot(abcNormal, acdNormal);
float dotBD = glm::dot(abdNormal, bcdNormal);
if(dotAC > CoplanarThreshold && dotBD > CoplanarThreshold)
{ // üçgenler yeterince paralel ise minimum açıyı bul.
// minimum açıyı buluyoruz çünkü slim tris'ler istemiyoruz!
float acMinAngle = std::min(trisMinAngle(A,B,C), trisMinAngle(A,C,D));
float bdMinAngle = std::min(trisMinAngle(A,B,D), trisMinAngle(B,C,D));
return acMinAngle > bdMinAngle;
}
else{ // Yeterince coplanar değiller.
return dotAC > dotBD; // Kırılma açısı daha küçük olan triangulation'ı seç.
}
}
Leave a Reply