Tuesday, October 3, 2017

On Supposition of a single entendre.

Missing a double entendre is when, in social intercourse, there is another meaning upon the lips, that one fails to fully wrap their head around or penetrate the whole of the available depth, a sort of premature interpretation.

Within this oral intercourse,
There is a seeming, source
Of a premature interpretation.
Flip it with a second destination.
On those lips, left wanting,
of a deeper thrust,
a pair of content's taunting,
their points securely trussed.
Beyond the naked point's, another.
It's hard to grasp
the whole, of the penetrable depth.

When in oral intercourse there is pair of points upon the lips, yet a failure to grasp the whole of the penetrable depth.

Double Entendre: n. pair of material and both points are grasped, and the whole of available depth is penetrated.

Double Entendre: when there is considerable pair, and both points are grasped

--- My hope here was to make a good and quippy definition for what a double entendre is, but I dunno, these seem a bit lackluster.

Friday, September 22, 2017

Adding to my list of oddities in computer science.

CS folks are enamored of dividing 2D space in 2D space chunks? It makes all of the math needlessly harder, even if it makes the math-sense and understandability easier. You divide 2D space into two instances of 1D space. The algorithms don't require trees, you can still easily access the needed data in log(n) time, update them as easy as a sorted list can be updated, and with a bit of style you can easily prove points don't need to be checked. It's weird because no algorithms do this, but you can do an amazing amount of very simple math to solve all the traditional problems in computational geometry with simpler algorithms.

• You can build the space in d*n*log(n) time (sorting lists).
• With sorted lists of points you can insert in as easy as inserting into a list.
• You can remove as easily as removing from a list.
• You can find the nearest neighbor to a point in a short algorithm in log(n) time.
• You can find k nearest neighbors to a point in a similar short algorithm in ~k*log(k)*log(n) time.
• You can do basically all the AABB math quite easily too. You can easily find in n time the bounding boxes relevant to a point. And update that point very easily.
• You can find if a point is inside a polygon.
• You can find all points within an axis aligned rectangle in trivial time.

But the really really pressing bits of this is that categorically these algorithms are tiny. Like they don't take much work at all. They are exceptionally short. And the datastructure is what modern memory systems are optimized for so you won't be cache missing all the time. And it's so common it's implemented in like four lines of code. So why the hell are all games doing collision detection of divided up 2D space in 2D chunks or 3D chunks in 3D space? Also, these algorithms obviously scale really easily with the degree of dimensionality. They don't violate theoretical points though. If you do a Nearest Neighbor Search in 3D it's basically identical code with the steps as the 2D code but since we're dealing with 3D, it can easily end up checking most all the points anyway simply because you can't rule out the remaining checks as quickly.

I needed a nearest neighbor search for my android app to find the nearest point to a point and do this many many times in real time. But, when a point is moved it required a lot to fix the pre-processed datastructure since they were organized into trees so the nodes needed to be fiddled with etc. This allowed for nodes to be updated en masse, and the lists to simply be very quickly resorted in a trivial amount of time and perfectly ready for the next tick.

