Homec4science
Diffusion CADD_mesher (dev/incorporate-qhull) Browse

rCADDMESH/src/Changes.txt
bc7fcdcf2704dev/incorporate-qhull

Last Change
Raw File

Changes.txt
View Options

$Id: //main/2015/qhull/src/Changes.txt#29 $
.............This file lists all changes to qhull and rbox.....................
------------
Need help
- Write an incremental addPoint using bucketed inputs and facet location search (see CGAL)
- Compute hyperplanes in parallel (cf. qh_setfactplane)
- Create Voronoi volumes and topology using a parallel implementation
- Produce conformant triangulations for merged facets using option 'Qt'
- Integrate 4dview with Geomview 1.9.5
- Qhull needs RPM and Debian builds (CMake's CPackRMP and CPackDeb).
- Qhull needs a mirror/archive site for old and new builds
- Constrained delaunay triangulation via Shewchuk's algorithm (ACM Symp. Comp. Geo., 1998)
- More enhancements -- http://www.qhull.org/html/qh-code.htm#enhance
- The C++ interface needs work. Give it a try and make it better.
http://github.com/qhull/qhull/wiki
Octave creates endpoints for the ridges that would extend to infinity to be able to draw the diagram [M. Voss]
- Explanation of clobbered warning for Qhull::runQhull and qh_new_qhull
- html/index.htm: Add "Nearly coincident points" to "When to use Qhull"
- html/index.htm: Add Tomilov's qhullhull.hpp for general position input.
- index.htm: Add Tomilov's qhullhull.hpp for general position input.
- qh-faq.htm: Add a note about merging slivers in a Delaunay triangulation [M. Treacy]
------------
Qhull 2015.2 2016/01/18 (7.2.0)
- Fixed memory leak in ~QhullQh [M. Sandim]
QhullQh.cpp: call checkAndFreeQhullMemory() in the destructor. Otherwise memT is not freed.
Remove checkAndFreeQhullMemory() from Qhull.h. It is not needed.
Remove calls to checkAndFreeQhullMemory in qhulltest. It is called by ~QhullQh()
libqhull_r.h: Document qh_ASvornoi and facetT.center
qh_freeqhull: if qh_NOmem, use qh_ALL
qh_memalloc: short memory is freed by qh_memfreeshort unless qh_NOmem
qh_memstatistics (mem.c): call qh_memcheck() as done in mem_r.c
qh_new_qhull calls qh_memcheck
qh_newvertex: free vertex on error
qh_projectinput: Free memory allocations on error
qh_rboxpoints: free simplex on error
qh_sethalfspace_all: Fixed memory leak on error QH8032 feasible not inside halfspace
qh_triangulate_facet: For TRInormals ('Q11') replace qh_copypoints with qh_memalloc
qh_triangulate_facet: Document qh.TRInormals
qh_voronoi_center: Free center on error
qhulltest: Fixed memory leak of s_testcases by calling RoadTest::deleteTests()
qhulltest: The 'add_*_test' functions append the test object to RoadTest::s_testcases
~RoadTest: declare virtual for Q_OBJECT, removeAll not needed
user_eg2: Check memory at end of each run
user_r.h: Add QHULL_CRTDBG for invoking Microsoft's memory leak detector
use _MSC_VER instead of QHULL_OS_WIN for QHULL_CRTDBG
Call qh_freeqhull with qh_ALL/!qh_ALL instead of 'True/False'
Include user_r.h with RoadError,h for QHULL_CRTDBG
Invoke _CrtSetDbgFlag... at beginning of program
Moved user_r.h/libqhull_r.h/qhull_ra.h as first include (for QHULL_CRTDBG)
Moved QHULL_OS_WIN from qhull_ra.h to user_r.h
Removed __CYGWIN__ from QHULL_OS_WIN (same as Qt's qglobal.h)
- check_dupridge: A bounding box is not sufficient to avoid dupridge errors
- qh_findbestneighor: Error if qh.CENTERtype is qh_ASvoronoi (i.e., no merging now)
- qh_printstatlevel: Remove unused parameter, 'start'
- QhullLinkedList::last() and back(): Return T instead of T& (T is computed)
- qh-code.htm: "How to convert code to reentrant Qhull"
Update "Nearly coincident points on an edge"
Add 2012 size of data structures to "Qhull on 64-bit computers"
- html/index.htm: Add CGAL to "When to use"
- qh-optq.htm: Add documentation for option 'Q12'
- Move suggestions from Changes.txt to qh-code.htm#enhance
- user_r.h: Fixed qh-us_r.html links
- Fixed links in html pages
- QhullIterator and QhullLinkedList: Include <iterator> [B. Boeckel]
- Moved include file for each C++ source file to the top of the includes
- Prepend cpp includes with "libqhullcpp/"
- RoadLogEvent includes RoadLogEvent.h
- QhullIterator.h: Only QHULL_DECLARE_SEQUENTIAL_ITERATOR is used.
- Compared src/libqhull/* to src/libqhull_r/* and resolved differences
- qh_printpoint in io.c skips qh_IDnone like io_r.c
- qhull_p-exports.def: Added three missing exports
- set_r.h: Removed countT. Too many issues
- libqhull_r/Makefile: Add help prompts to 'make qtest'
- libqhull.pro: Add '../libqhull/' to sources and headers
- libqhull/Makefile: Fixed -I,./,,/src
- qhull-zip.sh: Add CMakeModules to tarball [C. Rosenvik]
- CMakeLists.txt: Add targets qhullp and user_egp for qh_QHpointer and libqhull_p
- Reorganized 'make help'
- Makefile cleanall: Delete testqset and qhulltest from bin/
- Fix filetype of Unix-only files
- Fix Unix line endings for Makefile and check in qhull-zip.sh
- Fix Windows line-endings and check in qhull-zip.sh
- qhull-zip.sh: Check for Unix text files
------------
Qhull 2015.1 2016/01/03 (7.1.0)
- Add Rbox option 'Cn,r,m' to add nearly coincident points. Trigger for duplicate ridges
- Add Qhull option 'Q12' to ignore error on wide merge due to duplicate ridge
- qh_findbestlower: Call qh_findfacet_all to fix rare "flipped or upper Delaunay" error QH6228.
QH6228 input provided by J. Metz. Reported (date order): L. Fiaschi, N. Bowler, A. Liebscher, V. Vieira, N. Rhinehart, N. Vance, P. Shafer
- qh_check_dupridge: Check if wide merge due to duplicate ridge from nearly coincident points
- qh_initialhull: Fix error messages for initial simplex is flat
- qh_determinant: increased 2-d and 3-d nearzero by 10x due to a counter-example
- rbox: Add qh_outcoord() to output coordinates w/ or w/o iscdd
- qh_meminit (mem.c): Add call to qh_memcheck
- Compare libqhull/... to libqhull_r/... and resolve differences
- Update builds for DevStudio (qhull.sln for msdev 2005..2009, qhull-32.sln and qhull-64.sln for recent releases)
- qh-impre.htm: Add a section about precision errors for 'Nearly coincident points on an edge'
- html/index.htm#geomview: Document how to install, build, and use Geomview.
- html/index.htm: Emphasize program links and move related urls to end
- qhull/index.htm: Emphasize manual, geomview, and imprecision
- Fix documentation links in libqhull_r/index.htm
- Add 'Functions' link to documentation headers
- Change '<A>...</A>' to '<a>...</a>'
- libqhull_r/index.htm -- Add instructions for configuring web browsers for source links.
- libqhull_r/ -- Fix source links for ..._r.htm files
------------
Qhull 2015.0.7 2015/11/09 (7.0.7)
- Fix return type of operator-> in QhullLinkedList and other collection classes [F. Jares]
- Fix return types for QhullLinkedList
- Fix return types for QhullPoints
- Simplify return type for Coordinates::operator[] (same as QList)
- Add const to operators for QhullSet::iterator and add documentation
- Coordinates.h: Fix return types for operations of iterator and const_iterator
- Drop use of Perforce changelist number in qhull_VERSION of CMakeLists.txt
- Rename the md5sum files as *.tgz.md5sum instead of *-tgz.md5sum
- Fix build dependency for testqset_r [asekez]
- rbox.c depends on Qhull due to qh_lib_check which uses qh_version2 for error messages
- QhullFacet_test.cpp: Annotate Qhull invocations. Allows their repetition.
- QhullFacet_test.cpp: Adjust epsilon on distance tests
- Do not create libqhullcpp as a shared library. Qhull C++ classes may change layout and size.
- qhull-cpp.xml: Make a relative path to road-faq.xsl
------------
Qhull 2015.0.6 2015/10/20 (7.0.6.2013)
- In the libraries, exit() is only called from qh_exit(). qh_exit may be redefined.
- Add qh_fprintf_stderr to usermem.c. May be overridden to avoid use of stderr [D. Sterratt]
Add usermem to testqset builds
Used by qh_fprintf_rbox
- Remove most instances of stderr/stdout from libqhull, libqhull_r, and libqhullcpp [D. Sterratt]
qh_fprintf_stderr may be redefined. qh_meminit and qh_new_qhull use stderr as the default ferr
- qh_initflags: Use qh.fout instead of stdout for 'TO file'. A library caller may define a different qh.fout.
- qh_settemppush: Call qh_fprintf() instead of fprintf() on error.
- Rename qh_call_qhull as "Qhull-template" from user.c. Updated its references.
- qh-code.htm: "How to avoid</a> exit(), fprintf(), stderr, and stdout"
- html/index.htm: Fix table of contents for qh-code
- libqhull_r/index.htm: Rewrite introduction to Reentrant Qhull
- qh-faq.htm: Rewrite "Can Qhull use coordinates without placing them in a data file?"
- qh-get.html: Link to github
- Remove qhull_interface.cpp from the documentation
------------
Qhull 2015.0.5 2015/10/12 (7.0.5.1995)
- qh_new_qhull: default 'errfile' is 'stderr'. outfile and errfile are optional [B. Pearlmutter]
- qh_new_qhull: returns qh_ERRinput instead of exit() if qhull_cmd is not "qhull ..." [B. Pearlmutter]
- qhalf_r.c,etc: Add clear of qh.NOerrexit
- global.c: gcc 4.4.0 mingw32 segfault cleared by adding comment
- usermem_r-cpp.cpp: Optional file to redefine qh_exit() as throw "QH10003.." [B. Pearlmutter]
qh_exit() is called by qhull_r when qh_errexit() is not available.
- html/index.htm: Add bibliographic reference to Golub & van Loan and other references [R. Gaul]
- qhalf.htm: A halfspace is the points on or below a hyperplane [D. Strawn]
- qh-opto.htm#n: Defined inside, outside, on, above, and below a hyperplane [D. Strawn]
- qhalf.htm#notes: Recast the linear program using negative halfspaces (as used by Qhull) [D. Strawn]
- qhull_a.h: Fix comment '#include "libqhull/qhull_a.h" [fe rew]
- build/qhull*.pc.in: Templates for pkg-config (derived from Fedorra) [P. McMunn]
https://bitbucket.org/mgorny/pkg-config-spec/src/c1bf12afe0df6d95f2fe3f5e1ffb4c50f018825d/pkg-config-spec.txt?at=master&fileviewer=file-view-default
- Makefile: Remove user_eg3.o from LIBQHULLCPP_OBJS
- Makefile: Add .h dependencies for unix_r.o, etc.
- libqhull/Makefile: Fix build of rbox
- libqhull_r/Makefile: Fix build -I
- qhull.sln/user_eg3: Add dependency on libcpp
- Removed bin/libqhull_r.dll (should be qhull_r.dll)
- Removed build/qhulltest.vcproj (see build/qhulltest/qhulltest.vcproj)
------------
Qhull 2015.0.4 2015/9/30 (7.0.4.1984)
- qh-get.htm: Unix tarball includes version number (e.g., qhull-2015-src-7.1.0.1940.tgz) [Hauptman]
- qglobal.c: Add qh_version2 with Unix version for "-V" option [Hauptman]
- build/qhull-32.sln, *-32.vcxproj: Add Visual Studio 32-bit build for 2010+
- build/qhull-64.sln, *-64.vcxproj: Add Visual Studio 64-bit build for 2010+ [G. Lodron]
- make-vcproj.sh: Restore to eg/... It is required for Visual Studio builds
- README.txt: updated builds and reentrant Qhull
- Add documentation for QHULL_LIB_CHECK
- qh_lib_check: Check for unknown QHULL_LIB_TYPE
- qh-code.htm: Add memory requirements for 32- and 64-bit
------------
Qhull 2015.0.3 2015/9/22
- qh_mem, qh_merge: Log before 'delete' instead of afterwards [Coverity, K. Schwehr]
- qh_merge: Test for NULL horizon in qh_checkzero [Coverity, K. Schwehr]
- qh_matchneighbor: Check for matchfacet not a neighbor of facet [Coverity, K. Schwehr]
- qh_triangulate: Explicit check for visible==NULL [Coverity, K. Schwehr]
- qh_findbestfacet (unused by qhull): Fix test of isoutside [Coverity, K. Schwehr]
- qh_check_maxout: Check bestfacet!=0 for logging its id [Coverity, K. Schwehr]
- qh_nearvertex: Check for bestvertex not found [Coverity, K. Schwehr]
- qh_checkfacet: Check for missing neighbors of simplicial facets [Coverity, K. Schwehr]
- qh_setdelnth: Check 'nth' before using it [Coverity, K. Schwehr]
- Annotate code for Coverity warnings (most of these protected by qh_errexit) [K. Schwehr]
- qh_printfacet3math: explicit format string (duplicates change to io.c) [B. Pearlmutter]
- libqhull_r.h: fix spelling error (duplicates change to libqhull.h) [B. Pearlmutter]
- unix_r.c: fix spelling error (duplicates change to unix.c) [B. Pearlmutter]
- qhull_a.h: define qhullUnused() only if defined(__cplusplus) [R. Stogner]
- qh_version: Use const char str[]= "string" instead of const char * str= "string" [U. Drepper, p. 27]
- qh_newvertex: Use UINT_MAX instead of 0xFFFFFFFF
- qh_newridge: Use UINT_MAX instead of 0xFFFFFFFF
- Reviewed FIXUP notes
- QhullRidge_test: t_foreach use 'foreach(const QhullVertex &v, vertices)
- Made '#include "RoadTest.h" consistent across all C++ tests
- qh-code.htm: May also use libqhull_r (e.g., FOREACHfacet_(...))
- qh-get.htm: Add list of download build repositories
- Add CMakeModules/CheckLFS.cmake: Enables Large File Support [B. Pearlmutter]
- Makefile: Use -fpic at all times instead of -fPIC, [U. Drepper p. 15]
------------
Qhull 2015.0.2 2015/9/1
- global_r.c: Fixed spelling of /* duplicated in...qh_clear_outputflags */ [K. Schwehr]
- Replaced Gitorious with GitHub
- Moved 'to do' comments into Changes.txt
------------
Qhull 2015.0.1 2015/8/31
Source code changes
- Increased size of vertexT.id and ridgeT.id to 2^32 [H. Strandenes, C. Carson, K. Nguyen]
Reworded the warning message for ridgeT.id overflow. It does not affect Qhull output
- Add qh_lib_check to check for a compatible Qhull library.
Programs should call QHULL_LIB_CHECK before calling Qhull.
- Include headers prefixed with libqhull/, libqhull_r/, or libqhullcpp/
- Renamed debugging routines dfacet/dvertex to qh_dfacet/qh_dvertex
- Rewrote user_eg, user_eg2, and user_eg3 as reentrant code
- Renamed 'qh_rand_seed' to 'qh_last_random'. Declare it as DATA
- qh_initqhull_start2 sets qh->NOerrexit on initialization
User must clear NOerrexit after setjmp()
Other source code changes
- Define ptr_intT as 'long long' for __MINGW64__ [A. Voskov]
- poly_r.c: initialize horizon_skip [K. Schwehr]
- Removed vertexT.dim and MAX_vdim. It is not used by reentrant Qhull.
- Removed qhull_inuse. Not used by C++
- Removed old __MWERKS__/__POWERPC__ code that speed up SIOUX I/O
- Moved #include libqhull/... before system includes (e.g., <stdio.h>
- Comment-out _isatty declaration. Avoids "C4273 ... inconsistent dll linkage"
- Add random.h/random_r.h as an include file to random.c/random_r.c
- Rename rbox routines to qh_roundi/qh_out1/qh_out2n/qh_out3n
- Rename dfacet and dvertex to qh_dfacet and qh_dvertex
- Replace 'qhmem .zzz' with 'qhmem.zzz'
- Removed spaces between function name and parentheses
- Rename 'enum statistics' to 'enum qh_statistics'
- Declare rbox as DATA in qhull-exports.def and qhull_p-exports.def
- In comments, use 'qh.zzz' to reference qhT fields
- In qh_fprintf, use qhmem.ferr to report errors
- qh_fprintf may be called for errors in qh_initstatistics and qh_meminit
- qh_pointid returns qh_IDnone, qh_IDinterior, qh_IDunknown in place of -3, -2, -1 resp.
- getid_() returns qh_IDunknown in place of -1
- After qh_meminit, qhmem.ferr is non-zero (stderr is the default)
- Update qh_MEMalign in testqset.c to user.h (with realT and void*)
- Split rboxT into a header file
- Add rboxlib.h to libqhull_a.h
- Rename PI to qh_PI and extend to 30 digits
- Rename MAXdim to qh_MAXdim
- Change spacing for type annotations '*' and '&' in C++ header files
- Test for !rbox_output/cpp_object in qh_fprintf_rbox
- Remove 'inline' annotation from explicit inline declarations
- Column 25 formatting for iterators, etc.
- Use '#//!\name' for section headers
- QhullFacet.cpp: zinc_(Zdistio);
- Clear qhT.ALLOWrestart in qh_errexit
- Replace longjmp with qh_errexit_rbox in qh_rboxpoints
- Add jmpExtra after rbox_errexit to protect against compiler errors
- Add qh.ISqhullQh to indicate initialization by QhullQh()
- Add library warnings to 'rbox D4', user_eg, user_eg2, user_eg3
- Add headers to q_eg, q_egtest, and q_test
- Check that qh.NOerrexit is cleared before call to qh_initflags
Qhull documentation
- README.txt: Added references to qh-code.htm
- README.txt: Added section 'Calling Qhull from C programs'
- qh-code.htm: Moved Performance after C++ and C interface
- qh-code.htm: Moved Cpp Questions to end of the C++ section
- qh-code.htm: Fixed documentation for 'include' path. It should be include/libqhull
- qconvex.htm: Fixed documentation for 'i'. It triangulates in 4-d and higher [ref]
- Clarified qhalf space documentation for the interior point [J. Santos]
- rbox.c: Version is same date as qh_version in global.c
- gobal_r.c: Version includes a '.r' suffix to indicate 'reentrant'
Qhull builds
- Development moved to http://github.com/qhull/qhull
git clone git@github.com:qhull/qhull.git
- Exchanged make targets for testing.
'make test' is a quick test of qhull programs.
'make testall' is a thorough test
- Added 'make help' and 'make test' to libqhull and libqhull_r Makefiles
- CMakeLists.txt: Remove libqhull, libqhull_r, and libqhullcpp from include_directories
- CMakeLists.txt: Add qhull_SHAREDR for qhull_r
- CMakeLists.txt: Retain qhull_SHARED and qhull_SHAREDP (qh_QHpointer)
- CMakeLists.txt: Move qhull_SHARED and qhull_SHAREDP (qh_QHpointer) to qhull_TARGETS_OLD
Drop qhull_STATICP (use qhull_SHAREDP or qhull_STATIC)
Set SOVERSION and VERSION for shared libraries
- Move qhull_p-exports.def back to libqhull
- Switched to mingw-w64-install for gcc
- Improved prompts for 'make'
- qhull-all.pro: Remove user_eg3.cpp from OTHER_FILES
- libqhull.pro: Ordered object files by frequency of execution, as done before
- Add the folder name to C++ includes and remove libqhullcpp from INCLUDEPATH
- Changed CONFIG+=qtestlib to QT+=testlib
- Changed Makefile to gcc -O3 (was -O2)
- Changed libqhull/libqhull_r Makefiles to both produce rbox, qhull, ..., user_eg, and user_eg2
- Removed Debian 'config/...'. It was needed for Qhull 2012.
libqhull_r (reentrant Qhull)
- Replaced qh_qh with a parameter to each procedure [P. Klosterman]
No more globally defined data structures in Qhull
Simplified multithreading and C++ user interface
All functions are reentrant (Qt: "A reentrant function can ... be called simultaneously from multiple threads, but only if each invocation uses its own data.")
No more qh_QHpointer.
See user_eg3 and qhulltest
New libraries
libqhull_r -- Shared library with reentrant sources (e.g., poly_r.h and poly_r.c which replace libqhull's poly.h and poly.c)
libqhullstatic_r -- Static library with the same sources as libqhull_r
libqhullcpp -- The C++ interface using libqhullstatic_r (further notes below)
New executables
testqset_r -- Test qset_r.c (the reentrant version of qset.c
Source code changes for libqhull_r
- Add qh_zero() to initialize and zero memory for qh_new_qhull
- Remove qh_save_qhull(), qh_restore_qhull(), and qh.old_qhstat from global_r.c
- Remove qh_freeqhull2() (global_r.c)
- Remove qh_freestatistics() (stat_r.c)
- Remove qh_compare_vertexpoint (qhT is not available, unused code)
- Remove conditional code for __POWERPC__ from unix_r.c and rbox_r.c
- Move qh_last_random into qh->last_random (random_r.c)
- Rename sources files with a '_r' suffix. qhull_a.h becomes qhull_ra.h
- Replace 'qh' macro with 'qh->'
- Replace global qhT with parameter-0
- Add qhmemT to beginning of qhT. It may not be used standalone.
- Add qhstatT to end of qhT
- Remove qhull_inuse
- Change qhmem.zzz to qh->qhmem.zzz
- Replace qh_qhstat with qh->qhstat
- Remove qh_freestatistics
- Replace qh_last_random with qh->last_random
- Replace rboxT with qh->rbox_errexit, rbox_isinteger, rbox_out_offset
- Replace rbox.ferr/fout with qh->ferr/fout
- No qh for qh_exit, qh_free, qh_malloc, qh_strtod, qh_strtol, qh_stddev
- New qmake include files qhull-app-c_r.pri, qhull-app-shared_r.pri, qhull-libqhull-src_r.pri
- Replace 'int' with 'countT' and 'COUNTmax' for large counts and identifiers
- qhset converted to countT
- Removed vertexT.dim -- No longer needed by cpp
Removed MAX_vdim
- Guarantee that qh->run_id!=0. Old code assumed that qh_RANDOMint was 31 bits
Changes to libqhullcpp
- Added QhullVertexSet.h to libqhullcpp.pro and libqhullpcpp.pro
- QhullVertexSet: error if qhsettemp_defined at copy constructor/assignment (otherwise double free)
- Enable QhullSet.operator=. Copy constructor and assignment only copies pointers
- Changed QhullPoint.operator==() to sqrt(distanceEpsilon)
- Added assignment of base class QhullPoints to PointCoordinates.operator=
- Enable QhullPoints.operator=
- Rename PointCoordinates.point_comment to describe_points
- Add 'typename T' to definition of QhullSet<T>::value()
C++ interface
- Reimplemented C++ interface on reentrant libqhull_r instead of libqhull
- Prepend include files with libqhullcpp/
- Replaced UsingLibQhull with QhullQh and macro QH_TRY
Removed UsingLibQhull.currentAngleEpsilon and related routines
Removed UsingLibQhull_test.cpp
Replaced globalDistanceEpsilon with QhullQh.distanceEpsilon
Replaced globalAngleEpsilon with QhullQh.angleEpsilon
Moved UsingQhullLib.checkQhullMemoryEmpty to QhullQh.checkAndFreeQhullMemory
Replaced FACTORepsilon=10 with QhullQh.factor_epsilon=1.0
- To avoid -Wshadow for QhullQh*, use 'qqh' for parameters and 'qh()' for methods
- Moved messaging from Qhull to QhullQh
- Add check of RboxPoints* in qh_fprintf_rbox
- Renamed Qhull.initializeQhull to Qhull.allocateQhullQh
Added qh_freeqhull(!qh_ALL) as done by unix.c and other programs
- Moved QhullPoints.extraCoordinatesCount into QhullPoints.cpp
- Replaced section tags with '#//!\name ...'
- Removed qhRunId from print() to ostream.
- Removed print() to ostream. Use '<< qhullPoint' or '<< qhullPoint.print("message")'
C++ interface for most classes
- Remove qhRunId
- Add QhullQh *qh_qh to all types
Pointer comparisons of facetT,etc. do not test corresponding qh_qh
Added to end of type for debugging information, unless wasteful alignment
- Add QhullQh * to all constructors
- All constructors may use Qhull & instead of QhullQh *
- For inherited QhullQh types, change to 'protected'
- Renamed 'o' to 'other' except where used extensively in iterators
- Except for conditional code, merged the Conversion section into GetSet
- Removed empty(). Use isEmpty() instead
- Add operator= instead of keeping it private
- print_message=0 not allowed. Use "" instead.
- Rename isDefined() to isValid() to match Qt conventions
C++ interface by class
- Coordinates
Removed empty(). Use isEmpty() instead
Added append(dim, coordT*)
Reformated the iterators
Convert to countT
- PointCoordinates
Added constructors for Qhull or QhullQh* (provides access to QhullPoint.operator==)
Removed PointCoordinates(int pointDimension) since PointCoordinates should have a comment. Also, it is ambiguous with PointCoordinates(QhullQh*)
Renamed point_comment to describe_points
Convert to countT
- Qhull
Remove qhull_run_i
Remove qh_active
Replace property feasiblePoint with field feasible_point and methods setFeasiblePoint/feasiblePoint
Returns qh.feasible_point if defined
Moved useOutputStream to QhullQh use_output_stream
Renamed useOutputStream() to hasOutputStream()
Replaced qhull_dimension with qh->input_dim //! Dimension of result (qh.hull_dim or one less for Delaunay/Voronoi)
Removed global s_qhull_output= 0;
Move qhull_status, qhull_message, error_stream, output_stream to QhullQh
Renamed qhullQh() to qh()
Added check of base address to allocateQhullQh(), Was not needed for qhullpcpp
- QhullFacet
Constructor requires Qhull or QhullQh* pointer
Convert to countT
Dropped implicit conversion from facetT
Dropped runId
Add print("message") to replace print()
- QhullFacetList
Constructor requires Qhull or QhullQh* pointer
Convert to countT
Dropped runId
- QhullFacetSet
Removed empty(). Use isEmpty() instead
Constructor requires Qhull or QhullQh* pointer
Convert to countT
Dropped runId
Add operator=
Implement print("message")
- QhullHyperplane
Add hyperplaneAngle() method
Rewrite operator== to use hyperplaneAngle()
Reorganize fields to keep pointers aligned
Except for default constructor requires Qhull or QhullQh* pointer
Enable copy assignment
Reorganized header
- QhullLinkedList
Add operator=
Removed empty(). Use isEmpty() instead
Convert to countT
iterator(T) made iterator(const T &)
const_iterator(T) made const_iterator(const T &)
const_iterator(iterator) made const_iterator(const iterator &)
- QhullPoint
Add constructors for Qhull or QhullQh* pointer (for id() and operator==)
Add defineAs(coordT*)
Add getBaseT() and base_type for QhullSet<QhullPoint>
Added checks for point_coordinates==0
Removed static QhullPoint::id(), use QhullPoint.id() instead
distance() throws an error if dimension doesn't agree or if a point is undefined
Convert to countT
If !qh_qh, operator==() requires equal coordinates
Use cout<<p instead of cout<<p.print()
Reorganized
- QhullPoints
Add constructors for Qhull and QhullQh* (for qh.hull_dim, QhullPoint::operator==)
Remove QhullPoints(int pointDimension) since it is ambiguous with QhullPoints(QhullQh *qqh)
Add operator=
Removed empty(). Use isEmpty() instead
Convert to countT
operator==() tests if pointers are the same. Ituses distanceEpsilon if qh_qh is defined
Reorganized
- QhullPoints::Iterator and ConstIterator
Removed default constructors
Add constructors for Qhull and QhullQh* (for qh.hull_dim, QhullPoint::operator==)
Moved test of dimension from QHULL_ASSERT to operator==
Added QHULL_ASSERT of qh_qh
Convert to countT
- QhullPointSet
Constructor requires Qhull or QhullQh* instead of dimension()
Add operator=
Removed empty(). Use isEmpty() instead
Convert to countT
Always print print_message
Drop print(). Replace with print("")
- QhullQh
Added methods hasOutputStream(), disableOutputStream(), and enableOutputStream() (was Qhull UseOutputStream)
Add test of qh.NOerrexit to maybeThrowQhullMessage()
Add qhull_status, qhull_message, error_stream, output_stream from Qhull
Add factor_epsilon
- QhullRidge
Constructor requires Qhull or QhullQh* pointer
Dropped implicit conversion from ridgeT
Converted otherFacet() to 'const &'
Converted nextRidge3d() to 'const &'
Message for '<< QhullRidge' replaces " - " instead of preceding it
- QhullSet
Removed empty(). Use isEmpty() instead
Constructor requires Qhull or QhullQh* pointer
Convert to countT
Add operator=
- QhullVertex
Constructor requires Qhull or QhullQh* pointer
Convert to countT
Dropped implicit conversion from vertexT
Add message to '<< QhullVertex'
- QhullVertexSet
Removed empty(). Use isEmpty() instead
Constructor requires Qhull or QhullQh* pointer
Convert to countT
- UsingQhullLib
Removed
Replace setGlobalDistanceEpsilon with setFactorEpsilon
Replace globalDistanceEpsilon with distanceEpsilon
------------
Qhull 2012.1 2012/02/18 6.3.1.1494
- Fix CMakeLists for libqhull with MATCHES [P. Gajdos]
------------
Qhull 2012.1 2012/02/18 6.3.1.1490
Code changes
- Require option 'Qz' for Delaunay triangulation/Voronoi diagram
of cocircular/cospherical points [D. Sheehy]
- qh_errexit: Do not call qh_printsummary or qh_printstats on qh_ERRinput
- Change error QH6227 (all degenerate) from qh_ERRinput to qh_ERRprec
- Change error QH6159 (ID overflow) from qh_ERRinput to qh_ERRqhull
- eg/q_eg, q_egtest, q_test: Run if qconvex is in $PATH [M. Atzeri]
Build changes [M. Atzeri]
- Install to share/doc/qhull instead of share/doc/packages/qhull
- On Unix systems, install to share/man/man1 instead of man/man1
- CMakeLists: Remove the installation of user_eg* and testqset
- CMakeLists: Remove VERSION from qhull executables and libraries
- CMakeLists: Define qhull_SOVERSION instead of qhull_MAJOR
- CMakeLists: Set SOVERSION for shared libraries
- Rename libraries to qhull, qhull_d, qhull_p, and qhull_pd
libqhull6_p.vcproj is now libqhull_p.vcproj
mingw builds as libqhull.dll
cygwin builds as cygqhull-6.dll
linux builds as libqhull.so.6.3.1 with symbolic link as libqhull.so
- Developers using qhull 2011:
libqhull6.so is now libqhull_p.so. Do not use libqhull.so.
qhull6.dll is now qhull_p.dll. Do not use qhull.dll.
- Merged road/ into libqhullcpp/ and qhulltest/
Moved RoadLogEvent.* and RoadError.* to libqhullcpp
Moved RoadTest.* to qhulltest (requires Qt)
Installed RoadTest.h in libqhullcpp
Doc changes
- index.htm: Mathworks uses qhull for n-d
- qhull.htm: Fix qhull for qconvex
- qdelaun.htm/qvoronoi.htm: Use option 'Qz' for circular/cospherical inputs
- make help: Display targets
- Makefile: Better messaging
------------
Qhull 2012.1 2012/02/02 6.3.0.1483
Bug fixes
- Fixed qset.c for -fno-strict-aliasing. This gcc option is no longer needed
(disallow two pointers of differing types to the same memory location)
- Fixed error in qh_setappend_set if first set full and second set empty
- qh_setdelnth, qh_setdelnth_sorted: fixed wording of error message
- qh_setcheck: error message listed size and max backwards.
- qh_setequal: Allow NULL set as documented
- qh_setindex: Allow NULL set as documented
- qh_settemppush: report error if NULL
Code changes
- Add testqset: low level test of qset.c with mem.c
- qh_setendpointer: Implements QSet::endPointer()
- Assigned unique error code for qh_gethash
Build changes
- Added qhull.dll(.so) for Octave and other Debian builds
The global data structure qh_qh is statically defined (no qh_QHpointer)
Linked user_eg2 with qhull.dll (libqhull.so) instead of qhullstatic
Added qh_dllimport to libqhull.h for qhull.dll with MSVC
Changed qhull-app-shared.pri to use libqhull (without qh_QHpointer)
- Renamed libqhull6.so to libqhull6_p.so
Renamed qhull6.dll to qhull6_p.dll
The _p libraries (e.g., libqhull6_p.so) require -Dqh_QHpointer
Renamed qhull6.vcproj to libqhull6_p.vcproj
Added libqhullp/libqhullp.pro for shared library (libqhull6_p.so)
Added qhull-app-sharedp.pri for shared libraries with qh_QHpointer
- Install libqhull/*.htm files into include/libqhull
- Removed libqhull/qhull.h-deprecated [J. Eaton]
- Other changes to Makefile builds
Added 'make qtestall' as a smoketest of each qhull program
src/libqhull/Makefile: Use 'ar -rs ...' instead of ranlib
src/libqhull/Makefile: Fixed targets for cleanall
- Other changes to DevStudio builds
Moved pdb files for qhull libraries to lib/
AdditionalIncludeDirectories: Removed ../src/libqhullcpp
Use build-cmake/ for the DevStudio CMake build
- Other changes to Qt builds
Renamed qhull-libsrc.pri to qhull-libqhull-src.pri
- Added explicit d2u conversions to qhull-zip.sh
- Fixed \n vs. \r\n issues for Windows source files
Draft of Debian/AutoConf build (untested)
- Adjusted the Makefile.am's for the new directory structure.
- Added testqset to bin_PROGRAMS
- config/bootstrap.sh copies program sources into src/libqhull
- Kept qh_QHpointer=0 (static global data structure, qh_qh). It is faster.
Planning a new interface (qhull7?) which passes qh_qh as a parameter
- Added config/changelog from the 2003.1 Debian build
- Moved the debian/patches directory to config/
Optional patches to change smoketest message and turn on qh_QHpointer
- Deleted the debian directory. It was the old Debian build from 2003.1
Rafael Laboissiere's config directory replaced this build..
- Deleted Make-conf.sh (also the old Debian build)
Doc changes
- FAQ: Updated notes on computing volume of a Voronoi region
- Added direct link to ACM Digital Library for downloading the qhull paper
- Added link to Qhull in R
- qset.c: Updated notes about NULL sets
- qh_setappend: clarify qh_setappend for NULL newelem
- qh_setdellast: Fix head note
- Add build/README.txt
- Add uninstall instructions to README.txt and CMakeLists.txt
- Added instructions to create build/*.vcproj to CMakeLists.txt
- Update copyright to 2012
- Updated page links. Added Google books, patents, and blogs.
-----------
Qhull 2009.1.3 2011/12/06
configure: Add -fno-strict-aliasing if $GCC, Required for gcc 4.1+
------------
Qhull 2011.2 2011/11/29 6.2.1.1446
Bug fixes
- qh_new_qhull: Call qh_prepare_output if !outfile [A. Aldoma]
No effect on qhull users since qh_prepare_output is always called.
- Replace Qhull-go.pif with Qhull-go.lnk for Windows 7 64-bit [lots]
- Error if qh_newhashtable, qh_setnew, or qh_memalloc overflows [X. Cheng]
For example, 'rbox 64 D32' overflows hash table for qh_matchnewfacets
Qhull uses 32-bit ints for identifiers, counts, and sizes. See "WARN64"
- q_eg, q_test: change tail +3 to tail -n +3 [N. Dubray, M. Atzeri]
- Qhull-go.bat: Changed 'cmd' to '%comspec%'
Build changes
- Added src/libqhull/Makefile for simple gcc build of executables and lib
- qhulltest.vcproj: Replaced full path to QT with $QTDIR (e.g., c:/qt/4.7.4)
- Split userprintf_rbox.c from userprintf.c,
Otherwise qhull brings in rboxlib and rbox brings in libqhull
- Makefile: qhullx target must be after LIBQHULLS_OBJS
- Makefile: Explicitly list rbox dependencies for qhullx target
- MBorland: Fixed tabs
- Placed $LIBQHULLS_OBJS in same order. Frequently called ones together.
- Update file lists for Make-config.sh [O. Lahaye]
- CMakeLists: add README.txt,etc. to DOC_INSTALL_DIR [M. Atzeri]
- Restored qhull.h-deprecated.
qhull.h conflicts with Qhull.h on Windows systems [C. Abela]
- make-config.sh: Add warning that it is out-of-date
- Remove extra space in '#! /bin/sh' in q_eg, etc. [P. Cheeseman]
Source changes
- libqhull.h: Added qh_True and qh_False for True/False [A. Mutzel]
Did not remove or replace True/False since it is used everywhere
- Moved error message from qh_argv_to_command to caller. Avoids dependency.
- user_eg3.c: Use '10 D2' as default rbox (e.g., 'user_eg3 rbox qhull d')
- user.c, user_eg2.c: Add test of qh_qh as done in user_eg.c
- q_test: Removed duplicate test of qhull C-0.02
Documentation
- index.html: Added ACM Authorizer link to ACM Trans. Math. Software
- Split Delaunay and Voronoi FAQs
- FAQ: How to compute the volume of a Voronoi region [C, Brinch]
- Add 'FS' to qconvex prompt (total area and volume)
- Add clarification to 'Fv' about corner input sites [O. Can]
- Qhull-go.bat: Removed out-of-date advice. Added title.
- qh-code.htm: Updated the discussion of multi-threading for C++ [I. Pirwani]
Qhull 2009.1.2 2011/11/21
- Revert to LF line endings [P. Cheeseman]
- Remove out-of-date material from qhull-go.bat
- Replaced QHULL-GO with a lnk file
Qhull 2011.1 2011/05/23 6.2.0.1385 (exe/dll files unchanged)
- delaunay.vcproj: Fixed qhullstatic_d.lib for debug and minrelsize builds
- Did not redate the distribution
Qhull 2011.1 2011/05/18 6.2.0.1385 (exe/dll files unchanged)
- Add 'm' library to shared and static targets on Unix [A. Bouchard]
Qhull 2011.1 2011/05/14 6.2.0.1383 (exe/dll files unchanged)
- PointCoordinates.cpp: Add #include <iterator> [R. Richter, S. Pasko]
- Remove deprecated libqhull/qhull.h
Use libqhull/libqhull.h instead. Avoids confusion with libqhullcpp/Qhull.h
- Makefile: Add LIBDIR, INCDIR, and DESTDIR to install [L.H. de Mello]
Separate MAN install from DOC install
Create install directories
Installs headers to include/libqhull, include/libqhullcpp, include/road
- CMakeLists.txt: Add MAN_INSTALL_DIR for qhull.1 and rbox.1 man pages
Add RoadTest.h to include/road for Qt users (road_HEADERS)
- Renamed md5sum files to avoid two extensions
- qh-get.htm: Add Readme links and 2009.1 note.
- qh-optf.htm: Fix link
- index.htm: Updated Google Scholar link
- qhull-zip.sh: Improved error message.
------------
Qhull 2011.1 2011/04/17 6.2.0.1373
Changes to deliverables
- qvoronoi: Deprecated 'Qt' and 'QJn'. Removed from documentation and prompts.
These options produced duplicate Voronoi vertices for cospherical data.
- Removed doskey from Qhull-go.bat. It is incompatible with Windows 7
- Added 'facets' argument to user_eg3.cpp
- user_eg links with shared library
- qhulltest.cpp: Add closing prompt.
Changes to build system
- Reorganized source directories
- Moved executables to bin directory
- Add CMake build for all targets (CMakeFiles.txt) [M. Moll assisted]
- Add gcc build for all targets (Makefile)
- Fixed location of qhull.man and rbox.man [M. Moll]
- Add DevStudio builds for all targets (build/*.vcproj)
- Added shared library (lib/qhull6.dll)
Added qh_QHpointer_dllimport to work around problems with MSVC
- Added static libraries with and without qh_QHpointer (lib/qhullstatic.lib)
- Added eg/make-vcproj.sh to create vcproj/sln files from cmake and qmake
- Document location of qh_QHpointer
- Use shadow build directory
- Made -fno-strict-aliasing conditional on gcc version
- Added src/qhull-app-cpp.pri, src/qhull-app-c.pri, etc. for common settings
- Add .gitignore with ignored files and directories.
- Use .git/info/exclude for locally excluded files.
- Fixed MBorland for new directory structure
- cleanall (Makefile): Delete 'linked' programs due to libqhull_r and libqhull/Makefile
Changes to documentation
- qvoronoi.htm: Remove quotes from qvoronoi example
- qhull-cpp.xml: Add naming conventions
- index.htm: Add Google Scholar references
- qh-optf.htm: Add note about order of 'Fn' matching 'Fv' order [Q. Pan]
- Add patch for old builds in qh-get.htm
- Added C++ compiling instructions to README.txt
- Add instructions for fixing the DOS window
- Changed DOS window to command window
- Fixed html links
- qh-get.htm: Dropped the Spanish mirror site. It was disabled.
Changes to C code
- mem.h: Define ptr_intT as 'long long' for Microsoft Windows _win64 builds.
On Linux and Mac, 'long' is 64-bits on a 64-bit host
- Added qh_QHpointer_dllimport to work around MSVC problem
- qconvex.c,etc.: Define prototype for _isatty
- Define MSG_QHULL_ERROR in user.h
- Move MSG_FIXUP to 11000 and updated FIXUP QH11...
Changes to test code
- Add note to q_test than R1e-3 may error (qh-code.htm, Enhancements)
- Add test for executables to q_eg, etc.
- Fixed Qhull-go.bat. QHULL-GO invokes it with command.com,
Changes to C++ interface
- QhullFacet: Added isSimplicial, isTopOrient, isTriCoplanar, isUpperDelaunay
- Added Qhull::defineVertexFacetNeighbors() for facetNeighbors of vertices.
Automatically called for facet merging and Voronoi diagrams
Do not print QhullVertex::facetNeighbors is !facetNeighborsDefined()
- Assigned FIXUP identifiers
- QhullError: Add copy constructor, assignment operator, and destructor
- Add throw() specifiers to RoadError and QhullError
- Renamed RoadError::defined() to RoadError::isDefined()
- Add #error to Qhull.h if qh_QHpointer is not defined
Changes to C++ code
- Fixed bug reported by renangms. Vertex output throws error QH10034
and defineVertexNeighbors() does not exist.
- Define QHULL_USES_QT for qt-qhull.cpp [renangms]
- Reviewed all copy constructors and copy assignments. Updated comments.
Defined Qhull copy constructor and copy assignment [G. Rivet-Sabourin]
Disabled UsingQhullLib default constructor, copy construct, and copy assign
- Merged changes from J. Obermayr in gitorious/jobermayrs-qhull:next
- Fix strncat limit in rboxlib.c and global.c
- Changes to CMakeLists.txt for openSUSE
- Fixed additional uses of strncat
- Fixed QhullFacet::PrintRidges to check hasNextRidge3d()
- Removed gcc warnings for shadowing from code (src/qhull-warn.pri)
- Removed semicolon after extern "C" {...}
- Removed experimental QhullEvent/QhullLog
- Use fabs() instead of abs() to avoid accidental conversions to int
- Fixed type of vertex->neighbors in qh_printvoronoi [no effect on results]
- Removed unnecessary if statement in qh_printvoronoi
------------
qhull 2010.1 2010/01/14
- Fixed quote for #include in qhull.h [U.Hergenhahn, K.Roland]
- Add qt-qhull.cpp with Qt conditional code
- Add libqhullp.proj
- Add libqhull5 to Readme, Announce, download
- Reviewed #pragma
- Reviewed FIXUP and assigned QH tags
- All projects compile with warnings enabled
- Replaced 'up' glyphs with &#187;
- Moved cpp questions to qh-code.htm#questions-cpp
- Moved suggestions to qh-code.htm#enhance
- Moved documentation requests to qh-code.htm#enhance
- Add md5sum file to distributions
- Switched to DevStudio builds to avoid dependent libraries, 10% slower
Removed user_eg3.exe and qhullcpp.dll from Windows build
Fix qhull.sln and project files for qh_QHpointer
- Add eg/qhull-zip.sh to build qhull distribution files
------------
qhull 2010.1 2010/01/10
- Test for NULL fp in qh_eachvoronoi [D. Szczerba]
qhull 2010.1 2010/01/09
Changes to build and distribution
- Use qh_QHpointer=0 for libqhull.a, qhull, rbox, etc.
Use -Dqh_QHpointer for libqhullp.a, qhullcpp.dll, etc.
qh_QHpointer [2010, gcc] 4% time 4% space, [2003, msvc] 8% time 2% space
- Add config/ and project/debian/ for Autoconf build [R. Laboissiere]
from debian branch in git and http://savannah.nongnu.org/cvs/?group=qhull
- Add CMakeLists.txt [kwilliams]
- Fix tabs in Makefile.txt [mschamschula]
- Add -fno-strict-aliasing to Makefile for gcc 4.1, 4.2, and 4.3 qset segfault
- Remove user_eg.exe and user_eg2.exe from Windows distribution
- Order object files by frequency of execution for better locality.
Changes to source
- Remove ptr_intT from qh_matchvertices. It was int since the beginning.
- user.h requires <time.h> for CLOCKS_PER_SEC
- Move ostream<<QhullFacetList from inline to compiled.
- Removed ConvexHull/ from git. Not used.
------------
qhull 2009.1.1 2010/01/09
- Patch release of 2009.1.
qh_gethash allowed a negative result, causing overwrite or segfault
See git:qhull/project/patch/qhull-2003.1/poly.c-qh_gethash.patch
Compared results of q_test, q_eg, q_egtest with patched poly.c, qhull-2003.1
------------
qhull 2010.1 2010/01/07
- Assign type to qh.old_qhstat and memT.tempstack [amorilia]
- Replace tabs with spaces.
- Fix qh_pointid in case ptr_intT is unsigned
qhull 2010.1 2010/01/06
- Fixed serious bug in qh_gethash [poly.c]
- Documentation and build system are incomplete (see above)
- First release of C++ interface [qh-code.htm]
- Development moved to http://gitorious.org/qhull
git clone git@gitorious.org:qhull/qhull.git
- Did not fix conformant tesselations for 'Qt'.
For details, see http://www.qhull.org/news#bugs of May 2007 and Dec 2006.
- Use g++ builds for Windows distribution (10% faster than msvc2005)
Combined vcproj/ and qtproj/ into project/
vcproj will be replaced by qmake generated files
------------
qhull 2010.0.3 2010/01/05
Fixed bugs
- 'QJn': Fix qh.STOPcone in qh_build_withrestart(). It was not cleared.
- qh_initqhull_outputflags [global.c]: warn about Qc only if QHULLfinished
otherwise set if needed
qhull 2010.0.2 2010/01/04
Fixed bugs
- qh_gethash [poly.c]: fix sign conversion.
Previously, the result may be negative, leading to a segfault.
The bug is more likely with large address spaces
Reviewed all uses of %(modulo) for remainder with negative arguments
- Reviewed output of q_test and compared to results from 2003.1
Breaking code changes
- Return type of qh_gethash changed from unsigned to int. Matches 'size'
- addhash takes a signed hash
qh_addhash( newelem, hashtable, hashsize, hash )
Code changes
- Test for qh_qh in qh_printf
- Makefile.txt corrected for libqhull build [amorilia]
- Renamed index to idx to avoid shadowing BSD strings.h [kwilliams]
qhull 2010.0.1 2010/01/03
New Features:
- Added option 'Ta' to annotate output with message codes
Preliminary C++ support:
- C++ declarations may change without warning
- Preliminary documentation for Qhull's C++ interface [qh-code.htm#cpp, qhull-cpp.xml]
- Added user_eg3 as an example of Qhull.cpp
- Removed qhull_interface.cpp. Use Qhull.cpp instead.
If math.h breaks '#include qhull_a.h', preceed it with '#include math.h'
Changes to qhull options and results
- Allow 'd' and 'v' as the filename for 'TO ..' and 'TI ...' in qdelaunay [M. Jambon]
- 'rbox tN' requires an integer (previously allowed floats)
- Allow quoted filenames for 'TO ...' and 'TI ...'
- Prefix error messages and warnings with a message code (e.g., QH6012)
- Fixed rbox ignoring flags that were not separated by spaces
- Report all hidden options before exiting in qh_checkflags()
- Defined qh_OPTIONline [user.h] as max length of option line ('FO')
- Report error if negative arguments to rbox 'G', 'L', 'Z'
- Unknown rbox flag changed from a warning to an error
- Set error status 4 qh_ERRmem if rbox runs out of memory
- Removed extra spaces at end of line
Breaking Code Changes:
- Renamed qh.coplanarset to coplanarfacetset. Avoids conflict with facetT.coplanarset
- qh_restore_qhull() zeroes out qh.old_qhstat and qh.old_tempstack. Ownership moved.
- Rewrote save_qhull/restore_qhull
- Add Ztotcheck to zzdef_ [R. Gardener]
- Changed qh_malloc to size_t (was unsigned long)
- Declare qh_PRINT instead of int [kwilliams]
- In qh_printafacet(), changed error output to 'qh ferr'
Bug fixes to C code:
- Use gcc 4.4.0 or later. gcc 4.2.1, 4.2.2, and 4.3.2 -O2 segfaults in qset.c . gcc 4.1.1 was OK
See bug report http://gcc.gnu.org/ml/gcc-bugs/2007-09/msg00474.html
- Rewrite qh_setappend to avoid g++ 4.1, 4.2, and 4.3 strict_aliasing error.
Orion Poplawski (orion@cora.nwra.com)
http://www.rpmfind.net/linux/RPM/fedora/12/ppc/qhull-devel-2003.1-13.fc12.ppc64.html
- Fixed qh_findfacet_all(), "REALmin" should be "-REALmax" [L.A. Taylor].
Effects library users for convex hulls and halfspace intersections.
- qh_printfacet [io.c] Removed extra space for neighboring facets
- Report error if d points, Delaunay, and not Qz
- Fixed double-free of facet->centrum for triangulated facets
- Fixed mindist initialization if !testcentrum in io.c findbest_test [Ratcliff]
- Fixed parentheses around warning for missing 'Qc' [qh_initqhull_outputflags]
- Fixed rbox buffer overflow of 'command' when appending seedbuf
- Fixed option string for 'rbox t t999'. Although seed was correctly set to 999,
a random seed was appended to the rbox comment (e.g., 'rbox t t999 t32343')
- Fixed upper bound of sanity check for qh_RANDOMmax in qh_initqhull_globals()
Changes to C code
- Reordered #include from specific to general. Move up .h for module.
- Removed qh.old_stat -- never used
- Removed qh_clearcenters from qh_freeqhull. Duplicated by qh_delfacet
- qh_printcenter [io.c] removed unreachable fprintf argument
- qh_getarea() [geom2.c] ignored on multiple calls (qh.hasAreaVolume)
- qh_getarea() [geom2.c] checks facet->isarea. Set by QhullFacet.facetArea()
- qh_triangulate() [poly2.c] ignored on multiple calls (qh.hasTriangulation)
- Add statistics for vertex_visit and visit_id to buildtracing
- Defined scale and offset parameters for qh_randomfactor
Bug fixes and changes to mem.c/mem.h
- Fixed qhmem.totshort (total short memory in use)
- Memory tracing (T5) redone for sort order by object
- Added full tracing for short memory allocations.
- Added qhmem.totfree (total short memory on freelists)
Increases size of qh_memalloc_ and qh_memfree_
- Added qhmem.totdropped (leftover freesize at end of each short buffer)
- Added qhmem.totunused (short size - request size)
- Added qhmem.totbuffer (total short memory buffer w/o links)
- Added memory statistics to qh_NOmem;
- Added qh_memtotal to track allocated memory
- Renamed qh_memfree parameter to 'insize' for consistency with qh_memalloc
- Removed qhmem.curlong. qa_memfreeshort computes curlong from cntlong and cntfree
- In mem.h, changed ptr_intT to long. qh_meminit() checks that it holds a 'void*'
Fixed g++ and devstudio warnings
- Except for bit field conversions, compiles cleanly with
-Wall -Wextra -Wshadow -Wcast-qual -Wwrite-strings -Wno-sign-conversion -Wconversion
- Fixed warnings at VC8, level 4
- Fix data types to remove conversion warnings [kwilliams]
- Use size_t for calls to malloc,etc [kwilliams]
Retained int sizes for qset.h and mem.h. Follows Qt convention
and is easier to work with. int can be 64-bits if 2 billion facets
- Change literal strings to const char* [kwilliams]
- Added type casts to SETfirst and SETsecond [amorilia+alphax]
- getid_() returns an int [kwilliams]
- Add missing const annotations [kwilliams]
- Fixed 64-bit warnings (marked with "WARN64")
- Convert sizeof to (int) for int parameters
- In libqhull.c, added explicit casts from long to float, Avoids warning
- In global.c, cast time() to int for QRandom-seed. Avoids warning
Changes to C code for C++ support
- Add sln, vcproj, and qtpro files for building Qhull -- add to README notes
- Added dim to vertexT for cpp interface. Reduced size of qh.vertex_visit
- qh_produce_output [io.c] may be called multiple times (C++ interface)
- Moved SETsizeaddr_() to qset.h for use by QhullSet.cpp
- Option 'Tz' sets flag qh.USEstdout for QhullPoints.cpp
- Added support for multiple output runs from QhullPoints.outputQhull
- qh_clear_outputflags() resets the output flags
- qh_initqhull_outputflags split from qh_initqhull_globals
- Added qh.run_id, a random identifier for this instance of Qhull (QhullPoints)
- For qh.run_id, initqhull_start initializes qh_RANDOMseed to time instead of 1
- Extracted qh_argv_to_command (random.c) from qh_init_qhull_command and fixed a buffer overflow
- Moved qh_strtod/qh_strtol from global.c to random.c for use in rboxlib.c
- Split out random functions into random.c
- Added message codes to qh_fprintf(). See its definition in user.c
- Replaced exit, malloc, free, fprintf, and fputs with qh_malloc,...[J.W. Ratcliff]
- Added qh_fprintf, qh_malloc, qh_free, ph_printhelp_narrowhull to user.c
- Moved qh_printhelp_degenerate and qh_printhelp_singular from io.c to user.c
- Clear qh.ERREXITcalled at end of qh_errexit().
Documentation:
- Fixed out-of-date CiteSeer references
- Renamed html/qh-in.htm to html/qh-code.htm
- Add reference to 'Qt' to 'i'
- Add reference to 'FS' to 'FA'
- qh-impre.htm discusses precision issues for halfspace intersection
- Add cross references between options 'FA' and 'FS'
- Added link to Wolfram Research's MathWorld site
- Updated Fukuda's links
- Changed copyright to C.B. Barber for C++, documentation, and merge.c
- Updated Qhull citation with page numbers.
- Proposed project: constructing Voronoi diagram
- Proposed project: computing Voronoi volumes
- Replaced tabs with spaces in qhull.txt and rbox.txt
------------
qhull 2009.1 2009/6/11
This is a maintenance release done by Rafael Laboissiere <rafael@debian.org>.
- src/rbox.c (main): Avoid problems of evaluation order when
pre-incrementing arguments of strtod
- src/io.c (qh_produce_output), src/stat.c (qh_initstatistics): Use %lu
instead of %d in the format string for arguments of type size_t
- html/qhull.man, html/rbox.man: Fix several syntax, macros, and hyphen
problems in man pages
- The Autotools files have been generated with modern version of autoconf (2.63),
automake/aclocal (1.10.2), and libtool (2.2.6)
- Some character issues in the man pages are fixed
------------
qhull 2003.1 2003/12/30
New Features:
- Add Maple output ('FM') for 2-d and 3-d convex hulls [T. Abraham]
Breaking Code Changes:
- Annotate C code with 'const'. An ANSI compatible compiler is required.
Bug Fixes and Code Changes:
- Fixed qh_findbest() for upperdelaunay facets w/o better, lower neighbors
For library users and some qhull users [A. Cutti, E. Milloti, K. Sun]
- Preserved qhmem.ferr in qh_memfreeshort() for library users
- Removed 'static' from qh_compare... for io.h and merge.h [V. Brumberg]
- Split out qh_initqhull_start2() to avoid allocating qh_qh
- Split out qh_freeqhull2() to avoid freeing qh_qh
- Split out qh_produce_output2() and qh_prepare_output()
- qh_initstatistics() frees a previously existing qh_qhstat
- qh_initqhull_start2() checks that qh_initstatistics() called first
Documentation:
- Add warning to findDelaunay() and qh_in.htm about tricoplanar facets
- Noted Edelsbrunner's Geometry & Topology for Mesh Generation [qh-impre.htm]
- Noted Gartner's Miniball algorithm [qh_impre.htm]
- Noted Veron and Leon's shape preserving simplification [qh_impre.htm]
qhull 2003.1 2003/12/19
Bug Fixes:
- Reversed coordinate order for qh.ATinfinity in qh_projectinput [V. Brumberg]
This effects:
Qhull library 'd' or 'v' users with 'Qz' and unequal coordinate ranges.
qdelaunay/qvoronoi users with 'Qbk:0Bk:0', 'Qz', and unequal coordinate ranges
Changes to code:
- Replaced qh_VERSION with qh_version in global.c [B. Pearlmutter]
The previous techniques were either clumsy or caused compiler errors
- Removed unused variables from qh_findbest and qh_findbestnew [B. Pearlmutter]
- Note that qh.TESTpoints was added in 2002.1 for tsearch implementation
Changes to distribution:
- Added Unix distribution including Debian files [R. Laboissiere]
The previous Unix distribution is now the source distribution
- Added rpm distribution [L. Mazet]
- Investigated generation of Win32 dll. Need to define a C++ interface.
Changes to documentation:
- Moved Qhull to www.qhull.org (geom.umn.edu is not available)
- The Geometry Center is archived at http://www.geom.uiuc.edu
- Reviewed introduction to each program
Triangulated output ('Qt') is more accurate than joggled input ('QJ')
qdelaunay is 'qhull d Qbb' [C. Ulbrich]
qvoronoi is 'qhull v Qbb'
Added example of non-simplicial intersection to halfspace intersections
- Added warning about using the Qhull library.
- Added qhull timings to When to use Qhull [C. Ulbrich]
- Reorganized the home page index and the manual index
- Moved qh-home.htm to index.htm
Changes to examples
- Fixed options for eg/eg.t23.voronoi.imprecise [B. Pearlmutter]
------------
qhull 2002.1 2002/8/20
Changes to distribution:
- Set up savannah.nongnu.org/projects/qhull/ [R. Laboissiere]
- Set up www.thesa.com as a backup
- Added qh-get.htm, a local copy of the download page
- Added Visual C++ interface to Qhull, qhull_interface.cpp [K. Erleben]
- Use HTTP instead of FTP for downloading Qhull
- Renamed qhull-1.0.sit.hqx
Bug fixes:
- Fixed sign of coefficients for cdd halfspaces ('FD','Fd') [T. Abraham]
Changes to code:
- Replace qh_version with qh_VERSION in libqhull.h.
Allows shared libraries and single point of definition
- Added qh.TESTpoints for future implementation of tsearch
Changes to build
- Makefile.txt works under cygwin
- Added Make-config.sh to create a Debian build [R. Laboissiere]
- Added .exe to Makefile.txt#clean.
- In README, use -fno-strict-aliasing with gcc-2.95.1 [Karas, Krishnaswami]
- Fixed chmod in Makefile.txt [B. Karas]
Documentation updates
- Documented input options for each program [A. Montesinos]
- FAQ: "How to get the radii of the empty spheres for Voronoi vertices"
URL updates:
- Changed official URL from locate/qhull to software/qhull
- Changed URLs from relative to absolute in qh-home.htm and qh-get.htm
- Added URL for Newsgroup: comp.soft-sys.matlab
- Added URL for GNU Octave
- Added URLs for Google and Google Groups
- Replaced qhull_mail.html and qhull_bug.html with mailto links.
- Removed URL for Computational Geometry Tribune
- Changed URL for locate/cglist to software/cglist
- Used site relative links for qh-home.htm
------------
qhull 3.1 2001/10/04
New features
- Added option 'Qt' to triangulate non-simplicial facets
- Added option 'TI file' to input data from file
- Added option 'Q10' to prevent special processing for narrow distributions
e.g., RBOX 1000 L100000 s G1e-6 t1001803691 | QHULL Tv Q10
- Tried to compute Voronoi volumes ('Pv'). Requires dual face graph--not easy
See Clarkson's hull program for code.
Changes to options
- Added numtricoplanars to 'Fs'. Number of good, triangulated facets for 'Qt'
- Added Zdelvertextot to 'Fs'. If non-zero and Delaunay, input is degenerate
- Qhull command ('FQ') may be repeated.
- If 'TPn' and 'TWn' defined, trace the addition of point 'n'
otherwise continue tracing (previously it stopped in 4-d)
- Removed 'Ft' from qdelaunay. Use 'Qt o' or 'qhull d QJ Qt' instead.
For non-simplicial regions, 'Ft' does not satisify the Delaunay property.
- If 'Po' or 'TVn', qhull checks outer planes. Use 'Q5' to turn off.
- If 'T4', print facet lists and check polygon after adding each point
Corrections to code
- rbox: allow 'c' and 'd' with 's r', meshes, etc.
- qh_findbest: redesigned as directed search. qh_findbesthorizon for coplanar
qh_findbest is faster for many distributions
- qh_findbestnew: redesigned to search horizon of coplanar best newfacets
needed for distributions with a sharp edge,
e.g., rbox 1000 s Z1 G1e-13 | qhull Tv
- qh_findbest/qh_findbestnew: search neighbors of better horizon facets
was needed for RBOX 1000 s Z1 G1e-13 t996564279 | qhull Tv
and RBOX 1000 s W1e-13 P0 t996547055 | QHULL d Qbb Qc Tv
- qh_findbest with noupper: could return an upperdelaunay facet if dist>qh.MINoutside.
- qh_findbestnew: allow facet->upperdelaunay if dist > qh.MINoutside
- qh_partitioncoplanar: call qh_partitionpoint if outside and perpendicular
for distributions with a sharp edge
- qh_partitionvisible: report precision error if all newfacets degenerate.
was needed for RBOX 1000 s W1e-13 t995138628 | QHULL d
- qh_createsimplex: clears qh.num_visible, may be non-zero with 'TRn QJ'
Changes to prompts, warnings, and statistics
- For Delaunay & Voronoi, 's' reports deleted vertices due to facet merging.
They were incorrectly reported as nearly incident points.
- Warn if recompute centrum after constructing hull
- Simplified narrow hull warning and print all digits of cosine.
A narrow hull may lead to a point outside of the hull.
- Print total vertices deleted instead of ave. per iteration (Zdelvertextot)
- Improved tracing for qh_partitionpoint and qh_partitioncoplanar
- Added number of distance tests for checking outer planes (qh_check_maxout)
- Simplified "qhull precision error: Only n facets remain."
- Included 'TRn' in the causes of a premature exit
Changes to documentation
- README.txt: Added quickstart instructions for Visual C++
- rbox: Added example of edge of narrow lens, rbox 1000 L100000 s G1e-6
- Added cross references between options 'o' and 'p'.
- qh-eg.html: added examples comparing 'Qt', 'QJ', and neither 'Qt' nor 'QJ'
eg.15a.surface, eg.15b.triangle, eg.17a.delaunay.2, etc.
- Reorganized and enhanced discussion of precision problems in qh_impre.htm
- Fixed spelling errors [K. Briggs]
- Fixed link errors, validated HTML, and spell checked [HomeSite]
- Removed unnecessary #TOP links
- Added source links to the qh-quick.htm's header and footer
- qh-geom.htm, qh-poly.htm: add links to Voronoi functions in io.c
- src/index.htm: Added how to search libqhull.h for qhull options
- qvoronoi.htm/qdelaun.htm: 'Fc' and 'FN' includes deleted vertices
Changes to URLs
- Added http://www.voronoi.com and http://www.magic-software.com
Changes to code
- qh_qhull: if 'TVn' or 'TCn' do not call qh_check_maxout and qh_nearcoplanar
- reviewed time profile. Qhull is slower. Optimized qh_findbestnew()
- qh_addpoint: Added warning note about avoiding a local minimum
- qh_checkpolygon: report qh.facet_next error if NARROWhull & dist>MINoutside
- qh_findbest: renamed "newfacets" parameter to "isnewfacets" since it is boolT
- qh_findbest/qh_findbestnew: testhorizon even if !MERGING
Otherwise qhull c D6 | qhull Q0 Tv assigns coplanar points
- qh_resetlists: add qh_RESETvisible for qh_triangulate
- qh_findbest: search better facets first. Rewritten.
- qh_findbest: increased minminsearch, always check coplanar facets.
See: RBOX 1000 s Z1 G1e-13 t996564279 | QHULL Tv
- qh_findbestnew: report precision error for deleted cones [rare event]
e.g.: RBOX 1000 s W1e-13 P0 t1001034076 | QHULL d Qbb Qc Tv
- qh_findbesthorizon: search horizon of qh.coplanarset. New.
- qh_findbestsharp: replaced with qh_sharpnewfacets followed by qh_findbestnew
- qh_partitionpoint, Delaunay sites can not be inside. Otherwise points may
be outside upperDelaunay facets yet not near-inside Delaunay facets
See: RBOX s 1000 t993602376 | QHULL C-1e-3 d Qbb FA Tv
- qh_partitioncoplanar: call qh_findbest/qh_findbestnew with qh DELAUNAY
- qh_printlists: format long lines
- qh_printvertex: format long lines
- user.h: tightened qh_WARNnarrow and qh_MAXnarrow. Do not see problems
until they are -1.0.
- user.h: defined qh_DISToutside, qh_SEARCHdist, and qh_USEfindbestnew
- qh_checkfacet: in 3-d, allow #ridges > #vertices. Can get a vertex twice
in a ridge list, e.g, RBOX 1000 s W1e-13 t995849315 D2 | QHULL d Tc Tv
Changes to FAQ
- Recommended use of triangulated output ('Qt')
Changes to distribution
- Recompiled in Visual C++ 5.0 with optimization (as was version 2.6)
- q_test: Added bad cases for Qhull and tests for new features
Changes to Qhull library
- Added qh_triangulate() to poly2.c. It triangulates the output.
- Added option 'Q11' to copy normals and recompute centrums for tricoplanar facets
'FP' may not print the nearest vertex for coplanar points
Use option 'Q11' when adding points after qh_triangulate()
------------
qhull 3.0 2001/02/11
Changes to distribution
- added qconvex, qdelaunay, qhalf, and qvoronoi
- added qhull-interface.cpp on calling Qhull from C++ [K. Erleben]
- renamed to qhull3.0/.
- added eg/, html/, and src/ directories
Changes to URLs
- MathLab6 qhull: convhulln, delaunayn, griddatan, tsearchn, vororoin [Z. You]
- Wolfram Research wrote a Mathematica interface for qdelaunay [Hinton]
- Geomview moved from www.geom.umn.edu to www.geomview.org [M. Phillips}
- added URLs for tcsh and cygwin to README.txt
Changes to documentation
- reorganized table of contents and renamed qh-man.htm to index.htm
- wrote program documentation, dropped qh-opt.htm and qh-optv.htm
- added quick reference, qh-quick.htm
- reorganized qh-rbox.htm and renamed it to rbox.htm
- split up qh-c.htm for quick navigation
Corrections to code
- fixed type of arg for error message in qh_initqhull_globals [N. Max]
- fixed incorrect initialization of qh MINdenom_1 for scalepoints
- fixed drop dim for 'H Qbk:0Bk:0'. Added qh.feasible_point to qh_projectinput
- qh_WARNnarrow is angle between facet normals. Negate for warning message.
- statistics for Wangle/etc. concerns facet normals. Reworded [E. Voth]
- fixed error message for 'FC v'
- report cospherical points if Delaunay and error in qh_scalelast()
Changes to code
- turn on Pg if (QVn or QGn) and not (Qg or PG)
- turn on Qc if format option 'Fc', 'FP', or 'Gp' (removes warning)
- removed last good facet unless ONLYgood ('Qg').
- added count of non-simplicial or merged facets to 'FS'
- added count of non-simplicial facets to 's' (OK if #vertices==dim)
- added Znonsimplicial and Znowsimplicial to 'Ts'
- allow Mathematica output of dual polytope for halfspace intersection
- added qh_checkflags to globals.c for multiple front ends
- qh_initqhull_globals sets qh.MERGING if qh.MERGEexact
- removed hashentryT. It is no longer used.
Changes to prompts and warnings
- reorganized prompts
- reorganized synopsis for rbox.c
- print warning if 'Fc' or 'FP' with 'd QJ'. Coincident points are unlikely.
- ignore warning if options 'v i Pp'. qvoronoi users may need Delaunay tri.
- reworded warning if 'Pg' and 'QVn' is not a vertex.
- reworded warning for 'Qx Tv', qh_check_points() in poly2.c
- if 'Pp', turn off warning for 'Qbb' without 'd' or 'v'
- in qh_printsummary() of Voronoi and Delaunay, distinguish QVn, QGn, Pdn, PDn
Changes to FAQ
- added FAQ item for nearly flat Delaunay triangles [Z. You]
- added FAQ item for area and volume [R. Konatham]
- added FAQ item for Voronoi diagram of a square [J. Yong]
- edited FAQ item on point location in Delaunay triangles [Z. You]
- added FAQ item on nearly flat Delaunay triangles [Dehghani]
- added FAQ item about halfspace intersection [V. Tyberghein]
- added FAQ item for missing ridges [M. Schmidt]
- added FAQ item about qh_call_qhull [R. Snyder]
- added FAQ item about memory statistics [Masi]
- added FAQ item on meshing non-convex objects
- added FAQ item on MATLAB and Mathematica interface
------------
qhull 2.6 1999/04/19
- fixed memory overwrite (no effect) in qh_initstatistics() [K. Ford]
- added zdoc11 to qh-stat.h#ZZdef for !qh_KEEPstatistics [K. Ford]
- enhanced qh_initqhull_globals() test of qh_RANDOMint and qh_RANDOMmax
- added debugging option to always return qh_RANDOMmax from qh_rand()
- fixed option 'Qr', qh_initialvertices(), to allow a broken qh_rand()
fixed option 'Qr', qh_nextfurthest(), to allow narrow hulls
Option 'Qr' simulates the random incremental algorithm for convex hulls
- added note that qh.num_outside includes coplanar points for narrow hulls
- added FAQ items for triangles/ridges of 3-d Delaunay triangulation[P. Kumar]
- added FAQ item about on-line processing with the Qhull library [O. Skare]
- changed name of option 'Error-roundoff' to 'Distance-roundoff'
------------
qhull 2.6 1998/12/30
- for the unbounded rays of the Voronoi diagram, use a large box [Schmidt]
e.g., 'rbox P4,4,4 P4,2,4 P2,4,4 P4,4,2 10 | qhull v Fv' fails for point 0
while 'rbox P4,4,4 P4,2,4 P2,4,4 P4,4,2 10 c G5 | qhull v Fv' is OK.
- fixed qh_new_qhull() to use outfile/errfile instead of stdout/stderr [Ford]
- clarified COPYING.txt for use in other programs [Archer]
- improved qh_readpoints() error message for incorrect point count.
- added FAQ item for closest triangle to a point [Sminchisescu & Heijting]
- added FAQ item for is a point outside of a facet [Beardsley]
- added FAQ item for visiting facets of the Delaunay triangulation [Heijting]
- added link to Erickson's Computational Geometry Software
- added link to Sharman's HTML version of the comp.graphics.algorithms FAQ
- added link to Owen's Meshing Research Corner
- added note to 'd' about quadratic size of 'rbox 100 l | qhull d' [Kumar]
- added 'about a point' to mentions of halfspace intersection
- added request to qh-code.htm to compute largest empty circle [Hase]
- the DOS window in Windows NT is better than the DOS window in Windows 95
- removed obsolete qh_findfacet() from qh-c.htm [Sminchisescu]
------------
qhull 2.6 1998/8/12
new and modified features
- rbox: added option Mn,m,r to generate a rotated lattice or mesh
- rbox: report error if more than one of 'l', 'x', 'L', 's', or 'M'
Qhull library changes
- added qh_new_qhull() to user.c for calling qhull() from a program [D. Zwick]
rewrote user_eg.c to use qh_new_qhull(). Added qh_QHpointer example.
- added qh_CLOCKtype 2 in user.h to call times() for CPU time [B. Hemkemeier]
- renamed set.c/set.h to avoid conflict with STL's set.h [G. van den Bergen]
can also use '#include <qhull/qhull_a.h>' for Qhull library
fixed errors
- fixed qh_init_B() to call qh_initqhull_mem() once only [D. Zwick]
This only effects Qhull library users of qh_QHpointer.
- fixed qh_mergecycle_all() to check for redundant vertices [J. Nagle]
e.g., 'rbox M3,4 64 | qhull Qc' should report 8 vertices & 48 coplanars
- fixed gmcoord initialization in qh_setfacetplane() for qh.RANDOMdist
- turn off qh.RANDOMdist during qh_printfacetheader()
- fixed error messages for unknown option flags
documentation changes
- added note to FAQ on the Voronoi diagram of cospherical points [H. Hase]
- added note to 'Qu' on furthest-site Delaunay triangulation via convex hull
- added note to 'QJ' about coplanar points on the convex hull of the input
- added note that 'o' and 'FN' list Voronoi regions in site id order [Arvind]
- added links to Fukuda's introduction to convex hulls, etc. [H. Hase]
- added .c and .h source files to web distribution and qh-c.htm [J. Sands]
- documented qh_ZEROdelaunay. Delaunay and Voronoi diagrams do not include
facets that are coplanar with the convex hull of the input sites.
modified code
- replaced computed minnorm in qh_sethyperplane_det with distance test
- removed 'qh rand_seed' since random number generator is independent of qhull
- dropt 'qhull-PPC.sit.bin' from the distribution (out-of-date) [M. Harris]
------------
qhull 2.5 1998/5/4
fixed errors
- removed zero-area Delaunay triangles and furthest-site triangles [I. Beichl]
Zero-area triangles occur for points coplanar with the input's convex hull.
- replaced qh.MINnorm with computed minnorm in qh_sethyperplane_det [J. Nagle]
qh.MINnorm was incorrect for the convex hull of the "teapot" example.
Qhull runs 0-20% slower in 3-d and 4-d.
- allow 'Qg' with furthest-site Delaunay triangulation (may be faster)
- removed extra space in definition of FOREACHmerge_() for Alpha cc [R. LeRoy]
- fixed innerouter type in qh_printvdiagram2 [does not effect code, R. Adams]
documentation changes
- to browse qh-c.htm, set MIME type of .c and .h files to text/html
- added example of 3-d Delaunay triangulation to q-faq.htm
- added Delaunay and Voronoi examples to qh-optv.htm
------------
qhull 2.5 1998/2/4
- added option 'v Fi' for separating hyperplanes of bounded Voronoi regions
- added option 'v Fo' for separating hyperplanes of unbounded Voronoi regions
- option 'Pp' turns off the warning, "initial hull is narrow"
- fixed partial, 3-d Voronoi diagrams (i.e., 'v Fv QVn Tc')
- fixed missing statistics in qh_allstat* [T. Johnson]
- rearranged qh_printvdiagram. Use qh_eachvoronoi to iterate Voronoi ridges.
- added qh_check_points to qh-math.c
qhull 2.5 1998/1/28
- added option 'Fv' to print the Voronoi diagram
- added rbox option 'x' to generate random points in a simplex
- added rbox option 'y' to generate a simplex and random points
- added rbox option 'On' to offset the output
- add unpacking instructions to README.txt
- updated discussion of forced output, 'Po'
- sorted the options alphabetically
- removed __STDC__ check from libqhull.h for VisualC++
- moved qh_markvoronoi from qh_printvoronoi and cleared facet->seen flags
- added facet->seen2 flag for 'Fv'
qhull 2.5 1998/1/16
- fixed initialization of qh.last_low on restart of 'd QJ'
- renamed qh_JOGGLEmax to qh_JOGGLEmaxincrease
- updated URL for Fukuda's cdd program
qhull 2.5 1998/1/12
New or modified features
- added option 'Fx' to print vertices by point id [G. Harris, T. McClendon]
in 2-d, the vertices are printed in counter-clockwise order
for Delaunay triangl., 'Fx' lists the extreme points of the input sites
- added option 'QJ' to randomly joggle input instead of merging facets
- added option 'TO file' to output results to a file. Needed for Windows95.
- added option 'TRn' to rerun Qhull n times. Use to collect joggle statistics
Corrections
- fixed 2-d facet orientation for 'i' and 'o' outputs
- for Mathematica 2.2 ('m') changed %10.8g to %16.8f [A. Zhaxybayev]
- fixed incorrect warning for 'QV0 Qg' in qh_initbuild [B. Wythoff]
- fixed unaccessible statistic if !qh_KEEPstatistics for Wnewvertexmax
- fixed overestimate of qh ONEmerge for point sets outside of
first quadrant and far from the origin
- fixed overestimate of 'Qbb' for point sets far from the origin
- fixed potential overestimate of qh DISTround under 'Qbb'
- fixed 'p' printing coplanar points of unselected facets
- fixed 'Ft' printing centrums unnecessarily in 2-d
Changes to documentation
- wrote internal design documentation (qh-c.htm)
- started frequently asked questions (qh-faq.htm)
- added a section on joggled input to qh-impre.htm
- added joggle example to qh-eg.htm (eg.15.joggle)
- changed q_eg to use 'QJ' instead of 'Q0' were appropriate
- added an example to each of the main options
- added examples to rbox.htm
- added examples to the synopsis
- added a reference to Mucke, et al ['96], Fast randomized point location ...
- added code for printing Delaunay triangles to qh-code.htm [A. Tsui]
- options 'Pdk' and 'PDk' do not drop on equality
Improvements to the code
- reviewed warning messages for Qhull options in qh_initflags
- added warning to 's' if premature exit from 'TCn' or 'TVn'
- 's' prints max distance above/below only if qh.MERGING
- reduced maxoutside in qh_check_bestdist/qh_check_points for 'Rn'
- in post-merging, rebuild centrums of large facets that become small
- lowered cutoff for coplanar facets for ischeckmax/qh_findbest
- removed qh_check_maxout for 'Wn Q0'
- reset tracing after 'TPn' adds point in 4-d and higher
Changes for the Qhull library
- changed qh_setdelaunay to call qh_scalelast if used with 'Qbb' or 'QJ'
Delaunay callers to qh_findbestfacet, qh_addpoint, or qh_findfacet_all
should always use qh_setdelaunay as in user_eg.c
- defined qh.outside_err to check points against a given epsilon [E. Voth]
- added header to user_eg.c to avoid its incorporation into qhull [C. Begnis]
- added qh_nearcoplanar() calls to user_eg.c
only needed if use 'QJ'
- expanded __STDC__ warning message in libqhull.h [C. Begnis]
- renamed qh maxmaxcoord to qh MAXabs_coord
- replaced qh MAXlowcoord with qh MAXabs_coord
- random seed ('QR-n') is reset in qh_initqhull_globals after testing
- replaced 'FO' options "_max-coord/_min-coord" with "_max-width"/qh.MAXwidth
Other changes to Qhull functions
- report error for !bestfacet in qh_findbest (it shouldn't happen) [H. Meuret]
- set newbest in qh_findbest only if bestfacet updated
- renamed facet parameter for qh_findbest
- added maxdist argument to qh_checkpoint
- moved 'FO' output after qh_partitionall
- separated qh_initbuild from qh_qhull
- reinitialize globals modified by qh_buildhull
- moved initialization of qh.GOODvertexp & qh.GOODpointp to qh_initbuild
- separated qh_nearcoplanar from qh_check_maxout
- separated qh_geomplanes from qh_printfacet2geom, etc.
- separated qh_freebuild from qh_freeqhull
- separated qh_outerinner from io.c to return outer and inner planes
- separated qh_distround and qh_detroundoff from qh_maxmin
------------
qhull 2.4 97/4/2
New or modified features
- made 'C-0' and 'Qx' default options. Use 'Q0' to not handle roundoff errors
- removed point-at-infinity from Delaunay/Voronoi.
you no longer need to use 'Qu PDk'
- added 'Qz' to add a point-at-infinity to Delaunay and Voronoi constructions
- added published version of qhull article in ACM Trans Math Software
- ported qhull to Windows95 under Visual C++ and Borland C++
- added 'Ft' for triangulation by adding the centrums of non-simplicial facets
- added 'Gt' to display 3-d Delaunay triangulations with a transparent hull
- changed definition of coplanar point in output to qh min_vertex (see 'Qc')
it was qh MAXcoplanar ('Un') [could make vertices non-coplanar]
- automatically set 'Qi' for options 'd Qc' and 'v Qc'.
- reworded summary ('s') for Delaunay/Voronoi/halfspace.
use 'Fs' and 'FS' for summary statistics.
- for summary 's' of Delaunay/Voronoi, display number of coplanars for facets
if none, display total number of coplanars (i.e., non-vertices)
- input comment is first non-numeric text (previously limited to header)
- added input warning if use 'Qbb' without 'd' or 'v'
- 'Q3' can not be followed with a numeric option
Corrections
- fixed qh_partitioncoplanar() to not drop interior points if 'Qi' is used
- fixed 'FP d' to report distance in point set instead of paraboloid
- fixed qh_findbest() to search all coplanar facets for qh_check_maxout()
Changes to documentation
- added example eg.17f.delaunay.3 to show a triangulation of cospherical sites
- split up qh-opt.htm into multiple pieces
- split off qh-code.htm for Qhull code
- renamed .html files to .htm for Windows95
- rewrote qh-optv.htm on Delaunay triangulation and Voronoi vertices
- added 'man' pages qhull.txt and rbox.txt. These list all the options
- removed 'txt' versions of html files
- added note to 'PDk' about avoiding a 'd' option immediately after a float
- under option 'd', display the triangulation with 'GrD3', not 'GnrD3'
Changes to the Qhull library
- added 'format' argument to qh_printfacetNvertex_nonsimplicial() in io.c
- removed C++ type errors [J. Stern, S. Marino]
- created SETelemt, SETfirstt, etc. for specifying data types.
- use SETelem,etc. for assignments.
- changed setT.maxsize to 'int' to prevent type conversion warnings
- changed FOREACH.. to a comma expression for better code and less warning
- changed qh.vertex_visit and .visit_id to unsigned int to prevent warnings
- changed clock() to qh_CPUclock (user.h)
- qh_init_B() and qh_readpoints() do not set qh.ATinfinity for Delaunay tri.
- qh_setvoronoi_all() sets upper Delaunay facets if qh.UPPERdelaunay is set
- qh_nearvertex() returns distance in dim-1 for qh.DELAUNAY
- removed MSDOS path from qhull_command. Spaces in Win95 tripped qh_setflags
- removed memory.h from qhull_a.h. memset,etc. should be in strings.h
- split qh_prompt into pieces for Visual C++
- added note to qh_addpoint that coordinates can not be deallocated
- added Baker '89 to constrained Delaunay diagrams under Enhancements
please let me know if you try this
- added request for unbounded Voronoi rays to Enhancements
please let me know if you try this
------------
qhull V2.3 96/6/5
- fixed total area of Delaunay triangulation. [A. Enge]
It should ignore facets on the upper-envelope.
- if 'd Qu FA', the total area is summed over the upper-Delaunay triangles
- fixed sign of area for Delaunay triangulations.
- fixed cdd input format for Delaunay triangulation. [A. Enge]
- for cdd input, allow feasible point for halfspaces.
- warning if cdd output format for centrums, halfspace intersections, or OFF.
- print '0' for area ('Fa') if area is not computed for a facet
- option 'QR-n' sets random number seed to n without rotating input
- fixed qh_findbest() to retest coplanar and flipped facets after a restart
- for 'd Qu Ts' collects angle statistics for upper Delaunay facets
Changes to the Qhull library
- expanded user_eg.c for incremental constructions and Delaunay triangulation
- added discussion of incremental construction to qh_man.html#library
- WARNING: The default value of qh ATinfinity was changed from True to False.
A new flag, qh UPPERdelaunay, was defined for 'Qu'.
Please set qh ATinfinity if you explicitly add the point "at-infinity"
Please set qh ATinfinity if you explicitly call qh_projectinput.
Please set qh UPPERdelaunay if you explicitly cleared qh ATinfinity.
Other users do not need to change their code.
Now you can build a Delaunay triangulation without creating a point
"at-infinity". This removes a potential, hard-to-understand error.
qh_readpoints sets qh ATinfinity for options 'd' or 'v' without 'Qu'.
qh_initB sets qh ATinfinity for qh PROJECTdelaunay w/o qh UPPERdelaunay.
qh_projectinput adds a point "at-infinity" only if qh ATinfinity is set.
- added qh_setdelaunay to geom2.c to project points to paraboloid
- added qh_findbestfacet() to poly2.c to replace qh_findfacet()
- removed procedure qh_findfacet(). It does not always work.
- removed NULL option for facet in qh_addpoint(). It does not always work.
- added noupper parameter to qh_findbest.
- added search of upperdelaunay facets to qh_findbest()
- allowed qh_findbest() to start with a flipped or upperdelaunay facet
- removed qh_nonupper() -- it is no longer needed
- allow space at end of options
- fixed qh_projectinput for furthest-site Delaunay (qh PROJECTdelaunay 'd Qu')
- added voids to procedure declarations with empty parameter lists
------------
qhull V2.3 96/3/25
- fixed missing qh_check_maxout when coplanar points and no merged facets.
- fixed qh_freeqhull/allmem (e.g., if qh_NOmem) [only custom code] [E. Voth]
- fixed qh_freeqhull to free qh interior_point [E. Voth]
- fixed main() to free all of memory if qh_NOmem. Include "mem.h" [E. Voth]
- reset f.newcycle link in qh_mergecycle_all [E. Voth]
- fixed false error if 'Tc', coplanar points, and a narrow hull
- turn off 'Rn' when computing statistics, checking code, or tracing code
- removed ={0} from global.c and stat.c to reduce compiler warnings
- changed Makefile dependences to $(HFILES) for all but unix.o, set.o, mem.o
- pulled out qh_printpointid and reordered qh_pointid [E. Voth]
- removed some compiler warnings
- moved 'FO' print of options to just before qh_buildhull
- changed 'FO' to list difference from -1 for _narrow-hull
------------
qhull V2.2 96/2/15
- detect narrow initial hulls (cosine of min angle < qh_MAXnarrow in user.h).
Write warning if cosine < qh_WARNnarrow in user.h. If narrow (qh NARROWhull),
partition coplanar points as outside points and delay coplanar test to end.
Needed for RBOX 1000 L100000 s G1e-6 t995127886 | QHULL Tv
See 'limitations' in qh-impre.html for further discussion.
- corrected some confusions between 'FV' and 'Fv' in qh-opt.html
- fixed initialization error for small Voronoi diagrams (e.g., [0,0], [1,0], [0,1]) [J. Velez]
- fixed bad return from qh_mindiff in geom2.c
- for initial hull, first process facet with furthest outside point (qh_furthestnext)
- added facet->notfurthest flag for recomputing furthest point
- added check for __STDC__ (needs ANSI C) [E. Voth]
- reduced warning messages from [E. Voth]. e[1] in setT still reports a warning.
- added a cube to the discussion of option 'v' (Voronoi) in qh-opt.html [J. Velez]
- added notes about adjacent vertices to "Calling Qhull" in qh-man.html [R. Lewis & J. Velez]
- added note about 'lines closer' when viewing 3-d Delaunay triangulations [P. Kallberg]
- added option 'Q9' to always process furthest of furthest outside points.
- removed option 'Pp' from q_eg and qh-eg.html.
------------
qhull V2.2 95/12/28
- added option 'Qbb' to scale the last coordinate to [0,m] (max prev coord).
This reduces roundoff errors for Delaunay triangulations with integer coordinates.
- changed option 'Qu d' to print out the furthest-site Delaunay triangulation
Use options 'Qu d PD2' to compute the normal 2-d Delaunay triangulation without
the point at infinity.
- added notes to the documentation of option 'd'
- added notes to limitations of how Qhull handles imprecision
- added warning if options 'FP', 'Fc', or 'Gp' without option 'Qc' or 'Qi'
- added note to options 'PDk:n' and 'Pdk:n' that closest facet is returned if none match
- added check that 'Qbk' and 'QBk' does not invert paraboloid for 'd'
- added notes that qh_findfacet and qh_addpoint require lifted points for Delaunay triangulations
- fixed 'rbox s 5000 W1e-13 D2 | qhull d Qcu C-0 Qbb'
- fixed option 'QbB' (qh SCALEpoints was not set)
- fixed minor confusion between 'Gc' (print centrums) and 'Gp' (print points)
- rewrote qh_findbestnew for upper convex hull, Delaunay facets
- changed option name for 'Gp' from 'Gcoplanar' to 'Gpoints'
- changed "nearest" facet for 'Pdk' to threshold - normal
- reworked qh GOODclosest for 'Qg'
- added note that 'Qg' does not always work
- recorded option 'C-0' as "_zero-merge" in option 'FO'
- refined qh DISTround in qh_maxmin/geom2.c for Delaunay triangulations
qhull V2.2 95/12/4
- Version 2.2 fixes an important bug in computing Delaunay triangulations
and convex hulls with edges sharper than ninety degrees. The problem
occurs when processing a point at a sharp edge. A directed search can
not be used for partitioning because one side may hide facets from the
other side. The new lens-shaped distribution for rbox demonstrates the
problem. For example, 'rbox 100 L3 G0.5 s | qhull Tv' fails for Version 2.1.
O. Schramm found the bug when computing the Delaunay triangulation of points
near an outside edge.
I rewrote qh_findbest and related functions. Qh_findbest
uses an exhaustive test for sharp edges (qh_findbest_sharp).
Qh_findbest avoids the upper convex hull of Delaunay triangulations.
Options 'd' and 'v' no longer assign coplanar points to the upper convex hull.
Qh_check_maxout tests near-inside points. It ignores fully inside points.
When done, it removes near-inside points from the coplanar sets.
If you use qh_addpoint or qh_findbest, please review the function headers.
They do not work for lens-shaped hulls for arbitrary facets. They do work for
Delaunay triangulations.
Changes to options for V2.2
- added 'Qu' for computing the furthest-site Delaunay triangulation (upper hull)
and furthest-site Voronoi vertices.
- added 'FP' to print nearest vertex for coplanar points
- added coplanar count to 'Fs' and 's'
- added number of similar points to summary for Delaunay/Voronoi
- Option 'Qc' is no longer necessary when merging.
- 'o' format for Voronoi vertices ('v') generates "0" lines for similar points
- 'QRn' for Delaunay ('d' or 'v') now rotates about the Z axis (see qh_init_B).
Otherwise Qhull does not identify the upper hull
- removed option 'Qa' for "all points outside". In V2.1 it was automatically
set for 'd'. Even though it was a bad idea, it revealed the above bug.
- for option list ('FO'), added version, values for one-merge, maxpos, maxneg,
and near-inside, and flags for zero-centrum
- optimized 'C-0' and 'Qx'. These options ("zero-centrum") test vertices
instead of centrums for adjacent simplicial facets.
- if 'Tv', report number of points that are not verified due to qh_findbest
- Option 'Q8' ignores near-inside points.
rbox 95/12/3
- added lens distribution ('Ln') It may be used with 's', 'r', 'Wn', and 'Gn'
- removed default point count except for the test case, 'Dn'
- divided main() of rbox.c into sections
Documentation changes for V2.2
- added examples for lens distribution and furthest-site Delaunay triangulation
and renumbered the examples for q_eg
- described facet orientation in 'data structure' section [P. Soikkonen]
- added notes to qh-man.html/"What to do if something goes wrong"
- added note about using 'Tv' to verify the results [O. Schramm]
- expanded definition of f_r in Performance section [S. Grundmann]
- noted that Geomview display of a Voronoi diagram adds extra edges
for unbounded Voronoi cells
- rewrote error "convexity constraints may be too strong" [D. Newland]
- added limitations section to "Imprecision in Qhull"
- added note about zero-area facets to 'Imprecise convex hulls' in qh-impre.html
- added note to 'Qi' that it does not retain coplanar points
- added note that option 'Q5' may be used if outer planes are not needed
- added note to README.txt about Irix 5.1 [C. Goudeseune]
- added code fragment for visiting Voronoi vertices to "Calling Qhull" [M. Downes]
- added note about qh_addpoint() to "Calling Qhull" [M. Downes]
Errors fixed for V2.2
- use qh_sethyperplane_gauss if 3-d or 4-d norm is less than qh MINnorm
- count Zcentrumtests if qh_NOstat
- reversed sign convention for qh_sethyperplane_gauss
it was opposite to qh_sethyperplane_det
this effects qh_determinant and qh_detsimplex
- fixed error in qh_findgood_all with multiple restrictions, e.g., 'QVn Pdk'
- fixed call to qh_clearcenters for qh_produce_output
- in qh_errexit, report p0 if last furthest point
Changes for users of the Qhull library
- user code needs to define qh_version (see user_eg.c)
- merged initialization code into qh_init_A and qh_init_B [M. Mazzario]
old code works as before.
qh_initflags also sets qh qhull_command for qh_initthresholds
redid initialization for user_eg.c
- simplified user_eg.c. It computes the convex hull of a cube.
- added qh_setvoronoi_all in poly2.c to compute Voronoi centers
added related note to call_qhull
- added qh_findfacet to use in place of qh_findbest
- added qh_nearvertex to return nearest vertex in facet to point
- redid notes on multiple, concurrent calls in call_qhull/user.c
- changed BoolT to unsigned int (prevent implicit enum conversion warnings)
- added upperdelaunay to facetT. It indicates a facet of the upper convex hull.
- converted qhull-PPC.sit for CodeWarrior 7
Code changes for V2.2
- simplified calls to setjmp() for Cray J916 [Salazar & Velez]
- replaced fprintf(fp,string) with fputs in io.c
- 'qh num_coplanar' removed (too expensive and not used).
- added numcoplanars to qh_countfacets()
- added min norm to qh_normalize2(). qh_normalize() wasn't changed
- removed type casts from qh_point and qh_pointid [Salazar & Velez]
- account for roundoff error in detecting upper convex hull (qh ANGLEround).
- post merging uses qh_findbestnew for partitioning
- qh_findbestnew for qh_partitioncoplanar goes to best facet
- 'Qm' always processes points above the upper hull of a Delaunay triangulation
- GOODvertex initialized with qh_findbestnew instead of qh_findbest
- for 'v', qh_facetcenter returns furthest-neighbor vertex if 'Qu'
- added test for qh feasible_point if use 'Fp' and qh_sethalfspace_all
- reviewed Sugihara's algorithm for topologically robust beneath-beyond
- on error, report if qhull in post-merging or has completed
- if tracing, option 'FO' and qhull command always printed
- added current furthest point ("during p%d") to 'T-1' events
- added 'TWn' tracing for vertices of new facets (qh_setfacetplane)
- added 'TWn' tracing for vertices in an output facet (qh_check_maxout)
- reorganized split between poly/poly2.c and geom/geom2.c
- reordered object files in Makefile
------------
qhull V2.1 95/9/25
- converted qhull.man to html format, many edits
- referenced Shewchuk's triangle program and Schneiders' Mesh Generation page
- added option 'Qa' to force all points outside
automatically set for "precise" Delaunay or Voronoi [Salazar & Velez]
it is turned off by merging, 'Wn', 'Qc' or 'Qi'
- added coplanar points to option 'FN'
- moved option 'FO' to include default precision options
- changed default random number generator to qh_rand in geom2.c (user.h)
other code changes
- fixed option comment Pdrop-facets-dim-less, Qbound-dim-low, QbBound-unit-box
- defined ptr_intT for converting 64-bit ptrs to 'unsigned long' [D. Bremner]
- defined setelemT to distinguish actual size from pointers [D. Bremner]
use either e[...].p or e[...].i (user-level code should use set.h macros)
- changed %x to %p in format statements for pointers [D. Bremner]
- added test of REALmax,etc. to qh_maxmin [H. Poulard]
- added type parameter to qh_memalloc_() macro for type conversion
- added type conversion to qh_memalloc() calls where missing
- added type conversion to calls into set.c that return void*
other documentation changes:
- new URLs for graphics images
- fixed comment for facetT.neighbors in libqhull.h [P. Soikkonen]
- changed recommendations for precision errors in qh_printhelp_degenerate()
- added recommendation for 'V0' (facet is visible if distance >= 0)
- added note about 'long double' to user.h [S. Grundmann]
- added note about zero area Delaunay triangles for the 'v' option
- added note about locating Delaunay triangles to option 'd' [A. Curtis]
- added note that coplanar vertices correspond to duplicate points for 'd'
- added note about option 'd' automatically setting 'PDk' (lower convex hull)
- added note about precision errors to option 'd' [many users]
- added note about qh_findbest() to the Qhull library section [L. Lai]
- 'make install' renames qhull.man to qhull.1 for Unix [M. Phillips]
- renamed README, etc. to *.txt to match WWW conventions [D. Cervone]
------------
qhull V2.1 7/10/95
- in 2-d, 'v o' lists the vertex at infinity in order [R. Critchlow]
- it used to always list the vertex at infinity ("0") first
- rewrote description of 'v' option (Voronoi vertices and 2-d diagrams)
- added 'PFn' for printing facets whose area is at least 'n' [D. Holland]
- prefixed 'Q',etc. to the 'Q',etc. options in the long help prompt
- fixed references to 'Fv' and 'FV' options under option 'Hn,n,n'
- updated reference to cdd, <ftp://ifor13.ethz.ch/pub/fukuda/cdd/>
- in set.c, added some missing type coercions for qhmem.tempstack
qhull V2.1 6/12/95
- replaced qhull.ps with qhull-2.ps (paper submitted to ACM TOMS)
- use BUFSIZ for setvbuf for Power Macintosh
- number of good facets printed if QVn, QGn, Pd, or PD
- added Makefile for Borland C++ 4.02 with Win32 [D. Zwick]
- added note to Enhancements section of qhull.1 about constrained
Delaunay triangulations [T. Rasanen]
qhull V2.1 6/7/95
- fixed qh_facetarea_simplex() for non-simplicial facets [L. Schramm]
- fixed cast in qh_point and qh_pointid for 64-bit architectures
- fixed URL for Amenta's list of computational geometry software
- fixed cast in qh_meminitbuffers for qhmem.freelists
- added test for !qh half_space in qh readpoints
- clarified options for qh_printhelp_singular()
- discussed non-simplicial facet area under option 'Fa' in qhull.1
qhull V2.1 6/3/95
- home page for Qhull and new descriptions for the Qhull examples
http://www.qhull.org
- changed SIOUX buffering for Power Macintosh. It runs fast now.
added a project file for Metrowerk's C
- note in README about compiling qhull on the PC
qhull V2.1 beta 5/15/95
======= main changes ========
- added halfspace intersection ('Hn,n,n')
- facet merging is better, especially for high dimensions
- added 'Qx' for exact merges of coplanar points and precision faults
- facet merging is faster, especially for high dimensions.
e.g., convex hull of the 8-d hypercube is seven times faster
- added 'F' output formats for printing each aspect of the convex hull
- format 'Fa' computes facet areas, total area, and total volume
- format 'FO' writes a descriptive list of selected options to stderr
- moved all customization options to user.h
- changed the default precision to 'double' since it's needed for Delaunay.
using 'float' is faster and takes less space (REALfloat in user.h)
- option 'Qm' is no longer important for facet merging
- removed need for 'Qs' by selecting initial simplex with pos. determinants
- renamed 'Qv' to 'Q7' since virtual memory does not work well for qhull
- Qhull is available for the Power Mac (no graphical output)
====== other new and modified options ===========
- changed default MINvisible ('Vn') to a multiple of premerge_centrum ('C-n')
- added 'Un' option to set width of facet for coplanar points.
This replaces the previous rules for determining coplanar points.
- changed default MINoutside ('Wn') to twice MINvisible ('Vn')
- Geomview output adjusts point radii for MINvisible 'Vn'
- the input format allows the number of points to precede the dimension
- options 'v' 'd' 'FAn' and 'FMn' record good facets ('Pg')
- added 'Fd' and 'FD' options for homogeneous coordinates in cdd format
- in rbox, added 'h' flag to generate homogeneous coordinates in cdd format
- option 'PAn' prints out the n facets with the largest area
- option 'PMn' prints out the n facets with the most merges
- option 'Po' under tracing ('Tn') no longer tries to write erroneous facets
- option 'TCn' only prints the old 'visible' facets for 'f'
- 'TFn' reports intermediate results when post-merging
- option 'Ts' with option 'TFn' prints intermediate statistics
- the message for 'Tv' reports if it is checking outer planes
- 'Tz' sends stderr output to stdout
- added 'Q1' to ignore angle when sorting merges (merges are worse)
- added 'Q2' to not perform merges in independent sets (merges are worse)
- added 'Q3' to not remove redundant vertices (faster)
- added 'Q4' to avoid merges of old facets into new facets (does worse)
- added 'Q5' to skip qh_check_maxout (faster, but less accurate)
- added 'Q6' to skip pre-merge of concave and coplanar facets
- added 'Qv' for testing vertex neighbors for convexity (needs merge option)
- added warning if mix Geomview output with other outputs ('Po' turns off)
- options 'o v' for 3-d and higher sort the Voronoi vertices by index
======= documentation =======
- rewrote the introduction and precision sections
- added a section on performance
- added an example on halfspace intersection
- installed examples of Qhull in
<http://www.geom.uiuc.edu/graphics/pix/Special_Topics/Computational_Geometry/>
======= Makefile, user.h, and messages =======
- Makefile calls ./qhull, ./rbox, and prints short prompt for qhull
- added new statistics, e.g., for buildhull
- changed default qh_RANDOMtype to RAND_MAX with rand()
- added comment about numeric overflow to printhelp_singular
- reorganized the code to improve locality of reference
- option in mem.h (qh_NOmem) to turn off memory management in qhull
- option in user.h (qh_NOtrace) to turn off tracing in qhull
- option in user.h (qh_NOmerge) to turn off merging in qhull.
- use this instead of redefining qh_merge_nonconvex in user.c
- simplified user_eg.c. See qh_call_qhull() in user.c for the full version
======== bug fixes ============
- fixed error in number of points for 'rbox 100 r' (odd distribution)
- fixed performance error in qh_degen_redundant_neighbors
- qh_partitionpoint now sets facet->maxoutside for first outside point
- fixed performance error in partitioning when merging a large, regular cone
- removed memory leak in qh_appendmergeset
- removed double free of qh line under errors in qh_readinput()
- forcing output on error ('Po') fixed for options 'n' 'o' 'i' 's'
- fixed optimization error on HP machines [fprintf(... *p++)]
======== changes to libqhull.h for user code =======
- qh_collectstatistics and qh_printstatistics removed from libqhull.h.
should use qh_printallstatistics instead
- qh_findbest uses boolT for newfacets
- added qh_findbestnew for non-simplicial facets. qh_findbest is
too slow in this case since it needs to look at many nearly coplanar
facets.
- renamed qh_voronoi/qh_centrum to qh_ASvoronoi, qh_AScentrum
- changed facet->id to 32-bits, added new flags for merging
- added facet->f for facet pointers while merging and for facet area
- added dfacet/dvertex for printing facets/vertices while debugging
- added qh_produce_output and qh_printsummary
======== changes to code ==========
- moved qh_setfacetplane from qh_makenewfacets to qh_makenewplanes
- added qh_setfree2, qh_setcompact, and qh_setduplicate to set.c
- qh_findgooddist returns list of visible facets instead of setting global
- in qh_check_maxout, inside points may be added to coplanar list.
- qh_findbestnew used for qh_partitionall. It is faster.
- in qh_findbest, changed searchdist to MINvisible+max_outside+DISTround.
MINvisible is the default MAXcoplanar.
- cleaned up list management via qh_resetlists
- uses facet->dupridge to indicate duplicated ridges instead of ->seen
- qh_buildtracing records CPU time relative to qh hulltime instead of 0
========== changes to merging =======
- many performance improvements, especially in high-d.
- when merging, qh_findbest and qh_findbestnew stops search at qh_DISToutside
- vertex neighbors delayed until first merge
- post merges reported every TFn/2 merges
- vertex merging turned off in 7-d and higher (lots of work, no benefit).
vertex merging moved to qh_qhull_postmerging in 6-d.
- replaced qh min_vertex with MAXcoplanar for determining coplanarity
- pick closest facets to merge in duplicate ridge instead of flip/flip
(see qh_matchduplicates in poly2.c)
- optimize merge of simplex into a facet
- optimize merge of a "samecycle" of facets into a coplanar horizon facet
- cleaned up qh_forcedmerges/qh_flippedmerges and removed facet->newmerge
- rewrote qh_merge_degenredundant with separate queue
- qh_facetdegen replaced by facet->degenredun
- flipped neighbors no longer merged in preference to flip/non-flip pairs
- removed angle argument from qh_merge_degenredundant and qh_mergefacet
only used for tracing
- getmergeset_initial had extra test of neighbor->simplicial
- ridge->nonconvex is now set on only one ridge between non-convex facets
- moved centrum deletion to qh_updatetested
- qh_isnewmerge(facet) changed to facet->newmerge (removed NEWmerges)
- qh_findbestneighbor reports correct distance even if testcentrum
- added hull_dim factor to qh_BESTcentrum
- removed horizon preference in qh_merge_nonconvex (qh AVOIDold)
- facet->keepcentrum if qh WIDEfacet or qh_MAXnewcentrum extra vertices
------------
qhull V2.02 1/25/95
- rbox 'z' prints integer coordinates, use 'Bn' to change range
- fixed rare bug in qh_check_maxout when qh_bestfacet returns NULL
- fixed performance bug in findbestneighbor, should be + BESTnonconvex
- renamed 'notgood' flag in 'f' option to 'notG' flag (caused confusion)
- changed qh.hulltime to (unsigned) to prevent negative CPU times
- added random perturbations to qh_getangle under the 'Rn' option
- reviewed the documentation and enhancement list
- added discussion of how to intersect halfspaces using qhull
- replaced expression that caused incorrect code under an old version of gcc
- added buffer after qh.errexit in case 'jmp_buf' has the wrong size
- rewrote qh_printhelp_singular for lower-dimensional inputs
- rewrote qh_printhelp_degenerate
- added options for qh_RANDOMint in qhull_a.h
- changed time format for 'TFn' to %02d
------------
qhull V2.01 6/20/94
- fixed bug in qh_matchnewfacets that occured when memory alignment makes
facet->neighbors larger than necessary.
- fixed bug in computing worst-case simplicial merge of angle coplanar
facets (ONEmerge). This decreases (...x) in printsummary.
qhull V2.01 6/17/94
- added recommendation for 'Qcm' to documentation and help prompts
- added an input warning to qh_check_points ('Tv') if coplanars and no 'Qc'
- qh_partitionpoint: always counts coplanar partitions (Zcoplanarpart)
- rewrote qh_printhelp_degenerate to emphasize option 'C-0'
- For Geomview output, roundoff is not needed when printing the inner and
outer planes. This improves Geomview output for the 'Rn' option.
- For Geomview output without coplanar points or vertices, qh_GEOMepislon
is not needed. This removes the edge gap when displaying a Voronoi cell.
- For Geomview output 'Gp', direct vertices to the interior point
instead of the arithmetic center of the displayed vertices.
qhull V2.01 6/11/94
- if pre-merge, 'Qf' is automatically set. Otherwise an outside point may
be dropt by qh_findbest(). This slows down partitioning.
- always use 'Qc' if merging and all facet->maxoutside's must be right.
Otherwise distributions with many coplanar points may occassionally
miss a coplanar point for a facet. This is because qh_findbest, when
called by qh_check_maxout, can become stuck at a local maximum if
the search is started at an arbitrary facet. With 'Qc', the search
is started from a coplanar facet. For example,
rbox 1000 W8e-6 t | qhull C-0 Tv
will (rarely) report that a facet->minoutside is incorrect
- option 'Pp' turns off "Verifying" message for 'Tv'
- added qh_copynonconvex to qh_renameridgevertex (fixes rare error)
- 'rbox tn' sets random seed to n
- 'rbox t' reports random seed in comment line
- qh_errexit reports rbox_command | qhull_command and 'QR' random seed
- added additional tracing to bestdist and setfacetplane
- in qh_checkconvex, need to test coplanar against 0 instead of -DISTround
- in qh_checkconvex, always test centrums if merging. The opposite
vertex of a simplicial facet may be coplanar since a vertex of
a simplicial facet may be above the facet's hyperplane.
- fixed error handling in qh_checkconvex when merging
- in qh_printsummary, one merge ratio not printed if less than 'Wn'
- documented that 'Tv' verifies all facet->maxoutside
qhull V2.01 6/2/94
- 's' prints summary to stderr
- multiple output formats printed in order to stdout
- added statistic for worst-case distance for merging simplicial facets
can not hope for a better "max distance above/below facet"
print factor for "max distance.."/"merge simplicial" in printsummary
- fixed error in scaling input with min/max reversed ('Qb0:1B0:-1')
- fixed error in scaling if project & Delaunay & scale ('d Qb0:0B1:0b2:0')
- user_eg.c: qh_delpoint removed since it does not always work
- user_eg.c now works for either convex hull or Delaunay triangulation
- added PROJECTdelaunay for Delaunay triangulations and Voronoi diagrams
with libqhull.a and user_eg.c
- user_eg.c: if project or scale input, need to copy points
- user_eg.c: default just defines main, added fprintf's for qh_errprint etc.
- qh_gausselim: a 0 pivot no longer zeros the rest of the array,
need the remaining elements for area computation
- qh_qhull: restore cos_max, centrum_radius at end of POSTmerging
- qh_checkflipped with !allerror is >=0.0 instead of >0.0
- removed -Wall from gcc due to unnecesssary "warning: implicit declaration"
- renamed 'new' variables and fields to allow compilation by g++
- added README notes on C++, and "size isn't known"
- updated manual on 'Qg' with coplanar facets and no merging ('rbox c D7')
'Qg Pg' and 'Pg' produce different results because of precision problems
------------
Converting from qhull 1.01 to qhull 2.00
- 'qhull An' is now 'qhull Wn'
option 'Wn Po' is faster but it doesn't check coplanars
- 'qhull g' is now 'qhull G', and the output formats are different
- 'qhull c' is now 'qhull Tc'
- 'qhull f' is now 'qhull Qf'
- 'qhull o' is now 'qhull Po'
- 'qhull b' is now always done
- qhull and rbox now use floats, change REALfloat in libqhull.h for doubles
- qhull 2.00 fixes several initialization errors and performanace errors
e.g., "singular input" on data with lots of 0 coordinates
- 'rbox b' is now 'rbox c G0.48'
- all rbox distributions are now scaled to a 0.5 box (use 'Bn' to change)
- rbox now adds a comment line. This may be removed by 'rbox n'
- 'rbox r s Z G' no longer includes the positive pole
- no changes to the Macintosh version
qhull V2.00 5/23/94
- if force output ('Po'), facet->maxoutside= 'Wn' since coplanars not updated
convexity checked if precision problems or verify ('Tv')
- if merging, new facets always checked for flipped orientation
- a facet is visible (findhorizon) under 'Qm' if distance > max_vertex
- if using 'Qm' then min. outside is max_vertex instead of max_outside
- default is random()/srandom() in qhull_a.h, checked in initqhull_globals
- created internal strtod since strtod may skip spacing after number
- removed lower bound (1.0) for qh maxmaxcoord
- divzero needs to handle 0/0 and large/small
- decreased size of precise vertices
- need to initialize qh MINdenom_1 for scalepoints
- added factor of qh maxmaxcoord into DISTround (needed for offset)
- 'Rn' perturbs distance computations by random +/-n
- check_points needs an extra DISTround to get from precise point to computed
- rewrote some of the IMPRECISION section in qhull.man
- added the input format to the qhull prompt
- moved include files to qhull_a.h since some compilers do not use float.h
- added qhull.1 and rbox.1 since SGI does not ship nroff
- reduced cutoff for printpointvect
- use time for qhull random seed only if QR0 or QR-1
- radius of vertices and coplanar points determined by pre-merge values
qhull V2.00 5/12/94
- facet2point (io.c) used vertex0 instead of vertex1
- can't print visible facets after cone is attached
- shouldn't check output after STOPcone (TCn)
- statistic 'Wminvertex' and 'Wmaxoutside' only if MERGING or APPROXhull
- 'make doc' uses lineprinter format for paging
- warning if Gpv in 4-d
qhull V2.b05 5/9/94
- decreased size of precise vertices
- precise facets in 2-d print hyperplanes
- accounted for GOODpoint in printsummary
- added IMPRECISION section to qhull.man
- 'Qg' does work in 7-d unless there's many coplanar facets
c4science · Help