An FPGA acceleration for the kd-tree search in photon mapping

Takuya Kuhara, Takaaki Miyajima, Masato Yoshimi, Hideharu Amano

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Citations (Scopus)


Photon mapping is a kind of rendering techniques which enables depicting complicated light concentrations for 3D graphics. Searching kd-tree of photons with k-near neighbor search (k-NN) requires a large amount of computations. As k-NN search includes high degree of parallelism, the operation can be accelerated by GPU and recent multi-core microprocessors. However, memory access bottleneck will limit their computation speed. Here, as an alternative approach, an FPGA implementation of k-NN search operation in kd-tree is proposed. In the proposed design, we maximized the effective throughput of the block RAM by connecting multiple Query Modules to both ports of RAM. Furthermore, an implementation of the discovery process of the max distance which is not depending on the number of Estimate-Photons is proposed. Through the implementation on Spartan6, Virtex6 and Virtex7, it appears that 26 fundamental modules can be mounted on Virtex7. As a result, the proposed module achieved the throughput of approximately 282 times as that of software execution at maximum.

Original languageEnglish
Title of host publicationReconfigurable Computing
Subtitle of host publicationArchitectures, Tools, and Applications - 9th International Symposium, ARC 2013, Proceedings
Number of pages12
Publication statusPublished - 2013
Event9th International Symposium on Applied Reconfigurable Computing, ARC 2013 - Los Angeles, CA, United States
Duration: 2013 Mar 252013 Mar 27

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7806 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other9th International Symposium on Applied Reconfigurable Computing, ARC 2013
Country/TerritoryUnited States
CityLos Angeles, CA


  • Acceleration
  • FPGA
  • Photon Mapping
  • k-NN
  • kd-tree

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'An FPGA acceleration for the kd-tree search in photon mapping'. Together they form a unique fingerprint.

Cite this