Package cz.fidentis.analyst.data.kdtree.impl

Class TriangleKdTreeImpl

java.lang.Object
cz.fidentis.analyst.data.kdtree.impl.TriangleKdTreeImpl
All Implemented Interfaces:
KdTree, TriangleKdTree, Serializable
public class TriangleKdTreeImpl extends Object implements TriangleKdTree
!!!EXPERIMENTAL!!! Class for building a kd-tree for storing MeshTriangles. Triangles are only stored in leafs. Triangles which intersect splitting plane are stored in both children. Terminating condition for leafs is the maximum number of triangles stored in them (default 128).

leafSize determines the size of work-group if using GPU for vertex-to-triangle NN search. If not using GPU, disregard this message. DEPENDS ON HARDWARE! Usually must be a multiple of 32. The higher the number, the better the performance (But probably better to use bruteforce at that point). On RTX 4060 TI - max 128 tested, on Intel UHD 620 - max 256 tested.

See Also:

  • Constructor Details

    • TriangleKdTreeImpl

      public TriangleKdTreeImpl(List<MeshTriangle> triangles)
      Constructor.
      Parameters:
      triangles - List of MeshTriangle from which the tree is built.

    • TriangleKdTreeImpl

      public TriangleKdTreeImpl(Collection<MeshFacet> facets)
      Constructor. Extracts triangles from all MeshFacets and builds tree from them.
      Parameters:
      facets - Collection of MeshFacet

  • Method Details

    • getRoot

      public TriangleKdNode getRoot()
      Description copied from interface: KdTree
      Tree traversal - go to the "root" of the tree.
      Specified by:
      getRoot in interface KdTree
      Returns:
      root node of the tree

    • addNode

      public void addNode(MeshPoint meshPoint)
      Description copied from interface: KdTree
      Method for adding independent point to existing tree. The balance of the tree is not guaranteed after adding elements, it depends on the distribution of the added points. It can create long linear branches. In Poisson disk sub-sampling, where this method is used, it isn't a problem.
      Specified by:
      addNode in interface KdTree
      Parameters:
      meshPoint - point to add

    • getNumNodes

      public int getNumNodes()
      Description copied from interface: KdTree
      Return number of nodes in the k-d tree.
      Specified by:
      getNumNodes in interface KdTree
      Returns:
      number of nodes in the k-d tree

    • getDepth

      public int getDepth()
      Description copied from interface: KdTree
      Return the length of the longest path.
      Specified by:
      getDepth in interface KdTree
      Returns:
      Return the length of the longest path.

    • accept

      public void accept(KdTreeVisitor visitor)
      Description copied from interface: KdTree
      Visits this tree.
      Specified by:
      accept in interface KdTree
      Parameters:
      visitor - Visitor

    • getLeafSize

      public int getLeafSize()
      Description copied from interface: TriangleKdTree
      Getter for maximum leaf size. Used for the size of work-group on GPU.
      Specified by:
      getLeafSize in interface TriangleKdTree
      Returns:
      Maximum leaf size.

    • getClosestLeaf

      public TriangleKdNode getClosestLeaf(javax.vecmath.Point3d point)
      Traverses tree from root to the leaf closest to point.
      Specified by:
      getClosestLeaf in interface TriangleKdTree
      Parameters:
      point - Point to which to find the closest leaf.
      Returns:
      Leaf node closest to point

    • getLeafFromNode

      public TriangleKdNode getLeafFromNode(javax.vecmath.Point3d point, TriangleKdNode rootNode)
      Traverses tree from specified node to the leaf closest to point.
      Specified by:
      getLeafFromNode in interface TriangleKdTree
      Parameters:
      point - Point to which to find the closest leaf.
      rootNode - Node from which to start traversal.
      Returns:
      Leaf node closest to point