Repository navigation
Expand file tree
/
Copy pathcdt-tf.cpp
More file actions
258 lines (235 loc) · 10.1 KB
/
Copy pathcdt-tf.cpp
File metadata and controls
258 lines (235 loc) · 10.1 KB
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
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
// cdt-tf: trueform 2D constrained Delaunay triangulation.
//
// param = expected constraint crossings (0 = valid PSLG / unconstrained)
// n = input point count
// timed = arrays-in -> arrays-out (build tf points/edges from flat arrays,
// triangulate, emit faces+points back to flat arrays), median of 5.
//
// trueform is the reference, but it is still validated: `valid` here is a real
// postcondition check (bench::validate_cdt), not an assumption. A reference
// that grades itself pass unconditionally cannot catch its own regressions.
//
// Two deliberate configuration choices, both in the name of apples-to-apples:
//
// * The RAW triangulator, not tf::make_cdt. make_cdt performs parity-based
// interior extraction (it returns only triangles inside the constrained
// outlines). Every competitor here -- Triangle `-pc`, artem-ogre/CDT with
// eraseSuperTriangle, detria, CGAL -- returns the full convex-hull
// triangulation with constraints recovered. The local retained build uses
// its explicit topology-only phase and therefore does not compute region
// adjacency or labels for this benchmark.
//
// * The coordinate/exact width is PINNED and named, never left to the class
// default -- and it is reported as two separate library rows, because the
// two are not the same problem:
//
// tf float32 + int32 the mode callers actually use. The int32
// lattice is ~128x finer than a float32's 24-bit
// mantissa, so it costs nothing at this input
// precision -- and it is ~2x faster, because
// int32 evaluates predicates by direct exact
// integer arithmetic with no filter at all.
// tf64 float64 + int64 what tf.cdt gives a float64 caller
// (make_cdt runs resolve_int_type: double ->
// int64). This is the LIKE-FOR-LIKE row against
// CGAL EPICK, which is a double kernel.
//
// The raw class template defaults to int32 regardless of Coord, so writing
// <Index, double> and taking the default silently benchmarks double input
// at int32 precision. That flatters trueform by ~2x and is why this is
// spelled out rather than defaulted.
//
// ./cdt-tf <operand_list> [out_root=results/raw] [unused]
#include "../common/corpus.hpp"
#include "../common/csv.hpp"
#include "../common/meta.hpp"
#include "../common/pslg.hpp"
#include "../common/timer.hpp"
#if defined(TF_LOCAL_CDT) && TF_LOCAL_CDT
#include "local/include/trueform/topology/constrained_delaunay_triangulator.hpp"
#include "local/include/trueform/topology/cdt/delaunay_execution_policy.hpp"
#else
#include <trueform/topology/constrained_delaunay_triangulator.hpp>
#include <trueform/trueform.hpp>
#endif
#include <array>
#include <cstdio>
#include <string>
#include <vector>
#if defined(TF_SINGLE_THREAD) && TF_SINGLE_THREAD
#include <tbb/global_control.h>
#endif
namespace {
// Built twice from this one source (see cdt/CMakeLists.txt):
//
// tf split_constraints=true -- the shipped default. Resolves
// crossings, so it is the entry on BOTH axes.
// tf_nosplit split_constraints=false -- preserve constraints verbatim.
//
// tf_nosplit exists for fairness, not flattery. detria, poly2tri, Clipper2 and
// delabella offer exactly one contract: "constraints must not intersect."
// split_constraints=false is trueform offering that same contract, and it skips
// find_obstruction entirely -- strictly less work. Charting split=true against
// a library that never looks for crossings would bill trueform for work its
// opponent does not do. On a valid PSLG the honest comparison against a tier-1
// library is tf_nosplit; the tf/tf_nosplit delta is itself the interesting
// number (what crossing-detection costs on input that has none).
//
// The capability gate then does the right thing with no special-casing:
// tf_nosplit does not declare cap_crossings, so on axis B it records
// `rejected` -- exactly as detria will.
#ifndef TF_SPLIT_CONSTRAINTS
#define TF_SPLIT_CONSTRAINTS 1
#endif
#ifndef TF_LIB_SLUG
#define TF_LIB_SLUG "tf"
#endif
constexpr const char *kOperation = "cdt";
constexpr const char *kLibrary = TF_LIB_SLUG;
constexpr bool kSplitConstraints = TF_SPLIT_CONSTRAINTS != 0;
constexpr unsigned kCapabilities =
bench::cap_constraints | (kSplitConstraints ? bench::cap_crossings : 0u);
#ifndef TF_COORD
#define TF_COORD float
#define TF_INT tf::exact::int32
#define TF_MATCH_TOL 1e-5 // float32 round-trip through the lattice
#endif
#ifndef TF_MATCH_TOL
#define TF_MATCH_TOL 1e-9
#endif
using Index = int;
using Coord = TF_COORD;
#if defined(TF_LOCAL_CDT) && TF_LOCAL_CDT
#ifndef TF_EXECUTION
#define TF_EXECUTION tf::topology::cdt::serial_delaunay_execution_policy
#endif
using Cdt =
tf::constrained_delaunay_triangulator<Index, Coord, TF_INT, TF_EXECUTION>;
#else
using Cdt = tf::constrained_delaunay_triangulator<Index, Coord, TF_INT>;
#endif
volatile std::size_t g_sink = 0;
} // namespace
int main(int argc, char **argv) {
#if defined(TF_SINGLE_THREAD) && TF_SINGLE_THREAD
const tbb::global_control serial(tbb::global_control::max_allowed_parallelism,
1);
#endif
if (argc < 2) {
std::fprintf(stderr, "usage: %s <operand_list> [out_root]\n", argv[0]);
return 2;
}
const std::string list_path = argv[1];
const std::string out_root = argc > 2 ? argv[2] : "results/raw";
const auto operands = bench::load_operand_list(list_path);
bench::csv_writer csv(
bench::results_path(out_root, kOperation, kLibrary, "csv"),
{"out_points", "out_faces", "crossings_resolved", "recovery_checked"});
for (const auto &op : operands) {
const auto in = bench::load_pslg(op.path);
const std::string param = std::to_string(in.expected_crossings);
if (in.n_points() == 0) {
csv.row(op.case_id, 0, param, 0.0, 0, "error:empty_or_missing",
{"0", "0", "-1", "0"});
continue;
}
// Capability gate: record `rejected` rather than a timing for a case this
// library declares out of scope. (Vacuous for trueform; the shared shape
// matters because detria/poly2tri/Clipper2 will take this branch.)
if (in.has_crossings() && !(kCapabilities & bench::cap_crossings)) {
csv.row(op.case_id, in.n_points(), param, 0.0, 0,
bench::note::rejected_no_crossings, {"0", "0", "-1", "0"});
continue;
}
double time_ms = 0.0;
bench::cdt_check chk;
std::vector<std::array<double, 2>> out_points;
std::vector<std::array<Index, 3>> out_faces;
bool built = false;
try {
time_ms = bench::time_median_ms(
[&] {
// ---- timed: arrays-in -> arrays-out
// -------------------------------- Corpus is canonical float64
// (CONVENTIONS: identical bytes to every library). A float32 build
// converts here, inside the timer -- a real float32 caller would
// already hold float32 and skip this, so this is a small penalty
// against trueform, not a favour.
tf::points_buffer<Coord, 2> pts;
pts.reserve(in.points.size());
for (const auto &p : in.points)
pts.push_back(tf::point<Coord, 2>{Coord(p[0]), Coord(p[1])});
std::vector<std::array<Index, 2>> edges;
edges.reserve(in.segments.size());
for (const auto &s : in.segments)
edges.push_back({Index(s[0]), Index(s[1])});
Cdt cdt;
#if defined(TF_LOCAL_CDT) && TF_LOCAL_CDT
built = cdt.build_triangulation(
pts.points(), tf::make_edges(tf::make_range(edges)),
kSplitConstraints);
#else
built =
cdt.build(pts.points(), tf::make_edges(tf::make_range(edges)),
kSplitConstraints);
#endif
out_points.clear();
out_faces.clear();
if (built) {
#if defined(TF_LOCAL_CDT) && TF_LOCAL_CDT
const auto &faces = cdt.faces();
#else
auto faces = cdt.make_faces();
#endif
auto cpts = cdt.converted_points();
out_points.reserve(cpts.size());
for (std::size_t i = 0; i < cpts.size(); ++i)
out_points.push_back({cpts[i][0], cpts[i][1]});
out_faces.reserve(faces.size());
for (const auto face : faces)
out_faces.push_back({face[0], face[1], face[2]});
}
g_sink += out_faces.size();
// --------------------------------------------------------------------
},
5);
if (!built) {
chk.valid = 0;
chk.note = "build_failed";
} else {
std::vector<std::array<std::int32_t, 3>> f32;
f32.reserve(out_faces.size());
for (const auto &f : out_faces)
f32.push_back(
{std::int32_t(f[0]), std::int32_t(f[1]), std::int32_t(f[2])});
chk = bench::validate_cdt(in, out_points, f32, TF_MATCH_TOL);
}
} catch (const std::exception &e) {
chk.valid = 0;
chk.note = std::string("error:") + e.what();
}
csv.row(op.case_id, in.n_points(), param, time_ms, chk.valid, chk.note,
{std::to_string(chk.out_points), std::to_string(chk.out_faces),
std::to_string(chk.crossings_resolved),
chk.recovery_checked ? "1" : "0"});
}
bench::meta_info meta;
meta.operation = kOperation;
meta.library = kLibrary;
#if defined(TF_LOCAL_CDT) && TF_LOCAL_CDT
meta.library_version = "local-dc-retained";
#else
meta.library_version = "0.9.17";
#endif
#if defined(TF_SINGLE_THREAD) && TF_SINGLE_THREAD
meta.threads = 1;
#endif
bench::write_meta(
bench::results_path(out_root, kOperation, kLibrary, "meta.json"), meta);
// NB: exit 0 unconditionally. `g_sink` exists only to keep the optimiser from
// eliding the timed region; folding it into the return value (as the older
// harnesses do) makes the exit status depend on the data, and run.py uses
// check=True -- so a clean run whose sink lands odd is logged as FAILED.
(void)g_sink;
return 0;
}