Introducing GitExplorer (Stargit)

Multi repository source code project navigation with status overview and version control. To the left we visualize a dash board of repositories and sub-repositories, as seen stored  locally on disk. To the right we can focus on a particular repository which offers a 3D visualisation of the commit history and standard git functionality.

Multi repository source code project navigation with status overview and version control. To the left we visualize a dash board of repositories and sub-repositories, as seen stored  locally on disk. To the right we can focus on a particular repository which offers a 3D visualisation of the commit history and standard git functionality.

The GitExplorer software is used to manage large volumes of source code modules, game developments and animation productions. At GameFusion all source code, productions and client deliveries are securly monitored, controlled and stored in 'git' repositories. A big issue is the massive proliferation and management of large repositories. The size of individual repositories varies from a few kilobytes to tens of gigabytes, structured loosely on disk in a hierarchy of repositories and sub-repositories. A sub-repository tree approach is used in favor of referenced git sub-modules for greater flexibility.

The Git Explorer is a multi-platform native C++ application available on Windows, Linux and MacOS. The user interface is based on Qt, git functionality is powered by the open source libgit2, security uses openSSL and the project uses the GameFusion-3D-GameEngine for asset pre-visualisation.

The software is used internally at GameFusion for all developments and client projects. We are considering offering a release candidate preview in the near future. Selected features have been integrated into the 3D LevelEditor for a transparent cloud collaboration experience (WIP).

Other desktop version control software we like and have considered are GitHub and GitKraken. The problem we have found is that these are not adapted to our workflow or fail to perform on a big data hierarchical/approach. Finally, embedding GitExplorer functionality in the form of a library in our 3D software offers an integrated collaborative experience akin to what you can find in Microsoft Visual Studio, Unity and the UnrealEngine Editor.

Posted
AuthorAndreas Carlen

Introducing the GameFusion 3D LevelEditor

Introducing the LevelEditor developed in house and currently used in game production on PARASITE. One of the key features offered by this software is the ability to integrate advanced animated scenes from Maya into Unity. Notably, artists can update content and assets in Maya and then use the editor to update the Unity scene animation, geometry, materials and textures. Effectively, this offers a Maya to Unity pipeline where Maya content is imported and updated by reference. The standard Unity fbx import lacks some important features like non-bone animation import for such things as simple UI animation. In addition, materials do not always translate and textures are often lost. Finally, Unity and Maya use a different coordinate system for 3D space. The present LevelEditor has proven to be a valuable asset and internal tool to resolve these issues.

Introducing the LevelEditor developed in house and currently used in game production on PARASITE. One of the key features offered by this software is the ability to integrate advanced animated scenes from Maya into Unity. Notably, artists can update content and assets in Maya and then use the editor to update the Unity scene animation, geometry, materials and textures. Effectively, this offers a Maya to Unity pipeline where Maya content is imported and updated by reference.

The standard Unity fbx import lacks some important features like non-bone animation import for such things as simple UI animation. In addition, materials do not always translate and textures are often lost. Finally, Unity and Maya use a different coordinate system for 3D space. The present LevelEditor has proven to be a valuable asset and internal tool to resolve these issues.

Posted
AuthorAndreas Carlen

Old-school way

It's not hard to find the distance of a point p (represented as a position vector p) from the origin : simply compute norm(p).

Neither is it hard to find the distance of a plane P (represented in [N : -d] form) from the origin: it's simply d.

However, according to the information at this link, the process of finding the distance of a line represented homogeneously (in Plücker coordinates) from the origin is more involved.

For a line represented as {U : V}, (with U the line's 3-d direction vector and V the line's 3-d moment vector), its squared distance from the origin is

V , V⟩ / ⟨U , U

so the distance of a Plücker line to the origin is the square root of that.

 

  • These techniques offer no consistent methodology for determining the minimum distance of a geometric entity to the origin. We have one way of dealing with points, another way of dealing with planes, and yet another way of dealing with lines.

 

New-school way

Fortunately, GA provides a consistent framework for finding the (squared) distance of a k-flat X to the origin. Define

dX, O2 = || supp(X) || 2 , where supp(X) ∈ R N returns the support vector of X .

Recall that

  • eN + 1-1e N + 1 ≡ [0 : 1] , i.e., the origin of PN + 1

  • dir(X) = (e N + 1-1X) , giving the direction of k-flat X .

