Implement CSG in front-end.

9 files changed, 340 insertions, 81 deletions

diff --git a/dimension/common.nonterminals b/dimension/common.nonterminals
index 164440a..768e075 100644
--- a/dimension/common.nonterminals
+++ b/dimension/common.nonterminals
@@ -38,8 +38,14 @@
 %type <astnode> OBJECT
 %type <astnode> FINITE_SOLID_OBJECT
 %type <astnode> BOX
-%type <astnode> LIGHT_SOURCE
 %type <astnode> SPHERE
+%type <astnode> CSG_OBJECT
+%type <astnode> UNION
+%type <astnode> INTERSECTION
+%type <astnode> DIFFERENCE
+%type <astnode> MERGE
+%type <astnode> OBJECTS
+%type <astnode> LIGHT_SOURCE
 
 /* Object modifiers */
 %type <astnode> OBJECT_MODIFIERS
diff --git a/dimension/common.rules b/dimension/common.rules
index d5e8994..e477df5 100644
--- a/dimension/common.rules
+++ b/dimension/common.rules
@@ -114,6 +114,7 @@ CAMERA_MODIFIER: "angle" FLOAT {
 /* Objects */
 
 OBJECT: FINITE_SOLID_OBJECT
+      | CSG_OBJECT
       | LIGHT_SOURCE
       | "object" "{"
           IDENTIFIER
@@ -196,6 +197,56 @@ SPHERE: "sphere" "{"
       }
 ;
 
+CSG_OBJECT: UNION
+          | INTERSECTION
+          | DIFFERENCE
+          | MERGE
+;
+
+UNION: "union" "{"
+         OBJECTS
+         OBJECT_MODIFIERS
+       "}"
+     {
+       $$ = dmnsn_new_astnode2(DMNSN_AST_UNION, @$, $3, $4);
+     }
+;
+
+INTERSECTION: "intersection" "{"
+                OBJECTS
+                OBJECT_MODIFIERS
+              "}"
+            {
+              $$ = dmnsn_new_astnode2(DMNSN_AST_INTERSECTION, @$, $3, $4);
+            }
+;
+
+DIFFERENCE: "difference" "{"
+              OBJECTS
+              OBJECT_MODIFIERS
+            "}"
+          {
+            $$ = dmnsn_new_astnode2(DMNSN_AST_DIFFERENCE, @$, $3, $4);
+          }
+;
+
+MERGE: "merge" "{"
+         OBJECTS
+         OBJECT_MODIFIERS
+       "}"
+     {
+       $$ = dmnsn_new_astnode2(DMNSN_AST_MERGE, @$, $3, $4);
+     }
+;
+
+OBJECTS: OBJECT OBJECT {
+         $$ = dmnsn_new_astnode2(DMNSN_AST_ARRAY, @$, $1, $2);
+       }
+       | OBJECTS OBJECT {
+         $$ = $1;
+         dmnsn_array_push($$.children, &$2);
+       }
+
 LIGHT_SOURCE: "light_source" "{"
                 VECTOR "," COLOR
               "}"
diff --git a/dimension/common.terminals b/dimension/common.terminals
index 7ed8d98..4458af3 100644
--- a/dimension/common.terminals
+++ b/dimension/common.terminals
@@ -161,7 +161,7 @@
 %token DMNSN_T_DENSITY_MAP
 %token DMNSN_T_DENTS
 %token DMNSN_T_DF3
-%token DMNSN_T_DIFFERENCE
+%token DMNSN_T_DIFFERENCE               "difference"
 %token DMNSN_T_DIFFUSE                  "diffuse"
 %token DMNSN_T_DIMENSION_SIZE
 %token DMNSN_T_DIMENSIONS
@@ -238,7 +238,7 @@
 %token DMNSN_T_INTERIOR_TEXTURE
 %token DMNSN_T_INTERNAL
 %token DMNSN_T_INTERPOLATE
-%token DMNSN_T_INTERSECTION
+%token DMNSN_T_INTERSECTION             "intersection"
 %token DMNSN_T_INTERVALS
 %token DMNSN_T_INVERSE
 %token DMNSN_T_IOR                      "ior"
