You can watch it here

# Sanders' blog

Blog about random ideas about game development, geometry and computer graphics

## Friday, May 15, 2020

## Thursday, July 18, 2019

### Dot product and its relationship to matrices

Suppose you have a vector called

*direction*and a point

*P*and we want to get the distance along that vector relative to the origin.

We can use the dot-product like this:

myDistanceToOrigin = DotProduct(P, direction);Now if we want to get that point back again using

*myDistanceToOrigin*and

*direction*we can do:

P = myDistanceToOrigin * direction;So in a way a dot-product behaves like the inverse of a scalar * vector operation, along a line.

We're extracting how far a point is along a specific vector.

Now suppose we decompose a point into a distances using dot-products, one each for each axis:

myDistanceX = DotProduct(P, xAxis); myDistanceY = DotProduct(P, yAxis); myDistanceZ = DotProduct(P, zAxis);At this point we're left with 3 distances, along 3 vectors.

Is there a way to reverse this? why yes.

P = (myDistanceX * xAxis) + (myDistanceY * yAxis) + (myDistanceZ * zAxis);Now imagine that instead of using the original 3 vectors, we use different vectors.

What would happen?

Well each distance is a distance traveled on a particular axis, so we'd still end up with a valid point, but it would be positioned relative to the new vectors instead of the original vectors.

It would be

*transformed*into a different position.

*You might know this as a 3x3 matrix multiplication*

Except that for the 'distances' we simply use the X,Y and Z coordinates of a point/vector instead.

Note that if the xAxis has the values (1,0,0) , the yAxis has the values (0,1,0) and the xAxis has the values (0,0,1) the distances would be equal to the original X,Y & Z coordinates.

This is the identity matrix.

What we're essentially doing is defining an imaginary cube with 3 vectors, and then deforming that imaginary cube and all the points inside it.

So what about the 4x4 matrix? Well this is a 4D version of the 3x3 matrix, and it works the same way. Except that the fourth value is a coordinate in the fourth dimension but ends up acting like a translation in 3D space.

Planes are 4D, does this mean that in a 4x4 matrix we have planes instead of vectors?

No, not really.

The 4x4 matrices work with what we call homogenous coordinates, and I'm not going into this right now, because that's a whole different rabbit hole.

However, it

*is*possible to extract the planes that form that imaginary cube I mentioned before from the matrix.

## Next time

I'll write some more posts in the future about- ray-plane intersections
- snapping, how you'd snap a point on an arbitrary grid in 3D, or along a line
- half-edges, fat planes, and how you'd split a polygon using both

## Wednesday, July 17, 2019

### Dot products and planes

## The basics

**origin**a point at 0,0,0**unit length**a vector that has a length of 1**normalization**scaling a vector so that it's unit length**normal**a unit vector that is used to describe a direction**magnitude**the length of a vector

## The dot product

So the dot product is an operation that looks like thisfloat DotProduct(Vector3 a, Vector3 b) { return a.x * b.x + a.y * b.y + a.z * b.z; }Okay, sure, that's the code, but what does it

*do*?

*
The dot-product returns the distance from the origin (0,0,0)
to the projection of point B on vector A, in terms of the length of vector A.
*

*
The dot-product returns the distance from the origin (0,0,0)
to the projection of point B on vector A
*

So if the length of vector A is twice as long, then the returned dot product is half as big.

*Note that a dot product is "Commutative"*

*this which means you can swap vector A & B and you'll get the same results*

### Distance of a point along a line

So imagine having a line that is defined by a point

*lineStart*and a

**normalized**

*lineDirection*, and we want to know the distance from a point

*P*to

*lineStart*, how would we do that?

Well if we take the dot product of

*lineDirection*and point

*P*, we have the distance to the origin, which is not what we want. However, if we both move the point

*P*and

*lineStart*so that

*lineStart*is at the origin, we

**can**use the dot-product.

We can simply do this by subtracting

*lineStart*from both points

The final equation then becomeslineStart - lineStart= 0,0,0 (the origin)P - lineStart= pointPat the samerelativedistance tolineStart

