Subdividing 3D-datasets for hierarchical level-of-detail use

1 . A computer implemented method for subdividing 3D datasets in hierarchical level-of-detail for rendering, the method comprising:

obtaining a 3D dataset from a storage;

determining a bounding volume for the 3D dataset;

setting a first budget for 3D data in each node of a hierarchical tree;

generating a plurality of levels-of-detail and 3D data for said levels-of-detail from the 3D dataset until a version of the 3D dataset fits to the budget, including determining said version of the 3D dataset as the lowest level-of-detail data and determining the other levels-of-detail and 3D data of the plurality of levels-of-detail as higher levels-of-detail data;

arranging the hierarchical tree, comprising a plurality of nodes, each node associated with at least one other node of the plurality of nodes;

filling a root node with the version of the 3D dataset, that fit to the budget;

filling a node for second level-of-detail with the second level-of-detail data;

iteratively performing per node starting from the node for second level-of-detail:

determining a primitive count for the node;

in response to the primitive count being below the first budget, storing primitive data of the node, and if more levels-of-detail remain, filling all the next level-of-detail nodes of the current node with the next level-of-detail data;

in response to the primitive count being above the first budget, splitting the node to a first and a second leaf node by splitting the volume of the node along the longest side of the node by a splitting plane; and

determining per primitive of the first and the second leaf node if the primitive is crossing the splitting plane:

in response to a primitive of the first and the second leaf node crossing the splitting plane, defining splitting plane vertices at crossings points at the splitting plane and splitting the crossing primitive to add new primitives on both sides of the splitting plane using said splitting plane vertices, storing each new added primitive to one of the first and the second leaf nodes;

in response to the primitive not crossing the splitting plane, storing the primitive to one of the first and the second leaf nodes;

rendering, by a processor, a 3D view using the hierarchical level of detail data.

2 . The method according to claim 1 , wherein said splitting of the node is done in response to at least one of a unique vertex count being above a second budget and the primitive count being above the first budget.

3 . The method according to claim 1 , further comprising in response to the primitive count being below the budget, normalizing the primitives of the node with respect to a center point of the node.

4 . The method according to claim 3 , further comprising determining a bounding box for each node of a highest accuracy and normalizing the primitives of said node with respect to a center point of said node.

5 . An apparatus comprising at least one processor, and at least one memory including computer program code; the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus at least to perform: subdividing 3D datasets in hierarchical level-of-detail for rendering, including at least:

obtaining a 3D dataset from a storage;

determining a bounding volume for the 3D dataset;

setting a first budget for 3D data in each node of a hierarchical tree;

generating a plurality of levels-of-detail and 3D data for said levels-of-detail from the 3D dataset until a version of the 3D dataset fits to the budget, including determining said version of the 3D dataset as the lowest level-of-detail data and determining the other levels-of-detail and 3D data of the plurality of levels-of-detail as higher levels-of-detail data;

arranging the hierarchical tree, comprising a plurality of nodes, each node associated with at least one other node of the plurality of nodes;

filling a root node with the version of the 3D dataset, that fit to the budget;

filling a node for second level-of-detail with the second level-of-detail data;

iteratively performing per node starting from the node for second level-of-detail:

determining a primitive count for the node;

in response to the primitive count being below the first budget, storing primitive data of the node, and if more levels-of-detail remain, filling all the next level-of-detail nodes of the current node with the next level-of-detail data;

in response to the primitive count being above the first budget, splitting the node to a first and a second leaf node by splitting the volume of the node along the longest side of the node by a splitting plane; and

determining per primitive of the first and the second leaf node if the primitive is crossing the splitting plane:

in response to a primitive of the first and the second leaf node crossing the splitting plane, defining splitting plane vertices at crossings points at the splitting plane and splitting the crossing primitive to add new primitives on both sides of the splitting plane using said splitting plane vertices, storing each new added primitive to one of the first and the second leaf nodes;

in response to the primitive not crossing the splitting plane, storing the primitive to one of the first and the second leaf nodes;

rendering a 3D view using the hierarchical level of detail data.

6 . The apparatus according to claim 5 , wherein said splitting of the node is done in response to at least one of a unique vertex count being above a second budget and the primitive count being above the first budget.

7 . The apparatus according to claim 5 , wherein the processor is further configured to, in response to the primitive count being below the budget, normalize the primitives of the node with respect to a center point of the node.

8 . The apparatus according to claim 7 , wherein the processor is further configured to determine a bounding box for each node of a highest accuracy and normalize the primitives of said node with respect to a center point of said node.

9 . A non-transitory computer readable storage medium comprising instructions stored thereon that, when executed, subdivide 3D datasets in hierarchical level-of-detail for rendering, by performing operations comprising:

obtaining a 3D dataset from a storage;

determining a bounding volume for the 3D dataset;

setting a first budget for 3D data in each node of a hierarchical tree;

generating a plurality of levels-of-detail and 3D data for said levels-of-detail from the 3D dataset until a version of the 3D dataset fits to the budget, including determining said version of the 3D dataset as the lowest level-of-detail data and determining the other levels-of-detail and 3D data of the plurality of levels-of-detail as higher levels-of-detail data;

arranging the hierarchical tree, comprising a plurality of nodes, each node associated with at least one other node of the plurality of nodes;

filling a root node with the version of the 3D dataset, that fit to the budget;

filling a node for second level-of-detail with the second level-of-detail data;

iteratively performing per node starting from the node for second level-of-detail:

determining a primitive count for the node;

in response to the primitive count being below the first budget, storing primitive data of the node, and if more levels-of-detail remain, filling all the next level-of-detail nodes of the current node with the next level-of-detail data;

in response to the primitive count being above the first budget, splitting the node to a first and a second leaf node by splitting the volume of the node along the longest side of the node by a splitting plane; and

determining per primitive of the first and the second leaf node if the primitive is crossing the splitting plane:

in response to a primitive of the first and the second leaf node crossing the splitting plane, defining splitting plane vertices at crossings points at the splitting plane and splitting the crossing primitive to add new primitives on both sides of the splitting plane using said splitting plane vertices, storing each new added primitive to one of the first and the second leaf nodes;

in response to the primitive not crossing the splitting plane, storing the primitive to one of the first and the second leaf nodes;

rendering a 3D view using the hierarchical level of detail data.

10 . The non-transitory computer readable storage medium according to claim 9 , wherein said splitting of the node is done in response to at least one of a unique vertex count being above a second budget and the primitive count being above the first budget.

11 . The non-transitory computer readable storage medium according to claim 9 , wherein in response to the primitive count being below the budget, the primitives of the node are normalized with respect to a center point of the node.

12 . The non-transitory computer readable storage medium according to claim 11 , wherein a bounding box is determined for each node of a highest accuracy and the primitives of said node are normalized with respect to a center point of said node.