Radiosity algorithms running in sub-quadratic time

被引：0
|
作者：
Szirmay-Kalos, L [1 ]
Foris, T [1 ]
机构：
[1] Tech Univ Budapest, Dept Proc Control, H-1111 Budapest, Hungary
来源：
WSCG '97: THE FIFTH INTERNATIONAL CONFERENCE IN CENTRAL EUROPE ON COMPUTER GRAPHICS AND VISUALIZATION '97, CONFERENCE PROCEEDINGS, VOL 1-4 | 1997年
关键词：
radiosity method; iterative techniques; transillumination; complexity; painter's algorithm;
D O I：
暂无
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
This par,er presents an iterative radiosity algorithm that is capable to determine the radiosity of the patches in O(n log n) time and using only O(n) space. The basic idea is to compute the radiosity updates of all patches in a single direction parallely, requiring only one complete solution of the visibility problem per directions. The visibility problem is solved by painter's algorithm that is responsible for the O(n log n) time complexity, and thus it does not require large amount of z-buffer memory.
引用
收藏
页码：552 / 561
页数：10
相关论文
共 50 条
  • [21] Fluctuation estimates for sub-quadratic gradient field actions
    Brydges, David
    Spencer, Thomas
    JOURNAL OF MATHEMATICAL PHYSICS, 2012, 53 (09)
  • [22] Sub-quadratic time and linear space data structures for permutation matching in binary strings
    Moosa, Tanaeem M.
    Rahman, M. Sohel
    JOURNAL OF DISCRETE ALGORITHMS, 2012, 10 : 5 - 9
  • [23] Towards sub-quadratic time and space complexity solutions for the dated tree reconciliation problem
    Drinkwater, Benjamin
    Charleston, Michael A.
    ALGORITHMS FOR MOLECULAR BIOLOGY, 2016, 11
  • [24] Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
    Equi, Massimo
    Makinen, Veli
    Tomescu, Alexandru I.
    THEORETICAL COMPUTER SCIENCE, 2023, 975
  • [25] Graphs Cannot Be Indexed in Polynomial Time for Sub-quadratic Time String Matching, Unless SETH Fails
    Equi, Massimo
    Makinen, Veli
    Tomescu, Alexandru, I
    SOFSEM 2021: THEORY AND PRACTICE OF COMPUTER SCIENCE, 2021, 12607 : 608 - 622
  • [26] A sub-quadratic algorithm for conjunctive and disjunctive boolean equation systems
    Groote, JR
    Keinänen, M
    THEORETICAL ASPECTS OF COMPUTING - ICTAC 2005, 2005, 3722 : 532 - 545
  • [27] Estimates on modulation spaces for Schrodinger evolution operators with quadratic and sub-quadratic potentials
    Kato, Keiichi
    Kobayashi, Masaharu
    Ito, Shingo
    JOURNAL OF FUNCTIONAL ANALYSIS, 2014, 266 (02) : 733 - 753
  • [28] Holder continuity for nonlinear sub-elliptic systems with sub-quadratic growth
    Wang, Jialin
    Liao, Dongni
    Guo, Zhenhua
    Yu, Zefeng
    Wu, Shimin
    REVISTA DE LA REAL ACADEMIA DE CIENCIAS EXACTAS FISICAS Y NATURALES SERIE A-MATEMATICAS, 2015, 109 (01) : 27 - 42
  • [29] Sub-quadratic (1+ε)-approximate Euclidean Spanners, with Applications
    Andoni, Alexandr
    Zhang, Hengjie
    2023 IEEE 64TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, FOCS, 2023, : 98 - 112
  • [30] Complex dynamics of a sub-quadratic Lorenz-like system
    Li, Zhenpeng
    Ke, Guiyao
    Wang, Haijun
    Pan, Jun
    Hu, Feiyu
    Su, Qifang
    OPEN PHYSICS, 2023, 21 (01):
12345