ࡱ> &(%)` bjbj.  R$Uh^^^^^^^ t^^0^^^^$^^$ Neighbourhood gathering methods are commonly required in many real-time simulation scenarios, such as: crowd simulation and game AI for simulating the vision of the entities; SPH uid simulation for calculate the forces,density and viscosity interactions; and particle systems and physics simulation as the broad phase of the collision detection algorithm. In a naive implementation, it has a complexity of O(n2) required computations of the neighbourhood gathering algorithm, necessary for the proximity queries of all pair of entities in order to compute the relevant mutual interactions. In order to solve this problem, many works propose spatial data structures that subdivide the environment and classify the entities among the cells based on their position. Although this strategy minimizes the number of proximity queries to be treated, it is not e_cient when a large number of particles are grouped in the same cell. This thesis proposes a novel and e_cient data structure that maintains the entities into another paradigm of proximity data structure, called NGrid, where each cell contains only one entity and does not directly represent a discrete spatial subdivision. The NGrid proposal _lls the lack of GPU bounded architectures, which usually processes all elements in the scene at each frame. Results shows that the use of the NGrid in di_erent scenarios leads to a performance gain when compared to traditional data structure.  hGhD'CJOJQJ^JaJhD'OJQJ^JhD'OJQJ^JS d e  q # | - gdD' 7$8$H$gdD' ,1h. A!"#$% @@@ NormalCJ_HaJmHsHtH>A@> Fonte parg. padroTi@T  Tabela normal4 l4a ,k@, Sem listaSd eq#|-00000000000000000|-%0\%0%0hq%0   $,-59=HRS\^bglmwx{  *.1278=>@ADENOXYbino}   ,/089?@LQV`delnry  &')*34;?ABIQTU\]adijpqst} !#)*/167;<@AIJNORSYZ]cfgopy|   !(,-0578;<A]dD'G@x0@@UnknownG: Times New Roman5Symbol3& : Arial3CMR125CMMI121CMR8"1''  !42HX ?D'2RNeighbourhood gathering methods are commonly required in many real-time simulationvivianevivianeOh+'0(< LX x  TNeighbourhood gathering methods are commonly required in many real-time simulationviviane Normal.dotviviane1Microsoft Office Word@@ڛZ@ڛZ՜.+,0< hp|  UFF ' SNeighbourhood gathering methods are commonly required in many real-time simulation Ttulo  !"#$'Root Entry F3t)1Table WordDocument.SummaryInformation(DocumentSummaryInformation8CompObju  F#Documento do Microsoft Office Word MSWordDocWord.Document.89q