I hope I manage to explain this.
I am writing a macro that subdivides the object bounding box into smaller cells
and then uses trace() function to trace along 8 axes from the center of those
cells into their corners. When the object is hit, a light source is created at
the intersection point - _if_ there are no other light sources too close by.
NB! This desription is not very good, if you don't get it, skip it. Just check
the summary question at the bottom, please...

OK, I want that there are no other light sources closer than a specified
distance (to limit the overall number of light sources).
My current method is to use an array of Boolean flags (0-no light; 1-contains
light) for all cells and axes; then check the current and adjacent (already
processed) cells for light sources. If found (cell flag is 1), check the 8 axes
in that cell. The distance between the current intersection point and the found
light_source is then calculated. If the distance is smaller than the threshold
value, a new light source is created at the intersection point (and the current
cell and axis flags set to 1)
This doesn't entirely cover the method, but most of the other stuff stems
directly from those basic principles.

The macro works, but it's slow: a mere 3X3X3 division (3*3*3*8=216 traces)
takes ab. 1 min 30 to parse on my 486DX120. The first and foremost reason is my
proximity checking method.
So the question is: how can 3D proximity checking be done quicker? Would I need
to use an entirely different subdivision method (marching cubes or something)?

Margus

Post a reply to this message

On 18 Nov 1998 07:07:16 -0500, Margus Ramst <mar### [at] peakeduee> wrote:
>The macro works, but it's slow: a mere 3X3X3 division (3*3*3*8=216 traces)
>takes ab. 1 min 30 to parse on my 486DX120. The first and foremost reason is my
>proximity checking method.
>So the question is: how can 3D proximity checking be done quicker? Would I need
>to use an entirely different subdivision method (marching cubes or something)?

You could use a kd-tree, but if you manage to implement one in POV 
code - particularly one that handles dynamic insertions gracefully -
you're a better man than I.  I have a couple questions on your use of
trace(), though.  First, what do you do if you have two intersections
along one traced ray?  Second, wouldn't it be faster to just trace the
four corner-to-corner rays, especially in the cases where it doesn't 
hit anything?  

Do you currently ignore cells whose closest point is further than
the closest one found so far?  For example, if the point you're
thinking about adding is at the far left edge of the cell and 
you've already found one at the right edge of the cell to the
left, you can certainly ignore the three (nine) cells to the 
right completely.  Ditto if those cells are further than the
minimum distance to make then "too close."  Once you've selected
a cell, and assuming you haven't changed your trace code to use 
4 rays instead of 8, you can prequalify individual points in the 
same way.  This might add more code to be parsed that makes it 
not worthwhile, however.  

Also, make sure you break out of the loop when you find a 
single point within the "too close" range rather than 
continuing to look for more, and make sure you check cells 
in an optimal order (current one first, then face-adjacent 
cells, then edge-adjacent cells, then corner-adjacent cells.)  

It might help to break your code up into macros, with a single 
macro call inside each #if...#end, so POV doesn't have to 
spend so much time parsing and skipping the (possibly extensive) 
code inside the false conditionals each time through the loop.  
This only works, of course, if you expect the conditionals to 
be usually false, and if they have lots of code inside, because 
invoking a macro is a bit of extra work.  In case you don't 
follow what I'm saying, here's an example:

    #macro My_Macro( xx, yy, zz ) 
       ... lots of code ...
    #end
    
    #if ( usually_false_condition ) 
       My_Macro( xx, yy, zz )
    #end
 
is probably faster than

    #if ( usually_false_condition ) 
        ... lots of code ...
    #end

if it has to be skipped more than a couple of times.

Post a reply to this message

Ron Parker wrote:
> 
> You could use a kd-tree, but if you manage to implement one in POV
> code - particularly one that handles dynamic insertions gracefully -
> you're a better man than I. I have a couple questions on your use of
> trace(), though.  First, what do you do if you have two intersections
> along one traced ray?

