Re: Release candidate for Qhull 2012.1

[Ben Abbott]

On Jan 29, 2012, at 7:46 PM, Brad Barber wrote:

> At 07:15 PM 1/29/2012, Ben Abbott wrote:
> 
>> On Jan 29, 2012, at 5:35 PM, Brad Barber wrote:
>> 
>>> At 01:13 AM 1/29/2012, you wrote:
>>> 
>>>> ________________________________________
>>>> From: address@hidden address@hidden on behalf of Brad Barber address@hidden
>>>> Sent: Saturday, January 28, 2012 11:54 AM
>>>> To: address@hidden
>>>> Subject: Release candidate for Qhull 2012.1
>>>> 
>>>> Hi all,
>>>> 
>>>> See below for the Qhull 2012.1 release candidate.  It is not deployed to 
>>>> qhull.org, because I need feedback on the changes.   The goal of this 
>>>> release is to clean up the builds and make them suitable to Octave, R, and 
>>>> other users.
>>>> 
>>>> If something is broken for you in Qhull 2012.1, please let me know.
>>>> 
>>>> Qhull 2012.1 adds libqhull.so for Octave and other users.  This shared 
>>>> library uses a static global data structure .   It is the same as the 
>>>> debian build, Qhull 2009.1.  To help avoid confusion, libqhull6_p.so is 
>>>> the new name for qhull with a dynamic global data structure 
>>>> (-Dqh_QHpointer).
>>>> 
>>>> Qhull 2012.1 fixes strict aliasing in qset.c and adds a qset test program.
>>>> 
>>>> 
>>>> Qhull 2012.1 includes a draft debian build in the 'config/' directory.  
>>>> Someone will need to verify that it works.   As before, it produces 
>>>> libqhull.so and the qhull executables.  It could be updated to match the 
>>>> other builds.
>>>> 
>>>> A later version of Qhull may include a third interface to get rid of 
>>>> global variables.  It would pass qh_qhT as a parameter to each function 
>>>> call.  There would be a single source tree using a macro to enable the 
>>>> extra parameter.  There would be a third shared library, tentatively named 
>>>> libqhull7_t.so for "threading".   If so, the C++ interface will probably 
>>>> switch to this library.
>>>> 
>>>> http://gitorious.org/qhull/
>>>> http://gitorious.org/qhull/qhull/blobs/master/src/Changes.txt
>>>> http://www.qhull.org/download/qhull-2012.1-src-tgz.md5sum
>>>> http://www.qhull.org/download/qhull-2012.1-src.tgz
>>>> http://www.qhull.org/download/qhull-2012.1-zip.md5sum
>>>> http://www.qhull.org/download/qhull-2012.1.md5sum
>>>> http://www.qhull.org/download/qhull-2012.1.zip
>>>> 
>>>> Many thanks for helping with qhull.
>>>> 
>>>>                                      --Brad
>>>> 
>>>> 
>>>> 
>>>> I built Octave on Lion with this version of Qhull and this went OK.  It 
>>>> did fail one of the make check tests on convhulln:
>>>> octave:1> test convhulln
>>>> ***** testif HAVE_QHULL
>>>> cube = [0 0 0;1 0 0;1 1 0;0 1 0;0 0 1;1 0 1;1 1 1;0 1 1];
>>>> [h, v] = convhulln (cube);
>>>> assert (size (h), [6 4]);
>>>> h = sortrows (sort (h, 2), [1:4]);
>>>> assert (h, [1 2 3 4; 1 2 5 6; 1 4 5 8; 2 3 6 7; 3 4 7 8; 5 6 7 8]);
>>>> assert (v, 1, 10*eps);
>>>> !!!!! test failed
>>>> assert (size (h),[6, 4]) expected
>>>> 6   4
>>>> but got
>>>> 12    3
>>>> values do not match
>>>> 
>>>> The same error also occured with the Qhull package from MacPorts (2011.2). 
>>>>  The difference was that I did not have to apply Ben's patch using when 
>>>> building against this version.  Not applying Ben's patch to 2011.2 
>>>> resulted in many more make check failures.  
>>>> 
>>>> Any idea what could be happening to cause this to fail on Lion, but pass 
>>>> on Fedora?  
>>> 
>> 
>>> Hi Melvin,
>>> 
>>> Many thanks for testing convhulln on Lion and Fedora.
>>> 
>>> Your results for Lion indicate that Qhull triangulated the output instead 
>>> of retaining the cube's facets.  My guess is that for Lion, someone had set 
>>> options 'QJ' or 'Qt' which request triangulated output.  You can test this 
>>> case, by adding 'FO' to the option list (look for Qtriangulate or QJoggle 
>>> in the returned "Options selected").  
>>> 
>>> Try running the qhull program directly on Lion.   Here are the results with 
>>> and without triangulation.  
>>> 
>>> # Convex hull of a cube without triangulation
>>> rbox c | qhull i
>>> 6
>>> 4 6 2 0
>>> 1 5 4 0
>>> 5 7 6 4
>>> 3 1 0 2
>>> 7 3 2 6
>>> 3 7 5 1
>>> 
>>> # Convex hull of a cube with triangulation
>>> rbox c | qhull Qt i
>>> 12
>>> 6 2 0
>>> 4 6 0
>>> 5 4 0
>>> 1 5 0
>>> 5 6 4
>>> 6 5 7
>>> 2 3 0
>>> 3 1 0
>>> 6 3 2
>>> 3 6 7
>>> 3 5 1
>>> 5 3 7
>>> 
>>> If you do not find the reason, please send me the log file from option T4.
>>> 
>>>                               --Brad
>> 
>> I'm not sure it is a Lion thing or an Octave thing. The failure on 
>> Lion/Octave is part of Octave's test suite. The tests are part of 
>> convhulln.cc.
>> 
>>       
>> http://hg.savannah.gnu.org/hgweb/octave/file/b4d7de953066/src/DLD-FUNCTIONS/convhulln.cc
>> 
>> Per your (Brad) suggestion, I added "FO" to the options for the test that 
>> had been failing (1st of the three tests below).
>> 
>> %!testif HAVE_QHULL
>> %! cube = [0 0 0;1 0 0;1 1 0;0 1 0;0 0 1;1 0 1;1 1 1;0 1 1];
>> %! [h, v] = convhulln (cube, {"FO"});
>> %! assert (size (h), [6 4]); 
>> %! h = sortrows (sort (h, 2), [1:4]);
>> %! assert (h, [1 2 3 4; 1 2 5 6; 1 4 5 8; 2 3 6 7; 3 4 7 8; 5 6 7 8]);
>> %! assert (v, 1, 10*eps);
>> 
>> %!testif HAVE_QHULL
>> %! cube = [0 0 0;1 0 0;1 1 0;0 1 0;0 0 1;1 0 1;1 1 1;0 1 1];
>> %! [h, v] = convhulln (cube, "QJ");
>> %! assert (size (h), [12 3]); 
>> %! assert (sortrows (sort (h, 2), [1:3]), [1 2 4; 1 2 5; 1 4 5; 2 3 4; 2 3 
>> 6; 2 5 6; 3 4 8; 3 6 7; 3 7 8; 4 5 8; 5 6 8; 6 7 8]);
>> %! assert (v, 1.0, 1e6*eps);
>> 
>> %!testif HAVE_QHULL
>> %! tetrahedron = [1 1 1;-1 -1 1;-1 1 -1;1 -1 -1];
>> %! [h, v] = convhulln (tetrahedron);
>> %! h = sortrows (sort (h, 2), [1 2 3]);
>> %! assert (h, [1 2 3;1 2 4; 1 3 4; 2 3 4]);
>> %! assert (v, 8/3, 10*eps);
>> 
>> With "FO" the tests all pass.
>> 
>>>> test convhulln.cc
>> Options selected for Qhull 2011.2 2011/11/29:
>> run-id 1048646918  _pre-merge  _zero-centrum  _max-width  1
>> Error-roundoff 1.4e-15  _one-merge 9.7e-15  _near-inside 4.9e-14
>> Visible-distance 2.8e-15  U-coplanar-distance 2.8e-15  Width-outside 5.5e-15
>> _wide-facet 1.7e-14
>> PASSES 3 out of 3 tests
>> 
>> Looking at the qhull docs, I'm not sure that adding "FO" is expected for fix 
>> the problem, but just provide some information about which options were 
>> specified.
>> 
>> So, I tried passing an empty cellstring {""}, and that fixed the problem.
>> 
>> test convhulln.cc
>> PASSES 3 out of 3 tests
>> 
>> Looking at the Octave implementation, it looks to me (my c++ is weak so 
>> skepticism of my reading is merited) like Octave passing "Qt" in this 
>> instance if no options are specified.
>> 
>> Does this mean that we have found an Octave bug ?
>> 
>> Ben
> 
> 
>> Looking at the Octave implementation, it looks to me (my c++ is weak so 
>> skepticism of my reading is merited) like Octave passing "Qt" in this 
>> instance if no options are specified.
> 
> That would explain the behavior on Lion, but the Fedora results indicate that 
> 'Qt' is  not given as the default option list.  All platforms should use the 
> same default option string, otherwise 'm' programs will not be portable.

