Cad Cam Development



13 steps to perform CSG Tree Raycasting

CSG made out of sum of 4 Spheres

CSG made out of sum of 4 Spheres

There are numerous examples of normal ray casting. Almost everyone has heard about CSG. Each computer graphics book has printed a csg ray traced image. Performing Constructive Solid Geometrical operations is crucial in CAD/CAM and almost in every computer graphics application. There are lots of real-life examples where artists use it. Every computer graphics programmer should know how to code CSG raycasting and therefore I’m going to explain you some main ideas on csg ray casting that will help you to develop your own code. This article covers only implicit representation of surfaces does not present any knowledge about parametrical.

  1. CSG can be implemented either as a raycasting or modified Z-Buffer based algorithms. Both were subjects of research and lots of articles are available in internet
  2. CSG ray casting is computational expensive because you need to compute CSG node interval for every pixel in a screen, so you had better stick to proven programming rules and be very careful while programming.  You have to provide efficient data structures for CSG node and csg tree. I’ve chosen binary tree for CSG tree that is stored in table, short struct for storing single CSG node and some several auxiliary structs to manage additional information like Ray, Interval, Sphere, bounding box. I’ve chosen table for storing tree because my intention was to provide CUDA compatible code and it is easier to port a table to GPU rather than normal pointer-based binary struct. CUDA compatibility forced me to program rather in C than in C++. Following points are going to be executed for every planar point that describes screen coordinates, so that’s a lot.
  3. You’ve to perform some pre-render computations so that your rendering could be faster. Firstly, assign a bounding box to each csg node. You start from leafs of CSG tree and assign them an according sphere bounding box value. Then you move up for next upper levels so that you reach a root. While moving to root, you have to update each csg tree bounding box according to csg boolean operation that is stored in the node. So this is the first time you perform tree traversal. If you don’t remember tree traversal algorithms check it on wikipedia. It’s important to have bounding box in a root of csg tree so that it can be used in following steps.
  4. You start performing ray casting. Convert the screen coordinates to world coordinates and than check, whether a ray is inside root’s bounding box you’ve computed previously. If not, than move on the other screen coordinates. Otherwise, you need to traverse tree once again so that accurate values of csg intersections can be evaluated. This is the most important piece of code in this program, so do it carefully. See next points
  5. You start your second tree traversal from tree leafs and move towards root (just as it was written in point 4). While moving upwards, you check the values of current ray and current interval intersections. You’ll have 0 intersections at first in all leafs. A ray can be intersected with a leaf (sphere, because spheres are only in leafs, and aboves are only intervals) either once or never.  If you are in nodes other than leafs, perform csg boolean operation on the child set of parent. This means, that while traversing up the tree, you always work with a set of intervals that are stored in csg tree nodes and each time you visit a node you perform intersection evaluation and csg boolean operation evaluation. If you are in leaf, the size of this set is either 0 or 1, because either there will be intersections with ray, or no. So you call a function/procedure on set of intervals if only there any intervals on child nodes.

    CSG Tree consisting of 3 spheres

  6. Don’t forget to check ray intersection with sphere bounding box just before the accurate algorithm intersection call. This can save you some CPU cycles. Mine Ray-intersection algorithm is like in GPU gems and it tooks about 40 cycles to check the accurate values and ray- bounding box takes only about 6 cycles. So it’s worth checking and pruning! Choose geometrical algorithm for intersection rather than quadric and matrix based. Matrix based sphere representation will impose some problems on CUDA compatibility issues and will increase single size of Sphere structure (you have to store 16 float to represent sphere). If you store only x,y,z of center of sphere and radius, you use 4 times smaller space. The geometrical intersection algorithm is cheaper than matrix based intersection evaluation (40 CPU cycles instead of about 80).
  7. There will be some interval set sorting required, so choose proper algorithm depending on your needs (insertion sort or merge sort) if you don’t want to store intervals in each csg node in a range tree or interval tree.
  8. You can easily handle sum and intersection interval operation in linear time. Difference can be handled in logarithm time complexity, but this will require developing interval tree and storing it in each csg node. I personally use single table-based list to store intervals in the node so it has to be sorted in z minimal intersection value in ascending order to provide good results.  Sum is the easiest operation: you simply join the list from left child and right one and than perform sorting on it and you’re done. Intersection is similar: firstly get the lowest and biggest z value from  left child, and according from right child and than while joining lists from left child and right child you need to adjust intervals to the min/max values you’ve got from left child and right child. At the and sort the parent’s list and you’re done. The simplest difference operation takes place in n*n, n- number of intervals. You have to perform difference operation on each interval form left and right child. That’s how you can deal with csg operations on intervals. There are 16 situations you have to think about to handle interval boolean operation well. See some photo below.

    Possible CSG nodes settings

    Possible CSG nodes settings

  9. Rendering and shading. At this stage you’ve got an anwser on the following question: does my ray intersects csg tree, and which csg interval lie closest to ray position. Interval should contain information about sphere, so you can easily begin with shading. Shade objects as in normal raytrace/raycast, Phong shading provide good results and is nice and easy to program.

    Raycast of single sphere with Phong lightening

    Raycast of CSG Tree consisting of sum of two spheres

  10. If you render very big CSG trees, start considering developing algorithms like csg tree normalization like described in article: Near Real-Time csg rendering using tree normalization and geometric pruning. This will improve rendering time.

    Raycast of CSG Tree consisting out of three spheres

  11. Compilers optimalizations and memory management. Some memory allocation problem may appear. The will be a striking difference between debug version and release version. If you get a black screen(or equivalently nothing will appear) probably you use static memory allocations which is differently handled in debug and heavily optimized release version. So you should be aware about what optimizations you turn on and how you manage memory. I suggest you using dynamic memory allocations as much as possible. Check also some articles on msdn (if you’re coding using VS) that refers to Profile Guided Optimizations and related. Note that PGO cannot be used with OpenMP. This knowledge is substantial to provide your application extra fps. Well-written csg raycast should get about 30-40 fps on about 10 nodes on CPU and about 10000 fps on CUDA.
  12. Numerical methods and computations considerations. Note that you can easily get quadratic equations. So solve them in a correct numerical method. This means you had better use Viète’s formulas rather than traditional descriminant method that was teached in school and is described here. This is obligatory because you should avoid computing square roots due to their inaccuracy. Accurate computations are  extremely important in computing CSG intervals – because slight difference in computing interval’s zmin and zmax can give you different geometrical interpretation.  You should also compare doubles correctly and perform other mathematical operations more carefully than normal. Please take some CPU data representation errors into account and some operations like divisions and adjust your code to it. For instance write this code:
  13. double a,b;
    //perform operations on a and b
    //equals
    if( abs(a-b)<EPSILON)
    {
    //numbers are equal
    }
    

    instead of this:

    double a,b;
    //perform operations on a and b
    if(a==b){
    //numbers are equal
    }
    
  14. Rendering considerations
  15. Provide efficient rednering for your CSG tree. Personally, I’m using C OpenGL and Pixel Buffer Object to render code. If you’re using managed languages like C# draw on bitmap and once it’s completed flush to screen. Avoid drawing HDC contex and flushing simgle bits onto the screen due to performance reason. Good idea is to provide adaptive rendering. In first step you sample one pixel, for example the upper-left corner, you get a color of that pixel and colour all the screen pixels in that colour. Next you divide your screen into 4 equal parts, perform colour sampling on all of quarters and draw all pixels in a single quarter. You do it once you sampled single pixel. This method provides good results and was widely used in web browsers if the internet was slower than today.

  16. Source code and executable
  17. The original source code which solved all the problems I’ve been writing above was lost so I’ve put some previous version and the source code which you can build yourself is code that does not cover all the topics from above and is slower. Nevertheless is worth digging into if want to start your own CSG implicit tree rendering. You can download it from here. You can start modifying this code without major problems. The code has been produced in C using VS2010. There is a run.bat file so that the proper arguments to executable file could be provided. There are two files: the first one describing the CSG Tree made out of spheres and the second one describing lights. Phong shading has been used.

Advertisements

Trackbacks & Pingbacks

Comments

  1. * Paul, Le TEXIER says:

    Please could you send me &| repost the CSGRenderer archive.

    Download not available
    The following download is not available:

    http://rapidshare.com/files/444131448/CSGRenderer.zip 0 KB

    Is there a LINUX version ?
    Have you found the lost archive (with all the problems solved) ?

    Thanks

    | Reply Posted 6 years, 6 months ago


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: