[sixth-3d.git] /

/*
 * Sixth 3D engine. Author: Svjatoslav Agejenko.
 * This project is released under Creative Commons Zero (CC0) license.
 */
package eu.svjatoslav.sixth.e3d.renderer.raster.shapes.composite.base;

import eu.svjatoslav.sixth.e3d.geometry.Box;
import eu.svjatoslav.sixth.e3d.geometry.BspTree;
import eu.svjatoslav.sixth.e3d.geometry.Frustum;
import eu.svjatoslav.sixth.e3d.geometry.Point3D;
import eu.svjatoslav.sixth.e3d.gui.RenderingContext;
import eu.svjatoslav.sixth.e3d.gui.ViewSpaceTracker;
import eu.svjatoslav.sixth.e3d.gui.humaninput.MouseInteractionController;
import eu.svjatoslav.sixth.e3d.math.Transform;
import eu.svjatoslav.sixth.e3d.math.TransformStack;
import eu.svjatoslav.sixth.e3d.math.Vertex;
import eu.svjatoslav.sixth.e3d.renderer.raster.Color;
import eu.svjatoslav.sixth.e3d.renderer.raster.RenderAggregator;
import eu.svjatoslav.sixth.e3d.renderer.raster.shapes.AbstractShape;
import eu.svjatoslav.sixth.e3d.renderer.raster.shapes.basic.line.Line;
import eu.svjatoslav.sixth.e3d.renderer.raster.shapes.basic.solidpolygon.SolidPolygon;
import eu.svjatoslav.sixth.e3d.renderer.raster.shapes.basic.texturedpolygon.TexturedTriangle;
import eu.svjatoslav.sixth.e3d.renderer.raster.tessellation.TexturedPolygonTessellator;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * A composite shape that groups multiple sub-shapes into a single logical unit.
 *
 * <p>Use {@code AbstractCompositeShape} to build complex 3D objects by combining
 * primitive shapes (lines, polygons, textured polygons) into a group that can be
 * positioned, rotated, and manipulated as one entity. Sub-shapes can be organized
 * into named groups for selective visibility toggling.</p>
 *
 * <p><b>Usage example - creating a custom composite shape:</b></p>
 * <pre>{@code
 * // Create a composite shape at position (0, 0, 200)
 * AbstractCompositeShape myObject = new AbstractCompositeShape(
 *     new Point3D(0, 0, 200)
 * );
 *
 * // Add sub-shapes
 * myObject.addShape(new Line(
 *     new Point3D(-50, 0, 0), new Point3D(50, 0, 0),
 *     Color.RED, 2.0
 * ));
 *
 * // Add shapes to a named group for toggling visibility
 * myObject.addShape(labelShape, "labels");
 * myObject.hideGroup("labels");  // hide all shapes in "labels" group
 * myObject.showGroup("labels");  // show them again
 *
 * // Add to scene
 * viewPanel.getRootShapeCollection().addShape(myObject);
 * }</pre>
 *
 * <p><b>Level-of-detail tessellation:</b></p>
 * <p>Textured polygons within the composite shape are automatically tessellated into smaller
 * triangles based on distance from the viewer. This provides perspective-correct texture
 * mapping without requiring hardware support. The tessellation factor adapts dynamically.</p>
 *
 * <p><b>Extending this class:</b></p>
 * <p>Override {@link #beforeTransformHook} to customize shape appearance or behavior
 * on each frame (e.g., animations, dynamic geometry updates).</p>
 *
 * @see SubShape wrapper for individual sub-shapes with group and visibility support
 * @see eu.svjatoslav.sixth.e3d.renderer.raster.shapes.AbstractShape the base shape class
 * @see eu.svjatoslav.sixth.e3d.renderer.raster.tessellation.TexturedPolygonTessellator the level-of-detail polygon tessellator
 */
public class AbstractCompositeShape extends AbstractShape {
    /**
     * Source-of-truth registry of all sub-shapes added to this composite.
     *
     * <p>Each sub-shape is wrapped with its group identifier and visibility state.
     * Shapes are stored in insertion order and remain in this collection even when
     * hidden (visibility state toggles instead of removal).</p>
     *
     * <p><b>Performance note:</b> This list is NOT processed for every frame.
     * Instead, it serves as the authoritative source from which {@link #cachedRenderList}
     * is compiled whenever the cache becomes invalid (see {@link #cacheNeedsRebuild}).
     * Only modifications to this registry (add/remove/show/hide) trigger cache rebuild.</p>
     *
     * @see #cachedRenderList the frame-optimized cache derived from this registry
     * @see #cacheNeedsRebuild the flag controlling when the cache is rebuilt
     */
    private final List<SubShape> subShapesRegistry = new ArrayList<>();

    /**
     * Tracks the distance and angle between the camera and this shape to compute
     * an appropriate tessellation factor for level-of-detail adjustments.
     */
    private final ViewSpaceTracker viewSpaceTracker;

    /**
     * The current tessellation factor used for tessellating textured polygons into smaller
     * triangles for perspective-correct rendering. Higher values produce more triangles
     * for distant objects; lower values for nearby objects. Updated dynamically based
     * on view-space analysis.
     * <p>
     * TODO: move this to TexturedTriangle. LOD must be computed per textured triangle, not per-shape.
     */
    double currentTessellationFactor = 5;

    /**
     * Frame-optimized cache of shapes ready for rendering, derived from {@link #subShapesRegistry}.
     *
     * <p>This list is processed during every frame in the {@link #transform} method.
     * It contains:</p>
     * <ul>
     *   <li>Non-textured shapes (Line, SolidPolygon) - passed through directly</li>
     *   <li>Textured polygons - tessellated into smaller triangles based on current LOD factor</li>
     * </ul>
     *
     * <p><b>Caching strategy:</b> Regenerating this list involves texture tessellation which
     * is expensive. The list is rebuilt only when {@link #cacheNeedsRebuild} is true,
     * avoiding per-frame reconstruction overhead.</p>
     *
     * @see #subShapesRegistry the source registry this cache is derived from
     * @see #cacheNeedsRebuild the flag that triggers cache regeneration
     */
    private List<AbstractShape> cachedRenderList = new ArrayList<>();

    /**
     * Flag indicating whether {@link #cachedRenderList} needs to be rebuilt from {@link #subShapesRegistry}.
     *
     * <p>Set to {@code true} when:</p>
     * <ul>
     *   <li>A shape is added via {@link #addShape}</li>
     *   <li>A shape is removed via {@link #removeGroup}</li>
     *   <li>Group visibility changes via {@link #showGroup} or {@link #hideGroup}</li>
     *   <li>The tessellation factor changes significantly (determined by {@link #isRetessellationNeeded})</li>
     * </ul>
     *
     * <p>Set to {@code false} after {@link #retessellate} completes the cache rebuild.</p>
     *
     * <p>This flag enables the performance optimization of avoiding per-frame list
     * reconstruction - the registry is only re-processed when something actually changed.</p>
     *
     * @see #subShapesRegistry the source data that may need reprocessing
     * @see #cachedRenderList the cache that gets rebuilt when this flag is true
     */
    private boolean cacheNeedsRebuild = true;

    /**
     * Flag indicating this composite is the root scene container (ShapeCollection's root).
     *
     * <p>Root composites have different behavior for LOD-based tessellation:</p>
     * <ul>
     *   <li>Root position equals camera position, so distance to camera is always 0</li>
     *   <li>ViewSpaceTracker cannot compute meaningful tessellation factor for root</li>
     *   <li>Root uses fixed {@link #currentTessellationFactor} and skips LOD-based retessellation checks</li>
     *   <li>Root still performs N-gon triangulation when {@link #cacheNeedsRebuild} is true</li>
     * </ul>
     *
     * <p>Set via {@link #setRootComposite(boolean)} by ShapeCollection.</p>
     */
    private boolean isRootComposite = false;

    /**
     * The position and orientation transform for this composite shape.
     * Applied to all sub-shapes during the rendering transform pass.
     */
    private Transform transform;

    /**
     * Creates a composite shape at the world origin with no rotation.
     */
    public AbstractCompositeShape() {
        this(new Transform());
    }

    /**
     * Creates a composite shape at the specified location with no rotation.
     *
     * @param location the position in world space
     */
    public AbstractCompositeShape(final Point3D location) {
        this(new Transform(location));
    }

    /**
     * Creates a composite shape with the specified transform (position and orientation).
     *
     * @param transform the initial transform defining position and rotation
     */
    public AbstractCompositeShape(final Transform transform) {
        this.transform = transform;
        viewSpaceTracker = new ViewSpaceTracker();
    }

    /**
     * Adds a sub-shape to this composite shape without a group identifier.
     *
     * @param shape the shape to add
     */
    public void addShape(final AbstractShape shape) {
        addShape(shape, null);
    }

    /**
     * Adds a sub-shape to this composite shape with an optional group identifier.
     *
     * <p>Grouped shapes can be shown, hidden, or removed together using
     * {@link #showGroup}, {@link #hideGroup}, and {@link #removeGroup}.</p>
     *
     * @param shape   the shape to add
     * @param groupId the group identifier, or {@code null} for ungrouped shapes
     */
    public void addShape(final AbstractShape shape, final String groupId) {
        subShapesRegistry.add(new SubShape(shape, groupId, true));
        cacheNeedsRebuild = true;
    }

    /**
     * This method should be overridden by anyone wanting to customize the shape
     * before it is rendered.
     *
     * @param transformPipe the current transform stack
     * @param context       the rendering context for the current frame
     */
    public void beforeTransformHook(final TransformStack transformPipe,
                                    final RenderingContext context) {
    }

    /**
     * Returns the world-space position of this composite shape.
     *
     * @return the translation component of this shape's transform
     */
    public Point3D getLocation() {
        return transform.getTranslation();
    }

    /**
     * Returns the axis-aligned bounding box encompassing all sub-shapes.
     *
     * <p>The bounding box is computed by aggregating the bounds of all visible
     * sub-shapes, then transforming the result by this composite's own transform.</p>
     *
     * <p><b>Caching:</b> The bounding box is recomputed whenever
     * {@link #cacheNeedsRebuild} is true (shapes added/removed/visibility changed).
     * For nested composites, the bounds include their local transform offset.</p>
     *
     * @return the axis-aligned bounding box in this composite's local coordinates
     */
    @Override
    public Box getBoundingBox() {
        if (cachedBoundingBox == null || cacheNeedsRebuild) {
            if (subShapesRegistry.isEmpty()) {
                return super.getBoundingBox();
            }

            double minX = Double.MAX_VALUE;
            double maxX = Double.MIN_VALUE;
            double minY = Double.MAX_VALUE;
            double maxY = Double.MIN_VALUE;
            double minZ = Double.MAX_VALUE;
            double maxZ = Double.MIN_VALUE;

            for (final SubShape subShape : subShapesRegistry) {
                if (!subShape.isVisible()) {
                    continue;
                }

                final AbstractShape shape = subShape.getShape();
                final Box shapeBounds = shape.getBoundingBox();

                // Get bounds and apply sub-shape's transform if it's a composite
                Point3D shapeMin = new Point3D(shapeBounds.getMinX(), shapeBounds.getMinY(), shapeBounds.getMinZ());
                Point3D shapeMax = new Point3D(shapeBounds.getMaxX(), shapeBounds.getMaxY(), shapeBounds.getMaxZ());

                // If sub-shape is a composite, apply its transform to the bounds
                if (shape instanceof AbstractCompositeShape) {
                    final Transform subTransform = ((AbstractCompositeShape) shape).getTransform();
                    final Point3D subTranslation = subTransform.getTranslation();
                    shapeMin.add(subTranslation);
                    shapeMax.add(subTranslation);
                }

                minX = Math.min(minX, shapeMin.x);
                maxX = Math.max(maxX, shapeMax.x);
                minY = Math.min(minY, shapeMin.y);
                maxY = Math.max(maxY, shapeMax.y);
                minZ = Math.min(minZ, shapeMin.z);
                maxZ = Math.max(maxZ, shapeMax.z);
            }

            if (minX == Double.MAX_VALUE) {
                // No visible shapes
                return super.getBoundingBox();
            }

            cachedBoundingBox = new Box(
                    new Point3D(minX, minY, minZ),
                    new Point3D(maxX, maxY, maxZ)
            );
        }
        return cachedBoundingBox;
    }

    /**
     * Returns the sub-shapes registry (source of truth for all sub-shapes).
     *
     * <p>This is the authoritative list of all sub-shapes including hidden ones.
     * For per-frame rendering, use {@link #cachedRenderList} instead (accessed internally).</p>
     *
     * @return the registry list of all sub-shapes with their group and visibility metadata
     * @see #cachedRenderList the frame-optimized cache derived from this registry
     */
    public List<SubShape> getSubShapesRegistry() {
        return subShapesRegistry;
    }

    /**
     * Extracts all SolidPolygon instances from this composite shape.
     *
     * <p>Recursively traverses the shape hierarchy and collects all
     * SolidPolygon instances. Used for CSG operations where polygons
     * are needed directly without conversion.</p>
     *
     * @return list of SolidPolygon instances from this shape hierarchy
     */
    public List<SolidPolygon> extractSolidPolygons() {
        final List<SolidPolygon> result = new ArrayList<>();
        for (final SubShape subShape : subShapesRegistry) {
            final AbstractShape shape = subShape.getShape();
            if (shape instanceof SolidPolygon) {
                result.add((SolidPolygon) shape);
            } else if (shape instanceof AbstractCompositeShape) {
                result.addAll(((AbstractCompositeShape) shape).extractSolidPolygons());
            }
        }
        return result;
    }

    /**
     * Returns the view-space tracker that monitors the distance
     * and angle between the camera and this shape for level-of-detail adjustments.
     *
     * @return the view-space tracker for this shape
     */
    public ViewSpaceTracker getViewSpaceTracker() {
        return viewSpaceTracker;
    }

    /**
     * Hides all sub-shapes belonging to the specified group.
     * Hidden shapes are not rendered but remain in the collection.
     *
     * @param groupIdentifier the group to hide
     * @see #showGroup(String)
     * @see #removeGroup(String)
     */
    public void hideGroup(final String groupIdentifier) {
        for (final SubShape subShape : subShapesRegistry) {
            if (subShape.matchesGroup(groupIdentifier)) {
                subShape.setVisible(false);
                cacheNeedsRebuild = true;
            }
        }
    }

    /**
     * Determines whether textured polygons need to be re-tessellated based on tessellation factor change.
     * <p>
     * Re-tessellation is needed if the tessellation state is marked outdated, or if the ratio between
     * the larger and smaller tessellation factor exceeds 1.5x. This threshold prevents frequent
     * re-tessellation for minor view changes while ensuring significant LOD changes trigger updates.
     *
     * @param proposedNewTessellationFactor the tessellation factor computed from current view distance
     * @param currentTessellationFactor     the tessellation factor currently in use
     * @return {@code true} if re-tessellation should be performed
     */
    private boolean isRetessellationNeeded(final double proposedNewTessellationFactor, final double currentTessellationFactor) {

        if (cacheNeedsRebuild)
            return true;

        // retessellate if there is significant difference between proposed and current tessellation factor
        final double larger = Math.max(proposedNewTessellationFactor, currentTessellationFactor);
        final double smaller = Math.min(proposedNewTessellationFactor, currentTessellationFactor);

        return (larger / smaller) > 1.5d;
    }

    /**
     * Permanently removes all sub-shapes belonging to the specified group.
     *
     * @param groupIdentifier the group to remove
     * @see #hideGroup(String)
     */
    public void removeGroup(final String groupIdentifier) {
        final java.util.Iterator<SubShape> iterator = subShapesRegistry
                .iterator();

        while (iterator.hasNext()) {
            final SubShape subShape = iterator.next();
            if (subShape.matchesGroup(groupIdentifier)) {
                iterator.remove();
                cacheNeedsRebuild = true;
            }
        }
    }

    /**
     * Returns all sub-shapes belonging to the specified group.
     *
     * @param groupIdentifier the group identifier to match
     * @return list of matching sub-shapes
     */
    public List<SubShape> getGroup(final String groupIdentifier) {
        final List<SubShape> result = new ArrayList<>();
        for (int i = 0; i < subShapesRegistry.size(); i++) {
            final SubShape subShape = subShapesRegistry.get(i);
            if (subShape.matchesGroup(groupIdentifier))
                result.add(subShape);
        }
        return result;
    }

    /**
     * Checks if re-slicing is needed and performs it if so.
     *
     * <p>For root composites, skips LOD-based checks since distance to camera is 0.
     * Only retessellates when {@link #cacheNeedsRebuild} is true (shapes added/removed/visibility changed).</p>
     *
     * <p>For normal composites, checks both cache validity and LOD-based tessellation factor changes.</p>
     *
     * @param context the rendering context for logging
     */
    private void retessellateIfNeeded(final RenderingContext context) {

        if (isRootComposite) {
            if (cacheNeedsRebuild)
                retessellate(context);
            return;
        }

        final double proposedTessellationFactor = viewSpaceTracker.proposeTessellationFactor();

        if (isRetessellationNeeded(proposedTessellationFactor, currentTessellationFactor)) {
            currentTessellationFactor = proposedTessellationFactor;
            retessellate(context);
        }
    }

    /**
     * Paint solid elements of this composite shape into given color.
     *
     * <p>Applies recursively to nested {@code AbstractCompositeShape} sub-shapes.</p>
     *
     * @param color the color to apply to all solid sub-shapes
     */
    public void setColor(final Color color) {
        for (final SubShape subShape : getSubShapesRegistry()) {
            final AbstractShape shape = subShape.getShape();

            if (shape instanceof SolidPolygon) {
                ((SolidPolygon) shape).setColor(color);
            } else if (shape instanceof Line) {
                ((Line) shape).color = color;
            } else if (shape instanceof AbstractCompositeShape) {
                ((AbstractCompositeShape) shape).setColor(color);
            }
        }
    }

    /**
     * Assigns a group identifier to all sub-shapes that currently have no group.
     *
     * @param groupIdentifier the group to assign to ungrouped shapes
     */
    public void setGroupForUngrouped(final String groupIdentifier) {
        for (final SubShape subShape : subShapesRegistry)
            if (subShape.isUngrouped())
                subShape.setGroup(groupIdentifier);
    }

    @Override
    public void setMouseInteractionController(
            final MouseInteractionController mouseInteractionController) {
        super.setMouseInteractionController(mouseInteractionController);

        for (final SubShape subShape : subShapesRegistry)
            subShape.getShape().setMouseInteractionController(
                    mouseInteractionController);

        cacheNeedsRebuild = true;
    }

    /**
     * Marks this composite as the root scene container.
     *
     * <p>Root composites skip LOD-based tessellation factor checks since their position
     * equals the camera position (distance = 0). They use a fixed tessellation factor
     * and only retessellate when shapes are added, removed, or visibility changes.</p>
     *
     * <p>Called by {@code ShapeCollection} to configure its root composite.</p>
     *
     * @param isRoot {@code true} if this is the root composite, {@code false} otherwise
     */
    public void setRootComposite(final boolean isRoot) {
        this.isRootComposite = isRoot;
    }

    /**
     * Returns this composite's transform (position and orientation).
     *
     * @return the transform object
     */
    public Transform getTransform() {
        return transform;
    }

    /**
     * Sets the transform for this composite shape.
     *
     * @param transform the new transform
     * @return this composite shape (for chaining)
     */
    public AbstractCompositeShape setTransform(final Transform transform) {
        this.transform = transform;
        return this;
    }

    /**
     * Sets the cache rebuild flag, forcing {@link #cachedRenderList} to be regenerated.
     *
     * <p>Used by {@code ShapeCollection} to trigger retessellate when clearing the scene
     * or for other advanced use cases.</p>
     *
     * @param needsRebuild {@code true} to force cache rebuild on next frame
     */
    public void setCacheNeedsRebuild(final boolean needsRebuild) {
        this.cacheNeedsRebuild = needsRebuild;
    }

    /**
     * Enables or disables shading for all SolidTriangle and SolidPolygon sub-shapes.
     * When enabled, shapes use the global lighting manager from the rendering
     * context to calculate flat shading based on light sources.
     *
     * <p>Applies recursively to nested {@code AbstractCompositeShape} sub-shapes.</p>
     *
     * @param shadingEnabled {@code true} to enable shading, {@code false} to disable
     * @return this composite shape (for chaining)
     */
    public AbstractCompositeShape setShadingEnabled(final boolean shadingEnabled) {
        for (final SubShape subShape : getSubShapesRegistry()) {
            final AbstractShape shape = subShape.getShape();
            if (shape instanceof SolidPolygon) {
                ((SolidPolygon) shape).setShadingEnabled(shadingEnabled);
            } else if (shape instanceof AbstractCompositeShape) {
                ((AbstractCompositeShape) shape).setShadingEnabled(shadingEnabled);
            }
        }
        return this;
    }

    /**
     * Enables or disables backface culling for all SolidPolygon and TexturedTriangle sub-shapes.
     *
     * <p>Applies recursively to nested {@code AbstractCompositeShape} sub-shapes.</p>
     *
     * @param backfaceCulling {@code true} to enable backface culling, {@code false} to disable
     * @return this composite shape (for chaining)
     */
    public AbstractCompositeShape setBackfaceCulling(final boolean backfaceCulling) {
        for (final SubShape subShape : getSubShapesRegistry()) {
            final AbstractShape shape = subShape.getShape();
            if (shape instanceof SolidPolygon) {
                ((SolidPolygon) shape).setBackfaceCulling(backfaceCulling);
            } else if (shape instanceof TexturedTriangle) {
                ((TexturedTriangle) shape).setBackfaceCulling(backfaceCulling);
            } else if (shape instanceof AbstractCompositeShape) {
                ((AbstractCompositeShape) shape).setBackfaceCulling(backfaceCulling);
            }
        }
        return this;
    }

    /**
     * Performs an in-place union with another composite shape.
     *
     * <p>This shape's SolidPolygon children are replaced with the union result.
     * Non-SolidPolygon children from both shapes are preserved and combined.</p>
     *
     * <p><b>CSG Operation:</b> Union combines two shapes into one, keeping all
     * geometry from both. Uses BSP tree algorithms for robust boolean operations.</p>
     *
     * <p><b>Child handling:</b></p>
     * <ul>
     *   <li>SolidPolygon children from both shapes → replaced with union result</li>
     *   <li>Non-SolidPolygon children from this shape → preserved</li>
     *   <li>Non-SolidPolygon children from other shape → added to this shape</li>
     *   <li>Nested AbstractCompositeShape children → preserved unchanged (not recursively processed)</li>
     * </ul>
     *
     * @param other the shape to union with
     * @see #subtract(AbstractCompositeShape)
     * @see #intersect(AbstractCompositeShape)
     */
    public void union(final AbstractCompositeShape other) {

        final BspTree selfTree = new BspTree(clonePolygons(extractSolidPolygons()));
        final BspTree otherTree = new BspTree(clonePolygons(other.extractSolidPolygons()));

        // Remove from self any polygons that are inside other (interior faces)
        selfTree.clipTo(otherTree);

        // Remove from other any polygons that are inside self (interior faces)
        otherTree.clipTo(selfTree);

        // Invert other to convert remaining polygons for the next clip step
        otherTree.invert();

        // Clip inverted other against self to remove back-facing coplanar polygons
        otherTree.clipTo(selfTree);

        // Invert back to restore correct polygon orientation
        otherTree.invert();

        // Merge other's remaining polygons into self's BSP tree
        selfTree.addPolygons(otherTree.allPolygons());

        replaceSolidPolygons(selfTree.allPolygons());
        mergeNonPolygonChildrenFrom(other);
    }

    /**
     * Performs an in-place subtraction with another composite shape.
     *
     * <p>This shape's SolidPolygon children are replaced with the difference result.
     * The other shape acts as a "cutter" that carves out volume from this shape.</p>
     *
     * <p><b>CSG Operation:</b> Subtract removes the volume of the second shape
     * from the first shape. Useful for creating holes, cavities, and cutouts.</p>
     *
     * <p><b>Child handling:</b></p>
     * <ul>
     *   <li>SolidPolygon children from this shape → replaced with difference result</li>
     *   <li>Non-SolidPolygon children from this shape → preserved</li>
     *   <li>All children from other shape → discarded (other is just a cutter)</li>
     *   <li>Nested AbstractCompositeShape children → preserved unchanged</li>
     * </ul>
     *
     * @param other the shape to subtract (the cutter)
     * @see #union(AbstractCompositeShape)
     * @see #intersect(AbstractCompositeShape)
     */
    public void subtract(final AbstractCompositeShape other) {

        final BspTree target = new BspTree(clonePolygons(extractSolidPolygons()));
        final BspTree cutter = new BspTree(clonePolygons(other.extractSolidPolygons()));

        // Invert target: convert "inside" to "outside" and vice versa
        // This transforms the problem from "subtract B from A" to "intersect A's complement with B's complement"
        target.invert();

        // Clip target against cutter: removes parts of target that are INSIDE the cutter
        // Since target is inverted, this removes parts that were OUTSIDE the original target
        target.clipTo(cutter);

        // Clip cutter against (inverted) target: removes parts of cutter outside the inverted target
        // This keeps only cutter polygons that are inside the inverted target = outside original target
        cutter.clipTo(target);

        // Invert cutter to flip its inside/outside
        cutter.invert();

        // Clip inverted cutter against target: removes coplanar back-faces
        cutter.clipTo(target);

        // Invert cutter back to correct orientation
        cutter.invert();

        // Merge cutter's polygons into target's BSP tree
        target.addPolygons(cutter.allPolygons());

        // Invert target back to restore correct inside/outside orientation
        // Result: the carved-out volume (target minus cutter)
        target.invert();

        replaceSolidPolygons(target.allPolygons());
    }

    /**
     * Performs an in-place intersection with another composite shape.
     *
     * <p>This shape's SolidPolygon children are replaced with the intersection result.
     * Only the overlapping volume between the two shapes remains.</p>
     *
     * <p><b>CSG Operation:</b> Intersect keeps only the volume where both shapes
     * overlap. Useful for creating shapes constrained by multiple boundaries.</p>
     *
     * <p><b>Child handling:</b></p>
     * <ul>
     *   <li>SolidPolygon children from this shape → replaced with intersection result</li>
     *   <li>Non-SolidPolygon children from this shape → preserved</li>
     *   <li>All children from other shape → discarded</li>
     *   <li>Nested AbstractCompositeShape children → preserved unchanged</li>
     * </ul>
     *
     * @param other the shape to intersect with
     * @see #union(AbstractCompositeShape)
     * @see #subtract(AbstractCompositeShape)
     */
    public void intersect(final AbstractCompositeShape other) {

        final BspTree selfTree = new BspTree(clonePolygons(extractSolidPolygons()));
        final BspTree otherTree = new BspTree(clonePolygons(other.extractSolidPolygons()));

        // Invert self to convert "inside" to "outside"
        // This transforms intersection into: keep parts that are "outside both inverted shapes"
        selfTree.invert();

        // Clip other against inverted self: keeps only parts of other that are INSIDE original self
        // (because clipTo removes what's "outside" the BSP, and inverted self's "outside" = original self's "inside")
        otherTree.clipTo(selfTree);

        // Invert other (which now represents the intersection region)
        otherTree.invert();

        // Clip inverted self against (inverted intersection): removes parts outside the intersection
        selfTree.clipTo(otherTree);

        // Clip intersection result against inverted self: removes back-facing coplanar polygons
        otherTree.clipTo(selfTree);

        // Build final BSP tree from the clipped intersection polygons
        selfTree.addPolygons(otherTree.allPolygons());

        // Invert back to restore correct inside/outside orientation
        selfTree.invert();

        replaceSolidPolygons(selfTree.allPolygons());
    }

    /**
     * Creates deep clones of all polygons in the list.
     *
     * <p>CSG operations modify polygons in-place via BSP tree operations.
     * Cloning ensures the original polygon data is preserved.</p>
     *
     * @param polygons the polygons to clone
     * @return a new list containing deep clones of all polygons
     */
    private List<SolidPolygon> clonePolygons(final List<SolidPolygon> polygons) {
        final List<SolidPolygon> cloned = new ArrayList<>(polygons.size());
        for (final SolidPolygon p : polygons) {
            cloned.add(p.deepClone());
        }
        return cloned;
    }

    /**
     * Replaces this shape's SolidPolygon children with new polygons.
     *
     * <p>Preserves all non-SolidPolygon children (Lines, nested composites, etc.).</p>
     *
     * @param newPolygons the polygons to replace with
     */
    private void replaceSolidPolygons(final List<SolidPolygon> newPolygons) {
        // Remove all direct SolidPolygon children from this shape
        final Iterator<SubShape> iterator = subShapesRegistry.iterator();
        while (iterator.hasNext()) {
            final SubShape subShape = iterator.next();
            if (subShape.getShape() instanceof SolidPolygon) {
                iterator.remove();
            }
        }

        // Add all result polygons as new children
        for (final SolidPolygon polygon : newPolygons) {
            addShape(polygon);
        }

        cacheNeedsRebuild = true;
    }

    /**
     * Merges non-SolidPolygon children from another shape into this shape.
     *
     * <p>Copies all non-SolidPolygon children (Lines, nested composites, etc.)
     * from the other shape, preserving their group identifiers.</p>
     *
     * @param other the shape to merge non-polygon children from
     */
    private void mergeNonPolygonChildrenFrom(final AbstractCompositeShape other) {
        if (other == null) {
            return;
        }

        for (final SubShape otherSubShape : other.subShapesRegistry) {
            final AbstractShape otherShape = otherSubShape.getShape();
            if (!(otherShape instanceof SolidPolygon)) {
                addShape(otherShape, otherSubShape.getGroupIdentifier());
            }
        }

        cacheNeedsRebuild = true;
    }

    /**
     * Makes all sub-shapes belonging to the specified group visible.
     *
     * @param groupIdentifier the group to show
     * @see #hideGroup(String)
     */
    public void showGroup(final String groupIdentifier) {
        for (int i = 0; i < subShapesRegistry.size(); i++) {
            final SubShape subShape = subShapesRegistry.get(i);
            if (subShape.matchesGroup(groupIdentifier)) {
                subShape.setVisible(true);
                cacheNeedsRebuild = true;
            }
        }
    }

    /**
     * Retessellates all textured polygons, triangulates N-vertex solid polygons,
     * and rebuilds the cached render list.
     * Logs the operation to the debug log buffer if available.
     *
     * @param context the rendering context for logging, may be {@code null}
     */
    private void retessellate(final RenderingContext context) {
        cacheNeedsRebuild = false;

        final List<AbstractShape> result = new ArrayList<>();

        final TexturedPolygonTessellator tessellator = new TexturedPolygonTessellator(currentTessellationFactor);
        int texturedPolygonCount = 0;
        int solidPolygonCount = 0;
        int triangulatedPolygonCount = 0;
        int otherShapeCount = 0;

        for (int i = 0; i < subShapesRegistry.size(); i++) {
            final SubShape subShape = subShapesRegistry.get(i);
            if (!subShape.isVisible())
                continue;

            final AbstractShape shape = subShape.getShape();

            if (shape instanceof TexturedTriangle) {
                tessellator.tessellate((TexturedTriangle) shape);
                texturedPolygonCount++;
            } else if (shape instanceof SolidPolygon polygon) {
                final int vertexCount = polygon.getVertexCount();

                if (vertexCount == 3) {
                    result.add(polygon);
                    solidPolygonCount++;
                } else {
                    triangulateSolidPolygon(polygon, result);
                    triangulatedPolygonCount++;
                }
            } else {
                result.add(shape);
                otherShapeCount++;
            }
        }

        result.addAll(tessellator.getResult());

        cachedRenderList = result;

        if (context != null && context.debugLogBuffer != null) {
            context.debugLogBuffer.log("retessellate: " + getClass().getSimpleName()
                    + " tessellationFactor=" + String.format("%.2f", currentTessellationFactor)
                    + " texturedPolygons=" + texturedPolygonCount
                    + " solidPolygons=" + solidPolygonCount
                    + " triangulatedPolygons=" + triangulatedPolygonCount
                    + " otherShapes=" + otherShapeCount
                    + " resultingTexturedPolygons=" + tessellator.getResult().size());
        }
    }

    /**
     * Triangulates a convex solid polygon using fan triangulation.
     *
     * <p>Fan triangulation creates N-2 triangles from an N-vertex polygon by using
     * vertex 0 as the anchor and connecting it to each adjacent pair of vertices.</p>
     *
     * <p>Properties (color, shading, backface culling, mouse interaction) are
     * propagated to each resulting triangle to ensure consistent behavior.</p>
     *
     * @param polygon the polygon to triangulate (must have at least 4 vertices)
     * @param result  the list to add the resulting triangles to
     */
    private void triangulateSolidPolygon(final SolidPolygon polygon,
                                         final List<AbstractShape> result) {

        final Color color = polygon.getColor();
        final boolean shadingEnabled = polygon.isShadingEnabled();
        final boolean backfaceCulling = polygon.isBackfaceCullingEnabled();
        final MouseInteractionController mouseController = polygon.mouseInteractionController;

        final List<Vertex> vertices = polygon.vertices;
        final Vertex v0 = vertices.get(0);

        for (int i = 1; i < vertices.size() - 1; i++) {
            final Vertex v1 = vertices.get(i);
            final Vertex v2 = vertices.get(i + 1);

            final SolidPolygon triangle = new SolidPolygon(
                    v0.coordinate, v1.coordinate, v2.coordinate, color);

            triangle.setShadingEnabled(shadingEnabled);
            triangle.setBackfaceCulling(backfaceCulling);
            triangle.setMouseInteractionController(mouseController);

            result.add(triangle);
        }
    }

    @Override
    public void transform(final TransformStack transformPipe,
                          final RenderAggregator aggregator, final RenderingContext context) {

        // Add the current composite shape transform to the end of the transform
        // pipeline.
        transformPipe.addTransform(transform);

        // FRUSTUM CULLING: Check if this composite's bounds are visible
        // Root composite skips this check (its bounds are always the full scene)
        // Non-root composites check their aggregated bounds against the frustum
        if (context.frustum != null && !isRootComposite) {
            // Count this composite for culling statistics (before frustum test)
            if (context.cullingStatistics != null) {
                context.cullingStatistics.totalComposites++;
            }

            final Box localBounds = getBoundingBox();

            // Transform all 8 corners of the bounding box to view space
            final double minX = localBounds.getMinX();
            final double maxX = localBounds.getMaxX();
            final double minY = localBounds.getMinY();
            final double maxY = localBounds.getMaxY();
            final double minZ = localBounds.getMinZ();
            final double maxZ = localBounds.getMaxZ();

            final double[] xs = {minX, maxX};
            final double[] ys = {minY, maxY};
            final double[] zs = {minZ, maxZ};

            double viewMinX = Double.MAX_VALUE;
            double viewMaxX = -Double.MAX_VALUE;
            double viewMinY = Double.MAX_VALUE;
            double viewMaxY = -Double.MAX_VALUE;
            double viewMinZ = Double.MAX_VALUE;
            double viewMaxZ = -Double.MAX_VALUE;

            for (int i = 0; i < 8; i++) {
                final double x = xs[(i & 1)];
                final double y = ys[(i >> 1) & 1];
                final double z = zs[(i >> 2) & 1];

                final Point3D corner = transformPointToViewSpace(x, y, z, transformPipe);

                viewMinX = Math.min(viewMinX, corner.x);
                viewMaxX = Math.max(viewMaxX, corner.x);
                viewMinY = Math.min(viewMinY, corner.y);
                viewMaxY = Math.max(viewMaxY, corner.y);
                viewMinZ = Math.min(viewMinZ, corner.z);
                viewMaxZ = Math.max(viewMaxZ, corner.z);
            }

            final Box viewSpaceBounds = new Box(
                    new Point3D(viewMinX, viewMinY, viewMinZ),
                    new Point3D(viewMaxX, viewMaxY, viewMaxZ)
            );

            final Frustum frustum = context.frustum;
            final boolean visible = frustum.intersectsAABB(viewSpaceBounds);

            if (!visible) {
                // Entire composite outside frustum - skip processing all children
                if (context.cullingStatistics != null) {
                    context.cullingStatistics.culledComposites++;
                }
                transformPipe.dropTransform();
                return;
            }
        }

        viewSpaceTracker.analyze(transformPipe, context);

        beforeTransformHook(transformPipe, context);

        retessellateIfNeeded(context);

        // transform rendered subshapes
        for (final AbstractShape shape : cachedRenderList)
            shape.transform(transformPipe, aggregator, context);

        transformPipe.dropTransform();
    }

    /**
     * Transforms a point to view space using the current transform stack.
     * Helper method for frustum culling that transforms bounding box corners.
     *
     * @param x             the X coordinate in local space
     * @param y             the Y coordinate in local space
     * @param z             the Z coordinate in local space
     * @param transformPipe the current transform stack
     * @return the transformed point in view space
     */
    private Point3D transformPointToViewSpace(final double x, final double y, final double z,
                                              final TransformStack transformPipe) {
        final Point3D input = new Point3D(x, y, z);
        final Point3D result = new Point3D();
        transformPipe.transform(input, result);
        return result;
    }

}