Thursday, July 18, 2019

Dot product and its relationship to matrices

So in the previous post I explained that the dot-product returns a distance along a given vector.

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

I'm going to write some blog posts to try to help share some insights about geometry. Here I'm starting with the most important basic operations.

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 this
float 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.

If vector A is unit length, this becomes:

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

If both vectors are unit length, then the dot product will return 1 when they're perfectly aligned, -1 when one vector is pointing in the opposite direction, and 0 when the vectors are orthogonal.

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
lineStart - lineStart = 0,0,0 (the origin)
P - lineStart = point P at the same relative distance to lineStart
The final equation then becomes
distanceAlongLine = DotProduct((P - lineStart), lineDirection)

The plane equation

Another important tool in your vector algebra arsenal is the plane equation:
Ax+By+Cz = D
or
Ax+By+Cz-D = 0
As 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) + planeDistance
Note 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 * -planeDistance 
And 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

Thursday, September 28, 2017

Half-edge data structure considered harmful

Note this blog post assumes you're already familiar with half-edges.

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:

  1. Pointers are large (64-bit on 64-bit platforms) 
  2. It's more intuitive to bounds check an index than a pointer 
  3. Your debugger will actually show you legible values.
  4. 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 edgevertex 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:

struct 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.
Keep in mind that you'll probably need to end up with triangles at the end of your pipeline anyway.

A connected triangle ds could be modified to separate its neighbors and vertex indices, and its TriangleVertex could be split into to vertex and triangleEdge parts. You could just have 2 equal sized arrays for both. This way you would simply end up with triangle indices and vertices which could then be rendered directly. 

Keep in mind that this could 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.
For either data structure I strongly suggest you make a 'Validate' method that ensures that the topology is valid and that there is no issue. You can then use this validate method after any operation to ensure that your algorithms do what they're supposed to do and don't leave your topology in an invalid state. This method could be optional when compiling under Debug, for instance.

For me, the connected triangles my Validate method fit on my screen, for half-edges it's several hundreds of lines of code for me.

Let me know if I missed anything and I'll update the article accordingly.


[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.



Wednesday, August 24, 2016

Realtime CSG Level Editor for Unity released!

Whoohoo!

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 ...

It started so great .. I was so excited! .. my free consumer rift (I was a DK1 backer) arrived on the 6th of April!

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



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


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


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.


Finally some progress though!


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


Now I managed to continue the installation


And then ..


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

I try again ...


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 ...


Fortunately @Clavus came through once again


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!


So now everything should go smooth now, right?


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


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


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



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:



Update 2:
Tried it at work:

Sunday, April 3, 2016

CSG Unity plugin update 9

Yes, I'm still working on my real-time CSG plugin!

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.

Friday, January 22, 2016

CSG Unity plugin update 8

I guess I never posted this on my blog, oops!

Here's a video showing some WIP brush editing I've been working on.
It handles non-planar non-convex self-intersecting polygons.