News

Drawing Borders in Deep Rift 9

Drawing Borders in Deep Rift 9

My name is Niels Jørgensen and I'm the lead developer on DR9. In this DR9 update I'll talk a bit about a purely visual feature that we added to the DR9 map to make it more interesting to look at.

The DR9 world is procedurally generated and needs to be repetitive enough that no specific start location will give a player any huge advantage over another. This means that any given area on the map becomes more or less indistinguishable from any other - as you scroll around, you quickly loose track of what is where. To add insult to injury, player buildings also look the same (with minor variations for building levels, but still). Obviously we can't give thousands of player their own distinct architectural design and since there are no "factions" in the game and alliances are formed ad-hoc, neither of these provide a way to distinguish buildings either.

Borders

So, in order to provide some visual differentiation and to set areas apart, we decided to render the borders between players. Clearly indicating the size and shape of each players land helps players navigate and makes each area more distinct. It also looks cool :) When the idea first surfaced, it sounded great but also not very easy to implement - at least in any way that was acceptable performance-wise. I did however have this one word in the back of mind that I figured would somehow save me: Voronoi.

Voronoi Diagrams

I don't remember when I first heard or read about Voronoi Diagrams, but I do remember these guys: http://www.big-robot.com giving a rather funny presentation of how they used Voronoi diagrams to procedurally generate maps in "Sir, you are being hunted" back at Unite Nordic 2013 (jeez, time flies). Actually, the talk is on YouTube if you're interested , I'm in the front row, purple shirt, bald spot :)

https://www.youtube.com/watch?v=GYYuhuarTA0

There's a good page on WikiPedia if you want the details: WikiPedia on Voronoi

The TL;DR version: A Voronoi diagram divides a set of seed-points into convex shapes. There is one seed point in each shape and each shape contains all other points that are closer to that specific seed than they are to any other seed point. The edges of the shape naturally becomes the borders to the surrounding shapes. Sounds perfect.

Implementation

Luckily for me, I did not have to take this all the way from mathematical concept to working algorithm since several talented people had already laid the foundation and generously shared their implementations. Unfortunately, none of them decided to do it in C# which is what I needed, so I did have to port the code. The implementation I ended up using is a C++ derivation of Steven Fortune's original C implementation from AT&T, made by Shane O'sullivan:

Shane O'Sullivans C++ Voronoi implementation

The original source is available from Stevens web page, here:

Steven Fortune's original C implementation

My C# adaption is below if anyone feels like saving a few hours of tedious pointer-to-reference conversion.

Performance

Even though performance of the border generation is not super critical to DR9 - the points that serve as Voronoi "seeds" in DR9 are the cities and they don't move, nor are they created or destroyed at a very high frequency so the Voronoi generator does not need to run at anywhere near full frame-rate speed - I still decided to do some quick performance tests. I got rid of a bunch of C and C++ legacy annoyances like additional counters and funky size conversions that are not needed in C# and got a small ~20% performance bump for my efforts (probably not because there was anything wrong with the original code, but more likely because I had earned a penalty when porting, trying to be strict rather than fast). With this out of the way, and not feeling too eager to mess with the core algorithm, I zoned in on the use of hash tables. Even though hash tables are generally good for performance - at least at scale, something about this particular use-case just didn't taste right. Going on nothing but a hunch, I did not really expect to find any gains, so as a quick test, I just dumbed the hash tables down to a size of one, effectively turning them into complicated arrays. Somewhat to my surprise performance increased by another 15%. I initially assumed that my dataset was simply too small for the hashtables to be useful, and I was just suffering the overhead without the benefit, so I bumped my seed count from 128 to 2048. This had the completely unexpected effect of being 25% faster than the hashed version. Not only was hashing slower, it also scaled worse: Screen Shot 2017-09-11 at 22.38.17