Define

  • moment(X) as eN + 1 -1 ⌋ (e N + 1X) , giving the moment of k-flat X .

  • supp(X) is defined as moment(X) / dir(X), with / denoting geometric division if dir(X) is not scalar.

Compare this with the method given further above for the finding squared distance of Plücker line to origin.

 

Summary:

  • the squared distance of a k-flat to the origin is equal to the square of its support vector.

 

 

Posted
AuthorJason Wood
 

Recall that ∼ denotes the geometric dual, and ⌋ denotes the left contraction product (LCP).

Write the intersection of blades A and B as A ∨ B , which is equivalent to ∼A ⌋ B .

 
  • The intersection of 2-d lines L1 and L2 = ∼L1 ⌋ L2 , which is a 2-d point.

  • The intersection of 3-d line L and plane P = ∼L ⌋ P , which is a 3-d point.

  • The intersection of planes P1 and P2 = ∼P1 ⌋ P2 , which is a 3-d line.

This looks nice and regular, but if we apply it to a pair of 3-d lines, the formula gives us a grade-0 blade, which is a scalar! This is because in 3-d projective GA, lines and dual lines are both bivectors (grade-2).

This scalar is not without meaning, however: it corresponds to the distance between the lines.

So if the lines are skew (i.e., don't intersect), then the distance will be non-zero. If the distance is zero, then the lines intersect in a common plane, which reduces the problem to finding the intersection of lines in two dimensions. More on this later...

Posted
AuthorJason Wood

From the discussion about point-plane distance queries, we saw that pπpΠ = 0 when points and planes coincide.

Does the same apply to point-line distance queries as well?

Let's find out with a simple example:

Let L = | (1, 2, 3, 1) ∧ (4, 5, 6, 1) | =

(1 / √3) ( -e12 - 2e13 - e 23 - e14 - e24 - e34 ) be a normalized line in P3 .

Let p = (7e1 + 8e2 + 9e3 + e4 ) be a normalized point in P3 .

It's not hard to visualize that the point p = (7, 8, 9, 1) lies on the line passing through points (1, 2, 3, 1) and (4, 5, 6, 1) .

Does the math work?

Compute pL =

(1 / √3) (7e1 + 8e2 + 9e3 + e4 ) ( -e12 - 2e13 - e23 - e14 - e24 - e34 ) =

(1 / √3)( -7e123 - 7e124 - 7e134 - 16e213 - 8e214 - 8e234 - 9e312 - 9e314 - 9e324 -e412 - 2e413 - e423) .

Now is a good time to re-arrange (i.e., 'swap') basis blade indices so that they're ordered in 'canonical form'.

Negate the coefficient of basis elements whose indices require an odd number of swaps:

e213 ≡ -e123 so that -16e213 becomes +16e123 .

e214 ≡ -e124 so that -8e214 becomes +8e124 .

e314 ≡ -e134 so that -9e314 becomes +9e134 .

e324 ≡ -e234 so that -9e324 becomes +9e234 .

For an even number of swaps, just write the indices in order.

 

Now the equation reads:

(1 / √3)

( -7e123 - 7e124 - 7e134 + 16e123 + 8e124 - 8e234 - 9e123 + 9e134 + 9e234 - e124 - 2e134 - e234)

Grouping terms:

(1 / √3)( (-7 + 16 - 9)e123 + (-7 + 8 - 1)e124 + (-7 + 9 - 2)e134 + (-8 + 9 - 1)e234 )

Simplifying, we end up with:

pL = (1 / √3)( 0e123 + 0e124 + 0e134 + 0e234 )

which is the zero trivector (i.e., a degenerate plane formed by wedging together three collinear points), so the point does indeed lie on the line!

 

I'd also like to mention that while writing the calculations out by hand appears tedious (and it is), an efficient computer implementation of the above only performs 12 floating-point muls and 8 floating-point adds.

The ordering of basis blade indices, handling which coefficients go where, etc. can be performed at compile-time with template meta-programming techniques in the C++ or D programming languages.

Storage requirements are fairly undemanding: for 3-d k-flats, we need

  • 4 floats to store a point,
  • 4 floats for a plane, and
  • 6 floats for a line.

This is pretty much matches the storage requirements for these same entities within a standard 3-d engine setting. Note, however, that a line doesn't directly store any information about the points used to construct it (it's not a line segment).

 

Posted
AuthorJason Wood

It is assumed that the reader is familiar with 3-d computer graphics math-related topics as well as having some knowledge of Geometric Algebra.

1 Intro

