Almost-Delaunay Simplices in CGAL : Installation Manual Deepak Bandyopadhyay 1. Unzip the package into a directory named "ADCGAL" somewhere in your path. 2. Make sure CGAL and Boost are already installed and CGAL_MAKEFILE and CGALROOT are defined in the environment variables. 3. Copy the directory "include" within "CGALpatch" on top of the "include" within your CGAL installation, making a backup of the directory first. The following are the changed files, their paths and the reason they were upgraded (this upgrade can also be done automatically by the script "patchCGAL.bat" in Windows and patchCGAL in Linux. 3A. For Windows: ================ * Open MSVC++7.x/Intel Compiler. * Load project ADsimpCGAL7.vcproj (AD simplices) or ADCGAL7.vcproj (AD edges only). The projects differ in one preprocessor definiton (ADSIMP_CGAL) and in the files included (ADsimpCGAL.cpp should be only in ADsimpCGAL.vcproj) * Edit the Properties and change paths of CGAL and Boost libraries and include files to those on your system. * Compile. The output will lie in the directory "Release" under ADCGAL for ADCGAL.exe, AD simplices ("ReleaseEdge" for ADedgeCGAL, since we don't want the *.o files for the two versions to reside in the same place). 3B. For Linux ============= * Edit the Makefile (copy saved as Makefile.linux) to change the settings to your CGAL and BOOST installations, and your version of gcc. Make sure ADSIMP_CGAL is defined if you want to compile "AD simplices" code, and commented out for AD edge code. You can tell which version was actually compiled since the simplex version will take a non-zero time for Step 6 (written to standard output), and will not create *.AD3, *.del3, *.AD4, *.del4 files. There are Linux-specific includes also: the gcc version I used had the hash_table include file in a non-standard location, so I had to define -DCYGWIN_GCC_BUG and provide alternate code (most of these bugs affect compilation with Cygwin GCC 3.2.x also). Another is -DREPLACE_AUTO_REF_BOOST - this is unique to Linux, as the auto_ref smart pointer implmentation I used does not work in Linux, it uses Win32 API stuff to do threads that I tried to replace but could not make it work, so provide an alternate implementation using BOOST smart pointers. * Compile: "make ADedgeCGAL" or "make ADCGAL" for edges only or simplices, respectively. You make have to "make clean" and remove *.o before you change from one to the other (they should be built in different places to avoid this; right now both executables appear in the ADCGAL directory). 4. Use the executable or incorporate in scripts Usage: ADCGAL , more details in the usage manual. %%% Checklist of files in the current version, in directory ADCGAL before installation %%% C++ source files ADconvex.cpp ADedgeCGAL.cpp ADfunc.cpp ADjoggle.cpp ADmainCGAL.cpp ADPointNeighbors.cpp ADsimpCGAL.cpp auto_ref.cpp MyDelaunay.cpp tester.cpp %% C++ header files ADCGAL.h ADcommon.h ADconvex.h ADdefs.h ADfunc.h ADPointNeighbors.h ADutil.h auto_ref.h MyDelaunay.h MySTLextensions.h quick_mem_manager.h SortedTuples.h sorted_vector.h %% makefiles (Linux) and project files (Win) Makefile makefile.cyg Makefile.linux ADCGAL7.sln tester7.sln ADCGAL7.vcproj ADsimpCGAL7.vcproj tester7.vcproj %% sample input files (remove .out from these names to get third argument of ADCGAL) trouble.out 2bnh.out allpts.out 1lo6.out 1af70.out %% patch files for your CGAL installation patchCGAL* patchCGAL.bat patchCGAL.linux.lst patchCGAL.lst copy2CGAL.bat CGALpatch/include/CGAL/Convex_hull_traits_3.h CGALpatch/include/CGAL/Line_2_Line_2_intersection.h CGALpatch/include/CGAL/Ray_2_Line_2_intersection.h CGALpatch/include/CGAL/Segment_2_Line_2_intersection.h CGALpatch/include/CGAL/convex_hull_3.h CGALpatch/include/CGAL/convexity_check_3.h CGALpatch/include/CGAL/Cartesian/function_objects.h CGALpatch/include/CGAL/Constructions/kernel_ftC2.h CGALpatch/include/CGAL/Static_filters/Coplanar_orientation_3.h CGALpatch/include/CGAL/Static_filters/Coplanar_side_of_bounded_circle_3.h CGALpatch/include/CGAL/Static_filters/Orientation_2.h CGALpatch/include/CGAL/Static_filters/Orientation_3.h CGALpatch/include/CGAL/Static_filters/Side_of_oriented_circle_2.h CGALpatch/include/CGAL/Static_filters/Side_of_oriented_sphere_3.h %% Files that you should see added after a successful compilation: *.o (one for each *.cpp) ADCGAL (simplices Binary, which appears after you "make ADCGAL" ADedgeCGAL (edges Binary, which will appear only after you "make ADedgeCGAL" %% Description of CGAL patches: The changes to the convex hull files (convex_hull_3.h,Convex_hull_traits_3.h, convexity_check_3.h and Cartesian/function_objects.h) are to introduce a new plane class, one that stores vertices instead of a plane equation, and to use it each time we are testing for which side of a hull facet a new point is on. This was done to stop the crashes and infinite loops I was getting for certain point sets when using Convex_hull_3. The changed files here are due to Andreas Fabri. The changes to Static_filters/*.h are to make protected static filters classes public so the program can use them. For some reason these classes (that work for all predicates used in the DT but not in Convex_hull_3) are undocumented in CGAL-3.0 and were thus protected; the plan is to merge these classes in the Filtered_kernel in a future release. The remaining changes (to 2D kernel and intersection routines) are to avoid a degenerate case of segment/line or segment/ray intersection where the segment is vertical; a bounding box check for the interpoint lying on the segment used to fail, and a valid intersection was rejected. The fix, again by Andreas Fabri, is a rectangular stripe as a bounding box rather than a rectangle formed by the segment coordinates. %% Install Troubleshooting: Nothing here for now; make sure you have the right versions of all required libraries; that the CGAL patch files have been copied to correct directories; that CGALROOT, BOOSTDIR and CGAL_MAKEFILE environment variables are set; that all paths in the Makefile or %% Cygwin support: Cygwin support is claimed in the paper and it did indeed use to work at one time; however the changes we made to robustify the code broke it, so that it does not compile in Cygwin any more. The Cygwin makefile is still part of the distribution, and this should be fixable later. Please contact me if you need it to compile in Cygwin, and I will try to make it work again.