@@ -282,7 +282,7 @@
 %token DMNSN_T_MEDIA
 %token DMNSN_T_MEDIA_ATTENUATION
 %token DMNSN_T_MEDIA_INTERACTION
-%token DMNSN_T_MERGE
+%token DMNSN_T_MERGE                    "merge"
 %token DMNSN_T_MESH
 %token DMNSN_T_MESH2
 %token DMNSN_T_METALLIC
@@ -458,7 +458,7 @@
 %token DMNSN_T_U                        "u"
 %token DMNSN_T_U_STEPS
 %token DMNSN_T_ULTRA_WIDE_ANGLE
-%token DMNSN_T_UNION
+%token DMNSN_T_UNION                    "union"
 %token DMNSN_T_UP                       "up"
 %token DMNSN_T_USE_ALPHA
 %token DMNSN_T_USE_COLOR
diff --git a/dimension/grammar.epilogue b/dimension/grammar.epilogue
index 9a5d8a6..275e03d 100644
--- a/dimension/grammar.epilogue
+++ b/dimension/grammar.epilogue
@@ -133,8 +133,12 @@ dmnsn_astnode_string(dmnsn_astnode_type astnode_type)
   dmnsn_astnode_map(DMNSN_AST_DIRECTION,   "direction");
 
   dmnsn_astnode_map(DMNSN_AST_BOX,          "box");
-  dmnsn_astnode_map(DMNSN_AST_SPHERE,       "sphere");
+  dmnsn_astnode_map(DMNSN_AST_DIFFERENCE,   "difference");
+  dmnsn_astnode_map(DMNSN_AST_INTERSECTION, "intersection");
   dmnsn_astnode_map(DMNSN_AST_LIGHT_SOURCE, "light_source");
+  dmnsn_astnode_map(DMNSN_AST_MERGE,        "merge");
+  dmnsn_astnode_map(DMNSN_AST_SPHERE,       "sphere");
+  dmnsn_astnode_map(DMNSN_AST_UNION,        "union");
 
   dmnsn_astnode_map(DMNSN_AST_OBJECT_MODIFIERS, "object-modifiers");
 
diff --git a/dimension/lexer.l b/dimension/lexer.l
index 2fb37cd..77772ae 100644
--- a/dimension/lexer.l
+++ b/dimension/lexer.l
@@ -194,6 +194,7 @@ unsigned long wchar;
 "cos"                   RETURN_TOKEN(DMNSN_T_COS);
 "cosh"                  RETURN_TOKEN(DMNSN_T_COSH);
 "degrees"               RETURN_TOKEN(DMNSN_T_DEGREES);
+"difference"            RETURN_TOKEN(DMNSN_T_DIFFERENCE);
 "diffuse"               RETURN_TOKEN(DMNSN_T_DIFFUSE);
 "direction"             RETURN_TOKEN(DMNSN_T_DIRECTION);
 "div"                   RETURN_TOKEN(DMNSN_T_DIV);
@@ -209,6 +210,7 @@ unsigned long wchar;
 "green"                 RETURN_TOKEN(DMNSN_T_GREEN);
 "int"                   RETURN_TOKEN(DMNSN_T_INT);
 "interior"              RETURN_TOKEN(DMNSN_T_INTERIOR);
+"intersection"          RETURN_TOKEN(DMNSN_T_INTERSECTION);
 "ior"                   RETURN_TOKEN(DMNSN_T_IOR);
 "ln"                    RETURN_TOKEN(DMNSN_T_LN);
 "location"              RETURN_TOKEN(DMNSN_T_LOCATION);
@@ -217,6 +219,7 @@ unsigned long wchar;
 "light_source"          RETURN_TOKEN(DMNSN_T_LIGHT_SOURCE);
 "max"                   RETURN_TOKEN(DMNSN_T_MAX);
 "max_trace_level"       RETURN_TOKEN(DMNSN_T_MAX_TRACE_LEVEL);
