Introduction

Constructive Solid Geometry (CSG) is a methodology by which complex shapes can be made using simple geometric models. These models are defined in an unambiguous manner and are known as the primitives.

Simple primitives like a cuboid, sphere, cylinder etc are combined to form a complex shape which may not have otherwise seemed feasible. Treating each primitive seperately and creating simply algorithms for it and then integrating these algos to form a complete rendering package posed a very elegant and attractive problem to us. The whole concept seemed ingenous and also tempting to be tested.

In our project we have used a self-derived method very similar to the traditional ray-tracing algorithm. Primitives are generated using simple comands on which operations are performed. The operations manipulate these primitves in 3-D Euclidean space. The primitves can be translated, rotated, scaled and also boolean operations - intersection, union, difference - can be performed on them.

Methodology

A primitve is declared in a conceptual reference frame which makes it easier for the user to work in this conceptual frame and later to place it in the world co-ordinate system (wcs). Our whole input is read from a text file and is parsed into a tree. Each leaf node represents a primitve with a transformation matrix in-built. On combining 2 nodes with a boolean operation we get a new node that has these 2 nodes as children.

We define a screen by its origin at a particular point in the wcs. The x and y dimensions of the screen are defined in terms of the vectors U and V (Look at fig 1). The objective is to display all the pixels on the defined screen. So for each pixel on screen we shoot a ray in a particular direction which is given by the camera view direction vector. These rays are tracked and if they "hit" an object, the point belonging to the surface hit is displayed with the surface color shade which has been pre-defined.

Calculating the pt. of intersections of a ray with a set of complicated objects may prove very computationally intensive and difficult. To make the structure more elegant and simpler we percolate the ray down the parse tree until it is transformed to the conceptual co-ordinate axis of each of the primitives (the leaf nodes) that were used to define the complex object. Now the task boils down to finding whether an arbitrary ray intersects a primitve in its conceptual referance frame. If the intersection exists, the distance from the source to the pt. of intersection (which we call the near_distance) is noted and also the length of the ray (or span) that remains inside the body of the primitive (which we simply call the length).

Then the near_distance and the length of the individual primitives are compared and the appropriate action taken (depending on the operations). For example if we have a union of a cube and sphere, a ray shall be directed and the individual near_distances are compared and the surface representing the small near_distance is rendered on the screen (at the particular pixel)

It can be seen from the above figure that all the intersections of a ray with primitves boil down to finding the intersection of a directed vector with the primitive (in question) placed in a reference frame such that the orientation of the primitive with this ref. frame makes it easier to compute the arithmetic calculations involved .

About the software

The program was coded in c++.C++ being an object oriented programming language, made it easier for us to break the code into classes. The parse tree could be broken up into nodes, where the leaf nodes were representing the three primitives (sphere, box & cylinder) and the upper nodes were the operator nodes which ran the boolean operations on the children nodes.

It excepts input from a text file, specifying the object as a collection of primitives and operations, using a language which we have defined . The The COCO/R parser generator was used to make the parser to read the input and check it for trivial syntatical errors. The software assumes that an intelligent user is utilising it and hence does not check for user input errors.

To run the program one has to create an input text file of the various shapes he/she would like to create. The layout of the input text file is explained below. The next step is to simply execute the program giving the input text file as a parameter.

Getting comfortable with the software

The screen was defined at the point (0,0,10) i.e 10 units from the origin along the Z axis in the wcs. The camera view was defined along the negative Z axis. These parameters can be easily changed. The software takes in a text file which looks like the following:

---

/* yes we can have comments imbedded in the input file */

obj1 = sphere<3f> /* define a sphere with radius 3*/
obj2 = cylinder<2f,1f> translate<2f,0f,0f>; /* define and translate a cylinder */
obj3 = box<2f,2f,2f> rotate_y<45f>; rotate_x<20f>; rotate_z<-20f>; /* define a box and rotate it along the x,y and z axis by 45, 20 and -20(340) degrees respectively */
draw = translate <1f,1f,1f>; /* draw the union of the box and cylinder translated by one unit along all axis */


---

As you can figure out each primitive is defined as an "obj" along with a number. The parameters are defined in angular braces ("<" and ">").Each operation ends with a ";". All lengths and degrees are given in floats (that is why we need the letter f at the end).
Some sample files and output are shown below:

Finally more complicated objects can be generated using boolean operations. The following is a modelling of a chair.

Center of Mass feature

This program also calculates the center of mass of the whole composite body in the process of rendering it and displays it with a white circle at the end. The underlying assumption was that all the bodies defined are of the same density. This was necessary to simplify the calculations. Even if this is not the case, the whole body can be broken down into subsections of similar density and rendered part by part using our program. The collection of these points could then be effectively used to calculate mass properties of the whole object.

Conclusion

The cross lines that you notice on the output is not a program error but is caused by the Xlib graphics package while transforming the co-ordinates from the virtual screen to that of the physical screen. This may be removed by some hacking but we never went into those details.

The software has a lot of room for improvement. Essential features provided in a standard graphics package can be incorporated. A light source can be set, shading can improve the apperance of objects and also we can let the user view the objects in perspective mode. Also subtle but vital features like texture can be added. Shadows, reflections can also be incorporated since we have used the ray tracing algorithm.

References

• Computer Graphics
  - Foley & Van Dam
• "Combinatorial Solid Geometry, Boundary Representaations, and Non-Manifold Geometry"
  - Michael John Muuss & Lee A. Butler
• Some literature on CSG and ray tracing on the net