[vworld-tech] Filename based spatial relationship encoding scheme

[Crosbie Fitch]

I recently posted this to 'Game Dev - Algorithms' and just realised it may
be more or also relevant/apposite to this list.

NB I'm looking for the most brutally simple scheme that any Tom, Dick or
Harry could use to hijack a p2p file sharing system for 3D world
creation/distribution. In other words, I'm trying to figure out the
absolutely simplest/cheapest route to implementing a LSVE (albeit static and
non-interactive) hopefully with self-sustaining/snowballing potential.

-----Original Message-----
From: Crosbie Fitch [mailto:crosbie at cyberspaceengineers.org]
Sent: Thursday, 22 January 2004 9:36pm
To: 'gdalgorithms-list at lists.sourceforge.net'
Subject: Filename based spatial relationship encoding scheme


I thought I'd get the ball rolling with regard to figuring out a filename
encoding scheme that one could use to represent a limitless 3D world on a
P2P file sharing system.

Do let me know if this problem has already been solved. ;-)

I'd be grateful if anyone would like to glance over it. I've not thought it
through too hard, but from my own cuff it seems workable. If there are good
reasons why this can't possibly work, I'd like to hear them. If anyone has
any suggestions for improvement or "I'd do it a completely different way,
like this...!" comments they'd be gratefully received too.

NB Please assume that all collaborators participating in this P2P 3D world
are friendly - coping with malicious griefers is a whole other thread. I
just want to focus on the spatial relationship encoding at the mo.

It's another little foray along the lines of my idea that I described here:
www.cyberspaceengineers.org/SolarSystemeSegundo.html

It also touches on some of the queries I mentioned in the recent thread "Re:
[Algorithms] infinite precision spatial database".



Introduction
~~~~~~~~~~~~
A file is presumed to contain static geometry in a local co-ordinate space.

The filename contains no co-ordinates, but by specifying dependencies impies
a relative transform that is used to determine the co-ordinate space of the
file.

The entire collection of files represents a 3D universe. Only a small subset
is required for viewing a portion of the universe at any one time.

A file both represents a region of the universe, and a means of determining
what files are necessary to view it. A file is also a URL of sorts.

Filename Syntax
~~~~~~~~~~~~~~~

<Filename>::=<SOT><Name><ws>[ZZ<OPS><ws>]{<Name(Dependency N)><ws>}.<Type>

E.g. "Paris_ZZ444_Earth_Europe_France_.x"

<SOT> = Start of text

<Name>::= <Alpha>{<Alphanumeric>}
<Alpha>::=[A-Za-z]
<Alpha> = UTF-8 alpha also permitted.
<Alphanumeric>::<Alpha>|<Numeric>
<Numeric>::=[0-9]
<Numeric> = UTF-8 numerics also permitted.

<Name> = Any alphanumeric identifier of at least 1 char not starting with
'ZZ'. Not case sensitive, but case preserving.

<ws>::= '_'
<ws> = White space (may be mapped to single underscore)

<OPS>::= <octal digit><octal digit><octal digit>
<octal digit>::=[0-7]

<Type>::=
<Alphanumeric>|<Alphanumeric><Alphanumeric>|<Alphanumeric><Alphanumeric><Alp
hanumeric>


The meaning of files
~~~~~~~~~~~~~~~~~~~~
Each filename describes a scenery file containing geometry in local
coordinate space, with additional texturing and other supplemental
information as necessary. This may be anything from a simple, single object,
to a complex city.

Files are uniquely identified by their Name and filetype. However, files of
the same name are supposed to describe precisely the same scenery
irrespective of their filetype. All other components of the file name are
supplementary. NB A 'Name' is a universally unique identifier.

A file has the following properties:
	It has an author
	It has a creation/modification date
	It has a bounding sphere (precomputed or not)
		(centre and diameter)
	It may have dependencies
	It is positioned, oriented, and scaled with respect to up to three of its
dependencies (if any)

The meaning of OPS
~~~~~~~~~~~~~~~~~~
Three octal digits whose binary representation indicates whether or not the
nth dependency is involved in determining the orientation, position and/or
scale of the scenery.

Coordinate system: Right-hand-rule: X right, Y away, Z up.

Thus, an octal digit X:
	if 0: indicates that no dependencies are involved (world space)
	if 1,3,5, or 7: indicates the first dependency is involved
	if 2,3,6, or 7: indicates the second dependency is involved
	if 4,5,6, or 7: indicates the third dependency is involved.

O, the first digit (orientation):
0 dependencies = World co-ordinate frame
1 dependency = Same co-ordinate frame
2 dependencies = Align X axis with bounding sphere centres (or same as first
if concentric)
			Align Z with average of dependency Zs
3 dependencies = Align X axis with 1st BS centre to bisect 2nd & 3rd
			If not colinear align Z to normal of plane formed by BS centres, else
align Z with average dependency Z.

NB Orientation calculations to utilise quaternion representation and
spherical linear interpolation.

P, the second digit (position):
0 dependencies = Origin is world origin
>0 dependencies = origin is average of positions of dependency BSs.

S, the third digit (scale):
0 dependencies = Same scale as world
>0 dependencies = scale is 1 unit = Average dependency BS diameter

The absence of OPS is equivalent as follows:
to ZZ000 if no dependencies are provided
to ZZ111 if one dependency is provided
to ZZ333 if two dependencies are provided
to ZZ777 if at least three dependencies are provided.

The meaning of dependencies
~~~~~~~~~~~~~~~~~~~~~~~~~~~
A dependency gives the name of another file that is required for some
reason. It is likely that a file cannot be properly rendered/modelled until
its dependencies have been localised.

A file with no dependencies is presumed to be a anchor object. A viewer is
only expected to consider one anchor based dependency graph at any one time.
Anchor graphs may therefore disregard collisions with other anchor graphs.
It is possible that some anchors may have implicit positions, e.g. mapped to
planets in the solar system.

Circular dependency relationships, especially those that produce non-static
co-ordinate spaces can be detected and handled appropriately (?)

Searching
~~~~~~~~~

1) To search for a file of a particular name
Search for the pattern: <SOT><Name>_*.*  (In other words, file must start
with "Name_")

2) To search for files that are dependent on a particular file
Search for the pattern *_<Name>_*.* (In other words, file must contain
"_Name_", but not start with it)

If it is not possible to specify that a match pattern must commence a
filename, then a prefix will have to be adopted, e.g. XX vis
"XXParis_ZZ444_Earth_Europe_France_.x"

Guarantees
~~~~~~~~~~

A file guarantees that its bounding sphere will not exceed the total BS of
its first three dependencies (centred at any one of them). It's geometry may
be legally clipped in order to meet this guarantee.

Selection
~~~~~~~~~
The preferred version of a particular file is the most recent file of that
Name, that has a type compatible with the viewer's software, and that meets
the viewer's selection criteria (most popular, by particular author, as used
by friends, etc.). Other information may be encoded within the author
descriptor to assure accuracy of the file details.