distanceAlongLine = DotProduct((P-lineStart),lineDirection)

## The plane equation

Another important tool in your vector algebra arsenal is the plane equation:Ax+By+Cz = Dor

Ax+By+Cz-D = 0As you can see, a plane is stored as 4 floating point values (ABCD).

The ABC part is the normal, which signifies in what direction the plane is facing.

The D part is the (negative) distance of the plane to the origin, along that normal.

Since a plane is infinite in every direction except the direction of the normal, you can define any 2D plane in 3D space this way.

So this makes the distance of a point to a plane:

signedDistanceToPlane = DotProduct(planeNormal, point) + planeDistanceNote that the distance is signed, meaning that you can tell if a point is in front or behind the plane by checking it's sign.

If you need a point that lies on a plane, you can use:

pointOnPlane = planeNormal * -planeDistanceAnd in reverse, if you have a normal for a plane you can find the planeDistance, the D part of the plane equation, with:

planeDistance = -DotProduct(planeNormal, pointOnPlane)Note that this works with

*any*point that lies on the plane.

If you have 3 points A,B & C, you can calculate the normal by:

normal = Normalize(CrossProduct(B - A, C - A))Now imagine these 3 points all lying on the same plane, then B-A and C-A are 2 vectors that also lie on this plane. The cross product takes these 2 vectors and returns a vector that is perpendicular to both of them, which would be a vector pointing away from the plane.

*Normalize*scales it to unit length, giving us the plane normal.

Note that if these 3 points lie on the same line, it would result in a zero length normal.

If you want to calculate the normal of a polygon, don't just take the first 3 points and try to create a normal out of them, since they might be aligned even though subsequent points may not be.

For polygons it's better to use Newell's algorithm, this algorithm will work with most polygons as long as they're:

- not self-intersecting,
- planar (all points lie on the same plane)
- not degenerate (all points lie on the same line or form a singularity)

## Next time

I'll write some more posts in the future about- the relationship between the dot product and matrix algebra
- ray-plane intersections
- snapping, how you'd snap a point on an arbitrary grid in 3D, or along a line
- half-edges, fat planes, and how you'd split a polygon using both

## Thursday, September 28, 2017

### Half-edge data structure considered harmful

I've been using the half-edge data structure for mesh/topology operations for a while now and I've come to the conclusion that it's actually an anti-pattern.

The problem is that it has a very large potential 'problem surface area'.

Let's investigate:

struct HalfEdge { HalfEdgeIndex next; //HalfEdgeIndex prev; //(optional)

HalfEdgeIndex twin; VertexIndex vertex; PolygonIndex polygon; } struct Polygon { HalfEdgeIndex first; }

Note that i'm using indices here instead of pointers.

You should never use pointers in data structures like this because:

- Pointers are large (64-bit on 64-bit platforms)
- It's more intuitive to bounds check an index than a pointer
- Your debugger will actually show you legible values.
- Copying an entire mesh is trivial.

So what are the potential problems with a half-edge based mesh?

struct

**HalfEdge**:

**next, prev**:

potentially points to wrong edge, potentially points to self, or out of bounds index.**twin:**

potentially points to wrong edge, potentially points to self, or out of bounds index.

twin could lead to edge on same polygon.**vertex**:

potentially points to wrong vertex, or out of bounds index**polygon**:

potentially points to wrong polygon, or out of bounds index**twin + next, prev + twin:**(looping over vertex)

if either**twin**or**next/prev**is wrong, you might end up in an infinite loop.- The edge could be disconnected and not belong to any polygon
- Every time you follow an
**edge**to another**edge**,**vertex**or**polygon**there's a potential cache-miss since edges, vertices and polygons can be placed anywhere in memory relative to the current edge.

struct

**Polygon**:

**first**

potentially points to wrong edge, potentially points to self, or out of bounds index. The**first**edge might point to a chain of edges that never actually loops back to**first**, resulting in an infinite loop if you simply try to loop over the edges of a polygon.

