5000 Components

This demo introduces a vast dataset of 5000 Sphere elements randomly distributed in 3D space. All of them are spatially indexed into a single 3D R-tree instance in order to test each operation’s time cost under such circumstances.

(1) Initialize a 3D R-tree data structure to populate spheres

(2) Display the generated 3D R-tree in X3DOM canvas (optional - it takes some time since it has to draw about 5000 IndexedLineSet nodes)

Choose any of the following viewpoints to easily navigate and relocate query points and search area

Note  This X3DOM scene is based on a slightly modified version of the minimum conformance requirement of 500 children per grouping node found on X3D archive list, where its 3D content has been multiplied by 10 to reach the desired dataset size. Due to their excessive size (millions of relations) their presentation has been disabled.

POINT QUERY

Place a query point in the scene to search for intersecting objects


X:
N/A

Y:
N/A

Z:
N/A




REGION/WINDOW QUERY

Attach a moveable rectangular parallelepiped area to retrieve overlapping objects


Modify the predefined size of the presented search area

Size X:
Size Y:
Size Z:



k-NN QUERY

Attach a moveable Cone element to retrieve its k-th nearest neighbors


X:
N/A

Y:
N/A

Z:
N/A

Define k-NN sample



SPATIAL RELATIONS

Calculate spatial relations between indexed objects



No. of relations

Coordinates input above after the creation of the R-tree structure were also used in the baseline case study, which involved a set of comparison operations without indexing capabilities. Point query was represented by an intersection criterion aimed to validate the given coordinates against each 3D object's bounding box, while a containment check was applied for region query case. On the other hand, k-NN measurement took place with a sequential recording of the Euclidean distances between the given coordinates and each 3D object, followed by a sorting in an ascending order in order to retrieve the k-closest. Finally, the deduction of spatial relations was made through an exponential search for all possible combinations between scene's 3D objects.

POINT QUERY

X:
N/A

Y:
N/A

Z:
N/A




REGION/WINDOW QUERY

Size X:
Size Y:
Size Z:


k-NN QUERY

X:
N/A

Y:
N/A

Z:
N/A




SPATIAL RELATIONS



No. of relations

Tei of Crete
Multimedia Content Lab Master Thesis by Konstantinos Kontakis