I x number of days I’m offering the maximum bounty because I have been stuck on this single problem for 6+ months. I keep thinking I have it close just for an edge case to bite me in the ___ later. I need to find a solution that will always work…
The Objects
The only objects that exist in the world are polygons with a height. The polygon is defined by a position, with vertices as offset points from its position:
{
position: {
x: null,
y: null,
z: null
},
hitbox: {
vertices: [
[x,y],[x,y],[x,y]
],
height: null,
search_distance: null, // maximum possible distance across a polygon
},
max_vertice_y: null, // furthest top vertice y position
min_vertice_y: null // lowest bottom vertice y position
}
I have an algorithm that splits polygons into smaller polygons that prevent the scenario of a polygon being in front of, and behind another polygon. So for this example lets assume that all polygons will only exist in front of or behind any other.
Contrary to standard positioning, this world treats lower y values as being at the bottom of the screen and larger values being further towards the top
The Problem
It appears that every sort method I have come up with in the past and the current one I show below all share the same issue … a polygon (A) may be entirely below another (B), and therefore printed before it. However, later in the list a polygon (C) is found that is printed before (B), and after (A) because of the z position and height of (C) paired with the y position of (A). I can’t seem to create a method that preserves the truth of one polygon compared to another without affected the outcome of polygons sorted after it. I’m researching a topological sort at the moment but I can’t seem to define what a “dependency” is. I feel each polygon only has a list of everything before and after, which can change later if it appears before a polygon that itself appears before something in the “after” list of its predecessor.
Because of this I have tried a variation of merge sort, but my truths (conditions) break because of the situation mentioned above.
My most recent approach
function sortTerrain() {
// terrain_ground and terrain_decor are objects with the properties mentioned above
// create working "grab from list"
let comp_work = [...terrain_ground, ...terrain_decor];
// create sorted list
let working = [comp_work.shift()];
// while grab list isnt empty, take from and insert into sorted list
while (comp_work.length > 0) {
let current = comp_work.shift();
// get index of insert position
let insert = -1;
// start from the furthest forward printed object in the sorted list and work backwards until a truth is found
// **this was originally working from the start to end under the condition of when a truth is not found, exit and use last saved index ... this WORKS but, not as well as looking for a single truth. both still create the issue mentioned above
for (let i=working.length-1; i>=0; i--) {
let compare = working[i];
if (sameZPlane(current, compare)) {
// on same z plane, sort by y
// if guaranteed infront of
if (current.max_vertice_y < compare.min_vertice_y) {
insert = i;
break;
}
// if overlap on y
if (current.min_vertice_y < compare.max_vertice_y && current.max_vertice_y > compare.min_vertice_y) {
// check for ray cast to determine current is in front of compare
// also check rear-forward using rayCastInfrontOf(x, x, true) in case rear is smaller than the gap between a vertice pair of the front polygon
if (rayCastInfrontOf(current, compare) || rayCastInfrontOf(compare, current, true)) {
insert = i;
break;
} else if (current.min_vertice_y < compare.min_vertice_y) {
// if not, then check if current min is in front of compare min
insert = i;
break;
}
}
} else {
// sort by z index
if (current.position.z > compare.position.z) {
insert = i;
break;
} else if (current.position.z == compare.position.z) {
// shared z position yet failing sameZPlane is a 0 height terrain, sort by height
// THIS IS UNLIKELY TO CONTRIBUTE TO ANY PRINT ERRORS
if (current.hitbox.height > compare.hitbox.height) {
insert = i;
break;
}
}
}
}
// no insert location found, add at start of the stack
if (insert == -1) {
working.unshift(current);
} else {
// insert after last found index
working.splice(insert+1, 0, current);
}
}
}
function expandTerrainVertices() {
// can of worms
}
function rayCastInfrontOf(front, rear, reverse = false) {
// allow reverse check by sending truth boolean to reverse param
// safe ray length
let ray = (front.hitbox.search_distance + rear.hitbox.search_distance) * (reverse ? -1 : 1);
// shrink vertices of "front" so that rays casted will not give false positive to polygons sharing a vertice point + position value
let shrink_front_vertices = expandTerrainVertices(front, -1);
// run ray from all vertice points of front backwards (or rear forwards if reverse param is true) and see if it intersects any vertice connections in rear
// "middle" is used to get next safe vertice pair
let middle = 0;
for (let i=0; i<shrink_front_vertices.length; i++) {
middle = i+1;
if (middle == shrink_front_vertices.length) {
middle = 0;
}
// cast from middle point of vertices rather than from the vertice position itself, this is safer
let middle_point = {
x: (front.position.x + shrink_front_vertices[i][0] + front.position.x + shrink_front_vertices[middle][0])/2,
y: (front.position.y + shrink_front_vertices[i][1] + front.position.y + shrink_front_vertices[middle][1])/2
}
// loop rear vertice pairs
let next = 0;
for (let i2=0; i2<rear.hitbox.vertices.length; i2++) {
next = i2+1;
if (next == rear.hitbox.vertices.length) {
next = 0;
}
// check if ray cast from the middle position of the "front" polygon intercepts any vertice pairs on "rear" polygon
if (intercepts(
middle_point.x, middle_point.y,
middle_point.x, middle_point.y + ray,
rear.position.x + rear.hitbox.vertices[i2][0], rear.position.y + rear.hitbox.vertices[i2][1],
rear.position.x + rear.hitbox.vertices[next][0], rear.position.y + rear.hitbox.vertices[next][1]
)) {
return true;
}
}
}
return false;
}
// get intersection point of two lines
function intercepts(x1,y1,x2,y2,x3,y3,x4,y4) {
let s1_x = x2 - x1
let s1_y = y2 - y1
let s2_x = x4 - x3
let s2_y = y4 - y3
let s = (-s1_y * (x1 - x3) + s1_x * (y1 - y3)) / (-s2_x * s1_y + s1_x * s2_y);
let t = ( s2_x * (y1 - y3) - s2_y * (x1 - x3)) / (-s2_x * s1_y + s1_x * s2_y);
if (s >= 0 && s <= 1 && t >= 0 && t <= 1) {
return [precise(x1 + (t * s1_x)), precise(y1 + (t * s1_y))]
}
return false
}
function sameZPlane(a, b) {
let a_top = precise(a.position.z + a.hitbox.height);
let b_top = precise(b.position.z + b.hitbox.height);
if (
(a_top > b.position.z && a.position.z < b_top) ||
(b_top > a.position.z && b.position.z < a_top)
) {
return true;
}
return false;
}
