Assignment 1 information

Announcements

• Finally, here's a version of my polygon intersection that works under Windows:
  • polyint.cc

  NOTE: If you downloaded this file before Friday 2/2 7:45pm, you should download this new version because there was a bug in the old version. (There are a few new tests in the program for this case.)

  If you're using windows VisualC++, you must define the symbol IM_USING_STUPID_WINDOWS so you get the right version of the code.

  As I said before, I've tested this code (on UNIX and Windows) and believe it handles all the "weird" cases properly. You can see the test cases I used in the program.

  The Windows version will work fine under UNIX. The UNIX version, under windows, however doesn't work. I get two warnings when I compile it under windows, and the program crashes! The warnings are generated by the use of the assign function. The situation is that I do an intersection (which returns an Object). I need to know whether this Object is a PointC2 or a Segment, and you're supposed to use the CGAL::assign() function which does a dynamic_cast, and returns true if it is successful and false otherwise. (It also, of course, makes the assignment, but I don't do anything with the PointC2 or Segment after that --- I only want to know which it is.)

  The warning I get is something like "dynamic_cast used on a polymorphic type with /GR-; unpredictable behavior may result" The dynamic_cast throws an exception during execution which is not handled. This code follows the example on pp. 23--24 in the "Getting Started" guide. Perhaps one of you can figure out what we need to do to get this code to compile correctly under windows?

• Oops, I had made another mistake in the sample problem file that I missed. Two vertices of the "Triangle" obstacle were wrong. It should be solvable now.

• Hmmm... I don't know why the polygon intersection isn't working in CGAL. I'm finding out and will let you know. In the meantime, you can look at Example.C which is in the CGAL examples directory. This does a number of operations with polygons, but not intersections. It sets up CGAL differently than I did in my convexhull sample program.

  I will plan on either providing you with some code using CGAL that does polygon intersections or tell you how to do polygon intersections directly with CGAL.

• I figured out the problem with getting programs to compile with TOOGL. It seems there was no problem with interaction with CGAL; it was merely a problem with building the toogle_lib.lib file. See the TOOGL section for more details and a sample program.

• There is now some code you can use to read the input files. I tested it under UNIX g++ and under Windows Visual C++. See the Support code for reading input files section below.

• Oops, I made a mistake in the sample problem file: "bob" instead of the correct filename "robot_bob". Also, there wasn't a clear path from the start to the goal in this sample problem, so I made a change to the "RightQuadrilateral" in the "world1" file to make it clearer. (updated Sun 1/28)

• In answer to a question from Thursday 1/25: in doing the cellular decomposition, you must decide whether a cell is empty, full, or partially occupied. There are some cases where you can't tell without doing a few geometric intersections and other computations. I suggest one of the following approachis for this case:
  • You can use one or two CGAL routines, I think, to determine the correct answer. This correct answer comes at the cost of the time for the geometric computation.

  • You can sort of ignore the problem and avoid doing the extra geometric computation. Your solution should still be correct, though there is some additional cost here too.

  For written question 1 where it asks you to describe any important design decisions you made, describe this problem and the solution you decided upon.

• VOGLE is now installed in CS land. The example has been updated to work with the installed version in CS.

• If you downloaded the CGAL documentation before 10am Friday January 19, you might want to download the current version there now --- the old version did not include the images (mostly logos and backgrounds I think).

Assignment information

• Support code for reading the input files
• CGAL: The Computational Geometry Algorithms Library
  • CGAL under windows
• The TOOGL Graphics library for Windows
• The VOGLE Graphics library for X11/UNIX
• Sample inputs

Support Code for reading input files

NOTE: This is just sample code. I do read the points into a list of CGAL-supported points, but I throw all the information away once I read it. You'll probably want to keep it around in some class of your own design. Here's the file:

• rf.cpp

This code is a rewritten version of the code that Rob Foulis submitted for the first part of Assignment 1 (which I believe was an extension of the code I had provided in the convexhull program).

CGAL: The Computational Geometry Algorithms Library

• CGAL has been installed on the CS department new Suns, so if you're going to use those machines, you don't need to worry about installing CGAL yourself. There are two labs full of these Suns that you can use: Amos Eaton 217 and Amos Eaton 117.

• I have cached local copies of the software. Please note that this is available to us under a license for academic research and teaching only. See the CGAL home page for more information on the licensing.
  • Software and installation guide (gzipped tar file) [removed 1/25/02]
  • Software and installation guide (zip format) [removed 1/25/02]
  • Documentation in HTML (gzipped tar file) [removed 1/25/02]
  • Documentation in HTML (zip format) [removed 1/25/02]

  The documentation is also available in postscrip and pdf format as well.

• CGAL documentation (local HTML copy) [removed 1/25/02]

• The CGAL home page

• Here's a simple program that reads a file of points and computes the convex hull using CGAL.
  • convexhull.cpp (compiles under g++ and under Visual C++)
  • testpoints (a sample data file for the above program)
  • Makefile (works on CS department Suns)

• The instructions (which are packed in the tar file) tell you to unpack the distribution using a program such as winzip. After you do that, you can read the installation instructions in the top level directory.

• I had to add c:\progra~1\micros~1\vc98\bin to the PATH variable in the c:\dosprompt.bat file. This directory is where (on my computer) the command line visual c++ utilities such as nmake and cl live.

  Oh, I just learned that the dosprompt.bat file is just the filename we have specified in the "batch file" portion of the Properties/General of the MSDOS shell, so it may be different or nonexistent on your machine.

• Right click on the MSDOS shell icon and get the properties window. Change the initial environment size to 4096. With the default size, you'll run out of environment space during the install process.

• Start a DOS shell and run the vcvars32.bat This sets environment variables so that the command line compiler stuff will work.

• Go to the CGAL directory and type cgal_config msc mld to run this batch file. Watch for error messages. If it completes successfully, then type make_lib to compile the CGAL library. You can also compile the demos and examples if you want.

After this, go read the install.txt file very carefully! It tells you almost everything you need to know to set up Visual C++ to link to the CGAL library. This information is contained in section 4.2. The only thing that they don't say in this file is that when you add the CGAL.lib and gmp.lib in the Project/Settings/Link/Input page, you also have to add directories to the "Additional library paths" slot. On my computer, these are:

c:\cgal-2.2\lib\msvc,c:\cgal-2.2\auxiliary\wingmp\gmp-2.0.2\msvc

I had to make a few minor changes to my convexhull.cpp program to make it work. (For example, I didn't know how to specify command line arguments, and also the file I/O was slightly different for me --- I had to replace the error message in the file reading loop with a break statement.)

Although you are certainly more adept than I with Visual C++, here's my workspace/project files for the convexhull program. (Although note that it is set up for where I installed CGAL, in c:\CGAL-2.2)

• cvhull.zip

• The TOOGL graphics library home page

  You can download the software from here. The documentation that I printed and handed out in class is available on this page also.

• They use this library for CS1, so I expect it should be easy to use.

• You need to make a change before building the TOOGL library in order to be able to use it successfully in your own programs. The errors that some of you reported were (I presume) errors from linking, not compiling. My test program compiled fine once I added the proper directories for the include files. Here's what you need to do:
  • After you unpack the TOOGL distribution, open the workspace in the toogl directory. This has three projects: CMUgraphicsLib, toogle_demo, and toogle_lib.

  • In the "toogle_demo" project, there is a "canvas" folder that contains the file canvas.cpp. Move this file to the "sources" folder in the "toogle_lib" project.

  • Build the CMUgraphicsLib, and then build the toogle_lib. (You probably need to add a path or two in this process to find include files.)

  Here's a program and a test input that uses CGAL together. There wasn't any issue with CGAL and TOOGL not liking each other --- it was just an issue of not being able to find certain functions in the toogle_lib.lib library.

  • toogltest.cpp
  • polygon.txt

• I downloaded the software:
  • vogle-2.0b0.tar.gz --- they say this is a beta version, but I haven't had any trouble with it so far!
  • vogle-1.3.0.tar.gz --- this is supposedly the latest stable version

  This software is public domain software (though the authors encourage you to send them beer or other alcoholic beverage).

• The disadvantage of this software is that there isn't much documentation for it. One advantage is that I didn't have much trouble compiling it. I compiled it only to support X11 and postscript. I had to change a few things in the Makefile. I had to add:

  #include <fcntl.h>
  

  in the objects.c file, probably because I didn't set flags properly in the Makefile.

  You probably don't need to compile the fortran examples, so you should probably comment that part of the makefile out. (Under gnu-make, it made them despite the fact that I commented out the F77 variable.)

• There are a number of example programs (in the examples directory). The "teapot" program is neat. The "simple" program is probably a good one to look at. I had problems with some of the other sample programs not being able to access the font directories.

• The example programs ask you to type in the output device (X11), and they might ask you to set the environment variable USEOWNCMAP to 1. Here's how you can do it in a bash shell:

  USEOWNCMAP=1
  export USEOWNCMAP
  

• Here's a simple example program. These will work on CS machines (at least the new suns). You can find the installation at /projects/mobile-robotics/vogle. There are a few comments in the Makefile below, telling you such things as there are many example programs in the vogle directory that you can run.
  • vexample.cc
  • Makefile

• Sample problem 1
• World 1
• Robot file (Bob)