URSI-TÜRKİYE’2014 VII. Bilimsel Kongresi, 28-30 Ağustos 2014, ELAZIĞ
Etkin Bir Seken Işın Yöntemi Uygulaması Üzerine
Selim Şahin, Fatih Dikmen, A. Arif Ergin
Gebze Yüksek Teknoloji Enstitüsü
Elektronik Mühendisliği
Çayırova, Kocaeli
[email protected], [email protected], [email protected]
Özet: Karmaşık ve elektriksel olarak büyük nesnelerin radar kesit alanı veya saçıcı merkez tahmini için seken
ışın yöntemi (SIY) uygulanmasında hesaplama verimliliği yöntemlerine değinilecektir. Üçgenlenmiş bir
bilgisayar destekli tasarım (BDT) modeli ve bir ışın-üçgen kesişim algoritması kullanılarak yapılan SBR
işleminde, kesişimlerin belirlenmesini hızlandırmak için sınırlayıcı hacim (SH) olarak dikdörtgen kutular veya
küreler ile oluşturulabilen sekizli ağaç yapısı kullanılarak uzay bölümleme (UB) yapılırken sınırlayıcı hacim
seçiminin karmaşıklık derecesinin “önündeki katsayı” yı düşürmedeki etkisi önemlidir. Gerekli bilgisayar
kaynağını azaltmaya yönelik yeni teknikler sunulmaktadır.
Abstract: Computational efficiency of radar cross section or scattering center prediction of complex electrically
large objects is studied using shooting and bouncing rays (SBR) method. A triangulated CAD model is assumed
and SBR is processed by a ray-triangle intersection algorithm. An octree space partitioning, which might be
based on either rectangular boxes or spheres as bounding volumes, is used to speed up the intersection decision.
The effect of proper implementation and choice of the bounding volume to reduce ‘‘the constant in front’’ of the
leading order complexity is demonstrated. It is shown that the required computer resources can be reduced
drastically.
1. Giriş
Seken ışın yöntemi (SIY), karmaşık elektriksel olarak büyük cisim (KEOBC) lerin radar kesit alanı (RKA)
incelenmesinde ve saçılma merkezlerinin bulunmasında 20 yıldan fazladır kullanılmaktadır [1]. Yöntem,
mükemmel iletken veya kaplanmış KEOBCye ışınlar gönderilip takip edilirken son sekme noktasında fiziksel
optik (FO) ışıma integralleri alınarak uygulanır. İntegral alınırken, birden fazla (genelde 4) ışın ile oluşturulan
çokgen veya her ışının sahip olduğu varsayılan dairesel bir kesit kullanılan 2 farklı yöntem uygulanabilir [2].
SIY uygulamasının karmaşıklığı KEOBCnin bilgisayar destekli tasarım (BDT) modelinde bulunan üçgen
sayısı (N) ve modele gönderilen ışın sayısı (S) ile O(SN) olarak belirlenir. Gerçekçi BDT modelleri söz konusu
olduğunda hem N hem de S büyük sayılar olabileceğinden kullanılan ışın-üçgen kesişim algoritmasının hızı
önemlidir. Bu konu bilgisayarlı grafik teknolojisi (BGT) nin de önemli konularındandır. Bu iş yükünü
azaltabilmek amacıyla “uzay bölümleme (UB)” ve “sınırlayıcı hacim hiyerarşisi (SHH)” gibi BGT fikirleri
sekizli-ağaç uzay bölümlemesi ile kurulmuş ve kullanılmaktadır [3]. Bu yöntemlerde SH olarak kutu veya küre
kullanılarak işlem karmaşıklığı O(SN/2H) olan sürecin önündeki sabit sayı daha aşağıya çekilebilmektedir (H
kullanılan hiyerarşinin seviye sayısıdır). Işın takibinin hızlandırılması için ağaç yapısını oluştururken kullanılan
algoritma ve ağacı oluşturan sınırlayıcı hacim seçimi önemlidir. Etkin bir algoritmanın önemli bileşenleri
aşağıdaki gibi anılabilir. Sunumda bu konular detaylandırılacaktır.
2. Işın Tüpü İntegrali
Monokromatik ve zaman bağımlılığı ejωt olan saçılan uzak elektrik alan
Es (r , θ , φ ) ≈
e− jkr ˆ
θ Aθ + φˆ Aφ
r
(
)
(1)
aşağıdaki vektör potansiyel bileşenler ile tanımlanmıştır:
⎧⎪ ⎡ −φˆ ⎤
⎫⎪
⎡θˆ ⎤
⎡ Aθ ⎤ ⎛ jk ⎞
jkr '
⎢A ⎥ = ⎜
⎟ ∫∫ e × ⎨ ⎢ ˆ ⎥ × Eap (r ') + Z 0 ⎢ ˆ ⎥ × Hap (r ') ⎬ .nˆ dx ' dy '
⎣ φ ⎦ ⎝ 4π ⎠ tüp
⎪⎩ ⎣⎢ θ ⎦⎥
⎪⎭
⎣⎢φ ⎦⎥
(2)
URSI-TÜRKİYE’2014 VII. Bilimsel Kongresi, 28-30 Ağustos 2014, ELAZIĞ
Burada k yayılma yönü, k dalga sayısı, Z0 ortamın karakteristik empedansı; Eap(r) ve Hap(r) sırasıyla çıkış
noktasındaki elektrik ve manyetik alanlar veya ışın tüpünün dalga cephesidir. [2]’de türetilen biçim fonksiyonu
S(θ,ϕ) ile aşağıdaki yaklaşıklığı ışın tüpü integralinde kullandığımız ifadeyi oluşturur (rA son sekme noktasıdır).
⎡ Aθ ⎤ ⎡ Bθ ⎤ ⎛ jk
⎢ ⎥ ≈ ⎢ ⎥⎜
⎣ Aφ ⎦ ⎣ Bφ ⎦ ⎝ 4π
⎞
j .k.rA
S (θ , φ )
⎟ (∆A)çıkış e
⎠
(3)
S(θ,ϕ) biçim fonksiyonunun değerlendirilmesindeki yöntem seçimi FO uygulanmasında önemlidir. KEOBCin
radar kesit alanı veya saçılma merkezi tahmini için ışın tüpü üzerinde integrasyon, [3]te belirtildiği gibi, (3)
denklemindeki (∆A)exit sonsuz küçük ve çıkış çokgeni dairesel simetrik ise biçim fonksiyonu S(θ,ϕ)≈1 olur.
Gerçekçi bir KEOBC için gönderilen ışınların yoğunluğu (ışın/λ2, λ:dalga boyu) yeterince yüksek olmalıdır
(gerçek bir KEOBC için toplamda ~10-20 milyon ışın). Her gözlem açısı için bir aydınlatma penceresi
oluşturulur ve her bir ışın buradan gönderilir. h aynı sıradaki ardışık iki ışın arasındaki mesafe iken (∆A)exit=h2
sabit olarak bulunur. Işın penceresindeki her ışın numaralandırılıp (i) izlenir ve (3) denklemi, bulunulan açıdaki
RKA veya saçılma merkezi verisini hesaplamak için tekrarlanır:
⎧⎪ ⎡ Γ lTM Bθi ,l ⎤ ⎛ jk ⎞ 2 j .k.rA
⎡ Aθ ⎤
i
⎢ ⎥ ≈ ∑ ⎨ ⎢ l i ,l ⎥ ⎜
⎟h e
⎣ Aφ ⎦ ışıni ⎩⎪ ⎣⎢ Γ TE Bφ ⎦⎥ ⎝ 4π ⎠
toplam sekme sayısı: L ≥1
⎫⎪
⎬
⎭⎪sekme sayısı l =1
(4)
Burada ΓTM ve ΓTE “düzlemsel yüzeyin genelleştirilmiş yansıtma katsayıları” [3] dır.
3. Uzay Bölümleme ve Kesişim Tespit Algoritması
3.1. Işın-Üçgen Kesişim Algoritmasının Hızlandırılması
Bilgisayarda nesnelerin görüntülenebilmesi için ışın-üçgen kesişimi tespiti için daha hızlı yöntemler BGT
araştırmalarının konusudur ve SIY hızlandırılmasında önem kazanmıştır [3]. Burada söz konusu ışın-üçgen
kesişim algoritması [4]’te bahsedilen algoritmaya dayanmaktadır. Bu algoritmayı tercih edilir kılan üçgenin
bulunduğu düzlem için ayrıca test yapmamasından dolayı düzlem denklemi için gerekli verilerin tutulmasına
gerek kalmamasıdır. Böylece görüntü işlemcisinde hafıza kullanımı ve gerekli işlemci gücü azaltılabilmektedir.
3.2. Sekizli Ağaç Yapısı
Birbirine bağlı düğümlerden oluşan ağaç veri yapıları bilgisayar bilimlerinde geniş bir kullanım alanına
sahiptir. KEOBC in BDT modeline bu yapı, modeli oluşturan farklı boyutlardaki üçgenleri ilişkilendirerek
uygulandığında SIY için ışın-üçgen kesişimi arama işlemine hız kazandırılır. 3 boyutlu model ile çalışılırken her
düğüme ait sekiz çocuk bulunan sekizli ağaç yapısının kullanılması daha mantıklıdır. Kök olarak en küçük
sınırlayıcı kutu (EKSK) atanarak başlanan sekizli ağaç yapısını oluşturma işlemi ve gelişimine dair detaylar [3]te
bulunabilir. Ağaç yapısında sınırlayıcı hacim olarak kullanılan dikdörtgen kutularla onlara eşlenmiş kürelerin
yarıçapları ile o sınırlayıcı hacmin (kürenin veya kutunun) ağaçta hangi seviyede bulunduğu tespit edilebilir [3].
Tablo 1 de verilen C++ benzeri özyinelemeli sözde kod ile BDT üçgenlerinin her biri ağaç yapısında ilgili
seviyeye yerleştirilir.
3.3. Işın ve SH Kesişimi
Ağaç yapısı kullanıldığında ışın takibi işleminin karmaşıklığı O(N/2H) olarak tanımlanmıştır [3].
Hızlanmadaki en büyük etken, ağaç yapısında herhangi bir yerden sekmeyen ışınlar için ışın takibi işlemlerinin
kolaylıkla atlanabilmesidir. SH olarak küre kullanıldığında kesişim tespiti işleminin kutu kullanıldığındaki
işlemden daha hızlı olacağı iyi bilinmektedir.
4. Sonuç
Sunumda, anılan çerçeve içinde, bir SIY uygulamasının çeşitli unsurları detaylandırılacaktır. Bunlar kısaca
sayılırsa ([3]’ten de görülebileceği üzere):
(i)
Tek ışın takibi ile ışın tüpü yöntemi kullanılması,
(ii)
Hızlı üçgen-ışın kesişimi algoritması,
(iii)
Sekizli ağaç yapısı oluşturulurken SH-üçgen ilişkisi için arama yapmayan bir algoritma,
(iv)
Işın takibi yapılırken kutu-SH yerine küre-SH kullanımı
URSI-TÜRKİYE’2014 VII. Bilimsel Kongresi, 28-30 Ağustos 2014, ELAZIĞ
olarak sayılabilir ve bunlar sayesinde ile SIY algoritmasının karmaşıklığı değişmese bile kayda değer bir
hızlanma elde edilebilir.
Tablo 1: Sekizli ağaç yapısının oluşturulması için C++ sözde kodu
bool buDal::UcgenEkle(Ucgen){
// Bu dalın henüz bir üçgeni yoksa, false ile çık
if(!buDal.iceriyor(Ucgen.KapsayanKure.Merkez())){
return false;
}
// eğer bu dal ile eklenecek üçgenin seviyesi aynı ise, bu dal bir son düğüm, yani
// bir üçgen ile ilişkilendirilmiş fakat alt dalı olmayan bir daldır. Ucgeni son düğüme
// ata ve true ile çık.
if(Ucgen.KapsayanKure.Seviye == buDal.Seviye){
buDal.ataSonDugum(Ucgen);
return true;
}
// geçerli olan dalın var olan alt dalları üzerinde eklenecek üçgenin zaten
// var olup olmadığını bulmak için UcgenEkle işlemini yinele, varsa true ile çık
for each(buDal.altDal()){
if(buDal.altDal().UcgenEkle(Ucgen)) {return true;}
}
// eğer eklenecek üçgen alt dallarda bulunmuyorsa, yeni bir alt dal oluştur ve
// UcgenEkle işlemini yinele
buDal.CocukOlustur(Ucgen.KapsayanKure).UcgenEkle(Ucgen);
// true ile çık
return true;
}
5. Kaynaklar
1. H. Lee, R.C. Chou ve S.W. Lee, Shooting and bouncing rays: Calculating the RCS of an arbitrarily shaped
cavity, IEEE Trans Antennas Propag, 1989. s. 194-205.
2. S.W. Lee, H. Ling ve R. Chou, Ray-tube integration in shooting and bouncing ray method, Microwave Opt
Technol Letters, 1988. s. 286-289.
3. Fatih Dikmen, A. Arif Ergin, A. Levent Sevgili ve Bilgin Terzi, Implementation of an efficient shooting and
bouncing rays scheme, Microwave Opt Technol Letters, 2010. s. 2409-2413.
4. Trumbore, T. Möller ve B. Trumbore, Fast, minimum storage ray-triangle intersection, J Graph Tools 2,
1997. s. 21-28.
5. K.-S. Jin, T.-I. Suh, S.-H. Suk, B.-C. Kim ve H.-T. Kim, Fast ray tracing using a space-division algorithm
for RCS prediction, J Electromagn Waves Appl, 2006. s. 119-126.
Download