+"merge"                 RETURN_TOKEN(DMNSN_T_MERGE);
 "min"                   RETURN_TOKEN(DMNSN_T_MIN);
 "mod"                   RETURN_TOKEN(DMNSN_T_MOD);
 "no"                    RETURN_TOKEN(DMNSN_T_NO);
@@ -252,6 +255,7 @@ unsigned long wchar;
 "transmit"              RETURN_TOKEN(DMNSN_T_TRANSMIT);
 "true"                  RETURN_TOKEN(DMNSN_T_TRUE);
 "u"                     RETURN_TOKEN(DMNSN_T_U);
+"union"                 RETURN_TOKEN(DMNSN_T_UNION);
 "up"                    RETURN_TOKEN(DMNSN_T_UP);
 "v"                     RETURN_TOKEN(DMNSN_T_V);
 "val"                   RETURN_TOKEN(DMNSN_T_VAL);
diff --git a/dimension/parse.h b/dimension/parse.h
index a34e546..64fbf25 100644
--- a/dimension/parse.h
+++ b/dimension/parse.h
@@ -47,8 +47,12 @@ typedef enum {
   DMNSN_AST_DIRECTION,
 
   DMNSN_AST_BOX,
+  DMNSN_AST_DIFFERENCE,
+  DMNSN_AST_INTERSECTION,
   DMNSN_AST_LIGHT_SOURCE,
+  DMNSN_AST_MERGE,
   DMNSN_AST_SPHERE,
+  DMNSN_AST_UNION,
 
   DMNSN_AST_OBJECT_MODIFIERS,
 
diff --git a/dimension/realize.c b/dimension/realize.c
index fde751a..e70f1e3 100644
--- a/dimension/realize.c
+++ b/dimension/realize.c
@@ -659,6 +659,8 @@ dmnsn_realize_object_modifiers(dmnsn_astnode astnode, dmnsn_object *object)
   }
 }
 
+static dmnsn_object *dmnsn_realize_object(dmnsn_astnode astnode);
+
 static dmnsn_object *
 dmnsn_realize_box(dmnsn_astnode astnode)
 {
@@ -695,27 +697,6 @@ dmnsn_realize_box(dmnsn_astnode astnode)
   return box;
 }
 
-static dmnsn_light *
-dmnsn_realize_light_source(dmnsn_astnode astnode)
-{
-  dmnsn_assert(astnode.type == DMNSN_AST_LIGHT_SOURCE,
-               "Expected a light source.");
-
-  dmnsn_astnode point, color_node;
-  dmnsn_array_get(astnode.children, 0, &point);
-  dmnsn_array_get(astnode.children, 1, &color_node);
-
-  dmnsn_vector x0 = dmnsn_realize_vector(point);
-  dmnsn_color color = dmnsn_realize_color(color_node);
-
-  dmnsn_light *light = dmnsn_new_point_light(x0, color);
-  if (!light) {
-    dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate light.");
-  }
-
-  return light;
-}
-
 static dmnsn_object *
 dmnsn_realize_sphere(dmnsn_astnode astnode)
 {
@@ -743,6 +724,207 @@ dmnsn_realize_sphere(dmnsn_astnode astnode)
   return sphere;
 }
 
