500 Components

This demo exposes an X3DOM scene of 500 Sphere elements which are spatially indexed under the same 3D R-tree instance. Each operation of the implemented data structure scales quite well compared to the number of 3D objects, even in the case of spatial relations where their number comes in hundreds of thousands.

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

(2) Display the generated 3D R-tree in X3DOM canvas (optional - only 1 option available per browser instance)








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.

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