This is*very*easy to do unfortunately.- The polygon might be concave, self-intersecting or infinitely thin
- The polygon could only have 1 or 2 edges.
- All vertices on the polygon could lie on the same spot (singularity)
- The order of vertices could be flipped and the polygon could be orientated in the wrong direction (note; you'd have other connectivity problems on the polygon as well)
- The polygon could contain the same edge multiple times
- The polygon could contain the same vertex multiple times

Literally

*every step you take*could potentially be an issue. And if you can't control your input data you have to take each and every situation into account. You can't very well check the bounds of every next/prev/twin you follow so I hope you didn't make a mistake anywhere!

While developing/implementing an algorithm anything can go wrong at any time due to either a bug, or a situation you haven't considered. Worse still, the actual cause could be far removed from the place where you notice a problem since it's all a big pile of interconnected elements.

Half-edges are

*very*hard to debug. You can't see in your debugger what your polygon looks like, so you need to draw it out by hand or, for instance, create some extra code to generate an html page with svg graphics to render it for you, and then spit out html pages at certain points in your code to visualize what is going on.

Now every data structure will have at least

*some*of these problems.

But is there a data structure that at least decreases the problem surface area?

Well, recently I come across the data-structure at the end of this pdf.

Unfortunately it's not named here, they just called it 'triangle data structure'.

I modified it

*slightly*and call it a 'connected triangle' because calling it 'triangle ds' will just be too ambiguous. (let me know if there's an official name for this or if you have a better suggestion to name this)

**Update: In the book "Real-Time Collision Detection" an almost identical data structure is named "winged-triangle"**.

struct Triangle { TriangleEdge neighbors[3]; VertexIndex vertices[3]; } struct TriangleEdge { uint32 triangle : 30; uint32 edge : 2; } struct TriangleVertex { Vector3 vertex; // To allow you to quickly find a starting point to loop over a vertex TriangleEdge triangleEdge; }

struct

**Triangle**:

**neighbor**[x].**triangle**

potentially points to wrong triangle, potentially points to self, or out of bounds index.**neighbor**[x].**edge:**

potentially points to wrong edge on destination triangle, or out of bounds index.

could be 0-3 where 3 is an invalid value (only 3 edges on triangle)**vertices**[x]:

potentially points to wrong vertex, or out of bounds index.**neighbor + next edge index, prev edge index + neighbor:**(looping over vertex)

could potentially be an infinite loop- The triangle could contain the same vertex multiple times.
- The vertices could be in wrong index compared to neighbors
- The order of vertices could be flipped and the triangle could be orientated in the wrong direction (note; you'd have other connectivity problems on the triangle as well)
- You could have multiple neighbors pointing to same edge on same triangle
- All vertices on the triangle could be aligned (infinitely thin triangle)
- All vertices on the triangle could lie on the same spot (singularity triangle)

As you can see there is only one potential infinite loop; while looping over a vertex. But in practice that situation has never happened for me using both half-edges or the connected triangle ds. Also a triangle is always a triangle, it is always convex, never self-intersecting.

Cache misses are less likely to happen, compared to half-edges, since more data you'd be using at the same time is actually stored together.

Note that the classic half-edge structure doesn't have an equivalent to 'TriangleVertex', even though that would be trivial to add.

So for completeness sake:

**TriangleVertex**:

**triangleEdge**.**triangle:**

potentially points to wrong triangle, or out of bounds index.**triangleEdge.edge:**potentially points to wrong edge on destination triangle, or out of bounds index.

could be 0-3 where 3 is an invalid value(only 3 edges on triangle)

Now a triangle based data structure might not always be what you want. Sometimes you really need to deal with polygons, but if you don't I would strongly suggest to not use half-edges.

*potentially*be bad cache wise, but it really depends on your algorithms.

Also. it is potentially possible to store your half-edges contiguously in memory, maybe store your half-edges as an array in your polygon somehow etc. etc. and solve some of the potential problems that half-edges have. It'll definitely increase complexity in other areas like memory management though.

*P.S.*

[UPDATE]

Eric Arnebäck tweeted about this blog post and it got a lot of reactions, some of these reactions had some interesting links, which I'll share here.

- Mikkel Gjoel mentioned "Data Structures for multiresolution representation of unstructured meshes" which contains a Lath like data structure.
- Peter-Pike Sloan mentioned "Managing Adjacency in Triangular Meshes" by Charles Loop that has a similar data structure.
- Bruno Levy mentioned his own presentation "Half-edges/edge-uses: Half harmful, half useful!"

## Wednesday, August 24, 2016

### Realtime CSG Level Editor for Unity released!

Finally after years of working on it, I released my real-time CSG asset on the

**Unity asset store**!

###
The project page can be found here!

## Monday, April 11, 2016

### Consumer Oculus Rift Blues ...

I don't think I'll ever take it off ... pic.twitter.com/LImFLhFQjQ

— Sander van Rossen (@logicalerror) April 6, 2016

Thanks so much for the CV1 @oculus !

— Sander van Rossen (@logicalerror) April 6, 2016

Unfortunately I didn't have time to actually try it until the next day.

But then .. I plugged in my Oculus Rift and .. nothing.

I downloaded their compatibility tool and it said that my Intel i7-3930k processor isn't good enough, even though it's a lot faster than their minimum Intel i5-4590 processor according to all kinds of benchmarks.

So I got a little frustrated

looks like according to valve's steamvr performance test my machine is among the far high end of the required specs! I should get a vive

— Sander van Rossen (@logicalerror) April 7, 2016

@Clavus shouldn't .. but is .. also my USB 3.0 is apparently not good enough for some reason pic.twitter.com/538UqMni0j

— Sander van Rossen (@logicalerror) April 7, 2016

Then I started wonder if it was a software issue .. after all, it didn't automatically install anything when I plugged it in.

@Clavus I'm also wondering if there is any software / driver I need to install .. but I can't find anything anywhere

— Sander van Rossen (@logicalerror) April 7, 2016

I do vaguely remember seeing this piece of paper in the Oculus Rift box that had a web address on it, but somehow it got lost.

I tried to find something on the oculus home page, looked for "downloads" or "drivers", but it didn't turn up anything. All I could find was the SDK stuff.

Finally I turned to twitter .. thankfully @Clavus helped me out

@logicalerror config utility or Oculus Home? For CV1 you manage it via Oculus Home.

— Joeri van der Velden (@Clavus) April 7, 2016

Searching for "Oculus Home" finally made me find https://www.oculus.com/en-us/setup/.

Why was this virtually impossible to find from the main site?

Who knows .. I just know it cost me

*a lot*of time.

@Clavus I was looking for drivers or downloads and could only find sdk's .. great now the setup wants me to reboot .. welcome to the 90's!

— Sander van Rossen (@logicalerror) April 7, 2016

Finally some progress though!

@Clavus progress .. :( pic.twitter.com/WwCHlf40Tw

— Sander van Rossen (@logicalerror) April 7, 2016

After lots of uninstalling/reinstalling stuff & browsing I found the location of the error log.

@Clavus .. and apparently it fails at installing the visual c++ 2015 redistributables .. I already have vs2015 installed .. wtf

— Sander van Rossen (@logicalerror) April 7, 2016

@Clavus running the redistributable separately it fails because "another version is already installed" ... thanks @microsoft!

— Sander van Rossen (@logicalerror) April 7, 2016

@Clavus I uninstalled the newer vs2015 redistributable and let @occulus install the older one .. and now the error didn't appear!

— Sander van Rossen (@logicalerror) April 7, 2016

Now I managed to continue the installation

@Clavus @Occulus awesome, I got to the part where it complains that my USB 3.0 won't work with it

— Sander van Rossen (@logicalerror) April 7, 2016

And then ..

@Clavus skipped past that point and now bluescreen when installing @Microsoft xbox controller on @Microsoft OS :( pic.twitter.com/Qu0mz5sH5K

— Sander van Rossen (@logicalerror) April 7, 2016

Literally the first blue screen I've seen in years ..

I try again ...

@Clavus ok, after restart fortunately it automatically restarted half-way through the installation (no re-downloading!)

— Sander van Rossen (@logicalerror) April 7, 2016

@Clavus no blue-screen this time during xbox controller installation. sensor & rift aren't found due to USB issues though *sigh*

— Sander van Rossen (@logicalerror) April 7, 2016

So I guess the Oculus Rift really doesn't want to work with my onboard USB 3.0 ..

... even though I never had any issues with it before ...

@Clavus I guess I really need to get a USB card .. :-/

— Sander van Rossen (@logicalerror) April 7, 2016

Fortunately @Clavus came through once again

@logicalerror if the USB controller is still proving to be an issue, this expansion card definitely works: https://t.co/E8eHVjTdXx

— Joeri van der Velden (@Clavus) April 7, 2016

So I bit the bullet and ordered an USB controller card. Since it worked for @Clavus I figured that it would be a safe bet.

4 long days later my PCI USB controller finally arrived..

I wasted time making the mistake to think that the incorrect connector was supposed to be attached to the card. Oops!

@Clavus so USB card finally arrived ... but how am I supposed to power it with two cables that don't connect?? pic.twitter.com/tIv3FPSsLU

— Sander van Rossen (@logicalerror) April 11, 2016

@Clavus so it fits, yay!

— Sander van Rossen (@logicalerror) April 11, 2016

So now everything should go smooth now, right?

@Clavus well it still doesn't detect my oculus :( ... trying re-install of drivers

— Sander van Rossen (@logicalerror) April 11, 2016

@Clavus card shows up in device manager .. oculus does not

— Sander van Rossen (@logicalerror) April 11, 2016

So I try to try to use the repair option of the Oculus Setup.exe, which starts to re-download hundreds of megabytes of data ... again

@Clavus gah .. and now the setup fails because of course I installed my visual studio redistributable again .. ffuuuu

— Sander van Rossen (@logicalerror) April 11, 2016

So I try to reboot, un- and re-plugging cables in and out, but to no avail.

@Clavus ... then the sensor shows up. Rift however, is not being detected.

— Sander van Rossen (@logicalerror) April 11, 2016

Finally I give up. My Oculus Rift simply doesn't want to turn on.

I'm a sad panda today ...

— Sander van Rossen (@logicalerror) April 7, 2016

PS. I'm going to assume that these installer problems will go away eventually, once Oculus starts realizing the problems with it.

And

*hopefully*they'll make their USB code work with older USB plugs as well.

Now, I know I got the Rift for free, and I

**am**grateful. But I have to be honest; had I bought the Rift, after buying a Geforce Titan for it and it still didn't work, I'd ask for my money back and buy a Vive instead. (and I'm saying that as an Oculus fanboy)

I know that you're supposed to have an expensive system to run a Rift on anyway, but it's unreasonable to force people to upgrade stuff that doesn't need upgrading.

My system worked fine with the DK1 and DK2, I see no technical reason why it shouldn't have been made to work with the consumer Rift as well...

I really hope this will be fixed somehow .... :(

Only bright side is that it's not a distraction anymore, I need to work on my real-time CSG Unity plugin anyway!

**Update:**

Tried to re-install oculus software since apparently new version was released.

The result:

progress! ... pic.twitter.com/qscFdUSFOw

— Sander van Rossen (@logicalerror) April 12, 2016

**Update 2:**

Tried it at work:

ok, tried rift on machine at work, which meets their specifications. Still doesn't work. I guess I received an Oculus doorstop

— Sander van Rossen (@logicalerror) April 15, 2016

## Sunday, April 3, 2016

### CSG Unity plugin update 9

Here is some progress on CSG brush editing.

I decided I'll keep brush editing convex only for now, I really need to finish this plugin!

There's nothing that stops me from adding non-convex editing later on, it just means I need to handle a lot of of edge cases and that takes too much time right now.

As you can see in the video I also improved the grid rendering.

There are only some minor technical issues that I need to fix and then a list of trivial issues + polish.