Compare commits

...
Author SHA1 Message Date
Tanish Manku 80c6e07415 render: budget the points wide polylines sample (#1922 F-06a)
The filled band of a wide polyline and the centre line of a dashed one
sampled every arc segment with no total, as Polyline::tessellate did
before #2723. Both now spend the same MAX_TESSELLATED_POINTS budget per
polyline; past it the remaining arcs are chords.
2026-11-19 15:52:33 -07:00
Tanish Manku 8d78cd0959 io: budget the points hatch boundary curves are read into (#1922 F-06c)
An elliptic or spline HATCH edge is a few groups in the file but up to
about 4,000 points once read. The edges of one hatch now share at most
4M points and all hatches of one file 16M; past that an ellipse edge is
read as 9 points and a spline edge as its control (or fit) points, and
the read notes say how many hatches were read coarsely.
2026-11-19 15:52:33 -07:00
Tanish Manku fba309f8a6 render: budget the points one drawing builds (#1922 F-06b)
MAX_BLOCK_EXPANSION counts objects, not their size, so two million block
copies of one finely tessellated object could build billions of points.
Every polyline, triangle, point, ray and image corner is now charged to
one MAX_DISPLAY_POINTS (64M) budget shared by the whole build: parallel
parts, XCLIP parts and viewport contents. Past it nothing more is drawn,
block copies stop being visited and DisplayList::truncated is set, which
now also survives joining the parts of a parallel build. Primitive
offsets are converted with u32::try_from instead of wrapping.
2026-11-19 15:52:33 -07:00
12 changed files with 398 additions and 51 deletions
+61 -5
View File
@@ -67,11 +67,13 @@ struct Rx {
paper_views_dropped: Vec<(Option<String>, bool, Option<String>)>,
/// Upper-case name of the BLOCK whose entities are being read, if any.
block: Option<String>,
/// The points HATCH boundary curves may still be sampled into.
curves: hatch::CurvePoints,
}
/// Read a DXF file into a drawing.
pub fn read(bytes: &[u8]) -> Result<Drawing> {
read_budgeted(bytes, 4_000_000)
read_budgeted(bytes, 4_000_000, hatch::MAX_READ_CURVE_POINTS)
}
/// A block definition read from BLOCKS: name, base point, description, entities (owner, paper
@@ -82,8 +84,9 @@ type BlockDef = (String, Vec3, String, Vec<(Option<String>, bool, Entity)>, i64)
/// A LAYOUT object: name, tab order, block record, page setup and its limits (groups 10/11).
type LayoutDef = (String, u32, String, PageSetup, Option<(Vec2, Vec2)>);
/// Import DXF sections while sharing one materialized-table-cell budget across blocks and entity sections.
fn read_budgeted(bytes: &[u8], mut table_cells_left: usize) -> Result<Drawing> {
/// Import DXF sections while sharing one materialized-table-cell budget and one hatch curve-point
/// budget across blocks and entity sections.
fn read_budgeted(bytes: &[u8], mut table_cells_left: usize, curve_points: usize) -> Result<Drawing> {
let tags = craft_dxf::parse(bytes).map_err(|e| IoError::Format(e.to_string()))?;
let secs = sections(&tags);
if secs.is_empty() {
@@ -93,7 +96,7 @@ fn read_budgeted(bytes: &[u8], mut table_cells_left: usize) -> Result<Drawing> {
d.layouts.clear();
// A file without $INSUNITS declares no units (#1209); only new drawings take the template's.
d.header.set_i64("INSUNITS", 0);
let mut rx = Rx { pstyles: plot_style_names(&secs), ..Rx::default() };
let mut rx = Rx { pstyles: plot_style_names(&secs), curves: hatch::CurvePoints { left: curve_points, cut: 0 }, ..Rx::default() };
let mut blocks: Vec<BlockDef> = Vec::new();
let mut layout_objs: Vec<LayoutDef> = Vec::new();
let mut entities = Vec::new();
@@ -147,6 +150,14 @@ fn read_budgeted(bytes: &[u8], mut table_cells_left: usize) -> Result<Drawing> {
}
crate::dxf_raw::read(&secs, &mut d);
crate::dxf_clip::read(&mut d);
if rx.curves.cut > 0 {
// Echoed on open, returned by OPEN and listed by the CLI, so a coarse boundary is never silent.
let n = rx.curves.cut;
let which = if n == 1 { "hatch has" } else { "hatches have" };
d.read_notes.push(format!(
"DXF: {n} {which} more boundary curve points than CADCraft reads from one file; past that, elliptic and spline edges were read coarsely."
));
}
d.skipped_records = skipped;
Ok(d)
}
@@ -215,7 +226,7 @@ mod table_budget_tests {
let dxf = format!(
"0\nSECTION\n2\nBLOCKS\n0\nBLOCK\n2\nTEST\n10\n0\n20\n0\n{table}0\nENDBLK\n0\nENDSEC\n0\nSECTION\n2\nENTITIES\n{table}0\nENDSEC\n0\nSECTION\n2\nENTITIES\n{table}0\nENDSEC\n0\nEOF\n"
);
let d = read_budgeted(dxf.as_bytes(), 2).unwrap();
let d = read_budgeted(dxf.as_bytes(), 2, hatch::MAX_READ_CURVE_POINTS).unwrap();
let block = d.block("TEST").unwrap();
let count = |e: &Entity| match &e.kind {
EntityKind::Table(t) => t.cells.iter().map(Vec::len).sum::<usize>(),
@@ -225,3 +236,48 @@ mod table_budget_tests {
assert_eq!(d.model.iter().map(|e| count(e)).sum::<usize>(), 0);
}
}
#[cfg(test)]
mod hatch_budget_tests {
use super::*;
/// A HATCH of `edges` strongly curved degree-3 spline edges: a dozen groups each, sampled
/// into thousands of points.
fn spline_hatch(edges: usize) -> String {
let mut s = format!("0\nHATCH\n2\nSOLID\n70\n1\n91\n1\n92\n0\n93\n{edges}\n");
for _ in 0..edges {
s.push_str("72\n4\n94\n3\n73\n0\n74\n0\n95\n8\n96\n4\n");
for k in [0, 0, 0, 0, 1, 1, 1, 1] {
s.push_str(&format!("40\n{k}\n"));
}
for (x, y) in [(0.0, 0.0), (1e6, 1e6), (2e6, -1e6), (3e6, 0.0)] {
s.push_str(&format!("10\n{x}\n20\n{y}\n"));
}
}
s
}
fn hatch_points(d: &Drawing) -> usize {
let points = |e: &Entity| match &e.kind {
EntityKind::Hatch(h) => h.loops.iter().map(|l| l.vertices.len()).sum::<usize>(),
_ => 0,
};
d.model.iter().map(|e| points(e)).sum()
}
/// Two hatches share the file's curve-point budget (#1922): past it their spline edges are
/// read as their control points, and opening the file says so.
#[test]
fn hatch_curves_stop_at_the_read_budget_and_say_so() {
let dxf = format!("0\nSECTION\n2\nENTITIES\n{}{}0\nENDSEC\n0\nEOF\n", spline_hatch(10), spline_hatch(10));
let full = read_budgeted(dxf.as_bytes(), 4_000_000, hatch::MAX_READ_CURVE_POINTS).unwrap();
assert!(full.read_notes.is_empty(), "{:?}", full.read_notes);
assert!(hatch_points(&full) > 20_000, "{}", hatch_points(&full));
let d = read_budgeted(dxf.as_bytes(), 4_000_000, 1000).unwrap();
// The budget is checked before each edge: the last one sampled may pass it by its own
// points (at most about 4,000); every edge after it is its four control points.
assert!(hatch_points(&d) <= 1000 + 4001 + 20 * 4, "{}", hatch_points(&d));
assert_eq!(d.model.len(), 2);
assert!(matches!(d.read_notes.as_slice(), [note] if note.contains("2 hatches")), "{:?}", d.read_notes);
}
}
+1 -1
View File
@@ -20,7 +20,7 @@ pub(super) fn parse_entities(
if kind == "VIEWPORT" && crate::dxf_ext::is_paper_view(tags) {
rx.paper_views_dropped.push((owner.clone(), paper, rx.block.clone()));
}
let mut kindent = entity_with_table_budget(kind, tags, table_cells_left);
let mut kindent = entity_with_table_budget(kind, tags, table_cells_left, &mut rx.curves);
if let Some((c, _)) = kindent.as_mut()
&& let Some(n) = entity_plot_style(tags, rx)
{
+9 -4
View File
@@ -1,5 +1,5 @@
use super::common::{T, common, ocs, plan_of_tilted, run_points, tilted};
use super::hatch::hatch;
use super::hatch::{CurvePoints, hatch};
use super::mtext_dxf;
use super::text::{attdef, attrib_modes, attrib_props, mtext_from, multiline_attrib, split_embedded, text_from};
use super::{
@@ -11,7 +11,7 @@ use cadcraft_doc::PolyfaceMesh;
/// Parse one entity record. POLYLINE/INSERT followers are handled by the caller.
pub(super) fn entity(kind: &str, tags: &[Tag]) -> Option<(Common, EntityKind)> {
entity_with_table_budget(kind, tags, &mut 4_000_000)
entity_with_table_budget(kind, tags, &mut 4_000_000, &mut CurvePoints::default())
}
/// Parse one entity while charging materialized table cells to the caller's shared import budget.
@@ -123,7 +123,12 @@ fn spline(t: &T) -> Spline {
sp
}
pub(super) fn entity_with_table_budget(kind: &str, tags: &[Tag], table_cells_left: &mut usize) -> Option<(Common, EntityKind)> {
pub(super) fn entity_with_table_budget(
kind: &str,
tags: &[Tag],
table_cells_left: &mut usize,
curves: &mut CurvePoints,
) -> Option<(Common, EntityKind)> {
// The paper-space viewport our writer adds (dxf_write::paper_view) stays implicit.
if kind == "VIEWPORT" && crate::dxf_ext::is_paper_view(tags) {
return None;
@@ -236,7 +241,7 @@ pub(super) fn entity_with_table_budget(kind: &str, tags: &[Tag], table_cells_lef
"MLINE" => EntityKind::MLine(crate::dxf_mline::read_entity(tags)),
"3DFACE" => EntityKind::Face3d(Face3d { corners: [t.p(10), t.p(11), t.p(12), t.p(13)], hidden_edges: t.i(70).unwrap_or(0) as u8 }),
"HATCH" => {
let mut k = hatch(tags, &t)?;
let mut k = hatch(tags, &t, curves)?;
if let EntityKind::Hatch(h) = &mut k
&& tilted(c.extrusion, h.loops.iter().flat_map(|l| run_points(&l.vertices, h.elevation, true)))
{
+80 -8
View File
@@ -1,11 +1,60 @@
use super::common::T;
use super::{Color, EntityKind, Gradient, Handle, Hatch, HatchLoop, PolyVertex, Rgb, Spline, Tag, Vec2};
pub(super) fn hatch(tags: &[Tag], t: &T) -> Option<EntityKind> {
/// Upper bound on the points the elliptic and spline edges of one HATCH's boundary are sampled
/// into: the point budget the renderer gives one hatch's loops
/// ([`cadcraft_geom::MAX_TESSELLATED_POINTS`]).
const MAX_HATCH_CURVE_POINTS: usize = cadcraft_geom::MAX_TESSELLATED_POINTS;
/// Upper bound on the points the elliptic and spline edges of all HATCH boundaries in one file
/// are sampled into. Each such edge is a few groups in the file but up to about 4,000 points
/// (40 bytes each) once read, so a file of many small hatches could otherwise need hundreds of
/// gigabytes (#1922). 16 million points is 640 MB; a large real drawing (thousands of hatches
/// bounded by curves, a few hundred points an edge) is expected to sample a few million.
pub(super) const MAX_READ_CURVE_POINTS: usize = 16_000_000;
/// The curve-point allowance of one read, shared by every HATCH in it.
pub(super) struct CurvePoints {
/// Points still to be sampled.
pub(super) left: usize,
/// Hatches with an edge read coarsely because the allowance was spent.
pub(super) cut: usize,
}
impl Default for CurvePoints {
fn default() -> Self {
CurvePoints { left: MAX_READ_CURVE_POINTS, cut: 0 }
}
}
/// The allowance of the hatch being read: what is left of the file's, at most
/// [`MAX_HATCH_CURVE_POINTS`].
struct EdgeBudget {
left: usize,
/// An edge was read coarsely.
cut: bool,
}
impl EdgeBudget {
/// Whether an edge may still be sampled in full; when not, it is read coarsely, from its
/// own groups only. Checked before each edge, so the last one sampled may pass the budget
/// by that one edge's points.
fn sample(&mut self) -> bool {
self.cut |= self.left == 0;
self.left > 0
}
fn spend(&mut self, n: usize) {
self.left = self.left.saturating_sub(n);
}
}
pub(super) fn hatch(tags: &[Tag], t: &T, curves: &mut CurvePoints) -> Option<EntityKind> {
let (origin, background) = hatch_xdata(tags);
let pattern = t.s(2).unwrap_or_else(|| "SOLID".into());
let solid = t.i(70).unwrap_or(0) == 1;
let n_loops = t.i(91).unwrap_or(0).clamp(0, 100_000) as usize;
let mut budget = EdgeBudget { left: curves.left.min(MAX_HATCH_CURVE_POINTS), cut: false };
let start_left = budget.left;
let mut loops = Vec::new();
// Walk the boundary data after the 91 tag.
let start = tags.iter().position(|x| x.code == 91).map(|i| i + 1)?;
@@ -19,13 +68,17 @@ pub(super) fn hatch(tags: &[Tag], t: &T) -> Option<EntityKind> {
let flags = get(i)?.i64();
i += 1;
let outer = flags & 1 != 0;
let mut verts = if flags & 2 != 0 { polyline_boundary(tags, &mut i)? } else { edge_boundary(tags, &mut i)? };
let mut verts = if flags & 2 != 0 { polyline_boundary(tags, &mut i)? } else { edge_boundary(tags, &mut i, &mut budget)? };
if verts.len() > 1 && verts.first().map(|f| f.p).zip(verts.last().map(|l| l.p)).is_some_and(|(a, b)| a.near(b, 1e-9)) {
verts.pop();
}
let sources = boundary_sources(tags, &mut i);
loops.push(HatchLoop { vertices: verts, outer, sources });
}
curves.left = curves.left.saturating_sub(start_left.saturating_sub(budget.left));
if budget.cut {
curves.cut = curves.cut.saturating_add(1);
}
let solid = solid || pattern.eq_ignore_ascii_case("SOLID");
let (scale, angle) = (t.fd(41, 1.0), t.fd(52, 0.0).to_radians());
// Keep the file's definition lines even for a name the library knows: the library's versions
@@ -76,7 +129,7 @@ fn polyline_boundary(tags: &[Tag], index: &mut usize) -> Option<Vec<PolyVertex>>
Some(vertices)
}
fn edge_boundary(tags: &[Tag], index: &mut usize) -> Option<Vec<PolyVertex>> {
fn edge_boundary(tags: &[Tag], index: &mut usize, budget: &mut EdgeBudget) -> Option<Vec<PolyVertex>> {
let get = |i: usize| tags.get(i);
seek_code(tags, index, 93);
let count = get(*index)?.i64().clamp(0, 1_000_000) as usize;
@@ -89,8 +142,8 @@ fn edge_boundary(tags: &[Tag], index: &mut usize) -> Option<Vec<PolyVertex>> {
match kind {
1 => line_edge(tags, index, &mut vertices),
2 => circular_edge(tags, index, &mut vertices),
3 => elliptic_edge(tags, index, &mut vertices),
4 => spline_edge(tags, index, &mut vertices),
3 => elliptic_edge(tags, index, &mut vertices, budget),
4 => spline_edge(tags, index, &mut vertices, budget),
_ => {}
}
}
@@ -137,7 +190,11 @@ fn circular_edge(tags: &[Tag], index: &mut usize, vertices: &mut Vec<PolyVertex>
vertices.push(PolyVertex::new(end_point));
}
fn elliptic_edge(tags: &[Tag], index: &mut usize, vertices: &mut Vec<PolyVertex>) {
/// Most points an elliptic edge is read as once the curve-point allowance is spent: about as many
/// as the edge has groups.
const COARSE_ELLIPSE_POINTS: u32 = 8;
fn elliptic_edge(tags: &[Tag], index: &mut usize, vertices: &mut Vec<PolyVertex>, budget: &mut EdgeBudget) {
let center = Vec2::new(edge_value(tags, *index), edge_value(tags, *index + 1));
let major = Vec2::new(edge_value(tags, *index + 2), edge_value(tags, *index + 3));
let ratio = edge_value(tags, *index + 4);
@@ -148,14 +205,20 @@ fn elliptic_edge(tags: &[Tag], index: &mut usize, vertices: &mut Vec<PolyVertex>
let (start, end) = if ccw { (start_angle, end_angle) } else { (-end_angle, -start_angle) };
let ellipse = cadcraft_geom::Ellipse { center, major, ratio, start, end };
let mut points = Vec::new();
ellipse.tessellate(major.len() * 1e-3, &mut points);
if budget.sample() {
ellipse.tessellate(major.len() * 1e-3, &mut points);
budget.spend(points.len());
} else {
let sweep = ellipse.sweep();
points.extend((0..=COARSE_ELLIPSE_POINTS).map(|k| ellipse.at_param(start + sweep * f64::from(k) / f64::from(COARSE_ELLIPSE_POINTS))));
}
if !ccw {
points.reverse();
}
vertices.extend(points.into_iter().map(PolyVertex::new));
}
fn spline_edge(tags: &[Tag], index: &mut usize, vertices: &mut Vec<PolyVertex>) {
fn spline_edge(tags: &[Tag], index: &mut usize, vertices: &mut Vec<PolyVertex>, budget: &mut EdgeBudget) {
let get = |i: usize| tags.get(i);
let mut degree = 3;
let (mut knot_count, mut control_count) = (0, 0);
@@ -195,6 +258,14 @@ fn spline_edge(tags: &[Tag], index: &mut usize, vertices: &mut Vec<PolyVertex>)
if weights.len() != control.len() {
weights.clear();
}
// Past the allowance the edge is its control polygon (or fit points): no more points than
// the file gives.
if !budget.sample() {
let points = if control.is_empty() { fit } else { control };
let skip = usize::from(vertices.last().zip(points.first()).is_some_and(|(last, point)| last.p.near(*point, 1e-9)));
vertices.extend(points.into_iter().skip(skip).map(PolyVertex::new));
return;
}
let spline = Spline { degree, knots, control, weights, ..Spline::default() };
let spline = if spline.is_valid() {
spline
@@ -204,6 +275,7 @@ fn spline_edge(tags: &[Tag], index: &mut usize, vertices: &mut Vec<PolyVertex>)
Spline::from_control(spline.control, degree)
};
let points = spline.tessellate(1e-3);
budget.spend(points.len());
let skip = usize::from(vertices.last().zip(points.first()).is_some_and(|(last, point)| last.p.near(*point, 1e-9)));
vertices.extend(points.into_iter().skip(skip).map(PolyVertex::new));
}
+3 -1
View File
@@ -106,7 +106,8 @@ pub struct DisplayList {
pub sheet: Option<Sheet>,
/// Block contents expanded while building (see [`MAX_BLOCK_EXPANSION`]).
pub expanded: usize,
/// The expansion budget was spent: block contents past it are not in the list. The screen,
/// The block-expansion budget or the point budget ([`crate::MAX_DISPLAY_POINTS`]) was spent:
/// block contents or objects past it are not in the list. The screen,
/// plots and exports draw what is here; the CLI and the control channel report this, so an
/// output that leaves contents out is never silent (#1070).
pub truncated: bool,
@@ -207,4 +208,5 @@ pub(crate) fn append(dst: &mut DisplayList, src: DisplayList) {
dst.pens.extend(src.pens);
dst.bounds = dst.bounds.union(&src.bounds);
dst.expanded = dst.expanded.saturating_add(src.expanded);
dst.truncated |= src.truncated;
}
+5
View File
@@ -21,6 +21,11 @@ pub(crate) fn entity(b: &mut Builder, ctx: &Ctx, e: &Entity) {
if ctx.d.is_hidden_object(e.handle) || b.opts.cancelled() {
return;
}
// Once the build holds all the points it may, nothing more is drawn (or computed).
if b.points_spent() {
b.list.truncated = true;
return;
}
// The entity's named plot style and transparency (set by `entity_parts`), for everything it
// draws (block contents set their own).
let (saved, saved_transparency) = (b.named, b.transparency);
+43 -4
View File
@@ -1,7 +1,7 @@
//! Polygon filling: even-odd regions to triangles (slab decomposition), wide polylines.
use cadcraft_doc::LwPolyline;
use cadcraft_geom::{Polyline, Vec2};
use cadcraft_geom::{MAX_TESSELLATED_POINTS, Polyline, Segment, Vec2};
/// Triangulate an even-odd region bounded by closed loops (holes allowed) by cutting it into
/// horizontal slabs at every vertex y and emitting trapezoids. Two edges that cross inside a slab
@@ -116,8 +116,29 @@ fn crossing_y(l: &(f64, f64, f64), r: &(f64, f64, f64), ya: f64, yb: f64) -> Opt
(y > ya && y < yb && y - ya > 1e-12 && yb - y > 1e-12).then_some(y)
}
/// Triangles for a polyline with widths (constant or tapered per segment).
/// The points of `seg` (both ends included) into `pts`, spending `budget` as
/// [`Polyline::tessellate_within`] does: once it is spent the segment is its chord. Every arc of a
/// wide polyline samples up to thousands of points and makes six triangle corners from each, so a
/// polyline of many tiny-tolerance arcs would otherwise build gigabytes (#1922).
pub(crate) fn sample_within(seg: &Segment, tol: f64, budget: &mut usize, pts: &mut Vec<Vec2>) {
if *budget > 0 {
let from = pts.len();
seg.tessellate(tol, pts);
*budget = budget.saturating_sub(pts.len().saturating_sub(from));
} else {
pts.extend([seg.start(), seg.end()]);
}
}
/// Triangles for a polyline with widths (constant or tapered per segment), sampling at most
/// about [`MAX_TESSELLATED_POINTS`] points as the centre line does.
pub fn wide_polyline(p: &LwPolyline, tol: f64) -> Vec<Vec2> {
let mut budget = MAX_TESSELLATED_POINTS;
wide_polyline_within(p, tol, &mut budget)
}
/// [`wide_polyline`] spending `budget` sampled points.
fn wide_polyline_within(p: &LwPolyline, tol: f64, budget: &mut usize) -> Vec<Vec2> {
let pl = Polyline { vertices: p.vertices.clone(), closed: p.closed };
let mut out = Vec::new();
let n = p.vertices.len();
@@ -125,7 +146,7 @@ pub fn wide_polyline(p: &LwPolyline, tol: f64) -> Vec<Vec2> {
let v = p.vertices.get(i % n.max(1)).copied().unwrap_or_default();
let (w0, w1) = if p.const_width > 0.0 { (p.const_width, p.const_width) } else { (v.start_width, v.end_width) };
let mut pts = Vec::new();
seg.tessellate(tol, &mut pts);
sample_within(seg, tol, budget, &mut pts);
let m = pts.len();
if m < 2 {
continue;
@@ -149,7 +170,7 @@ pub fn wide_polyline(p: &LwPolyline, tol: f64) -> Vec<Vec2> {
}
#[cfg(test)]
mod tests {
pub(crate) mod tests {
use super::*;
fn area(tris: &[Vec2]) -> f64 {
@@ -271,6 +292,24 @@ mod tests {
assert_matches_oracle(&[tri], -1.0, 5.0);
}
/// A wide polyline of 100 half circles at a tiny tolerance: each could sample 4,096 points.
pub(crate) fn arcs() -> LwPolyline {
let vertices = (0..100)
.map(|i| cadcraft_geom::PolyVertex { bulge: 1.0, ..cadcraft_geom::PolyVertex::new(Vec2::new(f64::from(i) * 100.0, 0.0)) })
.collect();
LwPolyline { vertices, closed: false, const_width: 1.0, elevation: 0.0, plinegen: false }
}
/// Sampling stops at the budget, past which each arc is a chord (#1922). The budget is checked
/// before each segment, so the last one sampled may pass it by up to 4,096 points; each point
/// makes six triangle corners.
#[test]
fn wide_arcs_stop_sampling_at_the_budget() {
let mut budget = 1000;
let tris = wide_polyline_within(&arcs(), 1e-9, &mut budget);
assert!(!tris.is_empty() && tris.len() <= 6 * (1000 + 4096 + 2 * 100), "{}", tris.len());
}
#[test]
fn degenerate_input() {
assert!(triangulate_evenodd(&[vec![Vec2::ZERO, Vec2::X]]).is_empty());
+61 -13
View File
@@ -125,6 +125,11 @@ struct Builder<'a> {
shared_budget: Option<&'a std::sync::atomic::AtomicUsize>,
/// Transparency (percent) of the entity being drawn.
transparency: u8,
/// Points (polyline vertices and triangle corners) the whole build has charged so far, shared
/// by every part of it: the parts built in parallel, XCLIP parts and viewport contents.
points: &'a std::sync::atomic::AtomicUsize,
/// The most points the build may hold: [`MAX_DISPLAY_POINTS`] (less in tests).
max_points: usize,
}
/// Upper bound on the block contents drawn per display list (each block reference, MINSERT copy
@@ -133,6 +138,16 @@ struct Builder<'a> {
/// bounds the depth); past the limit the remaining block contents are not drawn.
pub const MAX_BLOCK_EXPANSION: usize = 2_000_000;
/// Upper bound on the points (polyline vertices plus triangle corners) one display list holds.
/// [`MAX_BLOCK_EXPANSION`] counts objects, not their size: two million copies of one finely
/// tessellated circle, or of a block of hatches and filled text, would otherwise build billions
/// of points and end the process when memory runs out. Past the limit the remaining objects are
/// not drawn and [`DisplayList::truncated`] is set. At 16 bytes a point this is 1 GiB, sixteen
/// times the [`cadcraft_geom::MAX_TESSELLATED_POINTS`] one polyline may sample; a large real
/// drawing (a million objects with tens of thousands of texts, drawn at screen detail or in full
/// for a plot) is expected to hold a few tens of millions.
pub const MAX_DISPLAY_POINTS: usize = 64_000_000;
impl<'a> Builder<'a> {
/// `color` and `lw` as the plot style table prints them.
fn styled(&self, color: Ink, lw: f32) -> (Ink, f32) {
@@ -152,7 +167,7 @@ impl<'a> Builder<'a> {
}
}
fn polyline(&mut self, ctx: &Ctx, color: Ink, lw: f32, pts: &[Vec2]) {
if pts.len() < 2 {
if pts.len() < 2 || !self.charge(pts.len()) {
return;
}
self.note_pen(color);
@@ -162,14 +177,15 @@ impl<'a> Builder<'a> {
/// A one-pixel line in `color` as the plot style prints it, without the style's lineweight
/// or pen: the centre line drawn on screen over a thin wide polyline.
fn hairline(&mut self, ctx: &Ctx, color: Ink, pts: &[Vec2]) {
if pts.len() < 2 {
if pts.len() < 2 || !self.charge(pts.len()) {
return;
}
let (color, _) = self.styled(color, 0.0);
self.push_polyline(ctx, color, 0.0, pts);
}
/// Push a polyline already charged to the point budget by the caller.
fn push_polyline(&mut self, ctx: &Ctx, color: Ink, lw: f32, pts: &[Vec2]) {
let start = self.list.verts.len() as u32;
let (Ok(start), Ok(len)) = (u32::try_from(self.list.verts.len()), u32::try_from(pts.len())) else { return };
for p in pts {
let q = ctx.xf.apply(*p);
self.list.bounds.add(q);
@@ -183,7 +199,7 @@ impl<'a> Builder<'a> {
transparency: self.transparency,
kind: Kind::Polyline,
start,
len: pts.len() as u32,
len,
});
}
/// The pixels of image `i` over its rectangle, cut to its clip boundary.
@@ -209,6 +225,9 @@ impl<'a> Builder<'a> {
return;
}
let (Ok(index), Ok(start)) = (u32::try_from(self.list.images.len()), u32::try_from(self.list.verts.len())) else { return };
if !self.charge(corners.len()) {
return;
}
for q in corners {
self.list.bounds.add(q);
self.list.verts.push(q);
@@ -232,9 +251,12 @@ impl<'a> Builder<'a> {
if tris.len() < 3 {
return;
}
let (Ok(start), Ok(len)) = (u32::try_from(self.list.tris.len()), u32::try_from(tris.len())) else { return };
if !self.charge(tris.len()) {
return;
}
self.note_pen(color);
let (color, _) = self.styled(color, 0.0);
let start = self.list.tris.len() as u32;
for p in tris {
let q = xf.apply(*p);
self.list.bounds.add(q);
@@ -248,7 +270,7 @@ impl<'a> Builder<'a> {
transparency: self.transparency,
kind: Kind::Tris,
start,
len: tris.len() as u32,
len,
});
}
/// Shaped text: strokes as polylines; TrueType glyphs filled (TEXTFILL) or outlined.
@@ -295,10 +317,13 @@ impl<'a> Builder<'a> {
}
}
fn point(&mut self, ctx: &Ctx, color: Ink, p: Vec2) {
let Ok(start) = u32::try_from(self.list.verts.len()) else { return };
if !self.charge(1) {
return;
}
let (color, _) = self.styled(color, 0.0);
let q = ctx.xf.apply(p);
self.list.bounds.add(q);
let start = self.list.verts.len() as u32;
self.list.verts.push(q);
self.list.prims.push(DPrim {
handle: ctx.top,
@@ -312,8 +337,11 @@ impl<'a> Builder<'a> {
});
}
fn infinite(&mut self, ctx: &Ctx, color: Ink, base: Vec2, dir: Vec2, ray: bool) {
let Ok(start) = u32::try_from(self.list.verts.len()) else { return };
if !self.charge(2) {
return;
}
let (color, _) = self.styled(color, 0.0);
let start = self.list.verts.len() as u32;
self.list.verts.push(ctx.xf.apply(base));
self.list.verts.push(ctx.xf.apply_vec(dir).normalized());
self.list.prims.push(DPrim {
@@ -340,15 +368,35 @@ impl<'a> Builder<'a> {
named: self.named,
shared_budget: self.shared_budget,
transparency: self.transparency,
points: self.points,
max_points: self.max_points,
}
}
/// Take one unit of the block-expansion budget; false once it is spent.
/// Take one unit of the block-expansion budget; false once it is spent, or once the build
/// holds all the points it may ([`MAX_DISPLAY_POINTS`]), so block copies stop being visited.
fn expand(&mut self) -> bool {
self.list.expanded = self.list.expanded.saturating_add(1);
let ok = match self.shared_budget {
Some(spent) => spent.fetch_add(1, std::sync::atomic::Ordering::Relaxed) < MAX_BLOCK_EXPANSION,
None => self.list.expanded <= MAX_BLOCK_EXPANSION,
};
let ok = !self.points_spent()
&& match self.shared_budget {
Some(spent) => spent.fetch_add(1, std::sync::atomic::Ordering::Relaxed) < MAX_BLOCK_EXPANSION,
None => self.list.expanded <= MAX_BLOCK_EXPANSION,
};
if !ok {
self.list.truncated = true;
}
ok
}
/// Whether the build holds all the points it may: nothing more is drawn.
fn points_spent(&self) -> bool {
self.points.load(std::sync::atomic::Ordering::Relaxed) >= self.max_points
}
/// Charge `n` points to the build's [`MAX_DISPLAY_POINTS`] budget before they are pushed;
/// false (and the list marked truncated) when they don't fit, and nothing is pushed. Once the
/// budget is spent nothing more is added to the count, so it stays within the limit plus one
/// primitive per thread building in parallel.
fn charge(&mut self, n: usize) -> bool {
use std::sync::atomic::Ordering::Relaxed;
let ok = !self.points_spent() && self.points.fetch_add(n, Relaxed).saturating_add(n) <= self.max_points;
if !ok {
self.list.truncated = true;
}
+45 -6
View File
@@ -3,7 +3,10 @@ use super::display::append;
use super::display::{DisplayList, Kind, NO_LAYER, PlotText, VIEWPORT_CONTENT};
use super::draw::entity;
use super::viewports::{MAX_VIEWPORTS, viewport};
use super::{Bounds2, Builder, Color, Ctx, Drawing, Entity, EntityKind, Handle, Lineweight, Mat3, Space, Vec2, paper, pen, plotstyle, point};
use super::{
Bounds2, Builder, Color, Ctx, Drawing, Entity, EntityKind, Handle, Lineweight, MAX_DISPLAY_POINTS, Mat3, Space, Vec2, paper, pen, plotstyle,
point,
};
/// Build options.
#[derive(Clone, Debug)]
@@ -99,9 +102,25 @@ pub(crate) fn top_ctx<'a>(d: &'a Drawing, xf: Mat3, top: Handle, frozen: &'a [St
}
fn build_space(d: &Drawing, space: &Space, opts: &Options, plotting: bool) -> DisplayList {
build_space_within(d, space, opts, plotting, MAX_DISPLAY_POINTS)
}
/// [`build_space`] holding at most `max_points` points.
pub(crate) fn build_space_within(d: &Drawing, space: &Space, opts: &Options, plotting: bool, max_points: usize) -> DisplayList {
let opts = &with_point_view(d, space, opts);
let styler = style_table(d, space, opts, plotting).map(|t| plotstyle::Styler::new(d, t));
let mut b = Builder { list: DisplayList::default(), opts, plotting, styles: styler.as_ref(), named: None, shared_budget: None, transparency: 0 };
let points = std::sync::atomic::AtomicUsize::new(0);
let mut b = Builder {
list: DisplayList::default(),
opts,
plotting,
styles: styler.as_ref(),
named: None,
shared_budget: None,
transparency: 0,
points: &points,
max_points,
};
if let Space::Paper(name) = space {
b.list.sheet = paper::sheet(d, name);
}
@@ -148,12 +167,21 @@ fn build_parallel(b: &mut Builder, d: &Drawing, store: &cadcraft_doc::EntityStor
use rayon::prelude::*;
let ents: Vec<&std::sync::Arc<Entity>> = store.iter().collect();
let budget = std::sync::atomic::AtomicUsize::new(0);
let (opts, plotting) = (b.opts, b.plotting);
let (opts, plotting, points, max_points) = (b.opts, b.plotting, b.points, b.max_points);
let parts: Vec<DisplayList> = ents
.par_chunks(PARALLEL_CHUNK)
.map(|chunk| {
let mut part =
Builder { list: DisplayList::default(), opts, plotting, styles: None, named: None, shared_budget: Some(&budget), transparency: 0 };
let mut part = Builder {
list: DisplayList::default(),
opts,
plotting,
styles: None,
named: None,
shared_budget: Some(&budget),
transparency: 0,
points,
max_points,
};
for e in chunk {
entity(&mut part, &top_ctx(d, Mat3::IDENTITY, e.handle, &[], &[]), e);
}
@@ -205,7 +233,18 @@ pub fn build_entities<'a, I: IntoIterator<Item = &'a Entity>>(d: &Drawing, ents:
} else {
opts
};
let mut b = Builder { list: DisplayList::default(), opts, plotting: false, styles: None, named: None, shared_budget: None, transparency: 0 };
let points = std::sync::atomic::AtomicUsize::new(0);
let mut b = Builder {
list: DisplayList::default(),
opts,
plotting: false,
styles: None,
named: None,
shared_budget: None,
transparency: 0,
points: &points,
max_points: MAX_DISPLAY_POINTS,
};
for e in ents {
entity(&mut b, &top_ctx(d, Mat3::IDENTITY, e.handle, &[], &[]), e);
}
+46
View File
@@ -1217,3 +1217,49 @@ fn rotated_and_reversed_copies_of_a_curved_loop_fill_once() {
});
assert_eq!(loops_of(&h).len(), 2);
}
// ---------- point budget (#1922) ----------
fn circle() -> EntityKind {
EntityKind::Circle(cadcraft_doc::Circle { center: Vec3::ZERO, radius: 100.0 })
}
/// A block of one circle referenced as 1,000 copies in place: every copy is cheap to the
/// block-expansion budget but costs hundreds of points.
fn arrayed_circles() -> Drawing {
let mut d = Drawing::new_imperial();
let mut blk = cadcraft_doc::Block::new("B");
blk.entities.push(block_entity(1, Common::default(), circle()));
d.blocks.insert("B".into(), std::sync::Arc::new(blk));
let EntityKind::Insert(mut ins) = insert_of("B") else { panic!("an insert") };
ins.cols = 1000;
d.add(&Space::Model, Common::default(), EntityKind::Insert(ins)).unwrap();
d
}
fn points(l: &DisplayList) -> usize {
l.verts.len() + l.tris.len()
}
#[test]
fn block_copies_stop_at_the_point_budget_and_say_so() {
let d = arrayed_circles();
let full = build(&d, &Space::Model, &Options::default());
assert!(!full.truncated && points(&full) > 100_000, "{}", points(&full));
let l = crate::pipeline::build_space_within(&d, &Space::Model, &Options::default(), false, 10_000);
assert!(l.truncated);
assert!(points(&l) > 0 && points(&l) <= 10_000, "{}", points(&l));
assert!(l.prims.iter().all(|p| p.start as usize + p.len as usize <= l.verts.len()));
}
#[test]
fn objects_built_on_all_cores_stop_at_the_point_budget_and_say_so() {
// Enough objects for the parallel build: the parts share one budget and report together.
let mut d = Drawing::new_imperial();
for _ in 0..600 {
d.add(&Space::Model, Common::default(), circle()).unwrap();
}
let l = crate::pipeline::build_space_within(&d, &Space::Model, &Options::default(), false, 10_000);
assert!(l.truncated);
assert!(points(&l) > 0 && points(&l) <= 10_000, "{}", points(&l));
}
+21 -4
View File
@@ -5,7 +5,10 @@ use super::draw::entity;
#[cfg(not(target_arch = "wasm32"))]
use super::pipeline::PARALLEL_CHUNK;
use super::pipeline::{Options, style_table, top_ctx, with_point_view};
use super::{Bounds2, Builder, Ctx, Drawing, Entity, EntityKind, Handle, MAX_BLOCK_EXPANSION, Mat3, Pen, Space, Vec2, clip, paper, pen, plotstyle};
use super::{
Bounds2, Builder, Ctx, Drawing, Entity, EntityKind, Handle, MAX_BLOCK_EXPANSION, MAX_DISPLAY_POINTS, Mat3, Pen, Space, Vec2, clip, paper, pen,
plotstyle,
};
/// Upper bound on viewports drawn per layout (hostile files).
pub(crate) const MAX_VIEWPORTS: usize = 256;
@@ -67,8 +70,18 @@ pub fn viewport_content(d: &Drawing, space: &Space, handle: Handle, area: Bounds
}
let opts = &with_point_view(d, space, opts);
let styler = style_table(d, space, opts, false).map(|t| plotstyle::Styler::new(d, t));
let mut b =
Builder { list: DisplayList::default(), opts, plotting: false, styles: styler.as_ref(), named: None, shared_budget: None, transparency: 0 };
let points = std::sync::atomic::AtomicUsize::new(0);
let mut b = Builder {
list: DisplayList::default(),
opts,
plotting: false,
styles: styler.as_ref(),
named: None,
shared_budget: None,
transparency: 0,
points: &points,
max_points: MAX_DISPLAY_POINTS,
};
contents(&mut b, d, vp, area, &Clip::Rect(area), paper::unit_mm_of(d, handle));
b.list
}
@@ -120,6 +133,8 @@ fn contents(b: &mut Builder, d: &Drawing, vp: &cadcraft_doc::Viewport, area: Bou
named: None,
shared_budget: Some(&budget),
transparency: 0,
points: b.points,
max_points: b.max_points,
};
#[cfg(not(target_arch = "wasm32"))]
let parallel = !b.plotting && b.styles.is_none() && d.model.len() >= 2 * PARALLEL_CHUNK;
@@ -131,7 +146,7 @@ fn contents(b: &mut Builder, d: &Drawing, vp: &cadcraft_doc::Viewport, area: Bou
// As `build_parallel`: chunks built side by side, joined in drawing order.
use rayon::prelude::*;
let ents: Vec<&std::sync::Arc<Entity>> = d.model.iter().collect();
let opts = b.opts;
let (opts, points, max_points) = (b.opts, b.points, b.max_points);
let parts: Vec<DisplayList> = ents
.par_chunks(PARALLEL_CHUNK)
.map(|chunk| {
@@ -143,6 +158,8 @@ fn contents(b: &mut Builder, d: &Drawing, vp: &cadcraft_doc::Viewport, area: Bou
named: None,
shared_budget: Some(&budget),
transparency: 0,
points,
max_points,
};
let c = ctx();
for me in chunk.iter().filter(|me| seen(me)) {
+23 -5
View File
@@ -1,7 +1,7 @@
//! Wide polylines with a linetype: each dash is a filled piece of the band, gaps are empty.
use cadcraft_doc::{Linetype, LwPolyline};
use cadcraft_geom::{Polyline, Vec2};
use cadcraft_geom::{MAX_TESSELLATED_POINTS, Polyline, Vec2};
use crate::linetype;
@@ -15,8 +15,9 @@ struct Sample {
}
/// Centre-line samples of each segment, widths interpolated as [`crate::fill::wide_polyline`]
/// does; distances start at 0 for each segment.
fn segments(p: &LwPolyline, tol: f64) -> Vec<Vec<Sample>> {
/// does; distances start at 0 for each segment. At most about `budget` points are sampled (see
/// [`crate::fill::sample_within`]); past it segments are chords.
fn segments(p: &LwPolyline, tol: f64, budget: &mut usize) -> Vec<Vec<Sample>> {
let pl = Polyline { vertices: p.vertices.clone(), closed: p.closed };
let n = p.vertices.len();
let mut out = Vec::new();
@@ -24,7 +25,7 @@ fn segments(p: &LwPolyline, tol: f64) -> Vec<Vec<Sample>> {
let v = p.vertices.get(i % n.max(1)).copied().unwrap_or_default();
let (w0, w1) = if p.const_width > 0.0 { (p.const_width, p.const_width) } else { (v.start_width, v.end_width) };
let mut pts = Vec::new();
seg.tessellate(tol, &mut pts);
crate::fill::sample_within(seg, tol, budget, &mut pts);
let m = pts.len();
if m < 2 {
continue;
@@ -71,7 +72,8 @@ fn edges(x: &Sample) -> (Vec2, Vec2) {
/// polyline; otherwise it restarts at every vertex. A pattern shorter than `min_pattern` fills
/// the whole band.
pub fn dashed(p: &LwPolyline, tol: f64, lt: &Linetype, scale: f64, min_pattern: f64) -> (Vec<Vec2>, Vec<Vec<Vec2>>, Vec<Vec<Vec2>>) {
let mut runs = segments(p, tol);
let mut budget = MAX_TESSELLATED_POINTS;
let mut runs = segments(p, tol, &mut budget);
if p.plinegen && runs.len() > 1 {
let mut whole: Vec<Sample> = Vec::new();
for run in runs {
@@ -114,3 +116,19 @@ pub fn dashed(p: &LwPolyline, tol: f64, lt: &Linetype, scale: f64, min_pattern:
}
(tris, ticks, centres)
}
#[cfg(test)]
mod tests {
use super::*;
/// The centre-line samples of a dashed wide polyline stop at the budget as the filled band's
/// do (#1922): every segment keeps a run, past the budget its two ends.
#[test]
fn dashed_wide_arcs_stop_sampling_at_the_budget() {
let mut budget = 1000;
let runs = segments(&crate::fill::tests::arcs(), 1e-9, &mut budget);
let samples: usize = runs.iter().map(Vec::len).sum();
assert_eq!(runs.len(), 99);
assert!(samples <= 1000 + 4096 + 2 * 99, "{samples}");
}
}