Geogram  Version 1.9.1-rc
A programming library of geometric algorithms
mesh_CSG.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2000-2023 Inria
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  *
8  * * Redistributions of source code must retain the above copyright notice,
9  * this list of conditions and the following disclaimer.
10  * * Redistributions in binary form must reproduce the above copyright notice,
11  * this list of conditions and the following disclaimer in the documentation
12  * and/or other materials provided with the distribution.
13  * * Neither the name of the ALICE Project-Team nor the names of its
14  * contributors may be used to endorse or promote products derived from this
15  * software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
21  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27  * POSSIBILITY OF SUCH DAMAGE.
28  *
29  * Contact: Bruno Levy
30  *
31  * https://www.inria.fr/fr/bruno-levy
32  *
33  * Inria,
34  * Domaine de Voluceau,
35  * 78150 Le Chesnay - Rocquencourt
36  * FRANCE
37  *
38  */
39 
40 #ifndef H_GEO_MESH_ALGO_MESH_CSG_H
41 #define H_GEO_MESH_ALGO_MESH_CSG_H
42 
43 #include <geogram/basic/common.h>
44 #include <geogram/mesh/mesh.h>
46 #include <geogram/basic/memory.h>
47 
53 namespace GEO {
54 
55  class ProgressTask;
56  class Image;
57 
61  class GEOGRAM_API CSGMesh : public Mesh, public Counted {
62  public:
63  CSGMesh();
64  ~CSGMesh() override;
70  const Box3d& bbox() const {
71  geo_debug_assert(vertices.nb() == 0 || bbox_initialized());
72  return bbox_;
73  }
74 
82  bool bbox_initialized() const;
83 
89  void update_bbox();
90 
98  void append_mesh(const CSGMesh* other, index_t operand = index_t(-1));
99 
110  bool may_have_intersections_with(const CSGMesh* other) const {
111  return bboxes_overlap(bbox(), other->bbox());
112  }
113 
114  private:
115  Box3d bbox_;
116  };
117 
122 
127  typedef std::vector< CSGMesh_var > CSGScope;
128 
134  class GEOGRAM_API CSGBuilder {
135  public:
137  static constexpr double DEFAULT_FA = 12.0;
138 
140  static constexpr double DEFAULT_FS = 2.0;
141 
143  static constexpr double DEFAULT_FN = 0.0;
144 
145  CSGBuilder();
146 
147  /****** Objects **********/
148 
149  CSGMesh_var square(vec2 size = vec2(1.0,1.0), bool center=true);
150  CSGMesh_var circle(double r=1.0);
151  CSGMesh_var cube(vec3 size = vec3(1.0, 1.0, 1.0), bool center=true);
152  CSGMesh_var sphere(double r=1.0);
153  CSGMesh_var cylinder(
154  double h=1.0, double r1=1.0, double r2=1.0, bool center=true
155  );
156  CSGMesh_var import(
157  const std::string& filename, const std::string& layer="",
158  index_t timestamp=0,
159  vec2 origin = vec2(0.0, 0.0), vec2 scale = vec2(1.0,1.0)
160  );
161  CSGMesh_var surface(
162  const std::string& filename, bool center, bool invert
163  );
164 
165  /****** Instructions ****/
166 
176  CSGMesh_var multmatrix(const mat4& M, const CSGScope& scope);
177 
183 
189 
197 
204  CSGMesh_var group(const CSGScope& scope) {
205  return union_instr(scope);
206  }
207 
214  CSGMesh_var color(vec4 color, const CSGScope& scope);
215 
220  CSGMesh_var hull(const CSGScope& scope);
221 
234  const CSGScope& scope,
235  double height = 1.0,
236  bool center = true,
237  vec2 scale = vec2(1.0,1.0),
238  index_t slices = 0,
239  double twist = 0.0
240  );
241 
242 
249  CSGMesh_var rotate_extrude(const CSGScope& scope, double angle = 360.0);
250 
257  CSGMesh_var projection(const CSGScope& scope, bool cut);
258 
263  CSGMesh_var append(const CSGScope& scope);
264 
265  /****** Parameters ******/
266 
272 
281  void set_fn(double fn) {
282  fn_ = std::max(fn, 0.0);
283  }
284 
291  void set_fs(double fs) {
292  fs_ = std::max(fs,0.01);
293  }
294 
301  void set_fa(double fa) {
302  fa_ = std::max(fa,0.01);
303  }
304 
311  void set_delaunay(bool x) {
312  delaunay_ = x;
313  }
314 
321  detect_intersecting_neighbors_ = x;
322  }
323 
333  void set_simplify_coplanar_facets(bool x, double angle_tolerance=0.0) {
334  simplify_coplanar_facets_ = x;
335  coplanar_angle_tolerance_ = angle_tolerance;
336  }
337 
345  void set_fast_union(bool x) {
346  fast_union_ = x;
347  }
348 
354  void set_verbose(bool x) {
355  verbose_ = x;
356  }
357 
363  bool verbose() const {
364  return verbose_;
365  }
366 
373  void add_file_path(const std::string& path) {
374  file_path_.push_back(path);
375  }
376 
382  file_path_.clear();
383  file_path_.push_back(".");
384  }
385 
386  protected:
387 
388  bool find_file(std::string& filename);
389 
390  void do_CSG(CSGMesh_var mesh, const std::string& boolean_expr);
391 
401  CSGMesh_var mesh, const std::string& boolean_expr,
402  bool keep_border_only=false
403  );
404 
411  const std::string& filename, const std::string& layer="",
412  index_t timestamp=0
413  );
414 
422  Image* load_dat_image(const std::string& file_name);
423 
432 
442  index_t get_fragments_from_r(double r, double twist = 360.0);
443 
444  private:
445  double fn_;
446  double fs_;
447  double fa_;
448  double STL_epsilon_;
449  bool verbose_;
450  index_t max_arity_;
451  std::vector<std::string> file_path_;
452  bool detect_intersecting_neighbors_;
453  bool delaunay_;
454  bool simplify_coplanar_facets_;
455  double coplanar_angle_tolerance_;
456  bool fast_union_;
457  };
458 
459  /**************************************************************/
460 
465  class GEOGRAM_API CSGCompiler {
466  public:
467 
468  CSGCompiler();
469  CSGMesh_var compile_file(const std::string& input_filename);
470  CSGMesh_var compile_string(const std::string& source);
471 
477  void set_verbose(bool x) {
478  builder_.set_verbose(x);
479  }
480 
486  return builder_;
487  }
488 
489  protected:
490 
491  /****** Value, Arglist **********************************/
492 
497  struct Value {
498  enum Type {NONE, NUMBER, BOOLEAN, ARRAY1D, ARRAY2D, STRING};
499 
500  Value();
501  Value(double x);
502  Value(int x);
503  Value(bool x);
504  Value(const std::string& x);
505  std::string to_string() const;
506 
507  Type type;
508  bool boolean_val;
509  double number_val;
510  vector<vector<double> > array_val;
511  std::string string_val;
512  };
513 
518  class ArgList {
519  public:
520  typedef std::pair<std::string, Value> Arg;
521 
522  index_t size() const {
523  return args_.size();
524  }
525 
526  const std::string& ith_arg_name(index_t i) const {
527  geo_assert(i < size());
528  return args_[i].first;
529  }
530 
531  const Value& ith_arg_val(index_t i) const {
532  geo_assert(i < size());
533  return args_[i].second;
534  }
535 
536  void add_arg(const std::string& name, const Value& value);
537  bool has_arg(const std::string& name) const;
538  const Value& get_arg(const std::string& name) const;
539  double get_arg(const std::string& name,double default_value) const;
540  int get_arg(const std::string& name, int default_value) const;
541  bool get_arg(const std::string& name, bool default_value) const;
542  vec2 get_arg(const std::string& name, vec2 default_value) const;
543  vec3 get_arg(const std::string& name, vec3 default_value) const;
544  vec4 get_arg(const std::string& name, vec4 default_value) const;
545  mat4 get_arg(
546  const std::string& name, const mat4& default_value
547  ) const;
548  std::string get_arg(
549  const std::string& name, const std::string& default_value
550  ) const;
551 
552  private:
553  vector<Arg> args_;
554  };
555 
556 
557  /****** Objects *****************************************/
558 
559  CSGMesh_var square(const ArgList& args);
560  CSGMesh_var circle(const ArgList& args);
561  CSGMesh_var cube(const ArgList& args);
562  CSGMesh_var sphere(const ArgList& args);
563  CSGMesh_var cylinder(const ArgList& args);
564  CSGMesh_var polyhedron(const ArgList& args);
565  CSGMesh_var polygon(const ArgList& args);
566  CSGMesh_var import(const ArgList& args);
567  CSGMesh_var surface(const ArgList& args);
568 
569  /****** Instructions ************************************/
570 
571  CSGMesh_var multmatrix(const ArgList& args, const CSGScope& scope);
572  CSGMesh_var resize(const ArgList& args, const CSGScope& scope);
573  CSGMesh_var union_instr(const ArgList& args, const CSGScope& scope);
574  CSGMesh_var intersection(const ArgList& args, const CSGScope& scope);
575  CSGMesh_var difference(const ArgList& args, const CSGScope& scope);
576  CSGMesh_var group(const ArgList& args, const CSGScope& scope);
577  CSGMesh_var color(const ArgList& args, const CSGScope& scope);
578  CSGMesh_var hull(const ArgList& args, const CSGScope& scope);
579  CSGMesh_var linear_extrude(const ArgList& args, const CSGScope& scope);
580  CSGMesh_var rotate_extrude(const ArgList& args, const CSGScope& scope);
581  CSGMesh_var projection(const ArgList& args, const CSGScope& scope);
582 
583  /***** Parser *******************************************/
584 
585  CSGMesh_var parse_instruction_or_object();
586  CSGMesh_var parse_object();
587  CSGMesh_var parse_instruction();
588  ArgList parse_arg_list();
589  Value parse_value();
590  Value parse_array();
591  bool is_object(const std::string& id) const;
592  bool is_instruction(const std::string& id) const;
593 
603  bool is_modifier(int toktype) const;
604 
605  /***** Parser internals ********************************/
606 
607  struct Token {
608  Token();
609  std::string to_string() const;
610  int type;
611  std::string str_val;
612  int int_val;
613  double double_val;
614  bool boolean_val;
615  };
616 
623  void next_token_check(char c);
624 
630 
636 
644 
648  int lines() const;
649 
653  int line() const;
654 
655 
660  [[noreturn]] void syntax_error(const char* msg);
661 
668  [[noreturn]] void syntax_error(const char* msg, const Token& tok);
669 
670  private:
671  std::string filename_;
672  void* lex_;
673  Token lookahead_token_;
674  CSGBuilder builder_;
675 
676  typedef CSGMesh_var (CSGCompiler::*object_funptr)(const ArgList& args);
677  typedef CSGMesh_var (CSGCompiler::*instruction_funptr)(
678  const ArgList& args, const CSGScope& scope
679  );
680  std::map<std::string, object_funptr> object_funcs_;
681  std::map<std::string, instruction_funptr> instruction_funcs_;
682  ProgressTask* progress_;
683  index_t lines_;
684  };
685 }
686 
687 #endif
#define geo_assert(x)
Verifies that a condition is met.
Definition: assert.h:149
#define geo_debug_assert(x)
Verifies that a condition is met.
Definition: assert.h:196
Axis-aligned bounding box.
Definition: geometry.h:669
Implements CSG objects and instructions.
Definition: mesh_CSG.h:134
index_t get_fragments_from_r(double r, double twist=360.0)
Computes the number of fragments, that is, edges in a polygonal approximation of a circle.
CSGMesh_var difference(const CSGScope &scope)
Computes the intersection between two meshes.
void set_delaunay(bool x)
If set, compute constrained Delaunay triangulation in the intersected triangles. If there are interse...
Definition: mesh_CSG.h:311
CSGMesh_var intersection(const CSGScope &scope)
Computes the intersection between two or more meshes.
CSGMesh_var color(vec4 color, const CSGScope &scope)
Groups several meshes into a single one and sets their color.
void set_fn(double fn)
Sets the number of fragments.
Definition: mesh_CSG.h:281
void post_process(CSGMesh_var mesh)
Post-processes the result of a previous intersection.
bool verbose() const
Tests wheter verbose mode is set.
Definition: mesh_CSG.h:363
CSGMesh_var group(const CSGScope &scope)
synonym for union.
Definition: mesh_CSG.h:204
void set_fast_union(bool x)
Sets fast union mode.
Definition: mesh_CSG.h:345
void set_fa(double fa)
Sets the minimum angle for a fragment.
Definition: mesh_CSG.h:301
void add_file_path(const std::string &path)
Adds a path to the file path.
Definition: mesh_CSG.h:373
void set_detect_intersecting_neighbors(bool x)
detect and compute intersections between facets that share a facet or an edge. Set to false if input ...
Definition: mesh_CSG.h:320
void set_simplify_coplanar_facets(bool x, double angle_tolerance=0.0)
Specifies whether coplanar facets should be simplified.
Definition: mesh_CSG.h:333
CSGMesh_var linear_extrude(const CSGScope &scope, double height=1.0, bool center=true, vec2 scale=vec2(1.0, 1.0), index_t slices=0, double twist=0.0)
Computes a 3D extrusion from a 2D shape.
void triangulate(CSGMesh_var mesh, const std::string &boolean_expr, bool keep_border_only=false)
Triangulates a 2D mesh.
Image * load_dat_image(const std::string &file_name)
Loads an ascii data file as an image.
void set_fs(double fs)
Sets the minimum size for a fragment.
Definition: mesh_CSG.h:291
CSGMesh_var multmatrix(const mat4 &M, const CSGScope &scope)
Groups several meshes into a single one and transforms them.
void set_verbose(bool x)
Displays (lots of) additional information.
Definition: mesh_CSG.h:354
CSGMesh_var rotate_extrude(const CSGScope &scope, double angle=360.0)
Computes a 3D extrusion from a 2D shape.
void reset_file_path()
Resets the file path to its default value, with only the current directory ".".
Definition: mesh_CSG.h:381
CSGMesh_var append(const CSGScope &scope)
Appends all meshes in scope into a unique mesh, without testing for intersections.
CSGMesh_var projection(const CSGScope &scope, bool cut)
Creates a 2D mesh from 3D mesh.
CSGMesh_var union_instr(const CSGScope &scope)
Computes the union of two or more meshes.
CSGMesh_var hull(const CSGScope &scope)
Computes the convex hull of several meshes.
CSGMesh_var import_with_openSCAD(const std::string &filename, const std::string &layer="", index_t timestamp=0)
For the file formats that are not supported by geogram, get help from OpenSCAD to convert them.
void reset_defaults()
Resets defaults value for fn, fs, fa.
A parsed argument list in a .csg file.
Definition: mesh_CSG.h:518
Creates meshes from OpenSCAD .csg files.
Definition: mesh_CSG.h:465
void syntax_error(const char *msg, const Token &tok)
Throws an exception with an error message.
Token next_token_internal()
Function to actually get the next token from the stream.
bool is_modifier(int toktype) const
Checks if a token corresponds to an instruction or object modifier.
void next_token_check(char c)
Checks that the next token is a given character.
int line() const
Gets the currently parsed line source.
Token lookahead_token()
Gets the next token without any side effect.
void set_verbose(bool x)
Displays (lots of) additional information.
Definition: mesh_CSG.h:477
void syntax_error(const char *msg)
Throws an exception with an error message.
CSGBuilder & builder()
Gets the CSGbuilder.
Definition: mesh_CSG.h:485
Token next_token()
Gets the next token.
int lines() const
Gets the total number of lines of the currently parsed source.
A Mesh with reference counting and bounding box.
Definition: mesh_CSG.h:61
bool bbox_initialized() const
Tests whether the bounding box was initialized.
void append_mesh(const CSGMesh *other, index_t operand=index_t(-1))
Appends a mesh to this mesh.
bool may_have_intersections_with(const CSGMesh *other) const
Tests whether this mesh may have an intersection with another mesh.
Definition: mesh_CSG.h:110
const Box3d & bbox() const
Gets the bounding box.
Definition: mesh_CSG.h:70
void update_bbox()
Computes the bounding box.
Base class for reference-counted objects.
Definition: counted.h:71
An image.
Definition: image.h:59
Represents a mesh.
Definition: mesh.h:2693
Tracks the progress of a task.
Definition: progress.h:240
A smart pointer with reference-counted copy semantics.
Definition: smart_pointer.h:76
Vector with aligned memory allocation.
Definition: memory.h:635
Common include file, providing basic definitions. Should be included before anything else by all head...
Types and functions for memory manipulation.
The class that represents a mesh.
std::string get_arg(const std::string &name)
Gets an argument value.
double angle(const vec3 &a, const vec3 &b)
Computes the angle between two 3d vectors.
Definition: geometry.h:266
void invert(vector< index_t > &permutation)
Inverts a permutation in-place.
Definition: permutation.h:253
Global Vorpaline namespace.
Definition: basic.h:55
SmartPointer< CSGMesh > CSGMesh_var
A smart pointer to a CSGMesh.
Definition: mesh_CSG.h:121
std::vector< CSGMesh_var > CSGScope
A list of CSGMesh.
Definition: mesh_CSG.h:127
bool bboxes_overlap(const Box &B1, const Box &B2)
Tests whether two Boxes have a non-empty intersection.
Definition: geometry.h:701
vecng< 3, Numeric::float64 > vec3
Represents points and vectors in 3d.
Definition: geometry.h:65
geo_index_t index_t
The type for storing and manipulating indices.
Definition: numeric.h:329
vecng< 2, Numeric::float64 > vec2
Represents points and vectors in 2d.
Definition: geometry.h:59
Pointers with automatic reference counting.
A parsed value in a .csg file.
Definition: mesh_CSG.h:497