Each axis in each cell is only tested once. If an intersection is found a
proximity test is conducted; the script then moves on to the next axis/cell
whether or not a light was created. I think this is sufficient: if more
precision is required, a higher division rate should be set.

> Second, wouldn't it be faster to just trace the
> four corner-to-corner rays, especially in the cases where it doesn't
> hit anything?

I'm not sure. The problem is that this would create errors in extreme cases (for
ex. tracing a box), when the object is tangent to some cells, but doesn't
intersect them. Secondly, I would need to allow 2 light sources per axis (for
ex. to get symmetrical distribution on a cylinder that is divided only 1X along
the length) - or double the division rate.
My current method allows only 1 light per axis. The coordinates of all light
sources are stored in an array (array[Axis][CellX][CellY][CellZ]); so it is easy
to fetch the coordinates of a light on a particular axis in a particular cell
and compare it with the current intersection point. With 2 lights possible on an
axis, the array would need to be given another dimension or something... I need
to think about this.

> 
> Do you currently ignore cells whose closest point is further than
> the closest one found so far?

No. But if I'm not mistaken, I would still have to check the distance between
the current intersection point and the closest point of the adjacent cell? If
so, this would give me no advantage.

> Ditto if those cells are further than the
> minimum distance to make then "too close."

The cells are not necessarily cube-shaped, this makes things more difficult.

Btw, I'll check tomorrow as to what is a "kd-tree" - and if I can make it handle
those dynamic intersections gracefully in POV code ;)

Thanks
Margus

Post a reply to this message

On Thu, 19 Nov 1998 03:42:40 +0200, Margus Ramst <mar### [at] peakeduee> wrote:
>> Do you currently ignore cells whose closest point is further than
>> the closest one found so far?
>
>No. But if I'm not mistaken, I would still have to check the distance between
>the current intersection point and the closest point of the adjacent cell? If
>so, this would give me no advantage.

Except that the closest point for a face-adjacent cell will always 
have two coordinates the same as the current intersection point, so 
you don't need to use vlength.  For the other 20 cells you'd have
to compute a distance anyway, so you might not save anything unless
one of those cells has more than one or two light sources in it or
unless the difference on a single axis is already larger than the
bound.  For example, if you can throw away a face-adjacent cell,
you can automatically throw away 8 more cells.  For the 2d case:

+---+---+---+
|   |   | X |
|   |   |   |
+---+---+---+
|   |A  | * |
|   | B |   |
+---+---+---+
|   |   | X |
|   |   |   |
+---+---+---+

If you have an intersection at A, and the closest point you've found 
is at B, you don't have to test the cell marked with a *, because it
is further away than your closest point so far.  Since you don't need 
to test it, you also don't need to test the two marked with X's.  The 
3d case is even better, because you can throw away 9 cells with a 
single floating-point comparison.

Post a reply to this message

You're right, of course. I didn't see the advantage at first. It might have a
drawback, but I'm not sure yet, so I won't discuss this.
The case whether or not a cell contains light sources is already determined with
a simple boolean test; also, I dont't test all 26 adjacent cells, only 13 at the
most (those that have already been processed). The rest are empty anyway.
Btw. I checked out the kd-tree... Not that I'm math-oriented enough to
comprehend the method, but I got the impression that the it is optimal for very
large data sets; I currently have to deal with somewhere around 100-500 points,
so the computational overhead might not be worth it - even if I could implemet
it.

Thanks
Margus

Ron Parker wrote:
> 
> Except that the closest point for a face-adjacent cell will always
> have two coordinates the same as the current intersection point, so
> you don't need to use vlength.  For the other 20 cells you'd have
> to compute a distance anyway, so you might not save anything unless
> one of those cells has more than one or two light sources in it or
> unless the difference on a single axis is already larger than the
> bound.  For example, if you can throw away a face-adjacent cell,
> you can automatically throw away 8 more cells.

Post a reply to this message