I'm not sure why this is and I have not had time to dig deeper, but there's a number of things that could be worth investigating:

  1. The nature of the algorithm may not need real random access, or my data set may have been skewed in such a way that it didn't - If the searches mostly find candidates in close proximity to where it is, a hashtable has very little use. I did try to shuffle the data but that only pushed the results further in the direction of the non-hashed version, even if only marginally so.
  2. The hash table implementation may have been broken, or using an inappropriate hashing function. I looked at this briefly and it seemed reasonable, using spatial position for hashing which matches the even distribution of my seeds nicely. I didn't do any profiling of the actual buckets to see if the fill was uneven, but I doubt it.
  3. The hash table may break optimization done by either the C# compiler or run-time or by the CPU (this could be anything from overflowing the pipeline or missing the cache to fouling up the CPUs branch prediction). Generally, less code, fewer branches, fewer method calls and less messing with shared variables results in better run-time optimization, even if your loops gets a bit longer. Long lesson learned by years of Java programming - you can really mess the hotspot compiler up if you try to be clever on its behalf.

Personally, I have my money on #3 :) In any case, once I had the Voronoi structure, connecting neighbouring shapes with the same owner was trivial, and so was traversing the surrounding edges to create a mesh for the border. The following screenshot shows borders in red, and lines connecting neighbours in gray. Seeds are considered to have the same owner if they have the same color.

Screen Shot 2017-09-11 at 20.50.11

