Tuesday, November 8, 2022

Implicit Half Edges

Someone asked me about implicit half edges, so I made a quick google sheets about it

Friday, May 15, 2020

GDC talk

I did a GDC talk on the latest CSG algorithm I developed!

You can watch it here

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

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.

Subscribe to: Posts (Atom)