Skip to main content

cadkit_core/
ops.rs

1//! Model traversal and derived properties: [`Document::walk`], [`Document::bbox`],
2//! [`Entity::resolved_color`] and [`EntityKind::type_name`].
3
4use std::collections::HashMap;
5use std::rc::Rc;
6
7use crate::aci;
8use crate::geom::{BBox, Point3, Vec3};
9use crate::geom_ops::{
10    EllipseArc, Transform, bulge_to_arc, ellipse_arc, extend_bbox, interpolate_fit_points,
11    nurbs_flatten,
12};
13use crate::model::{
14    Attachment, Block, Color, Document, Entity, EntityKind, HAlign, HatchEdge, Layer, VAlign,
15    Vertex,
16};
17
18/// Default nesting limit used by [`Document::bbox`] and the SVG renderer.
19pub const DEFAULT_WALK_DEPTH: u32 = 32;
20
21/// Default work budget of a walk, in abstract work units (see [`WalkOptions::max_work`]).
22pub const DEFAULT_MAX_WORK: u64 = 20_000_000;
23
24const BLACK: (u8, u8, u8) = (0, 0, 0);
25
26/// State handed to the [`Document::walk`] callback together with each entity.
27#[derive(Debug, Clone)]
28pub struct WalkContext<'a> {
29    /// Maps the entity's own coordinates to model-space coordinates (block placement,
30    /// array offsets and nesting already composed).
31    pub transform: Transform,
32    /// Nesting depth: 0 for entities directly in the model, +1 per block / group level.
33    pub depth: u32,
34    /// Layer inherited from the inserting entity. Entities on layer `"0"` (or without a
35    /// layer) inside a block take this layer, as AutoCAD does.
36    pub inherited_layer: Option<&'a str>,
37    /// Display color of the inserting entity, used to resolve `ByBlock` colors.
38    pub block_color: Option<(u8, u8, u8)>,
39    /// Layer name to color table shared by the walk, so color resolution needs no linear scan.
40    layer_colors: Option<Rc<HashMap<&'a str, Color>>>,
41}
42
43impl<'a> WalkContext<'a> {
44    /// Context of an entity that sits directly in a model.
45    pub fn root() -> Self {
46        Self {
47            transform: Transform::identity(),
48            depth: 0,
49            inherited_layer: None,
50            block_color: None,
51            layer_colors: None,
52        }
53    }
54
55    /// Effective layer name of `e` in this context (default layer `"0"`).
56    pub fn layer_name<'x>(&'x self, e: &'x Entity) -> &'x str {
57        match e.layer.as_deref() {
58            None | Some("0") => self.inherited_layer.unwrap_or("0"),
59            Some(name) => name,
60        }
61    }
62}
63
64/// Options of [`Document::bbox_with`].
65#[derive(Debug, Clone, Copy, PartialEq, Eq)]
66#[non_exhaustive]
67pub struct BBoxOptions {
68    /// Include `Image` entities in the box.
69    pub include_images: bool,
70    /// Work budget of the underlying walk (see [`WalkOptions::max_work`]); the box covers
71    /// what was visited before the budget ran out.
72    pub max_work: u64,
73}
74
75impl Default for BBoxOptions {
76    fn default() -> Self {
77        Self::new()
78    }
79}
80
81impl BBoxOptions {
82    /// Includes images, with the default work budget.
83    pub const fn new() -> Self {
84        Self {
85            include_images: true,
86            max_work: DEFAULT_MAX_WORK,
87        }
88    }
89
90    /// Sets [`Self::include_images`].
91    #[must_use]
92    pub const fn with_include_images(mut self, include_images: bool) -> Self {
93        self.include_images = include_images;
94        self
95    }
96
97    /// Sets [`Self::max_work`].
98    #[must_use]
99    pub const fn with_max_work(mut self, max_work: u64) -> Self {
100        self.max_work = max_work;
101        self
102    }
103}
104
105/// Options of [`Document::walk_with`].
106#[derive(Debug, Clone, Copy, PartialEq, Eq)]
107#[non_exhaustive]
108pub struct WalkOptions {
109    /// Deepest block / group nesting that is expanded.
110    pub max_depth: u32,
111    /// Expand `Insert` entities (and `Dimension` blocks). When false they are reported as-is.
112    pub expand_inserts: bool,
113    /// Work budget. Every visited entity costs 1 plus its size (vertices, spline samples,
114    /// text bytes, hatch edges, mesh faces), every insert array cell costs 1. When the budget
115    /// is used up the walk stops and [`WalkStats::truncated`] is set, so hostile nesting or
116    /// giant arrays cannot hang the caller.
117    pub max_work: u64,
118}
119
120impl Default for WalkOptions {
121    fn default() -> Self {
122        Self::new()
123    }
124}
125
126impl WalkOptions {
127    /// Expands inserts up to the default depth, with the default work budget.
128    pub const fn new() -> Self {
129        Self {
130            max_depth: DEFAULT_WALK_DEPTH,
131            expand_inserts: true,
132            max_work: DEFAULT_MAX_WORK,
133        }
134    }
135
136    /// Sets [`Self::max_depth`].
137    #[must_use]
138    pub const fn with_max_depth(mut self, max_depth: u32) -> Self {
139        self.max_depth = max_depth;
140        self
141    }
142
143    /// Sets [`Self::expand_inserts`].
144    #[must_use]
145    pub const fn with_expand_inserts(mut self, expand_inserts: bool) -> Self {
146        self.expand_inserts = expand_inserts;
147        self
148    }
149
150    /// Sets [`Self::max_work`].
151    #[must_use]
152    pub const fn with_max_work(mut self, max_work: u64) -> Self {
153        self.max_work = max_work;
154        self
155    }
156}
157
158/// Outcome of a walk.
159#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
160pub struct WalkStats {
161    /// The work budget ran out (or the callback asked to stop) before everything was visited.
162    pub truncated: bool,
163    /// Work units spent.
164    pub work: u64,
165}
166
167/// Work units charged for the content of an entity (on top of 1 per entity).
168fn entity_cost(kind: &EntityKind) -> u64 {
169    let n = |len: usize| len as u64;
170    match kind {
171        EntityKind::Polyline { vertices, .. } => n(vertices.len()),
172        EntityKind::Spline {
173            control_points,
174            fit_points,
175            ..
176        } => n(control_points.len().max(fit_points.len()))
177            .saturating_mul(SPLINE_SAMPLES as u64)
178            .min(100_000),
179        EntityKind::Text { value, .. } => n(value.len()),
180        EntityKind::MText { value, plain, .. } => n(value.len()) + n(plain.len()),
181        EntityKind::Hatch { loops, .. } => loops
182            .iter()
183            .flat_map(|l| l.edges.iter())
184            .map(|e| match e {
185                HatchEdge::Polyline { vertices, .. } => 1 + n(vertices.len()),
186                HatchEdge::Spline { control_points, .. } => {
187                    1 + n(control_points.len())
188                        .saturating_mul(SPLINE_SAMPLES as u64)
189                        .min(100_000)
190                }
191                _ => 4,
192            })
193            .fold(0u64, u64::saturating_add),
194        EntityKind::Dimension { points, .. } | EntityKind::Face { points, .. } => n(points.len()),
195        EntityKind::Polygon {
196            exterior,
197            interiors,
198        } => interiors.iter().fold(n(exterior.len()), |sum, ring| {
199            sum.saturating_add(n(ring.len()))
200        }),
201        EntityKind::Leader { vertices, .. } => n(vertices.len()),
202        EntityKind::Mesh { vertices, faces } => {
203            n(vertices.len())
204                + faces
205                    .iter()
206                    .map(|f| n(f.len()) + 1)
207                    .fold(0u64, u64::saturating_add)
208        }
209        _ => 0,
210    }
211}
212
213struct Walker<'a, F> {
214    blocks: HashMap<&'a str, &'a Block>,
215    layers: HashMap<&'a str, &'a Layer>,
216    colors: Rc<HashMap<&'a str, Color>>,
217    opts: WalkOptions,
218    include_hidden_layers: bool,
219    work: u64,
220    spent: u64,
221    truncated: bool,
222    stack: Vec<&'a str>,
223    f: F,
224}
225
226impl<'a, F: FnMut(&'a Entity, &WalkContext<'a>) -> bool> Walker<'a, F> {
227    fn layer_hidden(&self, name: &str) -> bool {
228        !self.include_hidden_layers
229            && self
230                .layers
231                .get(name)
232                .is_some_and(|l| !l.visible || l.frozen)
233    }
234
235    fn color_of(&self, e: &Entity, ctx: &WalkContext<'a>) -> (u8, u8, u8) {
236        let name = ctx.layer_name(e);
237        resolve_color(e.color, || self.colors.get(name).copied(), ctx.block_color)
238    }
239
240    /// Spends `cost` work units; false (and truncation) when the budget cannot cover it.
241    fn charge(&mut self, cost: u64) -> bool {
242        if self.truncated {
243            return false;
244        }
245        if cost > self.work {
246            self.work = 0;
247            self.truncated = true;
248            return false;
249        }
250        self.work -= cost;
251        self.spent += cost;
252        true
253    }
254
255    fn emit(&mut self, e: &'a Entity, ctx: &WalkContext<'a>) {
256        if !(self.f)(e, ctx) {
257            self.truncated = true;
258        }
259    }
260
261    fn visit_list(&mut self, list: &'a [Entity], ctx: &WalkContext<'a>) {
262        for e in list {
263            if self.truncated {
264                return;
265            }
266            self.visit(e, ctx);
267        }
268    }
269
270    fn visit(&mut self, e: &'a Entity, ctx: &WalkContext<'a>) {
271        if !self.charge(1 + entity_cost(&e.kind)) {
272            return;
273        }
274        let layer = ctx.layer_name(e);
275        if !e.visible || self.layer_hidden(layer) {
276            return;
277        }
278        match &e.kind {
279            EntityKind::Insert {
280                block,
281                position,
282                scale,
283                rotation,
284                normal,
285                columns,
286                rows,
287                column_spacing,
288                row_spacing,
289            } if self.opts.expand_inserts => {
290                let Some(def) = self.blocks.get(block.as_str()).copied() else {
291                    self.emit(e, ctx);
292                    return;
293                };
294                if ctx.depth >= self.opts.max_depth || self.stack.contains(&def.name.as_str()) {
295                    self.emit(e, ctx);
296                    return;
297                }
298                let child_layer: Option<&'a str> = match e.layer.as_deref() {
299                    None | Some("0") => ctx.inherited_layer,
300                    Some(l) => Some(l),
301                };
302                let block_color = Some(self.color_of(e, ctx));
303                self.stack.push(def.name.as_str());
304                'outer: for r in 0..(*rows).max(1) {
305                    for c in 0..(*columns).max(1) {
306                        if !self.charge(1) {
307                            break 'outer;
308                        }
309                        let offset = Vec3::new(
310                            f64::from(c) * column_spacing,
311                            f64::from(r) * row_spacing,
312                            0.0,
313                        );
314                        let local = Transform::from_insert_offset(
315                            *position,
316                            *scale,
317                            *rotation,
318                            *normal,
319                            def.base_point,
320                            offset,
321                        );
322                        let child = WalkContext {
323                            transform: ctx.transform.compose(&local),
324                            depth: ctx.depth + 1,
325                            inherited_layer: child_layer,
326                            block_color,
327                            layer_colors: ctx.layer_colors.clone(),
328                        };
329                        self.visit_list(&def.entities, &child);
330                    }
331                }
332                self.stack.pop();
333            }
334            EntityKind::Dimension {
335                block: Some(name), ..
336            } if self.opts.expand_inserts => match self.blocks.get(name.as_str()).copied() {
337                Some(def)
338                    if ctx.depth < self.opts.max_depth
339                        && !self.stack.contains(&def.name.as_str()) =>
340                {
341                    let child_layer: Option<&'a str> = match e.layer.as_deref() {
342                        None | Some("0") => ctx.inherited_layer,
343                        Some(l) => Some(l),
344                    };
345                    let child = WalkContext {
346                        transform: ctx.transform,
347                        depth: ctx.depth + 1,
348                        inherited_layer: child_layer,
349                        block_color: Some(self.color_of(e, ctx)),
350                        layer_colors: ctx.layer_colors.clone(),
351                    };
352                    self.stack.push(def.name.as_str());
353                    self.visit_list(&def.entities, &child);
354                    self.stack.pop();
355                }
356                _ => self.emit(e, ctx),
357            },
358            EntityKind::Group { children, .. } => {
359                if ctx.depth < self.opts.max_depth {
360                    let child = WalkContext {
361                        depth: ctx.depth + 1,
362                        ..ctx.clone()
363                    };
364                    self.visit_list(children, &child);
365                }
366            }
367            _ => self.emit(e, ctx),
368        }
369    }
370}
371
372impl Document {
373    /// Visits the drawable entities of `models[model_index]` with their model-space transform.
374    ///
375    /// - `Insert` entities are expanded through the block table (name lookup, arrays,
376    ///   nesting up to `max_depth`); the callback sees the block's entities, not the insert.
377    ///   An insert whose block is missing, that would recurse into a block already being
378    ///   expanded (cycle), or that sits deeper than `max_depth` is reported itself.
379    /// - `Dimension` entities that name an existing block are expanded the same way; others
380    ///   are reported as-is.
381    /// - `Group` children are visited with the group's transform; the group itself is not.
382    /// - Entities with `visible == false` and entities on hidden or frozen layers are skipped
383    ///   (together with everything below them).
384    ///
385    /// A missing model index visits nothing. The traversal is limited by the default work
386    /// budget ([`DEFAULT_MAX_WORK`]) so malicious block nesting cannot hang the caller.
387    pub fn walk<'a, F>(&'a self, model_index: usize, max_depth: u32, mut f: F)
388    where
389        F: FnMut(&'a Entity, &WalkContext<'a>),
390    {
391        let opts = WalkOptions {
392            max_depth,
393            ..WalkOptions::default()
394        };
395        self.walk_while(model_index, &opts, |e, c| {
396            f(e, c);
397            true
398        });
399    }
400
401    /// [`Document::walk`] with explicit [`WalkOptions`]; reports whether the work budget cut
402    /// the traversal short.
403    pub fn walk_with<'a, F>(
404        &'a self,
405        model_index: usize,
406        options: &WalkOptions,
407        mut f: F,
408    ) -> WalkStats
409    where
410        F: FnMut(&'a Entity, &WalkContext<'a>),
411    {
412        self.walk_while(model_index, options, |e, c| {
413            f(e, c);
414            true
415        })
416    }
417
418    /// Like [`Document::walk_with`], but the callback returns `false` to stop the traversal
419    /// (reported as `truncated`).
420    pub fn walk_while<'a, F>(&'a self, model_index: usize, options: &WalkOptions, f: F) -> WalkStats
421    where
422        F: FnMut(&'a Entity, &WalkContext<'a>) -> bool,
423    {
424        self.walk_while_internal(model_index, options, false, f)
425    }
426
427    /// Like [`Document::walk_while`], but also visits entities on hidden (`visible == false`)
428    /// or frozen (`frozen == true`) layers. Entities with `entity.visible == false` remain skipped.
429    pub fn walk_all_layers_while<'a, F>(
430        &'a self,
431        model_index: usize,
432        options: &WalkOptions,
433        f: F,
434    ) -> WalkStats
435    where
436        F: FnMut(&'a Entity, &WalkContext<'a>) -> bool,
437    {
438        self.walk_while_internal(model_index, options, true, f)
439    }
440
441    fn walk_while_internal<'a, F>(
442        &'a self,
443        model_index: usize,
444        options: &WalkOptions,
445        include_hidden_layers: bool,
446        f: F,
447    ) -> WalkStats
448    where
449        F: FnMut(&'a Entity, &WalkContext<'a>) -> bool,
450    {
451        let Some(model) = self.models.get(model_index) else {
452            return WalkStats::default();
453        };
454        let mut blocks = HashMap::new();
455        for b in &self.blocks {
456            blocks.entry(b.name.as_str()).or_insert(b);
457        }
458        let mut layers = HashMap::new();
459        for l in &self.layers {
460            layers.entry(l.name.as_str()).or_insert(l);
461        }
462        let mut colors = HashMap::new();
463        for l in &self.layers {
464            colors.entry(l.name.as_str()).or_insert(l.color);
465        }
466        let colors = Rc::new(colors);
467        let mut w = Walker {
468            blocks,
469            layers,
470            colors: Rc::clone(&colors),
471            opts: *options,
472            include_hidden_layers,
473            work: options.max_work,
474            spent: 0,
475            truncated: false,
476            stack: Vec::new(),
477            f,
478        };
479        let root = WalkContext {
480            layer_colors: Some(colors),
481            ..WalkContext::root()
482        };
483        w.visit_list(&model.entities, &root);
484        WalkStats {
485            truncated: w.truncated,
486            work: w.spent,
487        }
488    }
489
490    /// Bounding box (model-space XYZ) of everything [`Document::walk`] visits in
491    /// `models[model_index]`, or `None` when there is no geometry.
492    ///
493    /// Arcs, circles and ellipses use their exact extents, splines their sampled curve,
494    /// polylines include bulge arcs. Text is approximated (glyph width 0.6 x height) because
495    /// fonts are unknown; viewports and unknown records contribute nothing.
496    pub fn bbox(&self, model_index: usize) -> Option<BBox> {
497        self.bbox_with(model_index, &BBoxOptions::default())
498    }
499
500    /// [`Document::bbox`] with options; with `include_images: false` raster image frames are
501    /// ignored (their stored extent can dwarf the drawing, e.g. DGN raster frames).
502    pub fn bbox_with(&self, model_index: usize, options: &BBoxOptions) -> Option<BBox> {
503        self.bbox_internal(model_index, options, false)
504    }
505
506    /// Like [`Document::bbox_with`], including entities on hidden or frozen layers.
507    pub fn bbox_all_layers_with(&self, model_index: usize, options: &BBoxOptions) -> Option<BBox> {
508        self.bbox_internal(model_index, options, true)
509    }
510
511    fn bbox_internal(
512        &self,
513        model_index: usize,
514        options: &BBoxOptions,
515        include_hidden_layers: bool,
516    ) -> Option<BBox> {
517        let mut bb = None;
518        let walk = WalkOptions {
519            max_work: options.max_work,
520            ..WalkOptions::default()
521        };
522        self.walk_while_internal(model_index, &walk, include_hidden_layers, |e, ctx| {
523            if !options.include_images && matches!(e.kind, EntityKind::Image { .. }) {
524                return true;
525            }
526            entity_extents(e, &ctx.transform, &mut bb);
527            true
528        });
529        bb
530    }
531}
532
533fn display_rgb(c: Color) -> Option<(u8, u8, u8)> {
534    match c {
535        Color::Rgb { r, g, b } => Some((r, g, b)),
536        Color::Aci { index: 0 } | Color::ByLayer | Color::ByBlock => None,
537        Color::Aci { index: 7 } => Some(BLACK),
538        Color::Aci { index } => Some(aci::to_rgb(index)),
539    }
540}
541
542/// Shared color rule, see [`Entity::resolved_color`].
543fn resolve_color(
544    c: Color,
545    layer_color: impl FnOnce() -> Option<Color>,
546    block: Option<(u8, u8, u8)>,
547) -> (u8, u8, u8) {
548    if let Some(rgb) = display_rgb(c) {
549        return rgb;
550    }
551    match c {
552        Color::ByLayer => layer_color().and_then(display_rgb).unwrap_or(BLACK),
553        _ => block.unwrap_or(BLACK),
554    }
555}
556
557impl Entity {
558    /// Display color as RGB, resolved without block context (`ByBlock` becomes black).
559    ///
560    /// Rules: `Rgb` as stored; `Aci` through the AutoCAD table, except ACI 7 (the
561    /// "foreground" color, white on dark and black on light backgrounds) which is mapped to
562    /// black to read on a white page; `ByLayer` uses the layer's color (layer `"0"` when the
563    /// entity has none; a missing layer, or a layer color that is itself `ByLayer`/`ByBlock`,
564    /// gives black); `ByBlock` gives black here and the inserting entity's color via
565    /// [`Entity::resolved_color_in`].
566    pub fn resolved_color(&self, doc: &Document) -> (u8, u8, u8) {
567        self.resolved_color_in(doc, &WalkContext::root())
568    }
569
570    /// [`Entity::resolved_color`] inside a [`Document::walk`] callback: `ByBlock` resolves to
571    /// the color of the inserting entity and layer `"0"` to the inherited layer.
572    pub fn resolved_color_in(&self, doc: &Document, ctx: &WalkContext<'_>) -> (u8, u8, u8) {
573        let name = ctx.layer_name(self);
574        resolve_color(
575            self.color,
576            || match &ctx.layer_colors {
577                Some(map) => map.get(name).copied(),
578                None => doc.layers.iter().find(|l| l.name == name).map(|l| l.color),
579            },
580            ctx.block_color,
581        )
582    }
583
584    /// World-space bounding box of this entity without an additional placement transform.
585    pub fn bbox(&self) -> Option<BBox> {
586        entity_bbox(self, &Transform::identity())
587    }
588
589    /// Bounding box of this entity mapped through `transform`.
590    pub fn bbox_in(&self, transform: &Transform) -> Option<BBox> {
591        entity_bbox(self, transform)
592    }
593}
594
595impl EntityKind {
596    /// Stable lowercase name of the variant (matches the JSON `type` tag).
597    pub fn type_name(&self) -> &'static str {
598        match self {
599            Self::Point { .. } => "point",
600            Self::Line { .. } => "line",
601            Self::Polyline { .. } => "polyline",
602            Self::Circle { .. } => "circle",
603            Self::Arc { .. } => "arc",
604            Self::Ellipse { .. } => "ellipse",
605            Self::Spline { .. } => "spline",
606            Self::Text { .. } => "text",
607            Self::MText { .. } => "mtext",
608            Self::Insert { .. } => "insert",
609            Self::Hatch { .. } => "hatch",
610            Self::Dimension { .. } => "dimension",
611            Self::Face { .. } => "face",
612            Self::Polygon { .. } => "polygon",
613            Self::Leader { .. } => "leader",
614            Self::Image { .. } => "image",
615            Self::Viewport { .. } => "viewport",
616            Self::Mesh { .. } => "mesh",
617            Self::Group { .. } => "group",
618            Self::Unknown { .. } => "unknown",
619        }
620    }
621}
622
623// ---------------------------------------------------------------------------------------------
624// Shared primitives (also used by the SVG renderer)
625// ---------------------------------------------------------------------------------------------
626
627/// Circle/arc around the world point `center` in the plane of `normal`, mapped through `tf`.
628pub(crate) fn circle_arc(
629    center: Point3,
630    radius: f64,
631    start: f64,
632    end: f64,
633    normal: Vec3,
634    tf: &Transform,
635) -> EllipseArc {
636    EllipseArc::circle(Point3::default(), radius, start, end)
637        .transformed(&tf.compose(&Transform::plane(center, normal)))
638}
639
640/// Ellipse mapped through `tf` (ellipse data is in WCS).
641pub(crate) fn full_ellipse_arc(
642    center: Point3,
643    major: Vec3,
644    ratio: f64,
645    normal: Vec3,
646    start: f64,
647    end: f64,
648    tf: &Transform,
649) -> EllipseArc {
650    ellipse_arc(center, major, ratio, normal, start, end).transformed(tf)
651}
652
653/// Arc of the segment `a -> b` if `a.bulge` makes it curved, mapped through `tf`.
654///
655/// The bulge turns counter-clockwise about `normal`, so the arc is solved in the plane
656/// through `a` spanned by `arbitrary_axes(normal)`.
657pub(crate) fn segment_arc(
658    a: &Vertex,
659    b: &Vertex,
660    normal: Vec3,
661    tf: &Transform,
662) -> Option<EllipseArc> {
663    let plane = Transform::plane(a.position, normal);
664    let d = a.position.vector_to(b.position);
665    let local_b = (d.dot(plane.x), d.dot(plane.y));
666    let arc = bulge_to_arc((0.0, 0.0), local_b, a.bulge)?;
667    let e = EllipseArc {
668        center: Point3::new(arc.center.0, arc.center.1, 0.0),
669        u: Vec3::new(arc.radius, 0.0, 0.0),
670        v: Vec3::new(0.0, arc.radius, 0.0),
671        t0: arc.start_angle,
672        t1: arc.start_angle + arc.sweep,
673    };
674    Some(e.transformed(&tf.compose(&plane)))
675}
676
677/// Samples per knot span when splines are flattened.
678pub(crate) const SPLINE_SAMPLES: usize = 16;
679
680/// A spline as a polyline in model space: sampled NURBS, else interpolated fit points, else control points.
681pub(crate) fn spline_points(
682    degree: u32,
683    knots: &[f64],
684    control: &[Point3],
685    weights: &[f64],
686    fit: &[Point3],
687    closed: bool,
688    tf: &Transform,
689) -> Vec<Point3> {
690    let pts = if control.len() >= 2 {
691        nurbs_flatten(degree, knots, control, weights, SPLINE_SAMPLES)
692    } else if fit.len() >= 2 {
693        if let Some((deg, iknots, ictrl)) = interpolate_fit_points(fit, closed) {
694            nurbs_flatten(deg, &iknots, &ictrl, &[], SPLINE_SAMPLES)
695        } else {
696            fit.to_vec()
697        }
698    } else {
699        control.to_vec()
700    };
701    pts.into_iter().map(|p| tf.apply_point(p)).collect()
702}
703
704/// Rough text extents: `(x range, y range)` relative to the insertion point, before rotation.
705fn text_box(
706    chars: usize,
707    height: f64,
708    width_factor: f64,
709    halign: HAlign,
710    valign: VAlign,
711) -> ((f64, f64), (f64, f64)) {
712    let wf = if width_factor.is_finite() && width_factor > 0.0 {
713        width_factor
714    } else {
715        1.0
716    };
717    let w = 0.6 * height * wf * chars.max(1) as f64;
718    // Aligned/fit text without an end point starts at the baseline origin.
719    let valign = if matches!(halign, HAlign::Aligned | HAlign::Fit) {
720        VAlign::Baseline
721    } else {
722        valign
723    };
724    let x = match halign {
725        HAlign::Left | HAlign::Aligned | HAlign::Fit => (0.0, w),
726        HAlign::Right => (-w, 0.0),
727        _ => (-w / 2.0, w / 2.0),
728    };
729    let y = match valign {
730        VAlign::Baseline | VAlign::Bottom => (0.0, height),
731        VAlign::Middle => (-height / 2.0, height / 2.0),
732        VAlign::Top => (-height, 0.0),
733    };
734    (x, y)
735}
736
737fn extend_box(
738    bb: &mut Option<BBox>,
739    origin: Point3,
740    rotation: f64,
741    x: (f64, f64),
742    y: (f64, f64),
743    tf: &Transform,
744) {
745    let (s, c) = rotation.sin_cos();
746    for px in [x.0, x.1] {
747        for py in [y.0, y.1] {
748            let p = Point3::new(
749                origin.x + px * c - py * s,
750                origin.y + px * s + py * c,
751                origin.z,
752            );
753            extend_bbox(bb, tf.apply_point(p));
754        }
755    }
756}
757
758/// Lines of an MText entity (plain text preferred, format codes stripped by the reader).
759pub(crate) fn mtext_text_lines(value: &str, plain: &str) -> Vec<String> {
760    if !plain.is_empty() {
761        plain
762            .split('\n')
763            .map(|s| s.trim_end_matches('\r').to_owned())
764            .collect()
765    } else {
766        value.split("\\P").map(str::to_owned).collect()
767    }
768}
769
770/// Horizontal / vertical anchor of an MText attachment point: (-1 left | 0 center | 1 right,
771/// -1 top | 0 middle | 1 bottom).
772pub(crate) fn attachment_anchor(a: Attachment) -> (i8, i8) {
773    match a {
774        Attachment::TopLeft => (-1, -1),
775        Attachment::TopCenter => (0, -1),
776        Attachment::TopRight => (1, -1),
777        Attachment::MiddleLeft => (-1, 0),
778        Attachment::MiddleCenter => (0, 0),
779        Attachment::MiddleRight => (1, 0),
780        Attachment::BottomLeft => (-1, 1),
781        Attachment::BottomCenter => (0, 1),
782        Attachment::BottomRight => (1, 1),
783    }
784}
785
786/// Distance between MText baselines for a text height and line-spacing factor.
787pub(crate) fn mtext_line_height(height: f64, line_spacing: f64) -> f64 {
788    let f = if line_spacing.is_finite() && line_spacing > 0.0 {
789        line_spacing
790    } else {
791        1.0
792    };
793    height * f * (5.0 / 3.0)
794}
795
796fn extend_hatch_edge(bb: &mut Option<BBox>, edge: &HatchEdge, normal: Vec3, tf: &Transform) {
797    match edge {
798        HatchEdge::Line { start, end } => {
799            extend_bbox(bb, tf.apply_point(*start));
800            extend_bbox(bb, tf.apply_point(*end));
801        }
802        HatchEdge::Arc {
803            center,
804            radius,
805            start_angle,
806            end_angle,
807            ccw,
808        } => {
809            let (s, en) = if *ccw {
810                (*start_angle, *end_angle)
811            } else {
812                (*end_angle, *start_angle)
813            };
814            circle_arc(*center, *radius, s, en, normal, tf).extend_bbox(bb);
815        }
816        HatchEdge::Ellipse {
817            center,
818            major_axis,
819            ratio,
820            start_param,
821            end_param,
822            ccw,
823        } => {
824            let (s, en) = if *ccw {
825                (*start_param, *end_param)
826            } else {
827                (*end_param, *start_param)
828            };
829            full_ellipse_arc(*center, *major_axis, *ratio, normal, s, en, tf).extend_bbox(bb);
830        }
831        HatchEdge::Spline {
832            degree,
833            knots,
834            control_points,
835            weights,
836        } => {
837            for p in spline_points(*degree, knots, control_points, weights, &[], false, tf) {
838                extend_bbox(bb, p);
839            }
840        }
841        HatchEdge::Polyline { vertices, closed } => {
842            extend_polyline(bb, vertices, *closed, normal, tf)
843        }
844    }
845}
846
847fn extend_polyline(
848    bb: &mut Option<BBox>,
849    vertices: &[Vertex],
850    closed: bool,
851    normal: Vec3,
852    tf: &Transform,
853) {
854    for v in vertices {
855        extend_bbox(bb, tf.apply_point(v.position));
856    }
857    let n = vertices.len();
858    let segs = if closed { n } else { n.saturating_sub(1) };
859    for i in 0..segs {
860        if let (Some(a), Some(b)) = (vertices.get(i), vertices.get((i + 1) % n.max(1)))
861            && let Some(arc) = segment_arc(a, b, normal, tf)
862        {
863            arc.extend_bbox(bb);
864        }
865    }
866}
867
868fn entity_extents(e: &Entity, tf: &Transform, bb: &mut Option<BBox>) {
869    match &e.kind {
870        EntityKind::Point { position } => extend_bbox(bb, tf.apply_point(*position)),
871        EntityKind::Line { start, end } => {
872            extend_bbox(bb, tf.apply_point(*start));
873            extend_bbox(bb, tf.apply_point(*end));
874        }
875        EntityKind::Polyline {
876            vertices,
877            closed,
878            normal,
879        } => extend_polyline(bb, vertices, *closed, *normal, tf),
880        EntityKind::Circle {
881            center,
882            radius,
883            normal,
884        } => {
885            circle_arc(*center, *radius, 0.0, 0.0, *normal, tf).extend_bbox(bb);
886        }
887        EntityKind::Arc {
888            center,
889            radius,
890            start_angle,
891            end_angle,
892            normal,
893        } => {
894            circle_arc(*center, *radius, *start_angle, *end_angle, *normal, tf).extend_bbox(bb);
895        }
896        EntityKind::Ellipse {
897            center,
898            major_axis,
899            ratio,
900            start_param,
901            end_param,
902            normal,
903        } => {
904            full_ellipse_arc(
905                *center,
906                *major_axis,
907                *ratio,
908                *normal,
909                *start_param,
910                *end_param,
911                tf,
912            )
913            .extend_bbox(bb);
914        }
915        EntityKind::Spline {
916            degree,
917            knots,
918            control_points,
919            weights,
920            fit_points,
921            closed,
922        } => {
923            for p in spline_points(
924                *degree,
925                knots,
926                control_points,
927                weights,
928                fit_points,
929                *closed,
930                tf,
931            ) {
932                extend_bbox(bb, p);
933            }
934        }
935        EntityKind::Text {
936            position,
937            end_point: Some(end),
938            height,
939            normal,
940            ..
941        } => {
942            // Aligned / fit text: the baseline runs from `position` to `end_point`.
943            let dir = position.vector_to(*end);
944            let up = normal
945                .cross(dir)
946                .normalized()
947                .unwrap_or(Vec3::new(0.0, 1.0, 0.0))
948                .scaled(*height);
949            for p in [*position, *end] {
950                extend_bbox(bb, tf.apply_point(p));
951                extend_bbox(bb, tf.apply_point(p.translated(up)));
952            }
953        }
954        EntityKind::Text {
955            position,
956            height,
957            rotation,
958            width_factor,
959            value,
960            halign,
961            valign,
962            normal,
963            ..
964        } => {
965            let (x, y) = text_box(
966                value.chars().count(),
967                *height,
968                *width_factor,
969                *halign,
970                *valign,
971            );
972            extend_box(
973                bb,
974                Point3::default(),
975                *rotation,
976                x,
977                y,
978                &tf.compose(&Transform::plane(*position, *normal)),
979            );
980        }
981        EntityKind::MText {
982            position,
983            height,
984            width,
985            rotation,
986            value,
987            plain,
988            attachment,
989            line_spacing,
990            normal,
991            ..
992        } => {
993            let lines = mtext_text_lines(value, plain);
994            let widest = lines.iter().map(|l| l.chars().count()).max().unwrap_or(1);
995            let w = if *width > 0.0 && width.is_finite() {
996                *width
997            } else {
998                0.6 * height * widest as f64
999            };
1000            let h = mtext_line_height(*height, *line_spacing) * lines.len().max(1) as f64;
1001            let (ha, va) = attachment_anchor(*attachment);
1002            let x = match ha {
1003                -1 => (0.0, w),
1004                0 => (-w / 2.0, w / 2.0),
1005                _ => (-w, 0.0),
1006            };
1007            let y = match va {
1008                -1 => (-h, 0.0),
1009                0 => (-h / 2.0, h / 2.0),
1010                _ => (0.0, h),
1011            };
1012            extend_box(
1013                bb,
1014                Point3::default(),
1015                *rotation,
1016                x,
1017                y,
1018                &tf.compose(&Transform::plane(*position, *normal)),
1019            );
1020        }
1021        EntityKind::Insert { position, .. } => {
1022            extend_bbox(bb, tf.apply_point(*position));
1023        }
1024        EntityKind::Hatch { loops, normal, .. } => {
1025            for l in loops {
1026                for edge in &l.edges {
1027                    extend_hatch_edge(bb, edge, *normal, tf);
1028                }
1029            }
1030        }
1031        EntityKind::Dimension {
1032            points,
1033            text_position,
1034            ..
1035        } => {
1036            for p in points.iter().chain(text_position.iter()) {
1037                extend_bbox(bb, tf.apply_point(*p));
1038            }
1039        }
1040        EntityKind::Face { points, .. } => {
1041            for p in points {
1042                extend_bbox(bb, tf.apply_point(*p));
1043            }
1044        }
1045        EntityKind::Polygon {
1046            exterior,
1047            interiors,
1048        } => {
1049            for p in exterior.iter().chain(interiors.iter().flatten()) {
1050                extend_bbox(bb, tf.apply_point(*p));
1051            }
1052        }
1053        EntityKind::Leader { vertices, .. } => {
1054            for p in vertices {
1055                extend_bbox(bb, tf.apply_point(*p));
1056            }
1057        }
1058        EntityKind::Image {
1059            position,
1060            u_vector,
1061            v_vector,
1062            ..
1063        } => {
1064            for (a, b) in [(0.0, 0.0), (1.0, 0.0), (0.0, 1.0), (1.0, 1.0)] {
1065                let p = position.translated(u_vector.scaled(a).plus(v_vector.scaled(b)));
1066                extend_bbox(bb, tf.apply_point(p));
1067            }
1068        }
1069        EntityKind::Mesh { vertices, .. } => {
1070            for p in vertices {
1071                extend_bbox(bb, tf.apply_point(*p));
1072            }
1073        }
1074        EntityKind::Viewport { .. } | EntityKind::Group { .. } | EntityKind::Unknown { .. } => {}
1075    }
1076}
1077
1078/// Computes the world-space XYZ [`BBox`] of `entity` after applying `transform`, or `None` when
1079/// the entity contributes no drawable extent (`Viewport`, `Group`, `Unknown`, or empty geometry).
1080pub fn entity_bbox(entity: &Entity, transform: &Transform) -> Option<BBox> {
1081    let mut bb = None;
1082    entity_extents(entity, transform, &mut bb);
1083    bb
1084}
1085
1086fn seg_dist_xy(px: f64, py: f64, a: Point3, b: Point3) -> f64 {
1087    let dx = b.x - a.x;
1088    let dy = b.y - a.y;
1089    let len_sq = dx * dx + dy * dy;
1090    if !(len_sq.is_finite() && len_sq > 1e-24) {
1091        return (px - a.x).hypot(py - a.y);
1092    }
1093    let t = (((px - a.x) * dx + (py - a.y) * dy) / len_sq).clamp(0.0, 1.0);
1094    (px - (a.x + t * dx)).hypot(py - (a.y + t * dy))
1095}
1096
1097fn arc_dist_xy(px: f64, py: f64, arc: &EllipseArc) -> f64 {
1098    // Preserve exact circular picking after uniform scale/reflection. Chords otherwise
1099    // underestimate ring distance and can select points outside a small tolerance.
1100    let radius = arc.u.x.hypot(arc.u.y);
1101    let other_radius = arc.v.x.hypot(arc.v.y);
1102    let dot = arc.u.x * arc.v.x + arc.u.y * arc.v.y;
1103    if radius.is_finite()
1104        && radius > 0.0
1105        && (radius - other_radius).abs() <= radius * 1e-12
1106        && dot.abs() <= radius * other_radius * 1e-12
1107    {
1108        let dx = px - arc.center.x;
1109        let dy = py - arc.center.y;
1110        let t = (dx * arc.v.x + dy * arc.v.y).atan2(dx * arc.u.x + dy * arc.u.y);
1111        let sweep = arc.sweep();
1112        let travel = if sweep >= 0.0 { t - arc.t0 } else { arc.t0 - t };
1113        if sweep.abs() >= std::f64::consts::TAU - 1e-12
1114            || travel.rem_euclid(std::f64::consts::TAU) <= sweep.abs()
1115        {
1116            return (dx.hypot(dy) - radius).abs();
1117        }
1118        let a = arc.point(arc.t0);
1119        let b = arc.point(arc.t1);
1120        return (px - a.x).hypot(py - a.y).min((px - b.x).hypot(py - b.y));
1121    }
1122    let steps = ((arc.sweep().abs() / 0.1).ceil() as usize).clamp(16, 256);
1123    let mut best = f64::INFINITY;
1124    let mut prev = arc.point(arc.t0);
1125    for i in 1..=steps {
1126        let t = arc.t0 + (arc.t1 - arc.t0) * (i as f64) / (steps as f64);
1127        let cur = arc.point(t);
1128        best = best.min(seg_dist_xy(px, py, prev, cur));
1129        prev = cur;
1130    }
1131    best
1132}
1133
1134fn ring_contains_xy(px: f64, py: f64, ring: &[Point3], tf: &Transform) -> bool {
1135    let n = ring.len();
1136    if n < 3 {
1137        return false;
1138    }
1139    let mut inside = false;
1140    for i in 0..n {
1141        let (Some(ra), Some(rb)) = (ring.get(i), ring.get((i + 1) % n)) else {
1142            continue;
1143        };
1144        let a = tf.apply_point(*ra);
1145        let b = tf.apply_point(*rb);
1146        if (a.y > py) != (b.y > py) {
1147            let x_cross = a.x + (py - a.y) * (b.x - a.x) / (b.y - a.y);
1148            if px < x_cross {
1149                inside = !inside;
1150            }
1151        }
1152    }
1153    inside
1154}
1155
1156fn ring_edge_dist_xy(px: f64, py: f64, ring: &[Point3], closed: bool, tf: &Transform) -> f64 {
1157    let n = ring.len();
1158    if n == 0 {
1159        return f64::INFINITY;
1160    }
1161    if n == 1 {
1162        let p = ring
1163            .first()
1164            .map_or(Point3::default(), |pt| tf.apply_point(*pt));
1165        return (px - p.x).hypot(py - p.y);
1166    }
1167    let segs = if closed { n } else { n - 1 };
1168    let mut best = f64::INFINITY;
1169    for i in 0..segs {
1170        if let (Some(ra), Some(rb)) = (ring.get(i), ring.get((i + 1) % n)) {
1171            best = best.min(seg_dist_xy(
1172                px,
1173                py,
1174                tf.apply_point(*ra),
1175                tf.apply_point(*rb),
1176            ));
1177        }
1178    }
1179    best
1180}
1181
1182/// 2D distance in world XY coordinates from `point` `(x, y)` to `entity` mapped by `transform`,
1183/// or `None` when the entity has no 2D extent.
1184///
1185/// Circular arcs use exact XY distances; other curves use bounded polyline sampling.
1186/// Filled polygons/faces use their regions (including polygon holes). Other unsupported
1187/// kinds, hatches and annotations use bounding boxes and return zero inside those boxes.
1188pub fn entity_distance_xy(
1189    entity: &Entity,
1190    transform: &Transform,
1191    point: (f64, f64),
1192) -> Option<f64> {
1193    let (px, py) = point;
1194    if !(px.is_finite() && py.is_finite()) {
1195        return None;
1196    }
1197    match &entity.kind {
1198        EntityKind::Point { position } => {
1199            let p = transform.apply_point(*position);
1200            Some((px - p.x).hypot(py - p.y))
1201        }
1202        EntityKind::Line { start, end } => Some(seg_dist_xy(
1203            px,
1204            py,
1205            transform.apply_point(*start),
1206            transform.apply_point(*end),
1207        )),
1208        EntityKind::Polyline {
1209            vertices,
1210            closed,
1211            normal,
1212        } => {
1213            let n = vertices.len();
1214            if n == 0 {
1215                return None;
1216            }
1217            if n == 1 {
1218                let p = vertices
1219                    .first()
1220                    .map_or(Point3::default(), |v| transform.apply_point(v.position));
1221                return Some((px - p.x).hypot(py - p.y));
1222            }
1223            let segs = if *closed { n } else { n - 1 };
1224            let mut best = f64::INFINITY;
1225            for i in 0..segs {
1226                let (Some(a), Some(b)) = (vertices.get(i), vertices.get((i + 1) % n)) else {
1227                    continue;
1228                };
1229                let d = if let Some(arc) = segment_arc(a, b, *normal, transform) {
1230                    arc_dist_xy(px, py, &arc)
1231                } else {
1232                    seg_dist_xy(
1233                        px,
1234                        py,
1235                        transform.apply_point(a.position),
1236                        transform.apply_point(b.position),
1237                    )
1238                };
1239                best = best.min(d);
1240            }
1241            best.is_finite().then_some(best)
1242        }
1243        EntityKind::Circle {
1244            center,
1245            radius,
1246            normal,
1247        } => {
1248            let arc = circle_arc(*center, *radius, 0.0, 0.0, *normal, transform);
1249            Some(arc_dist_xy(px, py, &arc))
1250        }
1251        EntityKind::Arc {
1252            center,
1253            radius,
1254            start_angle,
1255            end_angle,
1256            normal,
1257        } => {
1258            let arc = circle_arc(
1259                *center,
1260                *radius,
1261                *start_angle,
1262                *end_angle,
1263                *normal,
1264                transform,
1265            );
1266            Some(arc_dist_xy(px, py, &arc))
1267        }
1268        EntityKind::Ellipse {
1269            center,
1270            major_axis,
1271            ratio,
1272            start_param,
1273            end_param,
1274            normal,
1275        } => {
1276            let arc = full_ellipse_arc(
1277                *center,
1278                *major_axis,
1279                *ratio,
1280                *normal,
1281                *start_param,
1282                *end_param,
1283                transform,
1284            );
1285            Some(arc_dist_xy(px, py, &arc))
1286        }
1287        EntityKind::Spline {
1288            degree,
1289            knots,
1290            control_points,
1291            weights,
1292            fit_points,
1293            closed,
1294        } => {
1295            let pts = spline_points(
1296                *degree,
1297                knots,
1298                control_points,
1299                weights,
1300                fit_points,
1301                *closed,
1302                transform,
1303            );
1304            let d = ring_edge_dist_xy(px, py, &pts, *closed, &Transform::identity());
1305            d.is_finite().then_some(d)
1306        }
1307        EntityKind::Leader { vertices, .. } => {
1308            let d = ring_edge_dist_xy(px, py, vertices, false, transform);
1309            d.is_finite().then_some(d)
1310        }
1311        EntityKind::Face { points, filled } => {
1312            if *filled && ring_contains_xy(px, py, points, transform) {
1313                return Some(0.0);
1314            }
1315            let d = ring_edge_dist_xy(px, py, points, true, transform);
1316            d.is_finite().then_some(d)
1317        }
1318        EntityKind::Polygon {
1319            exterior,
1320            interiors,
1321        } => {
1322            let in_ext = ring_contains_xy(px, py, exterior, transform);
1323            let in_hole = interiors
1324                .iter()
1325                .any(|hole| ring_contains_xy(px, py, hole, transform));
1326            if in_ext && !in_hole {
1327                return Some(0.0);
1328            }
1329            let mut best = ring_edge_dist_xy(px, py, exterior, true, transform);
1330            for hole in interiors {
1331                best = best.min(ring_edge_dist_xy(px, py, hole, true, transform));
1332            }
1333            best.is_finite().then_some(best)
1334        }
1335        _ => {
1336            let bb = entity_bbox(entity, transform)?;
1337            let dx = if px < bb.min.x {
1338                bb.min.x - px
1339            } else if px > bb.max.x {
1340                px - bb.max.x
1341            } else {
1342                0.0
1343            };
1344            let dy = if py < bb.min.y {
1345                bb.min.y - py
1346            } else if py > bb.max.y {
1347                py - bb.max.y
1348            } else {
1349                0.0
1350            };
1351            Some(dx.hypot(dy))
1352        }
1353    }
1354}
1355
1356#[cfg(test)]
1357mod tests {
1358    use std::f64::consts::PI;
1359
1360    use super::*;
1361    use crate::model::{Model, Units};
1362
1363    fn line(x0: f64, y0: f64, x1: f64, y1: f64) -> Entity {
1364        Entity::new(EntityKind::Line {
1365            start: Point3::xy(x0, y0),
1366            end: Point3::xy(x1, y1),
1367        })
1368    }
1369
1370    fn insert(block: &str, x: f64, y: f64) -> Entity {
1371        Entity::new(EntityKind::Insert {
1372            block: block.to_owned(),
1373            position: Point3::xy(x, y),
1374            scale: Vec3::new(1.0, 1.0, 1.0),
1375            rotation: 0.0,
1376            normal: Vec3::Z,
1377            columns: 1,
1378            rows: 1,
1379            column_spacing: 0.0,
1380            row_spacing: 0.0,
1381        })
1382    }
1383
1384    fn doc_with(models: Vec<Entity>, blocks: Vec<Block>) -> Document {
1385        Document {
1386            units: Units::default(),
1387            blocks,
1388            models: vec![Model {
1389                name: "Model".into(),
1390                entities: models,
1391                ..Model::default()
1392            }],
1393            ..Document::default()
1394        }
1395    }
1396
1397    fn block(name: &str, entities: Vec<Entity>) -> Block {
1398        Block {
1399            name: name.to_owned(),
1400            entities,
1401            ..Block::default()
1402        }
1403    }
1404
1405    fn collect(doc: &Document, depth: u32) -> Vec<(Point3, u32)> {
1406        let mut out = Vec::new();
1407        doc.walk(0, depth, |e, ctx| {
1408            if let EntityKind::Line { start, .. } = &e.kind {
1409                out.push((ctx.transform.apply_point(*start), ctx.depth));
1410            }
1411        });
1412        out
1413    }
1414
1415    #[test]
1416    fn walk_expands_nested_inserts() {
1417        let inner = block("inner", vec![line(0.0, 0.0, 1.0, 0.0)]);
1418        let outer = block("outer", vec![insert("inner", 5.0, 0.0)]);
1419        let doc = doc_with(vec![insert("outer", 0.0, 10.0)], vec![inner, outer]);
1420        let hits = collect(&doc, 8);
1421        assert_eq!(hits.len(), 1);
1422        assert_eq!(hits[0].0, Point3::new(5.0, 10.0, 0.0));
1423        assert_eq!(hits[0].1, 2);
1424    }
1425
1426    #[test]
1427    fn walk_depth_limit_reports_insert() {
1428        let inner = block("inner", vec![line(0.0, 0.0, 1.0, 0.0)]);
1429        let outer = block("outer", vec![insert("inner", 5.0, 0.0)]);
1430        let doc = doc_with(vec![insert("outer", 0.0, 0.0)], vec![inner, outer]);
1431        let mut inserts = 0;
1432        let mut lines = 0;
1433        doc.walk(0, 1, |e, _| match e.kind {
1434            EntityKind::Insert { .. } => inserts += 1,
1435            EntityKind::Line { .. } => lines += 1,
1436            _ => {}
1437        });
1438        assert_eq!((inserts, lines), (1, 0));
1439    }
1440
1441    #[test]
1442    fn walk_survives_cycles() {
1443        let a = block("a", vec![line(0.0, 0.0, 1.0, 1.0), insert("b", 1.0, 0.0)]);
1444        let b = block("b", vec![insert("a", 1.0, 0.0)]);
1445        let selfref = block("s", vec![insert("s", 0.0, 0.0)]);
1446        let doc = doc_with(
1447            vec![insert("a", 0.0, 0.0), insert("s", 0.0, 0.0)],
1448            vec![a, b, selfref],
1449        );
1450        let mut n = 0;
1451        doc.walk(0, 64, |_, _| n += 1);
1452        // line of a, the unexpandable insert of a inside b, and the unexpandable self insert.
1453        assert_eq!(n, 3);
1454        assert!(doc.bbox(0).is_some());
1455    }
1456
1457    #[test]
1458    fn walk_arrays_and_scale() {
1459        let blk = block("b", vec![line(0.0, 0.0, 1.0, 0.0)]);
1460        let mut ins = insert("b", 0.0, 0.0);
1461        ins.kind = EntityKind::Insert {
1462            block: "b".into(),
1463            position: Point3::xy(0.0, 0.0),
1464            scale: Vec3::new(2.0, 2.0, 1.0),
1465            rotation: PI / 2.0,
1466            normal: Vec3::Z,
1467            columns: 2,
1468            rows: 2,
1469            column_spacing: 10.0,
1470            row_spacing: 20.0,
1471        };
1472        let doc = doc_with(vec![ins], vec![blk]);
1473        let mut starts = Vec::new();
1474        doc.walk(0, 8, |e, ctx| {
1475            if let EntityKind::Line { start, .. } = &e.kind {
1476                starts.push(ctx.transform.apply_point(*start));
1477            }
1478        });
1479        assert_eq!(starts.len(), 4);
1480        // Spacing is in the rotated frame: column offset 10 along +Y, row offset 20 along -X.
1481        let has = |x: f64, y: f64| {
1482            starts
1483                .iter()
1484                .any(|p| (p.x - x).abs() < 1e-9 && (p.y - y).abs() < 1e-9)
1485        };
1486        assert!(has(0.0, 0.0) && has(0.0, 10.0) && has(-20.0, 0.0) && has(-20.0, 10.0));
1487    }
1488
1489    #[test]
1490    fn walk_huge_array_is_bounded() {
1491        let blk = block("b", vec![line(0.0, 0.0, 1.0, 0.0)]);
1492        let mut ins = insert("b", 0.0, 0.0);
1493        if let EntityKind::Insert { columns, rows, .. } = &mut ins.kind {
1494            *columns = u32::MAX;
1495            *rows = u32::MAX;
1496        }
1497        let doc = doc_with(vec![ins], vec![blk]);
1498        let mut n = 0u64;
1499        doc.walk(0, 8, |_, _| n += 1);
1500        assert!(n <= DEFAULT_MAX_WORK);
1501    }
1502
1503    #[test]
1504    fn walk_work_budget_counts_geometry_and_reports_truncation() {
1505        let big = Entity::new(EntityKind::Polyline {
1506            vertices: vec![Vertex::default(); 1000],
1507            closed: false,
1508            normal: Vec3::Z,
1509        });
1510        let doc = doc_with(vec![big.clone(), big.clone(), big], vec![]);
1511        let mut n = 0;
1512        let stats = doc.walk_with(
1513            0,
1514            &WalkOptions {
1515                max_work: 2_500,
1516                ..WalkOptions::default()
1517            },
1518            |_, _| n += 1,
1519        );
1520        assert_eq!(n, 2);
1521        assert!(stats.truncated);
1522        let stats = doc.walk_with(0, &WalkOptions::default(), |_, _| n += 1);
1523        assert!(!stats.truncated && stats.work == 3 * 1001);
1524        // The callback can stop the walk.
1525        let mut seen = 0;
1526        let stats = doc.walk_while(0, &WalkOptions::default(), |_, _| {
1527            seen += 1;
1528            false
1529        });
1530        assert_eq!(seen, 1);
1531        assert!(stats.truncated);
1532    }
1533
1534    #[test]
1535    fn walk_groups_and_hidden_layers() {
1536        let mut hidden = line(0.0, 0.0, 9.0, 9.0);
1537        hidden.layer = Some("off".into());
1538        let group = Entity::new(EntityKind::Group {
1539            group_kind: crate::model::GroupKind::Cell,
1540            name: None,
1541            origin: None,
1542            children: vec![line(0.0, 0.0, 1.0, 1.0), hidden],
1543        });
1544        let mut doc = doc_with(vec![group], vec![]);
1545        doc.layers.push(Layer {
1546            name: "off".into(),
1547            visible: false,
1548            ..Layer::default()
1549        });
1550        let hits = collect(&doc, 8);
1551        assert_eq!(hits.len(), 1);
1552        assert_eq!(hits[0].1, 1);
1553        // frozen too
1554        doc.layers[0].visible = true;
1555        doc.layers[0].frozen = true;
1556        assert_eq!(collect(&doc, 8).len(), 1);
1557        doc.layers[0].frozen = false;
1558        assert_eq!(collect(&doc, 8).len(), 2);
1559    }
1560
1561    #[test]
1562    fn walk_missing_model_and_block() {
1563        let doc = doc_with(vec![insert("nope", 0.0, 0.0)], vec![]);
1564        let mut n = 0;
1565        doc.walk(5, 8, |_, _| n += 1);
1566        assert_eq!(n, 0);
1567        doc.walk(0, 8, |_, _| n += 1);
1568        assert_eq!(n, 1);
1569    }
1570
1571    #[test]
1572    fn dimension_block_expanded() {
1573        let blk = block("*D1", vec![line(0.0, 0.0, 3.0, 0.0)]);
1574        let dim = Entity::new(EntityKind::Dimension {
1575            dimension_type: crate::model::DimensionType::Linear,
1576            points: vec![Point3::xy(100.0, 100.0)],
1577            text_position: None,
1578            measurement: None,
1579            text: None,
1580            block: Some("*D1".into()),
1581            style: None,
1582        });
1583        let doc = doc_with(vec![dim], vec![blk]);
1584        let bb = doc.bbox(0).unwrap();
1585        assert_eq!(bb.max.x, 3.0);
1586    }
1587
1588    #[test]
1589    fn bbox_of_shapes() {
1590        let circle = Entity::new(EntityKind::Circle {
1591            center: Point3::xy(5.0, 5.0),
1592            radius: 2.0,
1593            normal: Vec3::Z,
1594        });
1595        let poly = Entity::new(EntityKind::Polyline {
1596            vertices: vec![
1597                Vertex {
1598                    position: Point3::xy(0.0, 0.0),
1599                    bulge: 1.0,
1600                    ..Vertex::default()
1601                },
1602                Vertex::at(Point3::xy(2.0, 0.0)),
1603            ],
1604            closed: false,
1605            normal: Vec3::Z,
1606        });
1607        let doc = doc_with(vec![circle], vec![]);
1608        let bb = doc.bbox(0).unwrap();
1609        assert!((bb.min.x - 3.0).abs() < 1e-9 && (bb.max.y - 7.0).abs() < 1e-9);
1610        let doc = doc_with(vec![poly], vec![]);
1611        let bb = doc.bbox(0).unwrap();
1612        // Semicircle below the chord reaches y = -1.
1613        assert!((bb.min.y + 1.0).abs() < 1e-9 && (bb.max.x - 2.0).abs() < 1e-9);
1614        assert!(doc_with(vec![], vec![]).bbox(0).is_none());
1615        assert!(doc_with(vec![], vec![]).bbox(3).is_none());
1616    }
1617
1618    #[test]
1619    fn flipped_normal_keeps_wcs_center_and_flips_angles() {
1620        let neg = Vec3::new(0.0, 0.0, -1.0);
1621        let circle = Entity::new(EntityKind::Circle {
1622            center: Point3::xy(5.0, 0.0),
1623            radius: 1.0,
1624            normal: neg,
1625        });
1626        let bb = doc_with(vec![circle], vec![]).bbox(0).unwrap();
1627        assert!((bb.min.x - 4.0).abs() < 1e-9 && (bb.max.x - 6.0).abs() < 1e-9);
1628        // Plane x axis is -X: an arc from 0 to 90 degrees runs from (c.x - r, c.y) to (c.x, c.y + r).
1629        let arc = Entity::new(EntityKind::Arc {
1630            center: Point3::xy(10.0, 10.0),
1631            radius: 2.0,
1632            start_angle: 0.0,
1633            end_angle: PI / 2.0,
1634            normal: neg,
1635        });
1636        let bb = doc_with(vec![arc], vec![]).bbox(0).unwrap();
1637        let near = |a: f64, b: f64| (a - b).abs() < 1e-9;
1638        assert!(
1639            near(bb.min.x, 8.0)
1640                && near(bb.max.x, 10.0)
1641                && near(bb.min.y, 10.0)
1642                && near(bb.max.y, 12.0),
1643            "{bb:?}"
1644        );
1645    }
1646
1647    #[test]
1648    fn bulged_polyline_with_flipped_normal_bulges_the_other_way() {
1649        let mk = |normal: Vec3| {
1650            Entity::new(EntityKind::Polyline {
1651                vertices: vec![
1652                    Vertex {
1653                        position: Point3::xy(0.0, 0.0),
1654                        bulge: 1.0,
1655                        ..Vertex::default()
1656                    },
1657                    Vertex::at(Point3::xy(2.0, 0.0)),
1658                ],
1659                closed: false,
1660                normal,
1661            })
1662        };
1663        let near = |a: f64, b: f64| (a - b).abs() < 1e-9;
1664        let up = doc_with(vec![mk(Vec3::Z)], vec![]).bbox(0).unwrap();
1665        assert!(near(up.min.y, -1.0) && near(up.max.y, 0.0));
1666        let down = doc_with(vec![mk(Vec3::new(0.0, 0.0, -1.0))], vec![])
1667            .bbox(0)
1668            .unwrap();
1669        assert!(near(down.min.y, 0.0) && near(down.max.y, 1.0), "{down:?}");
1670        assert!(near(down.min.x, 0.0) && near(down.max.x, 2.0));
1671    }
1672
1673    #[test]
1674    fn bbox_with_can_ignore_images() {
1675        let poly = line(0.0, 0.0, 10.0, 10.0);
1676        let image = Entity::new(EntityKind::Image {
1677            path: None,
1678            position: Point3::xy(-50.0, -50.0),
1679            u_vector: Vec3::new(100.0, 0.0, 0.0),
1680            v_vector: Vec3::new(0.0, 100.0, 0.0),
1681            size_px: None,
1682        });
1683        let doc = doc_with(vec![poly, image.clone()], vec![]);
1684        assert!((doc.bbox(0).unwrap().max.x - 50.0).abs() < 1e-9);
1685        let bb = doc
1686            .bbox_with(
1687                0,
1688                &BBoxOptions {
1689                    include_images: false,
1690                    ..BBoxOptions::default()
1691                },
1692            )
1693            .unwrap();
1694        assert!((bb.max.x - 10.0).abs() < 1e-9);
1695        let only = doc_with(vec![image], vec![]);
1696        assert!(
1697            only.bbox_with(
1698                0,
1699                &BBoxOptions {
1700                    include_images: false,
1701                    ..BBoxOptions::default()
1702                }
1703            )
1704            .is_none()
1705        );
1706    }
1707
1708    #[test]
1709    fn aligned_text_bbox_covers_baseline() {
1710        let t = Entity::new(EntityKind::Text {
1711            position: Point3::xy(0.0, 0.0),
1712            end_point: Some(Point3::xy(10.0, 0.0)),
1713            height: 2.0,
1714            rotation: 0.0,
1715            width_factor: 1.0,
1716            oblique: 0.0,
1717            value: "x".into(),
1718            style: None,
1719            halign: HAlign::Aligned,
1720            valign: VAlign::Baseline,
1721            normal: Vec3::Z,
1722        });
1723        let bb = doc_with(vec![t], vec![]).bbox(0).unwrap();
1724        assert!(
1725            (bb.max.x - 10.0).abs() < 1e-9
1726                && (bb.max.y - 2.0).abs() < 1e-9
1727                && bb.min.y.abs() < 1e-9
1728        );
1729    }
1730
1731    #[test]
1732    fn insert_with_flipped_normal_uses_wcs_position() {
1733        let blk = block("b", vec![line(0.0, 0.0, 1.0, 0.0)]);
1734        let mut ins = insert("b", 10.0, 3.0);
1735        if let EntityKind::Insert { normal, .. } = &mut ins.kind {
1736            *normal = Vec3::new(0.0, 0.0, -1.0);
1737        }
1738        let doc = doc_with(vec![ins], vec![blk]);
1739        let mut pts = Vec::new();
1740        doc.walk(0, 8, |e, ctx| {
1741            if let EntityKind::Line { start, end } = &e.kind {
1742                pts.push((
1743                    ctx.transform.apply_point(*start),
1744                    ctx.transform.apply_point(*end),
1745                ));
1746            }
1747        });
1748        assert_eq!(pts.len(), 1);
1749        let (s, e) = pts[0];
1750        assert!((s.x - 10.0).abs() < 1e-9 && (s.y - 3.0).abs() < 1e-9);
1751        assert!((e.x - 9.0).abs() < 1e-9 && (e.y - 3.0).abs() < 1e-9);
1752    }
1753
1754    #[test]
1755    fn colors() {
1756        let mut doc = doc_with(vec![], vec![]);
1757        doc.layers.push(Layer {
1758            name: "L".into(),
1759            color: Color::Aci { index: 1 },
1760            ..Layer::default()
1761        });
1762        doc.layers.push(Layer {
1763            name: "0".into(),
1764            color: Color::Rgb { r: 1, g: 2, b: 3 },
1765            ..Layer::default()
1766        });
1767        let mut e = Entity::new(EntityKind::Point {
1768            position: Point3::default(),
1769        });
1770        assert_eq!(e.resolved_color(&doc), (1, 2, 3));
1771        e.layer = Some("L".into());
1772        assert_eq!(e.resolved_color(&doc), (255, 0, 0));
1773        e.layer = Some("missing".into());
1774        assert_eq!(e.resolved_color(&doc), (0, 0, 0));
1775        e.color = Color::Aci { index: 5 };
1776        assert_eq!(e.resolved_color(&doc), (0, 0, 255));
1777        e.color = Color::Aci { index: 7 };
1778        assert_eq!(e.resolved_color(&doc), (0, 0, 0));
1779        e.color = Color::Rgb { r: 9, g: 8, b: 7 };
1780        assert_eq!(e.resolved_color(&doc), (9, 8, 7));
1781        e.color = Color::ByBlock;
1782        assert_eq!(e.resolved_color(&doc), (0, 0, 0));
1783    }
1784
1785    #[test]
1786    fn byblock_and_layer_inheritance_through_insert() {
1787        let mut inner = line(0.0, 0.0, 1.0, 0.0);
1788        inner.color = Color::ByBlock;
1789        inner.layer = Some("0".into());
1790        let blk = block("b", vec![inner]);
1791        let mut ins = insert("b", 0.0, 0.0);
1792        ins.color = Color::Aci { index: 3 };
1793        ins.layer = Some("walls".into());
1794        let mut doc = doc_with(vec![ins], vec![blk]);
1795        doc.layers.push(Layer {
1796            name: "walls".into(),
1797            visible: true,
1798            ..Layer::default()
1799        });
1800        let mut seen = None;
1801        doc.walk(0, 8, |e, ctx| {
1802            seen = Some((e.resolved_color_in(&doc, ctx), ctx.layer_name(e).to_owned()));
1803        });
1804        assert_eq!(seen, Some(((0, 255, 0), "walls".to_owned())));
1805    }
1806
1807    #[test]
1808    fn byblock_chain_uses_layer_of_insert() {
1809        let mut inner = line(0.0, 0.0, 1.0, 0.0);
1810        inner.color = Color::ByBlock;
1811        let blk = block("b", vec![inner]);
1812        let ins = insert("b", 0.0, 0.0); // ByLayer on layer "0"
1813        let mut doc = doc_with(vec![ins], vec![blk]);
1814        doc.layers.push(Layer {
1815            name: "0".into(),
1816            color: Color::Aci { index: 1 },
1817            visible: true,
1818            ..Layer::default()
1819        });
1820        let mut seen = None;
1821        doc.walk(0, 8, |e, ctx| seen = Some(e.resolved_color_in(&doc, ctx)));
1822        assert_eq!(seen, Some((255, 0, 0)));
1823    }
1824
1825    #[test]
1826    fn type_names() {
1827        assert_eq!(line(0.0, 0.0, 1.0, 1.0).kind.type_name(), "line");
1828        assert_eq!(insert("a", 0.0, 0.0).kind.type_name(), "insert");
1829    }
1830
1831    #[test]
1832    fn clockwise_hatch_arc_and_ellipse_bbox() {
1833        use crate::HatchLoop;
1834        // Clockwise quarter-circle from pi/2 (0, 2) down to 0 (2, 0) stays in quadrant I.
1835        let cw_arc = Entity::new(EntityKind::Hatch {
1836            loops: vec![HatchLoop {
1837                edges: vec![HatchEdge::Arc {
1838                    center: Point3::default(),
1839                    radius: 2.0,
1840                    start_angle: PI / 2.0,
1841                    end_angle: 0.0,
1842                    ccw: false,
1843                }],
1844                external: true,
1845            }],
1846            solid: true,
1847            pattern: None,
1848            pattern_scale: 1.0,
1849            pattern_angle: 0.0,
1850            normal: Vec3::Z,
1851        });
1852        let bb = doc_with(vec![cw_arc], vec![]).bbox(0).unwrap();
1853        assert!(
1854            bb.min.x >= -1e-9
1855                && bb.min.y >= -1e-9
1856                && (bb.max.x - 2.0).abs() < 1e-9
1857                && (bb.max.y - 2.0).abs() < 1e-9,
1858            "unexpected clockwise hatch arc bbox: {bb:?}"
1859        );
1860
1861        // Clockwise quarter-ellipse from pi/2 (0, 1.5) down to 0 (3, 0) also stays in quadrant I.
1862        let cw_ellipse = Entity::new(EntityKind::Hatch {
1863            loops: vec![HatchLoop {
1864                edges: vec![HatchEdge::Ellipse {
1865                    center: Point3::default(),
1866                    major_axis: Vec3::new(3.0, 0.0, 0.0),
1867                    ratio: 0.5,
1868                    start_param: PI / 2.0,
1869                    end_param: 0.0,
1870                    ccw: false,
1871                }],
1872                external: true,
1873            }],
1874            solid: true,
1875            pattern: None,
1876            pattern_scale: 1.0,
1877            pattern_angle: 0.0,
1878            normal: Vec3::Z,
1879        });
1880        let bb = doc_with(vec![cw_ellipse], vec![]).bbox(0).unwrap();
1881        assert!(
1882            bb.min.x >= -1e-9
1883                && bb.min.y >= -1e-9
1884                && (bb.max.x - 3.0).abs() < 1e-9
1885                && (bb.max.y - 1.5).abs() < 1e-9,
1886            "unexpected clockwise hatch ellipse bbox: {bb:?}"
1887        );
1888    }
1889
1890    #[test]
1891    fn entity_bbox_and_distance_xy_distinguish_diagonal_line_from_box() {
1892        let diag = line(0.0, 0.0, 10.0, 10.0);
1893        let bb = diag.bbox().unwrap();
1894        assert_eq!(
1895            (bb.min.x, bb.min.y, bb.max.x, bb.max.y),
1896            (0.0, 0.0, 10.0, 10.0)
1897        );
1898        // (5, 5) sits directly on the diagonal; (0, 10) is inside the AABB but 5*sqrt(2) away.
1899        let d_on = entity_distance_xy(&diag, &Transform::identity(), (5.0, 5.0)).unwrap();
1900        let d_off = entity_distance_xy(&diag, &Transform::identity(), (0.0, 10.0)).unwrap();
1901        assert!(d_on < 1e-12);
1902        assert!((d_off - 5.0 * 2.0_f64.sqrt()).abs() < 1e-9);
1903
1904        let circle = Entity::circle(Point3::xy(0.0, 0.0), 5.0);
1905        // Center is 5 units from the ring; (5, 0) is on the ring.
1906        assert!(
1907            (entity_distance_xy(&circle, &Transform::identity(), (0.0, 0.0)).unwrap() - 5.0).abs()
1908                < 1e-3
1909        );
1910        assert!(entity_distance_xy(&circle, &Transform::identity(), (5.0, 0.0)).unwrap() < 1e-6);
1911
1912        let mut hidden = line(0.0, 0.0, 4.0, 0.0).on_layer("FROZEN");
1913        hidden.id = Some(9);
1914        let mut doc = doc_with(vec![hidden], vec![]);
1915        doc.layers.push(Layer {
1916            name: "FROZEN".into(),
1917            visible: true,
1918            frozen: true,
1919            ..Layer::default()
1920        });
1921        assert!(doc.bbox(0).is_none());
1922        assert!(
1923            doc.bbox_all_layers_with(0, &BBoxOptions::default())
1924                .is_some()
1925        );
1926    }
1927}
1928
1929#[cfg(test)]
1930mod picking_regressions {
1931    use super::*;
1932
1933    #[test]
1934    fn circular_picking_is_exact_between_old_sample_vertices() {
1935        let circle = Entity::circle(Point3::xy(0.0, 0.0), 1000.0);
1936        let angle = 0.037_f64;
1937        let point = (1000.001 * angle.cos(), 1000.001 * angle.sin());
1938        let d = entity_distance_xy(&circle, &Transform::identity(), point).unwrap_or(f64::INFINITY);
1939        assert!((d - 0.001).abs() < 1e-9);
1940        let arc = Entity::new(EntityKind::Arc {
1941            center: Point3::default(),
1942            radius: 5.0,
1943            start_angle: 0.0,
1944            end_angle: std::f64::consts::FRAC_PI_2,
1945            normal: Vec3::Z,
1946        });
1947        let d =
1948            entity_distance_xy(&arc, &Transform::identity(), (-5.0, 0.0)).unwrap_or(f64::INFINITY);
1949        assert!((d - 50.0_f64.sqrt()).abs() < 1e-9);
1950    }
1951}