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