1 #ifndef ConstructiveSolidGeometry_HXX
2 #define ConstructiveSolidGeometry_HXX
3
4 #include "Scene.hxx"
5 #include "EyeLightShader.hxx"
6
7 // valid operators
8 typedef enum operators
9 {
10 NONE,
11 DIFFERENCE,
12 UNION,
13 INTERSECT
14 };
15
16 /**
17 * data structure: binary tree
18 * each node can have :
19 - either zero or two children
20 - either an operator or a primitive
21 */
22 struct Node
23 {
24 operators op;
25 Node* left; // left child node
26 Node* right; // right child node
27 Primitive *primitive;
28 };
29
30 class CSG : public Primitive
31 {
32 private:
33 // save the root node
34 Node* fileNode;
35 // and the filename, the image should be written in
36 std::string output;
37
38 /**
39 * simple debug output
40 */
41 void print_out(Node* node)
42 {
43 std::cout << "Operator: " << node->op << std::endl;
44
45 if (node->left)
46 print_out(node->left);
47 if (node->right)
48 print_out(node->right);
49 }
50
51 /**
52 * move along the whole tree
53 */
54 void tree_shader(Node* node, Shader* shader)
55 {
56 if (node->primitive)
57 node->primitive->Primitive::setShader(shader);
58
59 if (node->left)
60 tree_shader(node->left,shader);
61 if (node->right)
62 tree_shader(node->right,shader);
63 }
64
65 /** Goldfeather Algorithmus
66 Construct a tree in normal form with the tree constructed from the file.
67 => intersection operators and subtraction operator has
68 * a left subtree which contains no union operators
69 * a right subtree which is a primitive
70 */
71 void Normalize(Node* node)
72 {
73 // leaf node
74 if (node->op == NONE)
75 return;
76
77 operators op = node->op;
78 operators right_op = node->right->op;
79 operators left_op = node->left->op;
80
81 Node save_node = *node;
82
83 // rule 1,4,6
84 if ( ( op == DIFFERENCE && right_op == UNION)
85 || (op == INTERSECT && ( right_op == INTERSECT || right_op == DIFFERENCE)) )
86 {
87 if (right_op == DIFFERENCE)
88 node->op = DIFFERENCE;
89
90 node->right = save_node.right->right;
91
92 Node* new_node = new Node;
93 new_node->left = save_node.left;
94 new_node->right = save_node.right->left;
95 new_node->primitive = NULL;
96 new_node->op = op;
97
98 node->left = new_node;
99 }
100
101 // rule 2,3,5
102 if ( ( op == INTERSECT && right_op == UNION )
103 || ( op == DIFFERENCE && ( right_op == INTERSECT || right_op == DIFFERENCE )) )
104 {
105 node->op = UNION;
106
107 Node* new_node_left = new Node;
108 new_node_left->left = save_node.left;
109 new_node_left->right = save_node.right->left;
110 new_node_left->primitive = NULL;
111 new_node_left->op = op;
112
113 Node* new_node_right = new Node;
114 new_node_right->left = save_node.left;
115 new_node_right->right = save_node.right->right;
116 new_node_right->primitive = NULL;
117 if (right_op == INTERSECT)
118 new_node_right->op = DIFFERENCE;
119 else new_node_right->op = INTERSECT;
120
121 node->left = new_node_left;
122 node->right = new_node_right;
123 }
124
125 // rule 7
126 if ( op == INTERSECT && left_op == DIFFERENCE )
127 {
128 node->op = DIFFERENCE;
129
130 node->right = save_node.left->right;
131
132 Node* new_node = new Node;
133 new_node->left = save_node.left->left;
134 new_node->right = save_node.right;
135 new_node->primitive = NULL;
136 new_node->op = INTERSECT;
137
138 node->left = new_node;
139 }
140
141 // rule 8, 9
142 if ( ( op == DIFFERENCE && left_op == UNION )
143 || ( op == INTERSECT && left_op == UNION ) )
144 {
145 node->op = UNION;
146
147 Node* new_node_left = new Node;
148 new_node_left->left = save_node.left->left;
149 new_node_left->right = save_node.right;
150 new_node_left->primitive = NULL;
151 new_node_left->op = op;
152
153 Node* new_node_right = new Node;
154 new_node_right->left = save_node.left->right;
155 new_node_right->right = save_node.right;
156 new_node_right->primitive = NULL;
157 new_node_right->op = op;
158
159 node->left = new_node_left;
160 node->right = new_node_right;
161 }
162
163 Normalize(node->right);
164 Normalize(node->left);
165 }
166
167 /**
168 * intersect ray with tree
169 */
170 bool NodeIntersect( Node* node, Ray &ray )
171 {
172 // if node is a leaf node, then intersect the contained primary with the ray
173 if (node->primitive)
174 return (node->primitive)->Intersect(ray);
175
176 /**
177 * we must test wheter the ray hits the two objects or not
178 * copy ray, so that original ray is preserved
179 */
180 Ray ray1 = ray;
181 Ray ray2 = ray;
182
183 /**
184 * for each point P: first check wheter P is inside or outside a given primitive
185 * parity == 1 iff P is inside the primitive, and 0 otherwise
186 * and compute the distance from ray origin to object 1 and respectively object 2
187 */
188 bool parity1 = NodeIntersect(node->left, ray1);
189 float entry_obj1 = ray1.t;
190
191 bool parity2 = NodeIntersect(node->right, ray2);
192 float entry_obj2 = ray2.t;
193
194 switch (node->op)
195 {
196 // do nothing if there is no operator
197 case NONE:
198 break;
199
200 /**
201 * for the union operator, check whether the ray hits one of the objects
202 * in case at least one object is hit, check which one is hit first
203 * in order to preserve the shader
204 */
205 case UNION:
206 if (parity1 || parity2)
207 if (entry_obj1 <= entry_obj2)
208 ray = ray1;
209 else ray = ray2;
210
211 return (parity1 || parity2);
212
213 // for the intersection operator:
214 case INTERSECT:
215
216 // ray must hit both objects
217 if ( !parity1 || !parity2 )
218 return false;
219
220 // determine shader (which object does the ray hit first?)
221 if ( entry_obj1 < entry_obj2 )
222 ray = ray2;
223 else ray = ray1;
224
225 return true;
226
227 // for the difference operator:
228 case DIFFERENCE:
229 {
230 // the ray must hit the first object
231 if ( ! parity1 )
232 return false;
233
234 // in case the first object is in front of the second one
235 if (entry_obj1 < entry_obj2)
236 {
237 ray = ray1;
238 return true;
239 }
240
241 // for computation of exit distance of ray through object 1
242 Ray help = ray;
243 help.org = ray.org + (ray1.t + Epsilon) * ray.dir;
244 help.hit = NULL;
245 help.t = Infinity;
246
247 // for computation of exit distance of ray through object 2
248 Ray copy = help;
249 copy.org = ray.org + (ray2.t + Epsilon) * ray.dir;
250
251 if (!NodeIntersect( node->left, help ))
252 return false;
253
254 if (!NodeIntersect( node->right, copy ))
255 return false;
256
257 float exit_obj1 = entry_obj1 + help.t;
258 float exit_obj2 = entry_obj2 + copy.t;
259
260 /**
261 * if the ray leaves object 1 before object 2
262 * => object 1 lies inside object 2
263 */
264 if (exit_obj1 <= exit_obj2 )
265 return false;
266 else {
267 // otherwise the ray covers the distance to the exit point of the second object
268 if (exit_obj2 < entry_obj1 )
269 {
270 ray = ray1;
271 return true;
272 }
273
274 ray = ray2;
275 ray.t = exit_obj2;
276 return true;
277 }
278 }
279
280 default:
281 return false;
282 }
283
284 return false;
285 }
286
287 /**
288 * Create leaf node with primitive
289 */
290 Node* PrimitiveLeaf ( Primitive* p )
291 {
292 Node* new_node = new Node;
293 new_node->op = NONE;
294 new_node->left = NULL;
295 new_node->right = NULL;
296 new_node->primitive = p;
297 return new_node;
298 }
299
300 /**
301 * File format: Reverse Polish Notation
302 * all primitives are shaded automatically with the EyeLightShader
303 */
304 void CreateTree(char *fileName, Scene *my_scene)
305 {
306 std::vector<Node*> list;
307 output = "output.ppm";
308
309 std::cout << "Reading CSG-file : " << fileName << std::endl;
310 std::ifstream ifile(fileName);
311
312 if (!ifile)
313 {
314 std::cout << "File " << fileName << " not found!" << std::endl;
315 exit(1);
316 }
317
318 while(!ifile.eof())
319 {
320 // get line
321 std::string curLine;
322 std::getline(ifile, curLine);
323
324 // read type of the line
325 std::istringstream issLine(curLine);
326 std::string lineType;
327 issLine >> std::ws >> lineType;
328
329 /**
330 * get sphere
331 * file format: Vec3f midpoint, float radius, Vec3f color
332 */
333 if (lineType == "sphere")
334 {
335 float x,y,z; // coordinates of center
336 float r; // radius
337 float c1,c2,c3; // color
338
339 issLine >> x >> y >> z;
340 issLine >> r;
341 issLine >> c1 >> c2 >> c3;
342
343 Shader* shader = new EyeLightShader ( my_scene, Vec3f(c1,c2,c3) );
344 Primitive* p = new Sphere (Vec3f(x,y,z), r);
345 p->setShader(shader);
346
347 /**
348 * create leaf node
349 */
350 Node* new_node = PrimitiveLeaf(p);
351 list.push_back(new_node);
352 }
353
354 /**
355 * get box
356 * file format: Vec3f min, Vec3f max, Vec3f color
357 */
358 else if (lineType == "box")
359 {
360 Vec3f min, max; // min and max-vectors
361 float x,y,z; // coordinates
362 float c1,c2,c3; // color
363
364 issLine >> x >> y >> z;
365 min = Vec3f(x,y,z);
366 issLine >> x >> y >> z;
367 max = Vec3f(x,y,z);
368 issLine >> c1 >> c2 >> c3;
369
370 Shader* shader = new EyeLightShader ( my_scene, Vec3f(c1,c2,c3) );
371 Primitive* p = new AABB (min, max);
372 p->setShader(shader);
373
374 /**
375 * create leaf node
376 */
377 Node* new_node = PrimitiveLeaf(p);
378 list.push_back(new_node);
379 }
380
381 /**
382 * get cone
383 * file format: Vec3f center, float radius, float height, Vec3f color
384 */
385 else if (lineType == "cone")
386 {
387 Vec3f center; // center
388 float radius; // radius
389 float height; // height
390 float c1,c2,c3; // color
391 float x,y,z; // coordinates
392
393 issLine >> x >> y >> z;
394 center = Vec3f(x,y,z);
395 issLine >> radius;
396 issLine >> height;
397 issLine >> c1 >> c2 >> c3;
398
399 Shader* shader = new EyeLightShader ( my_scene, Vec3f(c1,c2,c3) );
400 Primitive* p = new Cone( center, radius, height );
401 p->setShader(shader);
402
403 /**
404 * create leaf node
405 */
406 Node* new_node = PrimitiveLeaf(p);
407 list.push_back(new_node);
408 }
409
410 /**
411 * get infinite plane
412 * file format: Vec3f point, Vec3f normal
413 */
414 else if (lineType == "plane")
415 {
416 Vec3f point; // point in the plane
417 Vec3f normal; // normal vector of plane
418 float c1,c2,c3; // color
419 float x,y,z; // coordinates
420
421 issLine >> x >> y >> z;
422 point = Vec3f(x,y,z);
423 issLine >> x >> y >> z;
424 normal = Vec3f(x,y,z);
425 issLine >> c1 >> c2 >> c3;
426
427 Shader* shader = new EyeLightShader ( my_scene, Vec3f(c1,c2,c3) );
428 Primitive* p = new InfinitePlane( point, normal );
429 p->setShader(shader);
430
431 /**
432 * create leaf node
433 */
434 Node* new_node = PrimitiveLeaf(p);
435 list.push_back(new_node);
436 }
437
438 /**
439 * get axis aligned cylinder
440 * file format: Vec3f center, align alignment, float radius, float height, Vec3f color
441 */
442 else if (lineType == "cylinder")
443 {
444 float x,y,z; // coordinates of center
445 std::string get_align; // alignment
446 float h; // height
447 float r; // radius
448 float c1,c2,c3; // color
449
450 issLine >> x >> y >> z;
451 issLine >> get_align;
452
453 enum align alignment;
454 if (get_align.compare("xAxis") == 0)
455 alignment = xAxis;
456 else if (get_align.compare("yAxis") == 0)
457 alignment = yAxis;
458 else if (get_align.compare("zAxis") == 0)
459 alignment = zAxis;
460 else { std::cerr << "Unknown alignment" << std::endl;
461 exit(1);
462 }
463
464 issLine >> r;
465 issLine >> h;
466 issLine >> c1 >> c2 >> c3;
467
468 Shader* shader = new EyeLightShader ( my_scene, Vec3f(c1,c2,c3) );
469 Primitive* p = new Cylinder (Vec3f(x,y,z), alignment, r, h);
470 p->setShader(shader);
471
472 /**
473 * create leaf node
474 */
475 Node* new_node = PrimitiveLeaf( p );
476 list.push_back(new_node);
477 }
478
479 /**
480 * get operator
481 * file format: operator {UNION, DIFFERENCE, INTERSECT}
482 */
483 else if (lineType == "operator")
484 {
485 // assert: a binary operator needs two operands
486 if ( list.size() < 2 )
487 {
488 std::cerr << "Binary operator expects two operands." << std::endl;
489 exit(-1);
490 }
491
492 std::string get_op;
493 issLine >> get_op;
494
495 operators op;
496 if (get_op.compare("union") == 0)
497 op = UNION;
498 else if (get_op.compare("difference") == 0)
499 op = DIFFERENCE;
500 else if (get_op.compare("intersect") == 0)
501 op = INTERSECT;
502 else { std::cerr << "Unknown operator" << std::endl;
503 exit(1);
504 }
505
506 /**
507 * create a new node, where the operator is saved in
508 * and which has as children the last two operands read in
509 */
510 Node* new_node = new Node;
511 new_node->op = op;
512 new_node->left = list[ list.size() - 2 ];
513 new_node->right = list[ list.size() - 1 ];
514 list.pop_back();
515 list.pop_back();
516 new_node->primitive = NULL;
517
518 list.push_back(new_node);
519 }
520
521 /**
522 * in case a special filename is stated, save it
523 * otherwise render the image to "output.ppm"
524 */
525 else if (lineType == "filename")
526 {
527 issLine >> std::ws >> output;
528 }
529 }
530
531 /**
532 * at the end, we expect exact one operand in the list,
533 * namely the whole constructed CSG tree
534 */
535 if (list.size() == 1)
536 fileNode = list[0];
537 else {
538 std::cerr << "Illegal operation \n";
539 exit(1);
540 }
541
542 // std::cout << "Start normalization of CSG tree" << std::endl;
543 // Normalize(fileNode);
544 }
545
546 /**
547 * compute the overlapped part of the subtree's bounding box
548 * therefore get the bounding box of both subtrees
549 * and then compute the min and max vector by taking
550 * the max entries of the min vector
551 * the min entries of the max vector
552 */
553 Box* BoundsIntersection ( Node* node1, Node* node2 )
554 {
555 Box* bb1 = new Box();
556 Box* bb2 = new Box();
557 CalcBoundsOfTree( bb1, node1 );
558 CalcBoundsOfTree( bb2, node2 );
559
560 Vec3f min = Max( (*bb1).min, (*bb2).min );
561 Vec3f max = Min( (*bb1).max, (*bb2).max );
562
563 Box* BoundingBox = new Box();
564 BoundingBox->Extend( min );
565 BoundingBox->Extend( max );
566 return BoundingBox;
567 }
568
569 /**
570 * compute the bounding box of the CSG Tree
571 */
572 void CalcBoundsOfTree( Box* bb, Node* node)
573 {
574 /** for a primitive:
575 take the bounding box of this primitive
576 */
577 if (node->primitive)
578 bb->Extend ( (node->primitive)->GetBounds() );
579
580 /** for the difference operator:
581 the bounding box of the left subtree is sufficient
582 since we want everything of the left object except the overlapped part with the right object
583 */
584 if (node->op == DIFFERENCE)
585 CalcBoundsOfTree(bb, node->left);
586
587 /** for the union operator:
588 we need the bounding box of the right and the left subtree
589 */
590 else if (node->op == UNION)
591 {
592 CalcBoundsOfTree(bb, node->left);
593 CalcBoundsOfTree(bb, node->right);
594 }
595
596 /** for the intersect operator:
597 compute the overlapped part of the subtree's bounding box
598 */
599 else if (node->op == INTERSECT)
600 {
601 Box* BoundingBox = new Box();
602 BoundingBox = BoundsIntersection( node->left, node->right );
603 bb->Extend( *BoundingBox );
604 }
605 }
606
607 public:
608 /**
609 * constructor: create the CSG tree out of the given file
610 */
611 CSG( char *fileName, Scene *scene )
612 {
613 CreateTree(fileName,scene);
614 };
615
616 virtual ~CSG()
617 {};
618
619 /**
620 * intersect the object with a ray, do this recursively in NodeIntersect
621 */
622 virtual bool Intersect( Ray &ray )
623 {
624 return NodeIntersect(fileNode, ray);
625 }
626
627 /**
628 * simply take the normal of the hit primitive
629 */
630 virtual Vec3f GetNormal(Ray &ray)
631 {
632 return ray.hit->GetNormal(ray);
633 }
634
635 /**
636 * calculate the bounding box of the CSG tree, do this recursively in CalcBoundsOfTree
637 */
638 virtual Box CalcBounds()
639 {
640 Box BoundingBox;
641 CalcBoundsOfTree( &BoundingBox, fileNode );
642
643 return BoundingBox;
644 }
645
646 /**
647 * set the same shader to all primitives in the CSG tree
648 */
649 void setShader(Shader* shader)
650 {
651 tree_shader(fileNode, shader);
652 }
653
654 /**
655 * get the filename, the output should be written to
656 */
657 std::string GetName()
658 {
659 return output;
660 }
661 };
662
663 #endif
syntax highlighted by Code2HTML, v. 0.9.1