What did turn out to be something of a hassle, was rendering it. Ideally I just wanted it painted as a flat configurable-width line on top of the map, but the map is not flat and it is not "a" map, but rather a bunch of map-patches that are dynamically created and destroyed as the view changes. Because the shape of the Voronoi cells are highly dependent on neighbouring patches (in fact that's all it depends on) it was not practical to create Voronoi meshes for each patch - it had to be created independently of the patches. Creating a mesh that followed the terrain was not trivial for two reasons. The first is that the actual map patches are not a true representation of the procedural height map. The patches are sub-divided and smoothened to create a nicer terrain and also contain objects such as trees and mountains and thus the height at any given location was not readily available. The second problem is that the Voronoi diagram extends towards infinity (or 32000 as infinity is defined in DR9 :) ) and creating a mesh with that many vertices would never work. I had to find a way to draw the lines on the map, preferably by storing only the end-points of each border. My first attempt involved a rather exotic use of the depth buffer and a custom shader. I build a mesh of vertical planes and rendered their intersection with the map patches by measuring the distance in the depth buffer. It worked ok from certain angles, but not at all for borders that were perfectly vertical compared to the camera (which turned out to be a fairly common case):

Screen Shot 2017-08-25 at 09.31.58

Fiddling with the shader, I was able to make it less horrible, but never really good (notice how lines get thinner as they become vertical):

Screen Shot 2017-08-25 at 09.55.55

My second attempt was to create extruded upside-down U shapes instead of vertical planes. I used the actual procedural height data plus some small distance as the height of the inverted U, but limited to 10 points per edge. This meant that most "real" borders would get subdivided into small enough pieces that they kind of followed the terrain, while the outer ones that extended toward "infinity" would not generate ridiculous amounts of vertices. The problem with this approach was that the border would sometimes extend high above the terrain, and other times penetrate through it, disappearing all together.

The final solution turned out to be as simple as they come: I modified the shader to ignore Z-test and reduced the geometry to be only the flat upper face of the inverted U. Because the line kind of follows the terrain, it never gets wildly out of place, and even when it does deviate, nobody can tell because there is no telling where it *should* have been. This would not have worked if the user was able to tilt or rotate the camera as it would have broken the illusion, but as it happens, they can't :)

Screen Shot 2017-09-11 at 12.18.45

My C# port is listed below.

The way this works is that you create an instance of VoronoidGenerator supplying any class that you want to associate with the seeds - it does not matter what it is, only that you can somehow convert it into a 2D location. You then call AddSeed with each of the seeds you want included and finally Generate to build the actual Graph. Generate takes a locationResolver as its last parameter - this is a function that given a seed of your declared type must return a 2D position. When Generate completes, you can get the first edge in the graph with GetFirstEdge and then loop the graph by following edges (edge.next). Each graph edge contains the border end points as well as a reference to the seeds on either side of the border.

/* * The author of this software is Steven Fortune. Copyright (c) 1994 by AT&T * Bell Laboratories. * Permission to use, copy, modify, and distribute this software for any * purpose without fee is hereby granted, provided that this entire notice * is included in all copies of any software which is or includes a copy * or modification of this software and in all copies of the supporting * documentation for such software. * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED * WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. */ /* * This code was originally written by Stephan Fortune in C code. I, Shane O'Sullivan, * have since modified it, encapsulating it in a C++ class and, fixing memory leaks and * adding accessors to the Voronoi Edges. * Permission to use, copy, modify, and distribute this software for any * purpose without fee is hereby granted, provided that this entire notice * is included in all copies of any software which is or includes a copy * or modification of this software and in all copies of the supporting * documentation for such software. * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED * WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. */ /** * C# adaption for use with Unity by Niels Jørgensen, BoaNeo AB (http://www.boaneo.com) * * Permission to use, copy, modify, and distribute this software for any * purpose without fee is hereby granted, provided that this entire notice * is included in all copies of any software which is or includes a copy * or modification of this software and in all copies of the supporting * documentation for such software. * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED * WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. */ using System; using System.Collections.Generic; using UnityEngine; namespace BoaNeoTools.Source.MathNoHash { class Pool where T : new() { private List _memory = new List(); private int _free; public int length { get { return _free; } } public void Reset() { _free = 0; } public T Allocate() { if (_free >= _memory.Count) _memory.Add(new T()); T obj = _memory[_free++]; return obj; } public void Claim(T curr) { int idx = _memory.IndexOf(curr); if (idx >= 0 && idx < _free) { _memory.RemoveAt(idx); _free--; _memory.Add(curr); } } } class Point { public float x; public float y; } class Seed : Point { public object source; public int seednbr; public int refcnt; public Seed() { } public Seed(object seedSource) { source = seedSource; } } class Edge { public float a; public float b; public float c; public Seed[] ep = new Seed[2]; public Seed[] reg = new Seed[2]; public int edgenbr; } public class GraphEdge { public float x1; public float y1; public float x2; public float y2; public T s1; public T s2; public GraphEdge next; } class Halfedge { public Halfedge ELleft; public Halfedge ELright; public Edge ELedge; public int ELrefcnt; public int ELpm; public Seed vertex; public float ystar; public Halfedge PQnext; } public class VoronoiGenerator { Edge DELETED = new Edge(); // Used for ugly comparison const int le = 0; const int re = 1; private List _userSeeds = new List(); private int _seedIdx; private GraphEdge _allEdges; private Pool _pointPool = new Pool(); private Pool<GraphEdge> _graphEdgePool = new Pool<GraphEdge>(); private Pool _halfedgePool = new Pool(); private Pool _internalSeedPool = new Pool(); private Pool _edgePool = new Pool(); Halfedge ELleftend; Halfedge ELrightend; float xmin, xmax, ymin, ymax; int nvertices; Halfedge PQhash; int PQcount; float _perimeterXmin, _perimeterXmax, _perimeterYmin, _perimeterYmax; float _minDistanceBetweenSeeds; public GraphEdge GetFirstEdge() { return _allEdges; } public void AddSeed( T seedSource ) { _userSeeds.Add( new Seed(seedSource) ); } public void RemoveSeed( T seedSource ) { for (int i = 0; i < _userSeeds.Count; i++) { if (_userSeeds[i].source == (object)seedSource) { _userSeeds.RemoveAt(i); return; } } } public void Generate(float minX, float maxX, float minY, float maxY, float minDist, Func<T, Vector2> locationResolver) { if (_userSeeds.Count == 0) return; CleanupEdges(); int i; _minDistanceBetweenSeeds = minDist; _graphEdgePool.Reset(); _internalSeedPool.Reset(); _pointPool.Reset(); xmin = float.MaxValue; ymin = float.MaxValue; xmax = float.MinValue; ymax = float.MinValue; for (i = 0; i < _userSeeds.Count; i++) { Vector2 p0 = locationResolver((T)_userSeeds[i].source); _userSeeds[i].x = p0.x; _userSeeds[i].y = p0.y; _userSeeds[i].seednbr = i; _userSeeds[i].refcnt = 0; if (p0.x < xmin) xmin = p0.x; else if (p0.x > xmax) xmax = p0.x; if (p0.y < ymin) ymin = p0.y; else if (p0.y > ymax) ymax = p0.y; } _userSeeds.Sort((s1, s2) => { if (s1.y < s2.y) return -1; if (s1.y > s2.y) return 1; if (s1.x < s2.x) return -1; if (s1.x > s2.x) return 1; return 0; }); _seedIdx = 0; _edgePool.Reset(); nvertices = 0; float temp; if (minX > maxX) { temp = minX; minX = maxX; maxX = temp; } if (minY > maxY) { temp = minY; minY = maxY; maxY = temp; } _perimeterXmin = minX; _perimeterYmin = minY; _perimeterXmax = maxX; _perimeterYmax = maxY; _seedIdx = 0; Voronoi(); } private void ELinitialize() { _halfedgePool.Reset(); ELleftend = HEcreate(null, 0); ELrightend = HEcreate(null, 0); ELleftend.ELleft = null; ELleftend.ELright = ELrightend; ELrightend.ELleft = ELleftend; ELrightend.ELright = null; } Halfedge HEcreate(Edge e, int pm) { Halfedge answer = _halfedgePool.Allocate(); answer.ELedge = e; answer.ELpm = pm; answer.PQnext = null; answer.vertex = null; answer.ELrefcnt = 0; answer.ELleft = null; answer.ELright = null; answer.ystar = 0; return answer; } void ELinsert(Halfedge lb, Halfedge newHe) { newHe.ELleft = lb; newHe.ELright = lb.ELright; lb.ELright.ELleft = newHe; lb.ELright = newHe; } Halfedge ELleftbnd(Point p) { // Use hash table to get close to desired halfedge Halfedge he = ELrightend; //ntry += 1; // Now search linear list of halfedges for the correct one do { he = he.ELleft; } while (he != ELleftend && !RightOf(he, p)); return he; } // This delete routine can't reclaim node, since pointers from hash table may be present. void ELdelete(Halfedge he) { he.ELleft.ELright = he.ELright; he.ELright.ELleft = he.ELleft; he.ELedge = DELETED; } Seed LeftReg(Halfedge he) { if (he.ELedge == null) return _userSeeds[0]; return he.ELpm == le ? he.ELedge.reg[le] : he.ELedge.reg[re]; } Seed RightReg(Halfedge he) { if (he.ELedge == null) //if this halfedge has no edge, return the bottom seed (whatever that is) return _userSeeds[0]; //if the ELpm field is zero, return the seed 0 that this edge bisects, otherwise return seed number 1 return(he.ELpm == le ? he.ELedge.reg[re] : he.ELedge.reg[le]); } Edge Bisect(Seed s1, Seed s2) { Edge newedge = _edgePool.Allocate(); newedge.edgenbr = 0; newedge.a = newedge.b = newedge.c = 0; newedge.reg[0] = s1; //store the seeds that this edge is bisecting newedge.reg[1] = s2; RefBump(s1); RefBump(s2); newedge.ep[0] = null; //to begin with, there are no endpoints on the bisector - it goes to infinity newedge.ep[1] = null; float dx = s2.x - s1.x; //get the difference in x dist between the seeds float dy = s2.y - s1.y; float adx = dx > 0 ? dx : -dx; //make sure that the difference in positive float ady = dy > 0 ? dy : -dy; newedge.c = (float) (s1.x * dx + s1.y * dy + (dx * dx + dy * dy) * 0.5); //get the slope of the line if (adx > ady) { newedge.a = 1.0f; newedge.b = dy / dx; newedge.c /= dx; //set formula of line, with x fixed to 1 } else { newedge.b = 1.0f; newedge.a = dx / dy; newedge.c /= dy; //set formula of line, with y fixed to 1 } newedge.edgenbr = _edgePool.length - 1; return newedge; } //create a new seed where the HalfEdges el1 and el2 intersect - note that the Point in the argument list is not used, don't know why it's there Seed Intersect(Halfedge el1, Halfedge el2) { Edge e1 = el1.ELedge; Edge e2 = el2.ELedge; if (e1 == null || e2 == null) return null; //if the two edges bisect the same parent, return null if (e1.reg[1] == e2.reg[1]) return null; float d = e1.a * e2.b - e1.b * e2.a; if (-1.0e-10 < d && d < 1.0e-10) return null; float xint = (e1.c * e2.b - e2.c * e1.b) / d; float yint = (e2.c * e1.a - e1.c * e2.a) / d; Halfedge el; Edge e; if ((e1.reg[1].y < e2.reg[1].y) || (e1.reg[1].y == e2.reg[1].y && e1.reg[1].x < e2.reg[1].x)) { el = el1; e = e1; } else { el = el2; e = e2; } bool right_of_seed = xint >= e.reg[1].x; if ((right_of_seed && el.ELpm == le) || (!right_of_seed && el.ELpm == re)) return null; //create a new seed at the point of intersection - this is a new vector event waiting to happen Seed v = _internalSeedPool.Allocate(); v.refcnt = 0; v.seednbr = 0; v.x = xint; v.y = yint; return v; } // returns 1 if p is to right of halfedge e bool RightOf(Halfedge el, Point p) { Edge e = el.ELedge; Seed topSeed = e.reg[1]; bool right_of_seed = p.x > topSeed.x; if (right_of_seed && el.ELpm == le) return true; if (!right_of_seed && el.ELpm == re) return false; bool above; if (e.a == 1.0) { float dyp = p.y - topSeed.y; float dxp = p.x - topSeed.x; bool fast = false; if ((!right_of_seed & (e.b < 0.0)) | (right_of_seed & (e.b >= 0.0))) { above = dyp >= e.b * dxp; fast = above; } else { above = p.x + p.y * e.b > e.c; if (e.b < 0.0) above = !above; if (!above) fast = true; } if (!fast) { var dxs = topSeed.x - (e.reg[0]).x; above = e.b * (dxp * dxp - dyp * dyp) < dxs * dyp * (1.0 + 2.0 * dxp / dxs + e.b * e.b); if (e.b < 0.0) above = !above; } } else // e.b==1.0 { float yl = e.c - e.a * p.x; float t1 = p.y - yl; float t2 = p.x - topSeed.x; float t3 = yl - topSeed.y; above = t1 * t1 > t2 * t2 + t3 * t3; } return el.ELpm == le ? above : !above; } void EndPoint(Edge e, int lr, Seed s) { e.ep[lr] = s; RefBump(s); if (e.ep[re - lr] == null) return; ClipLine(e); DeRef(e.reg[le]); DeRef(e.reg[re]); _edgePool.Claim(e); } float Distance(Point s, Point t) { float dx = s.x - t.x; float dy = s.y - t.y; return Mathf.Sqrt(dx * dx + dy * dy); } void MakeVertex(Seed v) { v.seednbr = nvertices; nvertices += 1; } void DeRef(Seed v) { v.refcnt -= 1; if (v.refcnt == 0) _internalSeedPool.Claim(v); } void RefBump(Seed v) { v.refcnt += 1; } //push the HalfEdge into the ordered linked list of vertices void PQinsert(Halfedge he, Seed v, float offset) { he.vertex = v; RefBump(v); he.ystar = v.y + offset; Halfedge last = PQhash; Halfedge next; while ((next = last.PQnext) != null && (he.ystar > next.ystar || (he.ystar == next.ystar && v.x > next.vertex.x))) { last = next; } he.PQnext = last.PQnext; last.PQnext = he; PQcount += 1; } //remove the HalfEdge from the list of vertices void PQdelete(Halfedge he) { if (he.vertex != null) { Halfedge last = PQhash; while (last.PQnext != he) last = last.PQnext; last.PQnext = he.PQnext; PQcount -= 1; DeRef(he.vertex); he.vertex = null; } } bool PQempty() { return PQcount == 0; } Point PQ_min() { Point answer = _pointPool.Allocate(); answer.x = PQhash.PQnext.vertex.x; answer.y = PQhash.PQnext.ystar; return answer; } Halfedge PQextractmin() { Halfedge curr = PQhash.PQnext; PQhash.PQnext = curr.PQnext; PQcount -= 1; return curr; } void PQinitialize() { PQcount = 0; if (PQhash == null) { PQhash = new Halfedge(); } } void CleanupEdges() { _allEdges = null; } void PushGraphEdge(Seed s1, Seed s2, float x1, float y1, float x2, float y2) { GraphEdge newEdge = _graphEdgePool.Allocate(); // new GraphEdge(); newEdge.next = _allEdges; _allEdges = newEdge; newEdge.s1 = (T)s1.source; newEdge.s2 = (T)s2.source; newEdge.x1 = x1; newEdge.y1 = y1; newEdge.x2 = x2; newEdge.y2 = y2; } void out_triple(Seed s1, Seed s2, Seed s3) { // Debug.Log("OutTriple ()"); } void ClipLine(Edge e) { if (e.reg[0] == null) return; float x1 = e.reg[0].x; float x2 = e.reg[1].x; float y1 = e.reg[0].y; float y2 = e.reg[1].y; //if the distance between the two points this line was created from is less than the square root of 2, then ignore it if (Mathf.Sqrt(((x2 - x1) * (x2 - x1)) + ((y2 - y1) * (y2 - y1))) < _minDistanceBetweenSeeds) { return; } Seed s1, s2; if (e.a == 1.0 && e.b >= 0.0) { s1 = e.ep[1]; s2 = e.ep[0]; } else { s1 = e.ep[0]; s2 = e.ep[1]; } if (e.a == 1.0) { y1 = _perimeterYmin; if (s1 != null && s1.y > _perimeterYmin) { y1 = s1.y; } if (y1 > _perimeterYmax) { y1 = _perimeterYmax; } x1 = e.c - e.b * y1; y2 = _perimeterYmax; if (s2 != null && s2.y < _perimeterYmax) y2 = s2.y; if (y2 < _perimeterYmin) { y2 = _perimeterYmin; } x2 = (e.c) - (e.b) * y2; if (((x1 > _perimeterXmax) & (x2 > _perimeterXmax)) | ((x1 < _perimeterXmin) & (x2 < _perimeterXmin))) { return; } if (x1 > _perimeterXmax) { x1 = _perimeterXmax; y1 = (e.c - x1) / e.b; } ; if (x1 < _perimeterXmin) { x1 = _perimeterXmin; y1 = (e.c - x1) / e.b; } ; if (x2 > _perimeterXmax) { x2 = _perimeterXmax; y2 = (e.c - x2) / e.b; } ; if (x2 < _perimeterXmin) { x2 = _perimeterXmin; y2 = (e.c - x2) / e.b; } ; } else { x1 = _perimeterXmin; if (s1 != null && s1.x > _perimeterXmin) x1 = s1.x; if (x1 > _perimeterXmax) { x1 = _perimeterXmax; } y1 = e.c - e.a * x1; x2 = _perimeterXmax; if (s2 != null && s2.x < _perimeterXmax) x2 = s2.x; if (x2 < _perimeterXmin) { x2 = _perimeterXmin; } y2 = e.c - e.a * x2; if (((y1 > _perimeterYmax) & (y2 > _perimeterYmax)) | ((y1 < _perimeterYmin) & (y2 < _perimeterYmin))) { return; } if (y1 > _perimeterYmax) { y1 = _perimeterYmax; x1 = (e.c - y1) / e.a; } ; if (y1 < _perimeterYmin) { y1 = _perimeterYmin; x1 = (e.c - y1) / e.a; } ; if (y2 > _perimeterYmax) { y2 = _perimeterYmax; x2 = (e.c - y2) / e.a; } ; if (y2 < _perimeterYmin) { y2 = _perimeterYmin; x2 = (e.c - y2) / e.a; } } PushGraphEdge(e.reg[0],e.reg[1], x1, y1, x2, y2); } private void Voronoi() { PQinitialize( ); ELinitialize( ); NextSeed(); Seed new_seed = NextSeed(); Point newintstar = null; while (true) { if (!PQempty()) newintstar = PQ_min(); //if the lowest seed has a smaller y value than the lowest vector intersection, process the seed otherwise process the vector intersection if (new_seed != null && (PQempty() || new_seed.y < newintstar.y || (new_seed.y == newintstar.y && new_seed.x < newintstar.x))) { // new seed is smallest - this is a seed event Halfedge lbnd = ELleftbnd(new_seed); //get the first HalfEdge to the LEFT of the new seed Halfedge rbnd = lbnd.ELright; //get the first HalfEdge to the RIGHT of the new seed Seed bot = RightReg(lbnd); //if this halfedge has no edge, , bot = bottom seed (whatever that is) Edge e = Bisect(bot, new_seed); //create a new edge that bisects Halfedge bisector = HEcreate(e, le); //create a new HalfEdge, setting its ELpm field to 0 ELinsert(lbnd, bisector); //insert this new bisector edge between the left and right vectors in a linked list Seed p; if ((p = Intersect(lbnd, bisector)) != null) //if the new bisector intersects with the left edge, remove the left edge's vertex, and put in the new one { PQdelete(lbnd); PQinsert(lbnd, p, Distance(p, new_seed)); } lbnd = bisector; bisector = HEcreate(e, re); //create a new HalfEdge, setting its ELpm field to 1 ELinsert(lbnd, bisector); //insert the new HE to the right of the original bisector earlier in the IF stmt if ((p = Intersect(bisector, rbnd)) != null) //if this new bisector intersects with the { PQinsert(bisector, p, Distance(p, new_seed)); //push the HE into the ordered linked list of vertices } new_seed = NextSeed(); } else if (!PQempty()) // intersection is smallest - this is a vector event { Halfedge lbnd = PQextractmin(); //pop the HalfEdge with the lowest vector off the ordered list of vectors Halfedge llbnd = lbnd.ELleft; Halfedge rbnd = lbnd.ELright; //get the HalfEdge to the right of the above HE Halfedge rrbnd = rbnd.ELright;  Seed bot = LeftReg(lbnd); //get the seed to the left of the left HE which it bisects Seed top = RightReg(rbnd); //out_triple(bot, top, RightReg(lbnd)); //output the triple of seeds, stating that a circle goes through them Seed v = lbnd.vertex; MakeVertex(v); //set the vertex number - couldn't do this earlier since we didn't know when it would be processed EndPoint(lbnd.ELedge, lbnd.ELpm, v); //set the endpoint of the left HalfEdge to be this vector EndPoint(rbnd.ELedge, rbnd.ELpm, v); //set the endpoint of the right HalfEdge to be this vector ELdelete(lbnd); //mark the lowest HE for deletion - can't delete yet because there might be pointers to it in Hash Map PQdelete(rbnd); //remove all vertex events to do with the right HE ELdelete(rbnd); //mark the right HE for deletion - can't delete yet because there might be pointers to it in Hash Map var pm = le;   if (bot.y > top.y) //if the seed to the left of the event is higher than the seed { //to the right of it, then swap them and set the 'pm' variable to 1 var temp = bot; bot = top; top = temp; pm = re; } Edge e = Bisect(bot, top); //create an Edge (or line) that is between the two seeds. This creates //the formula of the line, and assigns a line number to it Halfedge bisector = HEcreate(e, pm); //create a HE from the Edge 'e', and make it point to that edge with its ELedge field ELinsert(llbnd, bisector); //insert the new bisector to the right of the left HE EndPoint(e, re - pm, v); //set one endpoint to the new edge to be the vector point 'v'. //If the seed to the left of this bisector is higher than the right //seed, then this endpoint is put in position 0; otherwise in pos 1 DeRef(v); //delete the vector 'v' //if left HE and the new bisector don't intersect, then delete the left HE, and reinsert it Seed p; if ((p = Intersect(llbnd, bisector)) != null) { PQdelete(llbnd); PQinsert(llbnd, p, Distance(p, bot)); } //if right HE and the new bisector don't intersect, then reinsert it if ((p = Intersect(bisector, rrbnd)) != null) { PQinsert(bisector, p, Distance(p, bot)); } } else break; } for (Halfedge lbnd = ELleftend.ELright; lbnd != ELrightend; lbnd = lbnd.ELright) { ClipLine(lbnd.ELedge); } } // return a single in-storage seed Seed NextSeed() { Seed s = null; if (_seedIdx < _userSeeds.Count) { s = _userSeeds[_seedIdx]; _seedIdx += 1; } return s; } } }