#417 RPN booleval

[Vasco Alexandre da Silva Costa]

I was looking at rt_booleval() in src/librt/bool.c. That code was quite hairy and hard to debug or maintain. So I took a stab at rewriting it.
So I wrote something which basically recompiles struct tree from its infix representation of a binary tree with pointers into a postfix (RPN) array.
This new representation uses a lot less memory (64-bits per tree node) and its traversal should be more cache coherent. It does not have all the data in the regular tree. It is a compiled optimized format with the data which is needed for rt_boolfinal: a critical part of the rendering algorithm.

I did some tests with some scenes, e.g. operators.g, to check how it worked. The new code is usually slightly faster at ray-tracing than the old one. It does require some pre-processing to build the optimized list but that is done only once on prep.

This code is much more maintainable and would even be trivial to extend to support XOR (maybe 7 lines of extra code) in the future. Currently supported operations include UNION, INTERSECT, DIFFERENCE, SOLID.

I couldn't find a scene with XOR in the .g in share/db to test. All scenes I tested seemed to work.

[Vasco Alexandre da Silva Costa]

Use the bitwise instead of the logical operators to perform the ops themselves. May be faster on some architectures. Haven't checked the assembly.

Looking at src/libged/put_comb.c XOR is not even supported in the "Combination Editor" from mged. Can't even input it. So I'm scratching my head here figuring out why it is still in the code? Legacy reasons?

Improved to use the RPN tree in every other processing done in src/librt/bool.c.

Added support for UOP_XOR in the actual processing. The infix to rpn tree compiler (rt_tree_rpn) still doesn't recognize XOR but this should be easy to add if you want to.

Rewrote rt_solid_bitfinder to not use stack based traversal of the infix tree. Just do a linear traversal on the rpn linearized tree array since we only to update the solids. Saves a whole bunch of memory.

Added printing function of RPN bool tree for optional debug output.

[Vasco Alexandre da Silva Costa]

• Updated the patch against SVN trunk r69006.
• Sped up 'bool_max_raynum' and 'bool_test_tree' functions.
• Added support for NOP and XOR operators.
• Fixed stack bounds overrun bug.
• Fixed unitialized memory bugs.