+static dmnsn_object *
+dmnsn_realize_union(dmnsn_astnode astnode)
+{
+  dmnsn_assert(astnode.type == DMNSN_AST_UNION, "Expected a union.");
+
+  dmnsn_astnode objects;
+  dmnsn_array_get(astnode.children, 0, &objects);
+
+  dmnsn_astnode o1node, o2node;
+  dmnsn_array_get(objects.children, 0, &o1node);
+  dmnsn_array_get(objects.children, 1, &o2node);
+
+  dmnsn_object *o1 = dmnsn_realize_object(o1node);
+  dmnsn_object *o2 = dmnsn_realize_object(o2node);
+
+  dmnsn_object *csg = dmnsn_new_csg_union(o1, o2);
+  if (!csg) {
+    dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate union.");
+  }
+
+  unsigned int i;
+  for (i = 2; i < dmnsn_array_size(objects.children); ++i) {
+    dmnsn_astnode onode;
+    dmnsn_array_get(objects.children, i, &onode);
+
+    dmnsn_object *object = dmnsn_realize_object(onode);
+    csg = dmnsn_new_csg_union(csg, object);
+    if (!csg) {
+      dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate union.");
+    }
+  }
+
+  dmnsn_astnode modifiers;
+  dmnsn_array_get(astnode.children, 1, &modifiers);
+  dmnsn_realize_object_modifiers(modifiers, csg);
+
+  return csg;
+}
+
+static dmnsn_object *
+dmnsn_realize_intersection(dmnsn_astnode astnode)
+{
+  dmnsn_assert(astnode.type == DMNSN_AST_INTERSECTION,
+               "Expected an intersection.");
+
+  dmnsn_astnode objects;
+  dmnsn_array_get(astnode.children, 0, &objects);
+
+  dmnsn_astnode o1node, o2node;
+  dmnsn_array_get(objects.children, 0, &o1node);
+  dmnsn_array_get(objects.children, 1, &o2node);
+
+  dmnsn_object *o1 = dmnsn_realize_object(o1node);
+  dmnsn_object *o2 = dmnsn_realize_object(o2node);
+
+  dmnsn_object *csg = dmnsn_new_csg_intersection(o1, o2);
+  if (!csg) {
+    dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate intersection.");
+  }
+
+  unsigned int i;
+  for (i = 2; i < dmnsn_array_size(objects.children); ++i) {
+    dmnsn_astnode onode;
+    dmnsn_array_get(objects.children, i, &onode);
+
+    dmnsn_object *object = dmnsn_realize_object(onode);
+    csg = dmnsn_new_csg_intersection(csg, object);
+    if (!csg) {
+      dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate intersection.");
+    }
+  }
+
+  dmnsn_astnode modifiers;
+  dmnsn_array_get(astnode.children, 1, &modifiers);
+  dmnsn_realize_object_modifiers(modifiers, csg);
+
+  return csg;
+}
+
+static dmnsn_object *
+dmnsn_realize_difference(dmnsn_astnode astnode)
+{
+  dmnsn_assert(astnode.type == DMNSN_AST_DIFFERENCE, "Expected a difference.");
+
+  dmnsn_astnode objects;
+  dmnsn_array_get(astnode.children, 0, &objects);
+
+  dmnsn_astnode o1node, o2node;
+  dmnsn_array_get(objects.children, 0, &o1node);
+  dmnsn_array_get(objects.children, 1, &o2node);
+
+  dmnsn_object *o1 = dmnsn_realize_object(o1node);
+  dmnsn_object *o2 = dmnsn_realize_object(o2node);
+
+  dmnsn_object *csg = dmnsn_new_csg_difference(o1, o2);
+  if (!csg) {
+    dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate difference.");
+  }
+
+  unsigned int i;
+  for (i = 2; i < dmnsn_array_size(objects.children); ++i) {
+    dmnsn_astnode onode;
+    dmnsn_array_get(objects.children, i, &onode);
+
+    dmnsn_object *object = dmnsn_realize_object(onode);
+    csg = dmnsn_new_csg_difference(csg, object);
+    if (!csg) {
+      dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate difference.");
+    }
+  }
+
+  dmnsn_astnode modifiers;
+  dmnsn_array_get(astnode.children, 1, &modifiers);
+  dmnsn_realize_object_modifiers(modifiers, csg);
+
+  return csg;
+}
+
+static dmnsn_object *
+dmnsn_realize_merge(dmnsn_astnode astnode)
+{
+  dmnsn_assert(astnode.type == DMNSN_AST_MERGE, "Expected a merge.");
+
+  dmnsn_astnode objects;
+  dmnsn_array_get(astnode.children, 0, &objects);
+
+  dmnsn_astnode o1node, o2node;
+  dmnsn_array_get(objects.children, 0, &o1node);
+  dmnsn_array_get(objects.children, 1, &o2node);
+
+  dmnsn_object *o1 = dmnsn_realize_object(o1node);
+  dmnsn_object *o2 = dmnsn_realize_object(o2node);
+
+  dmnsn_object *csg = dmnsn_new_csg_merge(o1, o2);
+  if (!csg) {
+    dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate merge.");
+  }
+
+  unsigned int i;
+  for (i = 2; i < dmnsn_array_size(objects.children); ++i) {
+    dmnsn_astnode onode;
+    dmnsn_array_get(objects.children, i, &onode);
+
+    dmnsn_object *object = dmnsn_realize_object(onode);
+    csg = dmnsn_new_csg_merge(csg, object);
+    if (!csg) {
+      dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate merge.");
+    }
+  }
+
+  dmnsn_astnode modifiers;
+  dmnsn_array_get(astnode.children, 1, &modifiers);
+  dmnsn_realize_object_modifiers(modifiers, csg);
+
+  return csg;
+}
+
+static dmnsn_object *
+dmnsn_realize_object(dmnsn_astnode astnode)
+{
+  switch (astnode.type) {
+  case DMNSN_AST_BOX:
+    return dmnsn_realize_box(astnode);
+  case DMNSN_AST_DIFFERENCE:
+    return dmnsn_realize_difference(astnode);
+  case DMNSN_AST_INTERSECTION:
+    return dmnsn_realize_intersection(astnode);
+  case DMNSN_AST_MERGE:
+    return dmnsn_realize_merge(astnode);
+  case DMNSN_AST_SPHERE:
+    return dmnsn_realize_sphere(astnode);
+  case DMNSN_AST_UNION:
+    return dmnsn_realize_union(astnode);
+
+  default:
+    dmnsn_assert(false, "Expected an object.");
+    return NULL; // Shut up compiler
+  }
+}
+
+static dmnsn_light *
+dmnsn_realize_light_source(dmnsn_astnode astnode)
+{
+  dmnsn_assert(astnode.type == DMNSN_AST_LIGHT_SOURCE,
+               "Expected a light source.");
+
+  dmnsn_astnode point, color_node;
+  dmnsn_array_get(astnode.children, 0, &point);
+  dmnsn_array_get(astnode.children, 1, &color_node);
+
+  dmnsn_vector x0 = dmnsn_realize_vector(point);
+  dmnsn_color color = dmnsn_realize_color(color_node);
+
+  dmnsn_light *light = dmnsn_new_point_light(x0, color);
+  if (!light) {
+    dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate light.");
+  }
+
+  return light;
+}
+
 static dmnsn_scene *
 dmnsn_realize_astree(const dmnsn_astree *astree)
 {
@@ -801,7 +983,12 @@ dmnsn_realize_astree(const dmnsn_astree *astree)
       break;
 
     case DMNSN_AST_BOX:
-      object = dmnsn_realize_box(astnode);
+    case DMNSN_AST_DIFFERENCE:
+    case DMNSN_AST_INTERSECTION:
+    case DMNSN_AST_MERGE:
+    case DMNSN_AST_SPHERE:
+    case DMNSN_AST_UNION:
+      object = dmnsn_realize_object(astnode);
       dmnsn_array_push(scene->objects, &object);
       break;
 
@@ -810,11 +997,6 @@ dmnsn_realize_astree(const dmnsn_astree *astree)
       dmnsn_array_push(scene->lights, &light);
       break;
 
-    case DMNSN_AST_SPHERE:
-      object = dmnsn_realize_sphere(astnode);
-      dmnsn_array_push(scene->objects, &object);
-      break;
-
     default:
       dmnsn_assert(false, "Unrecognised syntax element.");
     }