In standard 3-d engines, little distinction is made between points and vectors. For example, a 3-d vector a = (1, 2, 3) is treated either as a position vector or as a direction, depending on the context.

Homogeneous coordinates attempts to rectify that by appending an extra coordinate (or 'dimension', if you prefer) to vectors. In other words, if we're working in N-d, we add an extra dimension to the base space, and call this new space projective N-d.

Thus, the 3-d point version of a looks like a = (1, 2, 3, w ≠ 0) where w is the extra coordinate.

(Note that I use bold to indicate vectors, and italics for scalars and other non-vector quantities.)

What happens if w does equal 0? Then we have an improper point (also called a point at infinity), which is indistinguishable from a vector in the base space.

Why does this matter? Well, the typical way of converting a point back to its base space- representation (i.e., a vector) is to divide all of the point's components by w (which is then dropped). If w is equal to 0, this causes a divide-by-zero error.

Now, when using APIs like OpenGL or DirectX, the extra coordinate allows the use of 4x4 transformation matrices to perform not only scaling and rotation, but translation as well. Other parts of the 3-d pipeline also use homogeneous coordinates (clipping, perspective transformations, etc.).

1.1 Using homogeneous coordinates without being entirely aware of it

Homogeneous coordinates are also used implicitly when 3-d programmers manipulate planes in [n;-d] form, where n is the plane's 3-d normal vector, and d is the plane's distance from the origin.

Creating a plane X from three position vectors {a, b, c}, involves the following:

Let n = ((b - a) ⊗ (c - a)) / ||((b - a) ⊗ (c - a))|| , with ⊗ denoting the 3-d vector cross product.

Then X = [n, ⟨n, a⟩] , where ⟨u, v⟩ is the bra-ket notation denoting the dot product of vectors.

Taken as a whole, the above represents the typical state-of-the-art with regards to the use of homogeneous coordinates in 3-d apps. On rare occasions, we may also hear talk of Plücker coordinates, which offers interesting ways of manipulating lines and planes in 3-d.

Unfortunately, Plücker coordinates are usually presented de facto, that is, without explaining the structural 'method to the madness'.

 

On the other hand, GA provides an elegant and unified method for creating geometric entities such as lines and planes, extensible to any dimension.

 

2 Demonstrating GA

By way of example, let's create a plane using GA techniques:

Let {a, b, c} be three points in P3.

Then computing a normalized plane | Π | using GA can be done in the following manner.

Define a function dir(X) that computes the direction of k-flat X in PN as

dir(X) = (eN + 1X) ,

and function weight(X) as

weight(X) = || dir(X) ||

Then | Π | = X / weight(X) , where

  • X = ( abc ) ,
  • ∧ denotes the progressive product,
  • eN + 1 denotes the unit basis blade corresponding to the homogeneous coordinate, and
  • ⌋ denotes the left contraction product.

(Note: I prefer the term 'progressive' rather than the more frequently-used 'outer' since GA also offers a regressive product, which is dual in function to the progressive product.)

 

Now, some definitions are in order:

  • PN denotes the projective space of N dimensions, i.e., having dimensionality (1 + N) for a N-d base space.
  • A k-flat refers to a point, line or plane, each of which are k-vectors representing geometric entities. In other words, a 1-flat is a point (is a 1-vector), a 2-flat is a line (is a 2-vector) and a 3-flat is a plane (is a 3-vector).
  • The left contraction product, introduced by Dorst et al., is one of several inner products definable in GA, and probably the most useful for geometry.

 

Suppose you have two vectors of grade-m and grade-n, respectively. Then

Am ⌋ Bn = ⟨ A B ⟩ n - m , if (n - m) ≥ 0.
Where
* A B denotes the geometric product of multivectors A and B, and
* ⟨ M ⟩ k denotes the grade-k part selector (a.k.a. grade projection operator) of multivector M.

With this understanding, the function dir(X), which computes the direction of k-flat X, returns

  • a scalar if (k == 1), i.e., if X is a point. This corresponds to the w-coordinate of the point.
  • a vector if (k == 2), i.e., if X is a line. This corresponds to the direction of the line defined by b - a.
  • a bivector if (k ==3), i.e., if X is a plane. This corresponds to the bivector representing the plane's surface normal.

The function weight() computes the magnitude of the value returned by dir(), and returns a k-flat's weight (a scalar).

 

In summary, a k-flat is a k-vector, and has non-zero weight if it's not degenerate or improper (i.e., 'at infinity'). Furthermore, dividing the flat by its weight normalizes it.

