sloriot
commented
3 years ago Hi Olivier,
Nef (and Minkowski) requires exact constructions so it cannot work with floating point based number type.
Open ochafik opened 3 years ago
sloriot
commented
3 years ago Hi Olivier,
Nef (and Minkowski) requires exact constructions so it cannot work with floating point based number type.
ochafik
commented
3 years ago Hey Sebastien, thanks for confirming!
It's a bit far-fetched, but wondering how far I could go writing my own approximate kernel where a == b allows for some epsilon difference... do you know if anything of the sort has been attempted, or how doomed to fail it would be?
Also, exploring other leads, I was wondering if I could maybe use some approximate convex decomposition to limit the worst cases of many convex parts in OpenSCAD's custom minkowski algorithm. I came across https://github.com/CGAL/cgal/issues/3270, and I'm not sure whether the project was integrated into CGAL proper: the Triangulated Surface Mesh Segmentation looks close but not quite the same. Would you know how it compares / if there is hope to get the GSOC version for general use?
sloriot
commented
3 years ago Approximate won't work because internally it assumes that all the vertices of a face are coplanar which is no longer the case as soon as you are using a kernel with inexact constructions.
About the approximate convex decomposition, the PR is still opened https://github.com/CGAL/cgal/pull/3302 as I have to investigate why it is that slow (compared to the author's version).
ochafik
commented
3 years ago Approximate won't work because internally it assumes that all the vertices of a face are coplanar which is no longer the case as soon as you are using a kernel with inexact constructions.
I would be okay with lots of inaccuracies piling up and some failed assertions down the line forcing me to fall back to an exact kernel. Do you think the lack of assertions being thrown would be a good proxy to evaluate whether the nef / minkowski sum succeeded against all odds? A fast (best effort), approximate minkowski could potentially be great to have in OpenSCAD, if only for previews maybe.
the PR is still opened #3302 as I have to investigate why it is that slow (compared to the author's version).
Hah, cool, good luck! Also, even a suboptimal version could have great practical use, hope it lands!
ochafik
commented
3 years ago approximate kernel where a == b allows for some epsilon difference.
FWIW, I've taken a stab at making such a kernel, just to convince myself it was a bad idea. It's not pretty, it builds nefs alright on a handful of trivial models (Cartesian<FuzzyDouble>), even agrees to do nef csg ops, but... explodes in Convex_decomposition_3. Oh well, you warned me 🤷♂️.
// Copyright 2021 Google LLC.
// SPDX-License-Identifier: Apache-2.0
#pragma once
#include <cmath>
#include <type_traits>
// Field type for an Ipick: inexact predicates (epsilon), inexact construction (double) kernel
class FuzzyDouble {
public:
static constexpr double epsilon = 0.00000001;
double value;
template <typename T, std::enable_if_t<std::is_arithmetic<T>::value, bool> = true>
FuzzyDouble(T value) : value(static_cast<double>(value)) {}
FuzzyDouble(const FuzzyDouble& other) { *this = other; }
FuzzyDouble() : value(0.0) {}
operator double() const { return value; }
FuzzyDouble &operator=(const FuzzyDouble& other) { value = other.value; return *this; }
FuzzyDouble operator-() const { return -value; }
#define OP_TEMPLATE(T) \
template <typename T, std::enable_if_t<(std::is_arithmetic<T>::value || std::is_assignable<FuzzyDouble, T>::value), bool> = true>
OP_TEMPLATE(T) bool operator==(const T& x) const { return std::abs(value - static_cast<double>(x)) <= FuzzyDouble::epsilon;}
OP_TEMPLATE(T) bool operator!=(const T& x) const { return !(*this == x); }
OP_TEMPLATE(T) bool operator<(const T& x) const { return value + FuzzyDouble::epsilon < static_cast<double>(x); }
OP_TEMPLATE(T) bool operator<=(const T& x) const { return value <= static_cast<double>(x) + FuzzyDouble::epsilon; }
OP_TEMPLATE(T) bool operator>(const T& x) const { return value > static_cast<double>(x) + FuzzyDouble::epsilon; }
OP_TEMPLATE(T) bool operator>=(const T& x) const { return value + FuzzyDouble::epsilon >= static_cast<double>(x); }
OP_TEMPLATE(T) FuzzyDouble operator*(const T& x) const { return value * static_cast<double>(x); }
OP_TEMPLATE(T) FuzzyDouble operator/(const T& x) const { return value / static_cast<double>(x); }
OP_TEMPLATE(T) FuzzyDouble operator+(const T& x) const { return value + static_cast<double>(x); }
OP_TEMPLATE(T) FuzzyDouble operator-(const T& x) const { return value - static_cast<double>(x); }
OP_TEMPLATE(T) FuzzyDouble& operator*=(const T& x) { value *= static_cast<double>(x); return *this; }
OP_TEMPLATE(T) FuzzyDouble& operator/=(const T& x) { value /= static_cast<double>(x); return *this; }
OP_TEMPLATE(T) FuzzyDouble& operator+=(const T& x) { value += static_cast<double>(x); return *this; }
OP_TEMPLATE(T) FuzzyDouble& operator-=(const T& x) { value -= static_cast<double>(x); return *this; }
};
std::ostream& operator<<(std::ostream& out, const FuzzyDouble& n) { out << n.value; return out; }
std::istream& operator>>(std::istream& in, FuzzyDouble& n) { in >> n.value; return in; }
namespace std { FuzzyDouble sqrt(const FuzzyDouble& x) { return std::sqrt(x.value); } }
namespace CGAL {
inline FuzzyDouble min BOOST_PREVENT_MACRO_SUBSTITUTION(const FuzzyDouble& x,const FuzzyDouble& y){ return std::min(x.value, y.value); }
inline FuzzyDouble max BOOST_PREVENT_MACRO_SUBSTITUTION(const FuzzyDouble& x,const FuzzyDouble& y){ return std::max(x.value, y.value); }
CGAL_DEFINE_COERCION_TRAITS_FOR_SELF(FuzzyDouble)
CGAL_DEFINE_COERCION_TRAITS_FROM_TO(short ,FuzzyDouble)
CGAL_DEFINE_COERCION_TRAITS_FROM_TO(int ,FuzzyDouble)
CGAL_DEFINE_COERCION_TRAITS_FROM_TO(long ,FuzzyDouble)
CGAL_DEFINE_COERCION_TRAITS_FROM_TO(float ,FuzzyDouble)
CGAL_DEFINE_COERCION_TRAITS_FROM_TO(double ,FuzzyDouble)
template <>
class Algebraic_structure_traits<FuzzyDouble> : public Algebraic_structure_traits_base<FuzzyDouble,Field_with_sqrt_tag> {
public:
typedef Tag_false Is_exact;
typedef Tag_true Is_numerical_sensitive;
};
template <>
class Real_embeddable_traits<FuzzyDouble>: public INTERN_RET::Real_embeddable_traits_base<FuzzyDouble,CGAL::Tag_true>
{
typedef Algebraic_structure_traits<Type> AST;
public:
typedef Tag_true Is_real_embeddable;
typedef Uncertain<bool> Boolean;
typedef Uncertain<CGAL::Comparison_result> Comparison_result;
typedef Uncertain<CGAL::Sign> Sign;
typedef AST::Is_zero Is_zero;
struct Is_finite: public CGAL::cpp98::unary_function<Type,Boolean>{
inline Boolean operator()(const Type &x) const { return !std::isinf(x.value) && !std::isnan(x.value); };
};
struct Abs: public CGAL::cpp98::unary_function<Type,Type>{
inline Type operator()(const Type &x) const { return std::abs(x.value); };
};
struct To_interval: public CGAL::cpp98::unary_function<Type,std::pair<double,double> >{
inline std::pair<double,double> operator()(const Type &x)const{
return std::make_pair(x.value - FuzzyDouble::epsilon, x.value + FuzzyDouble::epsilon);
};
};
};
} //namespace CGAL
Hi CGAL team!
I've been struggling to use
Epick(orCartesian<double>) withNef_polyhedron_3: getting failures with even quite simple polyhedra, either during creation of the nef itself or during calls tominkowski_sum_3. The same models work great w/Epeckand other exact kernels. Is that expected?(also, not sure if relevant, but
Polyhedron_3::is_valid(false, /*level*/ 1)says these models aren't valid but level 0 says they are?)Context: I'm trying to find ways to speed up OpenSCAD's minkowski operations, which only use CGAL's minkowski with an exact kernel as a fallback. Their default algorithm is to decompose each operand in convex parts and union the hulls of the cross products of these respective parts. Since these hulls operate with
Epick, I figured, why not be inexact all the way and giveminkowski_sum_3another try? But it doesn't seem to work out of the box :-(I've pasted a self-contained reproduction case below, which can be compiled & run with:
Resulting output:
sphere(1, $fn=8);(run with./invalid_poly 1): fails to create the nef outrightsphere(1, $fn=3);(run with./invalid_poly 2): nef creation succeeds but minkowski_sum_3 fails:Source Code
invalid_poly.cc:Environment