CGAL users discussion list

["J.L.M." <>]

Thank you for your continued help with this problem. I must admit that 
some of my problems were with incorrectly oriented shapes. I wish that 
was my only problem though, because that I can fix.

Attached is my small example program using the kernel you suggested. 
Also attached are two shapes that I carefully examined. All facets of 
both shapes should be counter-clockwise oriented. With this program and 
these input shapes, I still get the assertion violation.

I hope you can have the time to verify that what I have done here is 
valid, and if so work towards a fix in CGAL.

Thanks a lot.

On 02/07/2011 03:15 AM, Sebastien Loriot (GeometryFactory) wrote:
> J.L.M. wrote:
> > I just tried the kernel you suggested and I get the same problem.
> >
> > terminate called after throwing an instance of
> > 'CGAL::Assertion_exception'
> > what(): CGAL ERROR: assertion violation!
> > Expr: Ntmp.is_valid()
> > File:
> > /import/lightcycle/home/jlm/school/masters_thesis/code/CGAL-3.7/include/CGAL/Minkowski_sum_3/bipartite_nary_union_sorted_combined.h
> >
> > Line: 222
> > Aborted
> Did you correctly orient the cube? (as explained in one of my previous
> email)
>
> try with the one attached.
>
> S.
>
>
> > On 01/24/2011 03:10 AM, Sebastien Loriot (GeometryFactory) wrote:
> > > I add a quick look but did not have time to finish my investigations.
> > > Can you try with CGAL::Simple_cartesian<CGAL::Gmpq> as Kernel and tell
> > > us whether you also observe the same problems?
> > >
> > > S.
> > >
> > >
> > > J.L.M. wrote:
> > > > I was wondering if any progress has been made to fix the boundary
> > > > function for Nef_polyhedron_3. I am using this code in a thesis, and I
> > > > am finding that I can not avoid the assertion in the Minkowski_sum_3
> > > > if I use a non-convex polyhedron. Limiting my input to convex
> > > > polyhedra greatly reduces the utility of my implementation, and my
> > > > experiment depends on non-convex polyhedra.
> > > >
> > > > Thank you for your time.
> > > >
> > > > Jason M'Sadoques
> > > >
> > > > On 12/27/2010 04:32 PM, J.L.M. wrote:
> > > > > Sebastien,
> > > > >
> > > > > Thank you for your reply. I have been on holiday, or I would have
> > > > > responded sooner. I hope you will be able to provide a fix to the
> > > > > boundary function, as this is essential to my research. If there is
> > > > > anything I can do to help, please let me know.
> > > > >
> > > > > Here are a few responses to your statements. The call to boundary is
> > > > > necessary for my work. What I am computing is the feasible region that
> > > > > contains all points in which the object can be placed and be wholly
> > > > > contained in the container (stored in result). If you would like, I
> > > > > have
> > > > > a paper I can provide to you that shows how this works.
> > > > >
> > > > > Second, I am wondering about your statement that I need to make a copy
> > > > > of container. I see that the minkowski_sum_3 modifies the input,
> > > > > and in
> > > > > my example code the input is container_boundary, and object.
> > > > > container_boundary should be a copy of container (well just the
> > > > > boundary
> > > > > of course).
> > > > >
> > > > > You are correct that the result is empty in this example. The correct
> > > > > algorithm uses the interior of the object (actually the inverted
> > > > > interior) in the Minkowski sum. I removed that part while simplifying
> > > > > the code to one that shows the problem.
> > > > >
> > > > > Thank you for pointing out the non-standard OFF files. I am
> > > > > creating my
> > > > > shapes in Blender, and I have to post-process them. First, Blender
> > > > > gives
> > > > > me coordinates that are something like 1.00001 or 0.99999, and I need
> > > > > them to be exact whole numbers for accurate computations. Also,
> > > > > Blender
> > > > > has Z increase up, and Y increase into the scene, which is different
> > > > > than I am used to with OpenGL, so I swapped those coordinates. It must
> > > > > be in my swapping of those that I have switched the orientation of the
> > > > > facets.
> > > > >
> > > > > Thank you again for your time.
> > > > >
> > > > > On 12/20/2010 08:26 AM, Sebastien Loriot (GeometryFactory) wrote:
> > > > > > J.L.M. wrote:
> > > > > > > I have been writing some programs that use the Nef_polyhedron_3 and
> > > > > > > Minkowski_sum_3 portions of the CGAL library. I have discovered a
> > > > > > > number of assertions with various input shapes. The attached
> > > > > > > backtrace
> > > > > > > shows one example problem. I have also attached a small example
> > > > > > > program, and the input shapes. The l-shape is shown in the attached
> > > > > > > jpeg file.
> > > > > > >
> > > > > > > This problem shows up in both CGAL 3.7 and 3.6.1. I am using GCC
> > > > > > > 4.5.1
> > > > > > > on Arch Linux with kernel version 2.6.36.
> > > > > > >
> > > > > > > I think this is a bug, since it does not occur with other input
> > > > > > > shapes. I would be very grateful if someone can help me fix it since
> > > > > > > the Minkowski_sum_3 is essential to my research.
> > > > > > >
> > > > > > > Thank you for your time.
> > > > > > >
> > > > > > > Jason M'Sadoques
> > > > > > >
> > > > > > >
> > > > > > >
> > > > > > > ------------------------------------------------------------------------
> > > > > > It seems their is a problem in boundary function.
> > > > > >
> > > > > > If I replace:
> > > > > > Nef_polyhedron_3 container_boundary(container.boundary());
> > > > > > by
> > > > > > Nef_polyhedron_3 container_boundary(container);
> > > > > >
> > > > > > Your program runs fine (with your data, the call to boundary is
> > > > > > superfluous).
> > > > > >
> > > > > > Note that as you are then reusing "container", you need to make a
> > > > > > copy
> > > > > > of it
> > > > > > (see
> > > > > > http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Minkowski_sum_3/Chapter_main.html)
> > > > > >
> > > > > >
> > > > > >
> > > > > >
> > > > > >
> > > > > > Note also that the difference you are computing will be empty as the
> > > > > > Minkowski sum contains "container".
> > > > > >
> > > > > > Finally, note that facets of your cube are clockwise oriented
> > > > > > while the
> > > > > > usual convention is to use counterclockwise oriented faces in off
> > > > > > files.
> > > > > >
> > > > > > I'll try to find a fix to boundary function and will post it here.
> > > > > >
> > > > > > S.
# Created by the script cgal_create_cmake_script
# This is the CMake script for compiling a CGAL application.