It is advisable to work with normalized k-flats, much in the same way as it is good practice to work with unit-length normal vectors in a standard 3-d app setting.

 

We saw how to create a normalized plane; now let's make a normalized line. The procedure is even simpler: for points {a, b}, a != b, simply compute a ^ b and divide by the weight.

The above method extends to any dimension: no having to create specialized classes and code for each geometric entity, no messing around with Plücker coordinates, etc!

 

Now let's look at things like distance queries, incidence relationships (i.e., finding intersections), etc.

 

Define the scalar distance between 3-d points and planes as

dp, Π = p ⌋ ∼Π ≡ ⟨p,∼Π

where ∼ denotes geometric dual, i.e.,

∼X = X IN-1

which is the geometric product of multivector X with the unit antiscalar inverse for PN

Q: What's going on here?

A: Let us first understand what Π represents: it is a 4-d trivector constructed by 'wedging' three points together (i.e., by having computed the progressive product of three points).

* The dual of any k-flat in PN is a (N + 1 - k) - vector in RN + 1

* Write the dual of a k-flat in lower case, so that ∼Π is rewritten as π (for planes), ∼Λ is rewritten as λ (for lines), etc..

Then π is a 4-d vector in [n, -d] form, while Π = d e123 + nz e124 - ny e134 + nx e234 , where the ni denote the coefficients of the plane's normal vector.

Since p is both a point in P3 and a vector in R4, and π is a vector in R4 as well, then clearly

dp, Πpπ ≡ ⟨p,π

In other words, the distance of any 3-d point to any 3-d plane is the result of evaluating the dot product between the point and the dual plane!

* Note also that the value of pπ = the value of pΠ .

Example:

Let p = (1, 2, -3, 1), and Π = (0, 0, 1, 1) ∧ (3, 0, 1, 1) ∧ (0, 5, 1, 1) = (15, 15, 0, 0) .

Then | Π | = (1, 1, 0, 0) and |π| = (0, 0, 1, -1). Interpret this as a plane at distance 1 from the origin and having normal = Z.

Computing p ⌋ |π| gives -4, and computing p ∧ | Π | gives -4e1234 .

Thus we see that p is at distance -4 from the plane.

  • It is not hard to imagine that if pπ = 0 (or if pΠ = 0), then the point lies on the plane.
  • It is also not hard to imagine that if the above works for point-plane distance queries, might not it also apply to point-line distance queries as well?

 

In summary,

  • the 'planes' that 3-d programmers are accustomed to working with are in fact 'dual planes' in the parlance of projective GA.
  • N-d points are just (N + 1)-d vectors.
  • Points and planes are geometrically dual to each other.

 

Posted
AuthorJason Wood

A Concrete Implementation of Linear Interpolation

Our senior programmer, Jason Wood, is currently working on implementing geometric algebra (GA) into our gaming engine and animation software!


Below is a sample of his code: note how he makes use of a simplified API.

Rotor3 interpolate(Rotor3 const& a, Rotor3 const& b, Real t) {
 return a * exp(t * log(b / a));
}

What it's doing is first using geometric division (b/a) to compute the rotation between a and b (which itself is a rotor). Then it takes the logarithm of that, which returns a 3-d bivector, which is then multiplied by the t parameter (which varies between 0 and 1). We then take this scaled bivector and exponentiate it, which returns a rotor in the global frame. To make this useful, it's pre-multiplied by rotor a to place it in the frame of the rotation (i.e., to make it 'start at a').

This gives the same results as calling slerp(qa, qb, t) using quaternions.

It's easy to make a higher-order interpolation function, for example cubic interpolation between 4 rotors. First define a function to perform quadratic interpolation:

Rotor3 interpolate(Rotor3 const& a, Rotor3 const& b, Rotor3 const& c, Real t) {
 return interpolate(interpolate(a, b, t), interpolate(b, c, t), t);
}

Then define the cubic version:

Rotor3 interpolate(Rotor3 const& a, Rotor3 const& b, Rotor3 const& c, Rotor3 const& d, Real t) {
 return interpolate(interpolate(a, b, t), interpolate(b, c, t), interpolate(c, d, t), t);
}

This is basically doing a version of de Casteljau 'corner cutting' for Bezier curves, i.e., recursively breaking the problem into sub-problems and combining results.

May not be the fastest in the world, but it is pretty clean. A slightly less clean but possibly faster version could use cubic Hermite interpolation instead.

- Jason Wood