If you speak of Octave running on Fedora, the "Qt" option is definitely being 
passed unless Octave has been patched on Fedora.

> This looks like an Octave bug.  Octave should follow MathWork's conventions 
> and make option 'Qt' the default on all platforms.  This changes the testcase.
>    http://www.mathworks.com/help/techdoc/ref/convhulln.html
>    http://www.qhull.org/html/qh-optq.htm#Qt
> 
> MathWork's documentation also indicates 'Qx' for 5-d and higher.  This option 
> is not needed since it is automatically set by Qhull in 5-d and higher 
> (unless 'Q0' is set).
>   http://www.qhull.org/html/qh-optq.htm#Qx
> 
> Without option 'Qt', users need to distinguish simplicial facets from 
> non-simplicial facets (in 3-d, triangles vs. squares and other polygons).    
> Modeling codes typically require simplicial facets.

For less than 5 dimensions, Octave uses "Qt" as the default option.  Otherwise, 
the defaults are "Qt Qx". If the user specifies any option, including an empty 
string, the defaults are not used (again if I'm reading the sources correctly).

        
http://hg.savannah.gnu.org/hgweb/octave/file/b4d7de953066/src/DLD-FUNCTIONS/convhulln.cc

It sounds to me as if Octave is doing the correct thing, but Octave's 1st test 
(in convhulln.cc) isn't written properly.

Below I compare Octave with Matlab. On Octave ...

cube = [0 0 0;1 0 0;1 1 0;0 1 0;0 0 1;1 0 1;1 1 1;0 1 1];
[h, v] = convhulln (cube)
h =

   3   4   2
   2   4   1
   6   2   1
   5   6   1
   4   8   1
   8   5   1
   7   3   2
   6   7   2
   7   4   3
   7   8   4
   7   6   5
   8   7   5

v =  1

... and on Matlab ...


cube = [0 0 0;1 0 0;1 1 0;0 1 0;0 0 1;1 0 1;1 1 1;0 1 1];
[h, v] = convhulln (cube)

h =

     3     4     2
     2     4     1
     6     2     1
     5     6     1
     4     8     1
     8     5     1
     7     3     2
     6     7     2
     7     4     3
     7     8     4
     7     6     5
     8     7     5

v =     1

If this all looks/sounds ok, I'll push the attached changeset.

Ben

changeset.patch
Description: Binary data