Real-time rendering techniques are critical and highly desirable in interactive graphics applications such as video games, flight simulations, and interactive design softwares. Offline rendering solutions such as raytracing, path tracing, photon mapping, and other Monte Carlo methods can generate very realistic images and capture fairly complicated effects such as caustics, soft shadows, atmospherical scattering or subsurface scattering, and environment lighting but take hours or even days to run. For interactive applications, a large number of real-time rendering techniques have been proposed. They, however, either capture effects that are too simplistic, missing critical complicated effects, or make very constraining assumptions that limit them to specific application scenarios. There is a wide gap and a large unexplored area between slow offline renderers and particular real-time solutions. In this thesis, we take analytical, frequency and wavelet based approaches to investigate efficient algorithms for more complicated natural phenomena. Practically, we aim to provide efficient solutions/tools that are general enough to be combined with existing real-time rendering techniques and expand the domain of tractable effects. On a theoretical level, we try to identify traits of graphics computation and uncover insights about the optimal mathematical representations, leveraging the advancing power of graphics hardware. While open topics are plenty, we choose to focus on key effects that are the most lacking in the current state of art of rendering techniques. In particular, we present solutions to four challenging problems. First, we consider real-time rendering of scenes in scattering media, capturing the effects of light scattering in fog, mist and haze. We present a physically based analytic model that captures these effects while maintaining real time performance and the ease of use of the OpenGL fog model. Our method is based on an explicit analytic integration of the single scattering light transport equations for an isotropic point light source in a homogeneous scattering medium. Second, we introduce a novel near-field relighting framework. At the core of this framework is an affine double and triple product integral theory - an important generalization of triple product wavelet integrals that enables one of the product functions to be scaled and translated. Our theoretical development overturns the long-held belief that operations such as affine transformation are difficult in wavelets and require converting to and from the pixel domain. We show through detailed analysis that while simple analytic formulae are not easily available, there is considerable sparsity that we can exploit computationally. The canonical coupling coefficients we derived and our way of exploiting unstructured sparsity are all new powerful insights. We demonstrate practical implementation of an intuitive lighting design system coupled with near-field relighting capabilities. We also illustrate initial examples of wavelet importance sampling with near-field area lights, and image processing directly in the wavelet domain. Finally, we present two frequency based approaches to normal map filtering and dynamic soft shadowing. Our main theoretical contributions in these applications are respectively formulating the normal map filtering as a convolution in the frequency domain and developing the spherical harmonic exponentiation and logarithm techniques. Our analysis has revealed important technical characteristics of light transport and reflectance. Our analytical, frequency and wavelet based approaches have opened up new perspectives for rendering novel effects that are conventionally viewed as difficult to achieve.