Re: Release candidate for Qhull 2012.1

[Ben Abbott]

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