project( Nef_3_example )

CMAKE_MINIMUM_REQUIRED(VERSION 2.4.5)

set(CMAKE_ALLOW_LOOSE_LOOP_CONSTRUCTS true)

if ( COMMAND cmake_policy )
  cmake_policy( SET CMP0003 NEW )  
endif()

find_package(CGAL QUIET COMPONENTS Core )

if ( CGAL_FOUND )

  include( ${CGAL_USE_FILE} )

  include( CGAL_CreateSingleSourceCGALProgram )

  include_directories (BEFORE ../../include)

  #I'm just adding the output of sdl-config --cflags -libs below.
  set(CMAKE_CXX_FLAGS "-frounding-math -ggdb3 -lGL -lGLU -lglut 
-I/usr/include/SDL -D_GNU_SOURCE=1 -D_REENTRANT -L/usr/lib -lSDL -lpthread")

  #create_single_source_cgal_program( "bug_union_find.cpp" )
  create_single_source_cgal_program( "bug_ntmp_invalid.cpp" )
  #create_single_source_cgal_program( "containment.cpp" )
  #create_single_source_cgal_program( "locate_point.cpp" )

else()
  
    message(STATUS "This program requires the CGAL library, and will not be 
compiled.")
  
endif()

/* This program shows the bug
terminate called after throwing an instance of 'CGAL::Assertion_exception'
  what():  CGAL ERROR: assertion violation!
Expr: Ntmp.is_valid()
File: /import/lightcycle/home/jlm/school/masters_thesis/code/CGAL-3.6.1/include/CGAL/Minkowski_sum_3/bipartite_nary_union_sorted_combined.h
Line: 222
Aborted
*/

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/IO/Nef_polyhedron_iostream_3.h>
#include <CGAL/minkowski_sum_3.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/OFF_to_nef_3.h>
#include <fstream>

//typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef CGAL::Simple_cartesian<CGAL::Gmpq>::Kernel Kernel;
typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron_3;
typedef CGAL::Polyhedron_3<Kernel> Polyhedron_3;

int main(int argc, char* argv[])
{
  Nef_polyhedron_3 container;
  std::ifstream file_stream("shapes/l_shape.off");
  int unhandled_facets=CGAL::OFF_to_nef_3(file_stream, container);
  file_stream.close();
  file_stream.clear();
  file_stream.open("shapes/cube.off");
  Nef_polyhedron_3 object;
  unhandled_facets=CGAL::OFF_to_nef_3(file_stream, object);

  Nef_polyhedron_3 container_boundary(container.boundary());
  Nef_polyhedron_3 result=container-CGAL::minkowski_sum_3(container_boundary, object);
  return(0);
}
OFF
8 6 0
1 -1 -1
1 -1 1
-1 -1 1
-1 -1 -1
1 1 -1
1 1 1
-1 1 1
-1 1 -1
4 0 1 2 3
4 4 7 6 5
4 0 4 5 1
4 1 5 6 2
4 2 6 7 3
4 4 0 3 7
OFF
16 14 0
1 -1 -1
1 -1 1
-1 -1 1
-1 -1 -1
3 3 -1
3 3 1
-1 3 1
-1 3 -1
1 1 1
3 1 1
1 1 -1
3 1 -1
1 3 1
-1 1 1
-1 1 -1
1 3 -1
4 0 1 2 3
4 4 5 9 11
4 13 2 1 8
4 13 14 3 2
4 6 7 14 13
4 6 13 8 12
4 12 8 9 5
4 15 12 5 4
4 7 6 12 15
4 0 10 8 1
4 10 11 9 8
4 0 3 14 10
4 7 15 10 14
4 15 4 11 10