3D Geometry Support in knn2 and SpatialIndex, and Best SRID for Minecraft Worlds

[Elijah Massey]

Hello,

I am working on a Minecraft mod to keep track of POIs in the world and announce them as the player approaches, and to aid the player in navigation by pathfinding and in other ways, and I have decided to use SpatiaLite because I anticipate there being hundreds of thousands of points and other geometries that I want to store and filter, if not more. I am starting by announcing the points of interest nearest to the player, and I thought that I would use knn2 since it seemed perfect for this. However, knn2 ignores the Z coordinate of all points I give it, and returns any geometries that are within the radius on the X and Y coordinates. I considered using SpatialIndex instead, and it does the same thing (except without sorting by distance) if I give it a circle made with makeCircle(x, y) or ST_Buffer(makePointZ(x,y,z)). There is no makeSphere function, and I am not sure whether SpatialIndex supports 3D at all. Are knn2 and SpatialIndex only 2D? In that case, I could probably use one of them in an inner subquery to get approximate results, and then use something like ST_3DDistance to filter and sort by the actual distance in a much smaller set of data points.

Also, is an SRID of -1 the best for a Minecraft worlds? The world is flat and 384 blocks thick, and it extends -29,999,984 blocks in both horizontal directions from (0,0). I am using Z as Minecraft's Y axis, since Y is vertical in Minecraft. If not, which SRID should I use or should I create a new one?

[ckgoo...@gmail.com]

Hi, could you use the WHERE clause with something like:

SQRT( X*X + Y*Y + Z*Z ) < MAX_DISTANCE?

Best, Chris

--
You received this message because you are subscribed to the Google Groups "SpatiaLite Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to spatialite-use...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/spatialite-users/fc4a7216-bba6-4cc1-bd54-39277581d27an%40googlegroups.com.

[a.fu...@lqt.it]

On Fri, 10 Jan 2025 19:16:27 -0800 (PST), Elijah Massey wrote:
> I am not sure whether SpatialIndex supports 3D at all. Are knn2 and
> SpatialIndex only 2D?
>

Hi Elijah,

Let's start by clarifying some basic notions.
SpatiaLite, just like PostGis and any other Spatial DBMS is designed
specifically for geographical applications.

The underlying spatial model is never true 3D, it's instead what many
define as 2.5D
That is, it's not exactly a flat surface (a true Euclidean plane),
it's rather a wavy and corrugated surface that follows the natural
relief of hills and mountains.
Z coordinates are simply used to represent sea level elevations,
they are never intended to describe solid objects in as in true 3D

The overall logic of the relationships between geometries always
remains purely 2D and is merely based on X and Y while Z is
systematically ignored.

I'm not at all sure that SpatiaLite can satisfactorily adapt
to the very specific needs of Minecraft; at first glance I
would say no.

> In that case, I could probably use one of them
> in an inner subquery to get approximate results, and then use
> something like ST_3DDistance to filter and sort by the actual
> distance
> in a much smaller set of data points.
>

In my opinion you can do better; SQLite's R*Tree, the real Spatial
Index engine, supports up to 5 dimensions.
Please read here for more details:

https://www.sqlite.org/rtree.html

If I understand correctly, you are simply interested in managing
3D POIs and 3D objects that can be simplified as cubes or
parallelepipeds or perhaps as spheres.

You shouldn't encounter too many difficulties in defining their
binary geometric representations in a BLOB, perhaps taking some
inspiration from what SpatiaLite does to adapt it to your needs.
Please see here:

https://www.gaia-gis.it/gaia-sins/BLOB-Geometry.html

At this point you would be able to directly exploit a SQLite
3D R*Tree for quickly pre-filtering objects in a small box.

For a more refined evaluation you simply need to define your
own function calculating 3D distances, which in the case of
simple points, parallelepipeds or spheres is particularly
simple and not at all complex.
Conclusions: building a small 3D geometry engine tailor-made
for Minecraft seems reasonably simple and shouldn't require
excessive development time.

You should also be able to solve the KNN problem without too
much effort, because ultimately it's just a matter of iteratively
executing direct queries on the 3D Spatial Index, gradually
enlarging the size of the search box until you find a sufficient
number of nearest candidates to be sorted by distance.