I hit upon this algorithm largely because I had also done considerable work with filling monotone polygons using a scanline, and used a sort of step-raytrace with line segments which is another brilliant algorithm (it's very similar to the good solution to the skyline problem), it's largely just a single list of all the points sorted along one axis. Then you scan through the list, keeping a working list of active line segments. This solves the perpendicular rays and finds all intersections of that perpendicular ray (it's literally the intersections of the active list of line segments) in fast enough time that a little android phone can do the ray traced lines in real time.

To speed up my attract tool (requires many nearest neighbor searches), I previously made an interesting nearest neighbor search with a point quadtree which equally used the same general idea that you could prove the invalidity of other parts of the tree by showing that the distance in just 1 dimension is greater than the shortest distance already found. I thought this was awesome as nobody seemed to have any nearest neighbor algorithms based on that rather rare datastructure.

But, if you could do this with a tree it would be much easier to do this with 2 different 1D sorted lists. Just binary search into the list, and go to each point in the +X, +Y, -X, -Y directions until the distance in just dX is greater than your best candidate so far.  You can also conclude things like if +X and -X are exhausted then there can be no closer point, as you proved all points exhausted (the points found in the other dimensions are going to be duplicates of the ones you ruled out). But, the point is implementing all of that is trivial compared to the other ways. And all the tricks in computational geometry are simply proving you don't have to check those other points, which is can be done with the same trick over and over, can this point further along this axis possibly be closer or included? For the K-nearest neighbor algorithm, you store the candidates in a heap sorted by distance and only compare the worst of them to the new potential candidates until just that one direction along is enough to be worse in which case no more points along that axis can possibly be better.

For Axis Aligned Bounding Boxes (AABB) you can rather simply add the start points and end points of the shapes. Then when you cross a threshold by traveling along the axis (only going to the next relevant point always as that's how the traversal works), you can trivially check if the relevant point is within that bounding box. So you can rather easily linearly iterate into the list and you'll know exactly which bounding boxes that point is within tracking them basically exactly as one would the skyline problem. Then moving that point within the space equally quite quick and just means updating any active elements as you cross thresholds (and if you don't cross any relevant boundaries, changing nothing at all). Equally it solves a number of common problems in collision detections like not updating something that moved in time to see that it struck something. As the object moves it needs to find it's place in the lists, which means you must process each element in order, which means you know if you hit anything, regardless whether you would now be completely on the other side of that object now.

I totally understand that it's easier to think in 3d space in 3d and 2d space in 2d so when you're partitioning space you are wildly more likely to divide the space in ways that does not screw up the dimensionality. It's easy to think of dividing a square into two half-squares but it's a bit weird to divide it into two equally lengthed lines. But the math is easier if you divide it into two lines for obvious reasons, even if it's harder to conceptualize.

Wednesday, June 28, 2017

A conclusion shopping around for a theory.

You sir are a donkey fucker. Okay, maybe you're not a donkey fucker, since there's no evidence of that. You sir, are a chicken fucker. Wait, no evidence there either. You sir are a squirrel fucker. -- Look, I have my conclusion, you fuck some kind of animal and when that type of animal is shot-down, I'm going to shop around for another type of animal. Because that's how this shit works apparently. --- Make some shit up, when that gets demolished, make different similar shit up, with generally the same conclusion.
You catch the analogy there goat-fucker?﻿

Tuesday, June 27, 2017

Approximating an arc with cubic bezier curves, yet another metric.

C = 0.552

Really,
C = 0.55201372171

The idea is that rather than minimize the extrema of the error we can instead minimize the total error. Graph out formula for the error and calculate what would be under the curve as a whole. So rather than positive and negative error equal it would seek to minimize the error overall. It's not too different from the other metrics. But, rather than trying to keep the first pixel from being wrong, it tries to keep the pixels as a whole from being wrong for as long as possible. It's different than the number for the extrema because oddly the graph is symmetric at 0.5. It's not symmetric with regard to the y axis, and has different amounts areas of positive and negative and the error shifts as the value of c shifts.

Mortensen's value. Even extrema point.
0.55191502449 at 0.0000001 increments
Total error:1180.57375326880434046054832219597498652621901536765190
Samples: 10000001

My calculated value, brute force.
0.55201372171 at 0.0000001 increments
Total error:1159.83397426356807198675826572857280613256846239728729
Samples: 10000001

Naive geometric value, with purely positive error ((4/3)*(sqrt(2) - 1).
0.552284749 at 0.0000001 increments
Total error:1401.62730758375303300973494715872257045283590056376636
Samples: 10000001

As we can see the total error over a million samples gives us an improvement of 20. Compared to the naive value for all error being positive we gain 242 which is better than Mortensen's gain of 222.

We're talking literally fractions of percents here, but this number has another advantage. You can call it .552 which is a much shorter fraction. Besides the more slices I do the more I narrow in on the value, but it's still a bit off. I'm pretty sure on most of those digits but without actually doing the calculus I can't get much better than that.

0.552 at 0.0000001 increments
Total error:1160.26180861006145200701189677079769078925976995284068
Samples 10000001

You'll notice my value is only 0.4279 different than that in total error over a million samples. And since that truncation lowers it, it will only make it a bit closer to the even extrema point, which is a fine metric.

P_0 = (0,1), P_1 = (c,1), P_2 = (1,c), P_3 = (1,0)
P_0 = (1,0), P_1 = (1,-c), P_2 = (c,-1), P_3 = (0,-1)
P_0 = (0,-1), P_1 = (-c,-1), P_2 = (-1,-c), P_3 = (-1,0)
P_0 = (-1,0), P_1 = (-1,c), P_2 = (-c,1), P_3 = (0,1)
with c = 0.552

Under this metric the cubic value something like: 0.92103099 which might be more important because really flattening out the error might matter in that case a lot more than in the cubic case. I'll call it 0.921

Friday, June 16, 2017

Using a quad to emulate an arc, solving for C.

Basic geometry allows one to solve for the best solution to use a value of C to make a bezier curve close to an arc. The naive solution using Geometry is

This is the solution to the question of we have anchor points on the curve and the curve touches the circle at the center, what value of C for a control point on the quadrant curve (0,1),(C,C),(1,0). Gives us the best fit to the curve.

However Mortenson points out that we are better if we minimize the error rather than allow all the error to be on one side of the circle.

This issue allows a few more percent with the Cubic Bezier form. But, it's more important if we're using one fewer control points. The same is also true at one fewer yet. If we have a square, what square looks most similar to a circle.

The if the naive geometry solution is the same we get:

. Where the corners touch the circle but do not exceed it. The other way you could do it is to have them only touch at the corners and just make the curve larger than the circle.

And finally we have Mortensen's solution to it, by making the metric for closest be the average error across the entire graph.

Well, solving this for 1 control point means doing the same thing he did. Which isn't super-trivial because it means calculating min and max error and adjusting various things. So I wrote a program to do it.

C= 0.92519820883625651516056680057654772234129017577799879993432335355559372311727101122467939843041708056568481020881580812152533756252840773920708961655740969447362217856208142868847332990974178763987890

Having the program I refigured it for Cubic:
0.55191502449351057074356272279256664233618039472430889733698053746758709885277817592685338345358001614300815257463095148547403466508799941938848910944812198495136713728128014911200347760723733292314480

Having a deviation in both directions of: ±0.00019607646987687817401874512914923 ....

Mortensen gave this as,
0.551915024494

Since we might well be using doubles I'd give it as:
0.5519150244935106

M0,1
C0.5519150244935106,1 1,0.5519150244935106 1,0
C1,-0.5519150244935106 0.5519150244935106,-1 0,-1
C-0.5519150244935106,-1 -1,-0.5519150244935106 -1,0
C-1,0.5519150244935106 -0.5519150244935106,1 0,1

And the c value for the quad bezier curve as:
0.9251982088362565

M0,1
Q0.9251982088362565 0.9251982088362565 1,0
Q0.9251982088362565 -0.9251982088362565 0,-1
Q-0.9251982088362565 -0.9251982088362565 -1,0
Q-0.9251982088362565 0.9251982088362565 0,1

This is much better than the more naive value: 0.91421356237 which is effectively unusable. While Mortensen's use for the cubic is great, it changes the quad naive to almost usable, generally not, but *almost* usable. The Mortensen-optimized value for quads is off by max 0.007767318 whereas the naive value is off by 0.010781424258 which is 28% better. Hm. That's the same value Mortensen got for the cubic.

Saturday, June 3, 2017

1 dimensional fractals.

1 dimensional fractals all look the same. That's why they are fractals. Get it? Because they are all lines. And fractals look the same. And all 1d anything is a line which looks like all the other lines. HAHAHAHAHAHA!

Thursday, May 25, 2017

Entirely Hex Words

My favorite: effedface. Though 0xeffdface would fit in an int. 0xFADEDBEE 0xBEDAFFED 0xDECAFBAE 0xFEEDFACE 0xDEFACADE

32 bit hexwords.

abasedly aba5ed17
abatable aba7ab1e
abatises aba715e5
abbacies abbac1e5
abbatial abba71a1
abbesses abbe55e5
abettals abe77a15
abigails ab16a115
ableists ab1e1575
abscised ab5c15ed
abscises ab5c15e5
abscissa ab5c155a
abseiled ab5e11ed
accessed acce55ed
accesses acce55e5
accidias acc1d1a5
accidies acc1d1e5
accosted acc057ed
acetylated ace7718d
acetylates ace77185
acetylic ace7711c
acidoses ac1d05e5
acidosis ac1d0515
acidotic ac1d071c
acolytes ac0177e5
aecidial aec1d1a1
affected affec7ed
affiliated aff1118d
affiliates aff11185
afflicts aff11c75
affordable af4dab1e
affordably af4dab17
afforested af4e57ed
agiotage a6107a6e
agitable a617ab1e
agitatedly a6178d17
albedoes a1bed0e5
alcaides a1ca1de5
alcaldes a1ca1de5
alcaydes a1ca7de5
aldolase a1d01a5e
alfalfas a1fa1fa5
algicide a161c1de
algidity a161d177
algology a1601067
alliable a111ab1e
allodial a110d1a1
allotted a11077ed
allottee a11077ee
allseeds a115eed5
alogical a1061ca1
asbestic a5be571c
ascetics a5ce71c5
asocials a50c1a15
assagais a55a6a15
assailed a55a11ed
assegais a55e6a15
assessed a55e55ed
assesses a55e55e5
assisted a55157ed
associated a550c18d
associates a550c185
assoiled a55011ed
astasias a57a51a5
astilbes a5711be5
atalayas a7a1a7a5
attaboys a77ab075
attendees a710dee5
attested a77e57ed
atticist a771c157
babbitts babb1775
babesias babe51a5
babydoll bab7d011
babysits bab75175
bacalaos baca1a05
baccalas bacca1a5
bagasses ba6a55e5
bagatelles ba6811e5
baggages ba66a6e5
baggiest ba661e57
bailable ba11ab1e
bailiffs ba111ff5
ballasts ba11a575
ballboys ba11b075
balletic ba11e71c
balliest ba111e57
ballista ba11157a
balloted ba1107ed
basaltes ba5a17e5
basaltic ba5a171c
baseball ba5eba11
baseless ba5e1e55
basicity ba51c177
basidial ba51d1a1
basified ba51f1ed
basifies ba51f1e5
basilect ba511ec7
basilica ba5111ca
basseted ba55e7ed
bassetts ba55e775
bassists ba551575
bastiles ba5711e5
bastille ba57111e
batistes ba7157e5
battalia ba77a11a
battiest ba771e57
baysides ba751de5
beasties bea571e5
beatable bea7ab1e
beatific bea71f1c
beatless bea71e55
bebloods beb100d5
bedabble bedabb1e
beddable beddab1e
bedotted bed077ed
bedsides bed51de5
beefalos beefa105
beefiest beef1e57
beefless beef1e55
befitted bef177ed
befleaed bef1eaed
befogged bef066ed
befooled bef001ed
begalled be6a11ed
belittle be11771e
bellboys be11b075
bellcast be11ca57
beltless be171e55
besieged be51e6ed
besieges be51e6e5
besotted be5077ed
biacetyl b1ace771
biasedly b1a5ed17
bibelots b1be1075
biblical b1b11ca1
biblists b1b11575
bicycled b1c7c1ed
bicycles b1c7c1e5
bicyclic b1c7c11c
biddable b1ddab1e
biddably b1ddab17
bifacial b1fac1a1
bifidity b1f1d177
bifocals b1f0ca15
bigfoots b16f0075
bilabial b11ab1a1
bilgiest b1161e57
billable b111ab1e
billeted b111e7ed
billetee b111e7ee
billfold b111f01d
bilsteds b1157ed5
bioassay b10a55a7
biocidal b10c1da1
biocides b10c1de5
biocycle b10c7c1e
biogases b106a5e5
biologic b101061c
biolyses b10175e5
biolysis b1017515
biolytic b101771c
biosolid b105011d
biotical b1071ca1
biotites b10717e5
biotitic b107171c
biscotti b15c0771
bisected b15ec7ed
bistable b157ab1e
biteable b17eab1e
bitsiest b1751e57
bittiest b1771e57
blasties b1a571e5
blastoffs b1a52ff5
bloodied b100d1ed
bloodies b100d1e5
bloodily b100d117

Hex words, as in words that can be spelled purely in hex.`

aa aa
aal aa1
aalii aa111
aaliis aa1115
aals aa15
aas aa5
ab ab
aba aba
abaca abaca
abacas abaca5
abaci abac1
abaft abaf7
abas aba5
abase aba5e
abased aba5ed
abasedly aba5ed17
abases aba5e5
abasia aba51a
abasias aba51a5
abatable aba7ab1e
abate ab8
abated ab8d
abates ab85
abatis aba715
abatises aba715e5
abattis aba7715
abattises aba7715e5
abaya aba7a
abayas aba7a5
abba abba
abbacies abbac1e5
abbacy abbac7
abbas abba5
abbatial abba71a1
abbe abbe
abbes abbe5
abbess abbe55
abbesses abbe55e5
abbey abbe7
abbeys abbe75
abbot abb07
abbotcies abb07c1e5
abbotcy abb07c7
abbots abb075
abdicable abd1cab1e
abdicate abd1c8
abdicated abd1c8d
abdicates abd1c85
abed abed
abele abe1e
abeles abe1e5
abelia abe11a
abelias abe11a5
abet abe7
abets abe75
abettal abe77a1
abettals abe77a15
abetted abe77ed
abide ab1de
abided ab1ded
abides ab1de5
abigail ab16a11
abigails ab16a115
abilities ab11171e5
ability ab11177
abiological ab101061ca1
abioses ab105e5
abiosis ab10515
abiotic ab1071c
abiotically ab1071ca117
ablate ab18
ablated ab18d
ablates ab185
able ab1e
abled ab1ed
ablegate ab1e68
ablegates ab1e685
ableist ab1e157
ableists ab1e1575
ables ab1e5
ablest ab1e57
ably ab17
abo ab0
abode ab0de
aboded ab0ded
abodes ab0de5

Wednesday, January 4, 2017

Reinventing the world without reinventing the wheel

I just made this up. Dibs.

"Reinventing the world without reinventing the wheel" - Tatarize.