Hi,

I am doing a university research project on optimising UTD ray-tracing. 
This is a long question and involves ray tracing and

electromagnetics.

Background
UTD stands for "uniform theory of diffraction". Simply put: UTD 
ray-tracing is ray-tracing using electromagnetic waves as opposed to light.

Instead of lights there are antenna's which radiate electromagnetic 
waves. Instead of an eye and 2D view plane the user can specify where in

3D space the electromagnetic radiation is to be determined. Instead of 
using an illumination model to determine the colour of pixels,

electromagnetic theory (ie. the uniform theory of diffraction) is used 
to determine the electromagnetic radiation along a ray.

Current implementation
The implementation of UTD ray-tracing (www.supernec.com) works as follows:
1. PATH FINDING: determine the geometrically path: determine the 
components (plates, cylinders etc.) off which the ray reflects, diffracts,

refracts etc. to get from the antenna to the observer position
2. SHADOW TESTS: determine if the path in 1 is "shadowed" by any 
components. This is the classic intersection tests in ray-tracing.
3. FIELD FINDING: if the path in step 2 is valid: apply the 
electromagnetic theory along the path

Steps 1 and 2 only use geometry and ray-tracing. Step 3 is purely 
electromagnetic.

Objective
I need to optimise step 1 (path finding). Step 2 (shadow tests) I can 
optimise using bounding boxes / spatial subdivisions etc.

The Problem
Step 1 was implemented in a peculiar way. Before I continue, I need to 
mention that I cannot change the way step 1 (path finding) works. I

need to optimise the current implementation. So no radical re-write of 
the software.

PATH FINDING works as follows:
Given:
-a 3d scene consisting of multiple components (plates, cylinders etc).
-a source and observer location. The source is a point on an antenna. 
The observer can be any where in space (including points on the antenna).
Algorithm:
1. A particular ray-type is specified, eg.
- single reflection off plate
- single reflection off cylinder
- single diffraction off the edge of a plate
- single reflection off plate followed by a single reflection off a cylinder
- reflection off any plate, then reflection off a cylinder, then 
diffraction off a plate's edge
etc. ...
2. The algorithm examines every combination of components and attempts 
to fit a ray in between source and observer that travels over the

required components. The points of reflection/diffraction/refraction are 
determined using 1) geometry for simple rays like single reflections

or single diffractions 2) iterative methods for higher order rays eg. 
double diffraction off 2 cylinders.
3. Once a path is found it is tested to see if
1) the laws of reflection / diffraction / refraction are obeyed
2) the points of reflection / diffraction / refraction are on the finite 
sized components. Step 2 initially assumes the components have

infinite size (infinite area plates, infinitely long cylinders etc.)
4. If the path survives step 3, the path is declared geometrically valid 
and the shadow tests can begin.

Path finding is different to graphical ray-tracing. Instead of shooting 
rays like in graphically ray-tracing, a ray is "bent" into place 
between the components in the scene and the source and observer.

In step 2 the number of component combinations grows quickly with the 
number of components in the scene. The problem is many of

the rays do not survive PATH FINDING. The reason: most of the points of 
reflection / diffraction / refraction are not located on the finite

sized components. A lot of time is spent examining physically impossible 
pathes.

My first idea:
For each antenna create a "light-buffer", ie. before ray tracing 
determine which components can be seen from the antenna. So if a component

cannot be seen from the antenna, then exclude it from path finding.

Problem: This solution ignores the fact that many paths fail path 
finding because they are not located on the finite sized components. The

antenna can often see at least a part of all components.

My second idea:
Ray coherence: The valid pathes vary little between neighbouring and 
closely space observer and source locations. So I only call path finding

at every n-th observer location. In between I use cached paths.

Problem: approximation / reduced accuracy; some valid paths are missed

My question:
1. How to speed up path finding as it is implemented presently ?
2. Comments on my 2 solutions ?
3. A better way to do the entire UTD-ray-tracing ?

If you did not understand (very likely), please tell me, then I will try 
again and you can possibly help me.

Thank you, in advance for any help

Robert Hartleb
r.h### [at] eewitsacza

Post a reply to this message