> Also, is an SRID of -1 the best for a Minecraft worlds? The world is
> flat and 384 blocks thick, and it extends -29,999,984 blocks in both
> horizontal directions from (0,0). I am using Z as Minecraft's Y axis,
> since Y is vertical in Minecraft. If not, which SRID should I use or
> should I create a new one?
>

Don't waste time with SRIDs, which are a concept that only makes
sense in the world of planets and other celestial bodies that have
a surface that is an ellipsoid.
It seems to me that the Minecraft reference model is something
completely different (and fortunately much simpler).

my 2 cents,
Sandro

[Elijah Massey]

That makes sense, and thank you for your detailed response. I did not realize how completely spatial DBMS's are designed around modeling the Earth's surface. The R*Tree should work well for getting POIs within a 3D bounding box, and for KNN. I was thinking some POIs would be more complex than parallelepipeds (large trees for example) but those should be easy to calculate bounding boxes for.

I would like to do path finding as well, for example giving the player directions to a distant or hard to find POI. Since JTS and Geos and other similar libraries are 2.5D, maybe I could use CDAL instead, and generate a surface mesh from the shape of the world? I could save all blocks into the database as 1x1x1 cubes, and then simplify each chunk (16x16x384) into one or more polyhedrons, and then simplify larger groups (perhaps 256 chunks, 16x16), and then simplify the entire world. When a block is broken or placed, I could update the block, then the chunk, then the chunk group, and then the world, so I never process millions of shapes at the same time. That would let me generate a surface mesh with one of CDAL's algorithms, and then use that or a graph made from that for path finding. However, I would have to either make the graph myself or change the geometry somehow to account for Minecraft rules, for example you can go under water but not for too long, but you can't walk across lava, and you can jump up a limited height, and things like that. I could manually traverse the world block by block, finding outer surfaces or openings at least 2 high, and using Minecraft rules to decide whether to create a link in the graph or not. Then I could automatically generate a graph for each chunk using this hand-written algorithm, and then when doing path finding, combine these graphs into larger ones until I find a path to the POI. This sounds like it may still be time-consuming to run though. What approach do people usually use to generate pathfinding graphs from spatial data representing terrain?
Sent from my iPad

> On Jan 11, 2025, at 04:12, a.fu...@lqt.it wrote:

> --
> You received this message because you are subscribed to a topic in the Google Groups "SpatiaLite Users" group.
> To unsubscribe from this topic, visit https://groups.google.com/d/topic/spatialite-users/69O9ghWYtRg/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to spatialite-use...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/spatialite-users/f0fe5c2fe0f54d3ff0ee30f22974a15f%40lqt.it.

[Elijah Massey]

Sorry, I meant to say CGAL, not CDAL.
Sent from my iPad

> On Jan 11, 2025, at 21:05, Elijah Massey <emass...@gmail.com> wrote:
>
> That makes sense, and thank you for your detailed response. I did not realize how completely spatial DBMS's are designed around modeling the Earth's surface. The R*Tree should work well for getting POIs within a 3D bounding box, and for KNN. I was thinking some POIs would be more complex than parallelepipeds (large trees for example) but those should be easy to calculate bounding boxes for.

[a.fu...@lqt.it]

Hi List,

I'm happy to announce a new open source initiative that may be of
interest to some of you.

The two most popular and widespread open source SpatialDBMS are
PostgreSQL+PostGIS and SQLite+Spatialite.
For many users it's highly desirable to be able to exchange data (not
only of the ordinary type bu
also Geometries) between the two DBMSes directly via pure SQL.

VirtualPG has been available since several years, a dynamic extension
to SQLite supponrting this kind of operation.
Please see:

https://www.gaia-gis.it/fossil/virtualpg/home


Today it becomes possible to exchange data even starting from the other
side thanks to PgSpider, a Foreign Data Wrapper for PostgreSQL
Please see:

https://github.com/pgspider/sqlite_fdw

GIS specific documentation is here:
https://github.com/pgspider/sqlite_fdw/blob/master/GIS.md


Conclusion: exchanging data (even Geometries) between PostGIS and
SpatiaLite and vice versa has never been as easy as today, whatever your
favorite open source Spatial DBMS you are most familiar with.

bye Sandro