1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
|
// Copyright (c) 2016 GeometryFactory (France).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org).
//
// $URL: https://github.com/CGAL/cgal/blob/v6.1.1/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/internal/Corefinement/predicates.h $
// $Id: include/CGAL/Polygon_mesh_processing/internal/Corefinement/predicates.h 08b27d3db14 $
// SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
//
//
// Author(s) : Sebastien Loriot
#ifndef CGAL_POLYGON_MESH_PROCESSING_INTERNAL_COREFINEMENT_PREDICATES_H
#define CGAL_POLYGON_MESH_PROCESSING_INTERNAL_COREFINEMENT_PREDICATES_H
#include <CGAL/license/Polygon_mesh_processing/core.h>
#include <boost/graph/graph_traits.hpp>
#include <CGAL/use.h>
namespace CGAL {
namespace Polygon_mesh_processing {
namespace Corefinement {
template<class TriangleMesh, class VertexPointMap, class Node_vector>
struct Less_along_a_halfedge{
typedef boost::graph_traits<TriangleMesh> GT;
typedef typename GT::halfedge_descriptor halfedge_descriptor;
halfedge_descriptor hedge;
const TriangleMesh& tm;
const VertexPointMap& vpm;
const Node_vector& nodes;
Less_along_a_halfedge(halfedge_descriptor hedge_,
const TriangleMesh& tm_,
const VertexPointMap& vpm_,
const Node_vector& nodes_)
: hedge(hedge_)
, tm(tm_)
, vpm(vpm_)
, nodes(nodes_)
{}
bool operator()(std::size_t i, std::size_t j) const {
return CGAL::collinear_are_strictly_ordered_along_line(
nodes.to_exact(get(vpm, target(hedge,tm))),
nodes.exact_node(j),
nodes.exact_node(i));
}
};
//Considering the plane with normal vector [o_prime,o] and containing o.
//We define the counterclockwise order around o when looking from
//the side of the plane containing o_prime.
//We consider the portion of the plane defined by rotating a ray starting at o
//from the planar projection of p1 to the planar projection of p2 in
//counterclockwise order.
//The predicates indicates whether the planar projection of point q lies in this
//portion of the plane.
//Preconditions:
// o_prime,o,p1 are not collinear
// o_prime,o,p2 are not collinear
// o_prime,o,q are not collinear
// o_prime,o,p1,q are not coplanar or coplanar_orientation(o,o_prime,p1,q)==NEGATIVE
// o_prime,o,p2,q are not coplanar or coplanar_orientation(o,o_prime,p2,q)==NEGATIVE
template <class Kernel>
bool sorted_around_edge(
const typename Kernel::Point_3& o_prime, const typename Kernel::Point_3& o,
const typename Kernel::Point_3& p1, const typename Kernel::Point_3& p2,
const typename Kernel::Point_3& q)
{
//guarantee to have non-flat triangles
CGAL_precondition( !collinear(o_prime,o,p1) );
CGAL_precondition( !collinear(o_prime,o,p2) );
CGAL_precondition( !collinear(o_prime,o,q) );
//no two triangles are coplanar and on the same side of their common edge
CGAL_precondition( !coplanar(o_prime,o,p1,q)
|| coplanar_orientation(o,o_prime,p1,q)==NEGATIVE );
CGAL_precondition( !coplanar(o_prime,o,p2,q)
|| coplanar_orientation(o,o_prime,p2,q)==NEGATIVE );
typename Kernel::Orientation_3 orientation;
const auto s0 = orientation(o_prime, o, p1, p2);
if ( s0==COPLANAR ) {
//o, o_prime, p1 and p2 are coplanar
Orientation orient=orientation(o_prime,o,p1,q);
CGAL_precondition(orient!=COPLANAR);
return orient==POSITIVE;
}
//o, o_prime, p1 and p2 are not coplanar
const auto s1 = orientation(o_prime, o, p1, q);
const auto s2 = orientation(o_prime, o, q , p2);
if (s0 == POSITIVE) // the angle p1,o,p2 is smaller that Pi.
return ( s1 == POSITIVE )
&& ( s2 ==POSITIVE ); //true if the angles p1,o,q and q,o,p2 are smaller than Pi
else
return ( s1 != NEGATIVE )
|| ( s2 != NEGATIVE ); //true if the angle p1,o,q or the angle q,o,p2 is smaller than or equal to Pi
}
template <class Kernel>
bool p_is_below_q(const typename Kernel::Point_3& o_prime, const typename Kernel::Point_3& o,
const typename Kernel::Point_3& p, const typename Kernel::Point_3& q)
{
CGAL::Orientation res = CGAL::orientation(o_prime, o, p, q);
CGAL_assertion(res != CGAL::COPLANAR);
return res == CGAL::POSITIVE;
}
template <class Kernel>
bool are_triangles_coplanar_same_side(
const typename Kernel::Point_3& o_prime, const typename Kernel::Point_3& o,
const typename Kernel::Point_3& P, const typename Kernel::Point_3& q)
{
if ( CGAL::orientation(o_prime, o, P ,q) != COPLANAR )
return false;
Orientation cpl_orient = coplanar_orientation(o_prime, o, P, q);
CGAL_assertion( cpl_orient != COLLINEAR );
return cpl_orient == POSITIVE;
}
template <class Node_id, class Node_vector, class vertex_descriptor, class VPMP, class VPMQ>
bool are_triangles_coplanar_same_side(Node_id o_prime_index,
Node_id o_index,
Node_id p_index,
Node_id q_index,
vertex_descriptor p,
vertex_descriptor q,
const VPMP& vpm_p,
const VPMQ& vpm_q,
const Node_vector& nodes)
{
const Node_id NID((std::numeric_limits<Node_id>::max)());
return are_triangles_coplanar_same_side<typename Node_vector::Exact_kernel>(
nodes.exact_node(o_prime_index),
nodes.exact_node(o_index),
p_index == NID ? nodes.to_exact(get(vpm_p,p)) : nodes.exact_node(p_index),
q_index == NID ? nodes.to_exact(get(vpm_q,q)) : nodes.exact_node(q_index)
);
}
template <class Node_id, class Node_vector, class vertex_descriptor, class VPMP, class VPMQ>
bool sorted_around_edge( Node_id o_prime_index,
Node_id o_index,
Node_id p1_index,
Node_id p2_index,
Node_id q_index,
vertex_descriptor p1,
vertex_descriptor p2,
vertex_descriptor q,
const VPMP& vpm_p,
const VPMQ& vpm_q,
const Node_vector& nodes)
{
const Node_id NID((std::numeric_limits<Node_id>::max)());
return sorted_around_edge<typename Node_vector::Exact_kernel>(
nodes.exact_node(o_prime_index),
nodes.exact_node(o_index),
p1_index == NID ? nodes.to_exact(get(vpm_p,p1))
: nodes.exact_node(p1_index),
p2_index == NID ? nodes.to_exact(get(vpm_p,p2))
: nodes.exact_node(p2_index),
q_index == NID ? nodes.to_exact(get(vpm_q,q))
: nodes.exact_node(q_index ) );
}
template <class Node_id, class Node_vector, class vertex_descriptor, class VPMP, class VPMQ>
bool p_is_below_q( Node_id o_prime_index,
Node_id o_index,
Node_id p_index,
Node_id q_index,
vertex_descriptor p,
vertex_descriptor q,
const VPMP& vpm_p,
const VPMQ& vpm_q,
const Node_vector& nodes)
{
const Node_id NID((std::numeric_limits<Node_id>::max)());
return p_is_below_q<typename Node_vector::Exact_kernel>(
nodes.exact_node(o_prime_index),
nodes.exact_node(o_index),
p_index == NID ? nodes.to_exact(get(vpm_p,p))
: nodes.exact_node(p_index),
q_index == NID ? nodes.to_exact(get(vpm_q,q))
: nodes.exact_node(q_index) );
}
} } } // CGAL::Polygon_mesh_processing::Corefinement
#endif // CGAL_POLYGON_MESH_PROCESSING_INTERNAL_COREFINEMENT_PREDICATES_H
|
