[aukio-3d.git] /

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

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

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 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>Perspective-correct texturing:</b></p>
 * <p>Textured polygons are rendered with Quake-style perspective-correct scanline
 * mapping ({@code TexturedTriangle}), so no screen-size tessellation is needed.</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.aukio.e3d.renderer.raster.shapes.AbstractShape the base shape class
 */
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.
     * Used e.g. by TextCanvas for distance-based rendering mode selection.
     */
    private final ViewSpaceTracker viewSpaceTracker;

    /**
     * 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>Shapes passing through directly (Line, TexturedTriangle, ...)</li>
     *   <li>Solid polygons with more than 3 vertices - fan-triangulated</li>
     * </ul>
     *
     * <p><b>Caching strategy:</b> 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>
     * </ul>
     *
     * <p>Set to {@code false} after {@link #rebuildRenderList} 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>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.MAX_VALUE;
            double minY = Double.MAX_VALUE;
            double maxY = -Double.MAX_VALUE;
            double minZ = Double.MAX_VALUE;
            double maxZ = -Double.MAX_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 (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;
            }
        }
    }

    /**
     * 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;
    }

    /**
     * Rebuilds the cached render list if shapes were added, removed, or
     * visibility changed since the last rebuild.
     *
     * @param context the rendering context for logging
     */
    private void rebuildRenderListIfNeeded(final RenderingContext context) {
        if (cacheNeedsRebuild)
            rebuildRenderList(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>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 on this composite and all nested composites recursively.
     *
     * <p>Used by {@code ShapeCollection} to trigger a render-list rebuild 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;
        // Propagate to nested composites
        for (final SubShape subShape : subShapesRegistry) {
            final AbstractShape shape = subShape.getShape();
            if (shape instanceof AbstractCompositeShape composite) {
                composite.setCacheNeedsRebuild(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;
            }
        }
    }

    /**
     * Rebuilds the cached render list from the shape registry:
     * textured triangles pass through as-is (perspective-correct scanline
     * rendering needs no tessellation), N-vertex solid polygons are
     * fan-triangulated, everything else passes through.
     * Logs the operation to the debug log buffer if available.
     *
     * @param context the rendering context for logging, may be {@code null}
     */
    private void rebuildRenderList(final RenderingContext context) {
        cacheNeedsRebuild = false;

        final List<AbstractShape> result = new ArrayList<>();
        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) {
                result.add(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++;
            }
        }

        cachedRenderList = postprocessRenderList(result);
        renderListVersion++;
        globalRenderListVersion.incrementAndGet();

        if (context != null && context.debugLogBuffer != null) {
            context.debugLogBuffer.log("rebuildRenderList: " + getClass().getSimpleName()
                    + " texturedPolygons=" + texturedPolygonCount
                    + " solidPolygons=" + solidPolygonCount
                    + " triangulatedPolygons=" + triangulatedPolygonCount
                    + " otherShapes=" + otherShapeCount);
        }
    }

    /**
     * Returns the global render list version: incremented every time ANY
     * composite's render list is rebuilt. Used by derived structures
     * (BSP trees, GI scene snapshots) to detect that they must rebuild.
     *
     * @return monotonically increasing global version
     */
    public static int getGlobalRenderListVersion() {
        return globalRenderListVersion.get();
    }

    /**
     * Collects the triangles of this composite's current render list,
     * recursing into nested composites. These are the exact objects that
     * get transformed and rendered: triangulated render-list polygons, or
     * lightmapped wrappers for
     * {@link eu.svjatoslav.aukio.e3d.renderer.raster.shapes.composite.LightmappedCompositeShape}.
     *
     * <p>Render lists are built lazily during transform; composites that
     * have not been transformed yet (or are frustum-culled) contribute
     * nothing. Vertices are in each composite's local space — callers
     * combining several composites should require identity transforms.</p>
     *
     * @param out list receiving the triangles
     */
    public void collectRenderTriangles(final List<AbstractCoordinateShape> out) {
        if (cachedRenderList == null)
            return;
        for (final AbstractShape shape : cachedRenderList) {
            if (shape instanceof SolidPolygon
                    || shape instanceof eu.svjatoslav.aukio.e3d.renderer.raster.shapes.basic.texturedpolygon.TexturedTriangle)
                out.add((AbstractCoordinateShape) shape);
            else if (shape instanceof AbstractCompositeShape)
                ((AbstractCompositeShape) shape).collectRenderTriangles(out);
        }
    }

    /**
     * Hook: post-processes the freshly rebuilt render list before it becomes
     * the rendering cache. The default implementation returns the list
     * unchanged. Subclasses may replace the list — e.g.
     * {@link eu.svjatoslav.aukio.e3d.renderer.raster.shapes.composite.LightmappedCompositeShape}
     * wraps its polygons into lightmapped triangles here.
     *
     * @param renderList the render list built from the shape registry
     * @return the render list to cache and render
     */
    protected List<AbstractShape> postprocessRenderList(final List<AbstractShape> renderList) {
        return renderList;
    }

    /**
     * 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.incrementAndGet();
            }

            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.incrementAndGet();
                }
                transformPipe.dropTransform();
                return;
            }
        }

        viewSpaceTracker.analyze(transformPipe, context);

        beforeTransformHook(transformPipe, context);

        rebuildRenderListIfNeeded(context);

        // transform rendered subshapes
        if (shouldForkTransform(context)) {
            transformChildrenParallel(transformPipe, aggregator, context);
        } else {
            transformChildrenSerial(transformPipe, aggregator, context);
        }

        transformPipe.dropTransform();
    }

    /**
     * Minimum number of children before the parallel fork is considered at
     * all. A single child cannot be split; splitting happens in the child.
     */
    private static final int PARALLEL_TRANSFORM_MIN_SHAPES = 2;

    /**
     * Minimum total subtree weight (leaf primitives below this composite)
     * before forking its transform into parallel chunks. Below this, the
     * serial walk is cheaper than the fork overhead. Deliberately above
     * one sphere's generated triangle count (~960 at 16 segments):
     * measured 2026-09-04, forking those pays task overhead per chunk for
     * negligible serial work (35k chunk tasks on a 3000-sphere scene were
     * SLOWER than serial).
     */
    private static final int PARALLEL_TRANSFORM_MIN_SUBTREE_WEIGHT = 2048;

    /**
     * Minimum weight per parallel chunk task. Keeps chunk granularity
     * coarse enough that task dispatch overhead stays negligible.
     */
    private static final int PARALLEL_TASK_MIN_WEIGHT = 512;

    /**
     * Cached subtree weight from {@link #getTransformWeight}, valid for
     * {@link #subtreeWeightCycle} only.
     */
    private int cachedSubtreeWeight;

    /**
     * Transform cycle id the cached subtree weight was computed on.
     * Keyed on the globally unique cycle id, not the per-context frame
     * number, so alternating between rendering contexts cannot produce
     * stale cache hits.
     */
    private long subtreeWeightCycle = -1;

    /**
     * Transform cycle id the cached subtree weight was last RECOMPUTED on.
     * Separate from {@link #subtreeWeightCycle} (last read): the refresh
     * gate measures the age of the computation, not of the last access.
     */
    private long subtreeWeightComputeCycle = -1;

    /**
     * {@link #renderListVersion} at the last weight recomputation.
     */
    private int weightListVersion = -1;

    /**
     * Bumped whenever ANY composite rebuilds its render list. Lets the
     * weight shortcut react to structural changes anywhere in the tree
     * within one cycle, at O(1) per node per cycle — scanning direct
     * children's versions instead costs O(leaves) per frame because leaf
     * lists dominate (measured 2026-09-04: +3-4 ms/frame on a 400-sphere
     * scene).
     */
    private static final AtomicInteger globalRenderListVersion = new AtomicInteger();

    /**
     * {@link #globalRenderListVersion} value seen at the last weight
     * recomputation.
     */
    private int weightGlobalVersion = -1;

    /**
     * Bumped every time {@link #cachedRenderList} is rebuilt. Gates weight
     * recomputation: while the list is unchanged, the cached weight is
     * reused without re-walking the subtree.
     */
    private int renderListVersion;

    /**
     * Full subtree weight re-walks are O(total leaves below this node),
     * which costs real milliseconds on big meshes. With an unchanged render
     * list the cached weight is refreshed at most every this many cycles;
     * structural changes (rebuilds) recompute immediately.
     */
    private static final long WEIGHT_REFRESH_CYCLES = 16;

    /**
     * Total transform weight of this composite: the sum of its children's
     * weights, i.e. roughly the number of leaf primitives below it.
     * Computed lazily; recomputed only when this node's render list was
     * rebuilt or the cache is older than {@link #WEIGHT_REFRESH_CYCLES}
     * cycles (children's internal rebuilds are picked up by the periodic
     * refresh). Used solely for parallel fork load balancing, never for
     * correctness, so brief staleness is harmless.
     *
     * <p>Thread safety: a composite's fork decision runs on exactly one
     * thread per cycle. Chunk-thread reads are cycle-stamped cache hits
     * published through the executor's happens-before edge.</p>
     *
     * @param renderingContext the rendering context (cycle identity)
     * @return subtree transform weight, at least 1
     */
    @Override
    public int getTransformWeight(final RenderingContext renderingContext) {
        final long cycle = renderingContext.transformCycleId;
        if (subtreeWeightCycle == cycle) {
            return cachedSubtreeWeight;
        }
        final int globalVersion = globalRenderListVersion.get();
        if (weightListVersion == renderListVersion
                && weightGlobalVersion == globalVersion
                && cycle - subtreeWeightComputeCycle < WEIGHT_REFRESH_CYCLES) {
            // Nothing rebuilt anywhere and computation fresh: keep the
            // value, just re-stamp the read. O(1) per node per cycle.
            subtreeWeightCycle = cycle;
            return cachedSubtreeWeight;
        }
        int weight = 0;
        for (final AbstractShape child : cachedRenderList) {
            weight += child.getTransformWeight(renderingContext);
        }
        cachedSubtreeWeight = Math.max(1, weight);
        subtreeWeightCycle = cycle;
        subtreeWeightComputeCycle = cycle;
        weightListVersion = renderListVersion;
        weightGlobalVersion = globalVersion;
        return cachedSubtreeWeight;
    }

    /**
     * Decides whether this composite forks its children's transform into
     * parallel chunks: enough children to split, and enough TOTAL weight
     * below it to amortize the fork overhead. Weight (not local child
     * count) is what matters: a deep narrow tree with two heavy children
     * forks just like a flat mesh with thousands of leaves.
     *
     * @param context the rendering context (provides the coordinator)
     * @return true when the parallel fork should be taken
     */
    private boolean shouldForkTransform(final RenderingContext context) {
        if (context.transformCoordinator == null) {
            return false;
        }
        if (cachedRenderList.size() < PARALLEL_TRANSFORM_MIN_SHAPES) {
            return false;
        }
        return getTransformWeight(context) >= PARALLEL_TRANSFORM_MIN_SUBTREE_WEIGHT;
    }

    /**
     * Target number of task chunks per available processor core.
     * More tasks than cores gives the pool load balancing across
     * shapes with uneven transform cost.
     */
    private static final int PARALLEL_TASKS_PER_CORE = 4;

    /**
     * Transforms all children serially on the calling thread.
     *
     * @param transformPipe the transform stack (includes this composite's transform)
     * @param aggregator    the aggregator to queue visible shapes into
     * @param context       the rendering context
     */
    private void transformChildrenSerial(final TransformStack transformPipe,
                                         final RenderAggregator aggregator,
                                         final RenderingContext context) {
        for (final AbstractShape shape : cachedRenderList) {
            shape.transform(transformPipe, aggregator, context);
        }
    }

    /**
     * Forks the children's transform into parallel chunk tasks on the
     * frame's {@link ParallelTransformCoordinator} and returns immediately
     * WITHOUT waiting for them.
     *
     * <p>Works at any nesting level: a heavy composite reached inside a
     * chunk task forks its own children into the same coordinator. This is
     * deadlock-safe because chunk tasks never block on other tasks; only
     * the orchestrating render thread waits (in the coordinator's drain).</p>
     *
     * <p>Stack snapshotting: this composite's transform is dropped from
     * {@code transformPipe} right after this method returns, long before
     * the chunk tasks run, so the pipe is copied HERE on the forking
     * thread. Each task then copies the snapshot for its own working stack.
     * The snapshot is never mutated after publication, so concurrent
     * copying by chunk tasks is safe.</p>
     *
     * <p>Thread-safety notes: sibling composites are exclusively owned by
     * one chunk, so their per-instance caches (render list, bounding
     * boxes, own transform's cached matrix) never race. The vertex
     * frameNumber cache is a benign race: every thread writes the same
     * value.</p>
     *
     * @param transformPipe the transform stack (includes this composite's transform)
     * @param aggregator    unused in the parallel path: per-task aggregators
     *                      are merged by the coordinator's drain
     * @param context       the rendering context (provides the coordinator)
     */
    private void transformChildrenParallel(final TransformStack transformPipe,
                                           final RenderAggregator aggregator,
                                           final RenderingContext context) {
        // Snapshot the render list reference. With the pipelined render
        // loop, the NEXT pass's tree walk can already be running while
        // this pass's chunk tasks are still queued (the drain happens in
        // the async continuation, not before the next walk). That walk
        // may rebuild this composite's render list, REASSIGNING
        // cachedRenderList to a new list of a different size. The chunk
        // ranges below are computed against this list instance, so the
        // chunk tasks must index this same instance — re-reading the
        // field inside the lambda raced with the rebuild and threw
        // IndexOutOfBoundsException. (The old list stays alive and valid
        // for this pass; each pass transforms into its own vertex slot.)
        final List<AbstractShape> renderList = cachedRenderList;
        final int size = renderList.size();
        final int totalWeight = getTransformWeight(context);
        final int processors = Runtime.getRuntime().availableProcessors();
        final int targetTasks = processors * PARALLEL_TASKS_PER_CORE;
        final int taskWeight = Math.max(PARALLEL_TASK_MIN_WEIGHT,
                (totalWeight + targetTasks - 1) / targetTasks);

        // Pass 1: count chunks, cutting by ACCUMULATED WEIGHT so that a
        // node with few but heavy children (e.g. two 25k-triangle halves
        // of a fractal) still splits into multiple tasks
        int taskCount = 0;
        int accumulated = 0;
        for (int i = 0; i < size; i++) {
            accumulated += renderList.get(i).getTransformWeight(context);
            if (accumulated >= taskWeight) {
                taskCount++;
                accumulated = 0;
            }
        }
        if (accumulated > 0) {
            taskCount++;
        }

        if (taskCount < 2) {
            transformChildrenSerial(transformPipe, aggregator, context);
            return;
        }

        final ParallelTransformCoordinator coordinator = context.transformCoordinator;
        if (!coordinator.tryReserveTasks(taskCount)) {
            // Frame-wide task budget exhausted: transform inline
            transformChildrenSerial(transformPipe, aggregator, context);
            return;
        }

        final TransformStack snapshot = new TransformStack(transformPipe);

        // Pass 2: submit chunks (weights are frame-cached, cheap re-walk)
        int from = 0;
        accumulated = 0;
        for (int i = 0; i < size; i++) {
            accumulated += renderList.get(i).getTransformWeight(context);
            if (accumulated >= taskWeight || i == size - 1) {
                final int chunkFrom = from;
                final int chunkTo = i + 1;
                coordinator.submit(() -> {
                    // Pooled scratch: the stack (9.6 KB of arrays) and
                    // the chunk aggregator (queue keeps its capacity
                    // across frames) come from the coordinator's static
                    // pools — previously each chunk allocated both on
                    // every frame.
                    final TransformStack taskStack =
                            coordinator.borrowStack(snapshot);
                    try {
                        final RenderAggregator taskAggregator =
                                coordinator.borrowAggregator();
                        for (int c = chunkFrom; c < chunkTo; c++) {
                            renderList.get(c).transform(taskStack, taskAggregator, context);
                        }
                        return taskAggregator;
                    } finally {
                        coordinator.returnStack(taskStack);
                    }
                });
                from = i + 1;
                accumulated = 0;
            }
        }
    }

    /**
     * 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;
    }

}