Re: Release candidate for Qhull 2012.1

[Rik]

On 01/29/2012 04:16 PM, address@hidden wrote:
> Message: 6
> Date: Sun, 29 Jan 2012 19:15:51 -0500
> From: Ben Abbott <address@hidden>
> To: Brad Barber <address@hidden>
> Cc: address@hidden
> Subject: Re: Release candidate for Qhull 2012.1
> Message-ID: <address@hidden>
> Content-Type: text/plain; CHARSET=US-ASCII
>
>
> 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 ?

I don't think so.  Check the help text for convhulln in Octave which I quote below:

     An optional second argument, which must be a string or cell array
     of strings, contains options passed to the underlying qhull
     command.  See the documentation for the Qhull library for details
     `http://www.qhull.org/html/qh-quick.htm#options'.  The default
     options depend on the dimension of the input:

        * 2D, 3D, 4D: OPTIONS = `{"Qt"}'

        * 5D and higher: OPTIONS = `{"Qt", "Qx"}'

     If OPTIONS is not present or `[]' then the default arguments are
     used.  Otherwise, OPTIONS replaces the default argument list.  To
     append user options to the defaults it is necessary to repeat the
     default arguments in OPTIONS.  Use a null string to pass no
     arguments.

So the default case for the 3D cube input is to pass the option "Qt".  The question still remains why this input with this option works perfectly fine on Fedora, but not on Lion.  If it is an option passing problem you could try passing "Qt" directly on the command line.  This will replace the default option string.

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, "Qt");
assert (size (h), [6 4]);

I still expect that to fail in Lion, but it is worth testing.

--Rik