基于FPGA加速的bird-oid object算法實現(xiàn)

1. 項目概述

模型說明

Bird-oid object 簡稱Boids模型，是美國的一個圖形計算機科學(xué)家Craig Reynolds在 1986 年開發(fā)出來的。

他的Boids模型為集群個體抽象出三個基本行為：分離（seperation）、對齊（alignment）、與聚集（cohesion）。將這三種行為按一定權(quán)重進(jìn)行混合，可以讓群體出現(xiàn)秩序化的社會性行為。這個模型自從提出到現(xiàn)在一直持續(xù)影響著社會學(xué)、生物學(xué)、計算機科學(xué)等學(xué)科的發(fā)展。基于這個模型的應(yīng)用其實很多， 比如現(xiàn)在的集群無人地面車輛，集群無人機燈光秀等等。

項目說明

本項目使用DE1 SoC的ARM A9處理器和FPGA邏輯的組合，不僅成功地模擬了動態(tài)boid (bird-oid object)群集模式，而且還優(yōu)化了周期要求和執(zhí)行時間。

本項目首先創(chuàng)建了一個完全運行在ARM A9處理器上的“基線”設(shè)計。這個基線設(shè)計是使用C代碼創(chuàng)建的，能夠以每秒60幀的速度計算最多3,000個對象的群集模式。

我們的第二個對比設(shè)計是在FPGA上創(chuàng)建一個更新功能可以計算和更新每個物體在x和y坐標(biāo)上的位置，以及它們在x和y方向上的速度。最后成功地在FPGA上模擬了最多顯示150個對象的boids群集模式。

這個項目的目標(biāo)是改善更新功能所需的周期數(shù)，并看到總體執(zhí)行時間的改進(jìn)。如果能夠減少運行更新的專用硬件的循環(huán)次數(shù)，估計就最終可以在ARM處理器上進(jìn)行超過3000個對象的計算。

2. 實現(xiàn)原理

要創(chuàng)建boids群集模擬，需要遵循三個主要步驟:分離、對齊和聚集。

分離 Separation：離得太近的物體會相互遠(yuǎn)離

對齊 Alignment：對齊是指每個物體試圖匹配其可見范圍內(nèi)物體的速度，朝著周圍同伴的平均方向前進(jìn)

聚集 Cohesion：朝著周圍同伴的平均位置移動

當(dāng)對象之間靠得太近時，執(zhí)行兩個步驟使對象之間稍微散開一點。第一步是計算當(dāng)前節(jié)點到最近節(jié)點的距離：

close_dx += boid.x - otherboid.x

close_dy += boid.y - otherboid.y

一旦這被計算出來，我們就創(chuàng)造了一個回避因素：avoidfactor。這個avoidfactor雖然仍然相對較小，但將乘以之前計算的close_dx和close_dy值:

boid.vx += close_dx*avoidfactor

boid.vy += close_dy*avoidfactor

下一步是對齊所需的計算。我們執(zhí)行以下步驟:

在開始更新特定對象時，三個變量(xvel_avg、yvel_avg和neighboring_boids)為零。

循環(huán)遍歷每一個其他的對象。如果到特定對象的距離小于可見范圍，則

xvel_avg += otherboid.vx
yvel_avg += otherboid.vy

neighboring_boids += 1

循環(huán)遍歷所有其他物體后，如果neighboring_boids > 0，則執(zhí)行以下操作:

xvel_avg = xvel_avg/neighboring_boids
yvel_avg = yvel_avg/neighboring_boids

然后根據(jù)以下公式更新速度:

boid.vx += (xvel_avg - boid.vx)*matchingfactor
boid.vy += (yvel_avg - boid.vy)*matchingfactor

（其中matchingfactor是一個可調(diào)參數(shù)）

最后一次物體對物體的更新是基于聚集性，因為每個物體對象都在其可見范圍內(nèi)緩慢地轉(zhuǎn)向其他對象的質(zhì)心。它是這樣做的:

1. 在開始更新特定對象時，三個變量(xpos_avg、ypos_avg和neighboring_boids)為零

2. 循環(huán)遍歷每一個其他的對象。如果到特定對象的距離小于可見范圍，則

xpos_avg += otherboid.x
ypos_avg += otherboid.y
neighboring_boids += 1

循環(huán)遍歷所有其他對象后，如果neighboring_boids > 0，則執(zhí)行以下操作:

xpos_avg = xpos_avg/neighboring_boids
ypos_avg = ypos_avg/neighboring_boids

然后根據(jù)以下公式更新速度：

boid.vx += (xpos_avg - boid.x)*centeringfactor
boid.vy += (ypos_avg - boid.y)*centeringfactor

（其中centeringfactor是一個可調(diào)參數(shù)）

對象更新的最后一步是確定對象何時需要轉(zhuǎn)動，以便所有對象都保持在正在使用的VGA屏幕的范圍內(nèi)。這可以通過下面的條件語句來實現(xiàn):

ifboid.x boid.vx=boid.vx+turnfactor
ifboid.x>rightmargin:
boid.vx=boid.vx-turnfactor
ifboid.y>bottommargin:
boid.vy=boid.vy-turnfactor
ifboid.y boid.vy=boid.vy+turnfactor

當(dāng)使用不同的微控制器和顯示器時，邊界條件和背后的邏輯保持不變。

審核編輯：劉清