diff --git a/tests/dimension/demo.pov b/tests/dimension/demo.pov
index 3ecc36f..d14cebb 100644
--- a/tests/dimension/demo.pov
+++ b/tests/dimension/demo.pov
@@ -36,35 +36,37 @@ light_source {
   <-15, 20, 10>, color rgb <1, 1, 1>
 }
 
-box {
-  <-1, -1, -1>, <1, 1, 1>
+difference {
+  box {
+    <-1, -1, -1>, <1, 1, 1>
 
-  rotate 45*x
+    rotate 45*x
 
-  texture {
-    pigment {
-      color rgbft <0, 0, 1, 0.25, 0.5>
+    texture {
+      pigment {
+        color rgbft <0, 0, 1, 0.25, 0.5>
+      }
+      finish {
+        reflection { 0.5 }
+      }
     }
-    finish {
-      reflection { 0.5 }
+
+    interior {
+      ior 1.1
     }
   }
 
-  interior {
-    ior 1.1
-  }
-}
+  sphere {
+    <0, 0, 0>, 1.25
 
-sphere {
-  <0, 0, 0>, 1.25
-
-  texture {
-    pigment {
-      color rgb <0, 1, 0>
-    }
-    finish {
-      phong 0.2
-      phong_size 40.0
+    texture {
+      pigment {
+        color rgb <0, 1, 0>
+      }
+      finish {
+        phong 0.2
+        phong_size 40.0
+      }
     }
   }
 }
diff --git a/tests/dimension/demo.sh b/tests/dimension/demo.sh
index f294a4f..687d43c 100755
--- a/tests/dimension/demo.sh
+++ b/tests/dimension/demo.sh
@@ -35,33 +35,39 @@ demo_exp=$(echo -n \
   (light_source
     (vector (integer -15) (integer 20) (integer 10) (integer 0) (integer 0))
     (vector (integer 1) (integer 1) (integer 1) (integer 0) (integer 0)))
-  (box
-    (vector (integer -1) (integer -1) (integer -1) (integer 0) (integer 0))
-    (vector (integer 1) (integer 1) (integer 1) (integer 0) (integer 0))
-    (object-modifiers
-      (rotate (vector (integer 45) (integer 0) (integer 0)
+  (difference
+    (array
+      (box
+        (vector (integer -1) (integer -1) (integer -1) (integer 0) (integer 0))
+        (vector (integer 1) (integer 1) (integer 1) (integer 0) (integer 0))
+        (object-modifiers
+          (rotate (vector (integer 45) (integer 0) (integer 0)
+                          (integer 0) (integer 0)))
+          (texture
+            (pigment
+              (vector (integer 0) (integer 0) (integer 1)
+                      (float 0.25) (float 0.5)))
+            (finish
+              (reflection
+                (vector (float 0.5) (float 0.5) (float 0.5)
+                        (float 0.5) (float 0.5))
+                (vector (float 0.5) (float 0.5) (float 0.5)
+                        (float 0.5) (float 0.5))
+                reflection-items)))
+          (interior
+            (ior (float 1.1)))))
+      (sphere
+        (vector (integer 0) (integer 0) (integer 0) (integer 0) (integer 0))
+        (float 1.25)
+        (object-modifiers
+          (texture
+            (pigment
+              (vector (integer 0) (integer 1) (integer 0)
                       (integer 0) (integer 0)))
-      (texture
-        (pigment
-          (vector (integer 0) (integer 0) (integer 1)
-                  (float 0.25) (float 0.5)))
-        (finish
-          (reflection
-            (vector (float 0.5) (float 0.5) (float 0.5) (float 0.5) (float 0.5))
-            (vector (float 0.5) (float 0.5) (float 0.5) (float 0.5) (float 0.5))
-            reflection-items)))
-      (interior
-        (ior (float 1.1)))))
-  (sphere
-    (vector (integer 0) (integer 0) (integer 0) (integer 0) (integer 0))
-    (float 1.25)
-    (object-modifiers
-      (texture
-        (pigment
-          (vector (integer 0) (integer 1) (integer 0) (integer 0) (integer 0)))
-        (finish
-          (phong (float 0.2))
-          (phong_size (float 40)))))))' \
+            (finish
+              (phong (float 0.2))
+              (phong_size (float 40)))))))
+      object-modifiers))' \
 | tr '\n' ' ' | sed -r 's/[[:space:]]+/ /g')
 
 if [ "$demo" != "$demo_exp" ]; then