Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 10 May 2006
Offline Last Active Sep 07 2013 03:50 PM

Topics I've Started

convex hull 3d triangles

27 June 2012 - 05:22 PM

Trying to work this through myself without looking at other complete algorithms.

Taking set of 3d points, and computing convex hull formed by triangles.

What I have so far (as a candidate solution; doesn't need to be more optimal), based on quick-hull ideas:

fun convex_hull(points) {
	// cannot form a hull
	if (points.length < 3) return []

	// trivial; degenerate hull formed by points
	if (points.length == 3) return [points, [points[0], points[2], points[1]]]

	sort points lexicographically along axis (1, 0, 0)
	p0 = points[0]
	p1 = points[sorted.length - 1]
	p2 = point furthest from line containing p0, p1

	fun recurse(points, p0, p1, p2) {
		n = normal(p0, p1, p2)
		discard p from points where p in [p0, p1, p2] or (p-p0) dot n < 0

		if (points.length == 0) return [p0, p1, p2]
		else {
			 sort points lexicographically along axis n
			 return recurse(points, p0, p1, p3) concat
					recurse(points, p1, p2, p3) concat
					recurse(points, p2, p0, p3)

	candidates = recurse(points, p0, p1, p2) concat recurse(points, p0, p2, p1)

    // remove any triangles not part of hull
	discard (p0, p1, p2) from candidates where exists p in points s.t (p - p0) dot normal (p0, p1, p2) > 0

    // remove any degenerate triangles (still allowing 0-area triangles).
    discard (p0, p1, p2) from candidates where p0 == p1 || p0 == p2 || p1 == p2

	return candidates;

Now, this works for some test cases (including simple (perfect) boxes) in that it gives me a set of triangles which as a whole can unify to give the convex hull, but i'm interested in how you can take this further to produce a minimal set of triangles as many of the triangles returned by this implementation will be overlapping.

I imagine that without drastically changing the algorithm, you could identify those triangles that are coplanar, collect vertices, order by angle in plane and do a trivial triangulation as a fan. But I would worry about numerical issues with determining coplanar planes in the general case here.

I've so far avoided that I can tell numerical issues by doing a lexicographical sort (which in the general case involves computing a tangent and bitangent for the given axis to additionally project onto for the sorting if projections on primary axis are equal).

compute bounds on total value (intersecting plane with box in N dimensions)

31 January 2012 - 08:50 AM

(NOT homework, don't worry)

We have a number payments of which we don't know the exact value.
And the number of payments which fit into a given disjoint set of ranges together with the percentage of the total value of payments, that payments from this range provide.

How can we compute the bounds on the total sum of payments?

For instance say that we know:

there are 4 payments in the range 0 <= x < 5
and 2 payments in the range 5 <= x < 20
and 2 payments in the range 20 <= x < 100

and that the payments in the range 0 <= x < 5 provide 10.7% of the total
payments in the range 5 <= x < 20 provide 27.7% of the total
and payments in the range 20 <= x < 100 provide 61.6% of the total

I think it should be clear we don't actually care about the value of specific payments, only their average within the range so that we can reason about the total value of payments in a given range, so that we would have:

0 <= X < 20
10 <= Y < 40
40 <= Z < 200

and that X = 0.107(X+Y+Z), Y = 0.277(X+Y+Z), Z = 0.616(X+Y+Z)

and we want to compute the upper and lower bounds of X+Y+Z.

It seems to me that the 3 equalities define a plane like:
(1/0.107 - 3)X + (1/0.277 - 3)Y + (1/0.616 - 3)Z = 0

and so we can find the upper/lower bounds of the total by intersecting the plane with the box defined by the inequalities, and at each interesting point (the lines intersecting the box) compute the total value and find the min/max of those to get the upper and lower bounds.

This would extend to any number of ranges in increasing dimensions, my only issue now is actually going about implementing this.

Not sure how to name this. bitfields and searches.

25 January 2012 - 01:05 PM

a set of listeners like:
Listener = { { Type } , { Type } )

and a set of objects like:
Object = { Type }

The problem:


Given two Object's, does there exist a listener which is valid for the pairing of types, where a set of object types xs, is valid for a set of listener types ys if xs and ys have a non-empty intersection.

~ so for example:

listener = ( {A,B,C}, {D,E} )

object1 = {A,D}
object2 = {B}

then the listener is valid for the pairing of object1/object2 since {A,D} n {D,E} != 0, and {B} n {A,B,C} != 0


We can encode the set of types in a bitfield (assuming for now that we don't care about the limited number of types such an encoding would allow) which makes it very easy to check for the 'validitity' of a pairing, (x&y)!=0 replacing xs intersect ys != 0

But the main issue is how can we store the listeners to make such a search effecient? (Compared to say, having a list of all listeners and iterating them checkign each one to see if it's valid)

Decompose complex polygon to disjoint simple subsets

01 September 2011 - 04:20 PM

I'm looking to decompose a complex polygon (defined by a single closed vertex loop) into it's disjoint simple subsets based on the even-odd rule to what constitutes being inside/outside said complex polygon.

I already have a typical n.log(n) implementation to find all the intersections of said polygon, it is the strategy to take in seperating the regions at the intersections that is eluding me so as to fit my requirements

Looking for a good hash for 2 integers

21 August 2011 - 05:08 PM

I have two integers (incremented from 0, so not uniformly distributed in general) which I want to combine into a single integer in a small range (0 -> 0xffff) to best avoid hash collisions.

I've tried different things like: ((~a)-b)&0xffff, (a*106039+b)&0xffff, etc. but I can't seem to get any better than an 80% collision rate, even if both integers are well below 0xffff

I do want this hash to be as lightweight as possible also as it's in a performance critical area

--- edit:

seems i made a big error in determining the collision rate, it's actually more like 1.3%