No Pity for the Masses

The Turing Test is well known in the computer science field. It’s a proposal for a test that asks whether a computer can demonstrate intelligence. You see, despite my grandmother’s adorable assumption that her computer knows everything about her, computers only know what you tell them. On top of that they can only act as they are programmed, for the most part. AI has come a long way but it’s still a far cry from skynet.

If you follow the wiki link above for the Turing Test and follow it down to ‘Weaknesses’ you’ll see the biggest problems: humans are dumb, fallible, and irrational. How do you train something coached in logic to be illogical? This isn’t Star Trek IV: The Voyage Home, the computer isn’t going to suddenly have an emotional moment after saving the whales. You could argue that a sufficiently powerful computer (think Hitchhikers Guide) could account for all possibilities but this isn’t the reality in which we live… yet.

Technology will continue to blur the line between human and machine but not in the ways people think. If the Turing Test was quantifiable lets say the current state is 10 out of 100. Lets also say that the test output is filtered using a language to text msg. parser that communicates via cell phone with 15-20 year olds. It has been shown time and again the best way to simulate human behavior is to introduce failure. For example replace every “the” with ‘teh’ to simulate poor typing skills. All of us use cues like these to bucket our social hierarchy. By translating proper English to acronyms and teen colloquialisms we add another layer of obfuscation to a computer’s output. This additional layer blurs our AI’s speech such that the score of 10 of 100 above becomes 20 of 100 without changing the response set.

For Example:

Computer: I am having a nice day outdoors.
Conversion: gr8 day 2b out

Alright so I missed the text msg. generational mark, cut me some slack on the bad example. I text as much as the next kid but I prefer full sentences (thanks to my full qwerty keyboard.) I still punctuate my instant msgs. The point is apparent though. As an end user if you weren’t given clues as to the authors identity I would contend that most would say the converted text is from a real person.

It will get easier to simulate teen behavior the more prevalent social networking becomes in our daily lives. Information, language, & pictures are all readily available to the public. What was once difficult to quantify, teen behavior, is now open to the world. It will be much simpler to spoof an awkward teen than a philosopher. Like computers most highschoolers can’t discuss the human condition on any but the most rudimentary levels.

So be warned, when the end is nigh and it will come as a text msg: “All your base are belong to us”

Now that our term is over I can post some of my code from my computer graphics project. I’m keeping the blocked access to my school account for future projects so you’ll need to use the direct link: http://www.daksystems.net/svn/public/WPI/CS543/

Login/Pass:
login: Guest
password: guest

The folder is accessible like any other in my repo.

What’s of interest? Take a look at the DakGen folder. Our project for fall term was to create a software implementation of OpenGL. This includes a full rendering pipeline from raw 3D data to 2D screen coordinates from an arbitrary camera in space. To affect this type of view I implemented the following features:

1. Camera::LookAt(oglCamera::lookAt) – Similar to ‘gluLookAt’ function found in Mesa or Glut.   This allows the user to specify an arbitrary position in space from which to look.
2. Perspective Projection Matri(oglCamera::setProjection): We create both parallel and perspective projection matrices.  Currently only perspective is set up to work, parallel was disabled for my final project.
3. Perspective Division(oglCamera::setProjection):  In order to speed up clipping we normalize our data to the range -1 to 1 in all dimensions.  Our clipping algorithm is greatly simplified in that it is a single dimension problem now.
4. Clipping(oglGeomMgr::clipTriByPlane):  Clipping was actually pulled due to a glitch.  The code is still there for you to look at.
5. Culling(oglGeomMgr::cull_back_faces): Here we remove any faces not facing the user.  It should be noted that this function took on a life of it’s own.  cull_back_faces() basically controls the entire pipeline.  It chooses what faces are visible, converts them to camera UVN coordinates, clips them, and performs lighting calculations.
6. Phong Reflectivit(oglGeomMgr::phong_reflect):  What 3D engine would be complete without shading and reflectivity?  Because we did this in software I only ever tested a single light source.  It is possible to calculate other lights simply by iterating through them but this could get expensive.  Phong reflectivity is calculated for every single non-zero z-buffer pixel.

oglGeomMgr handles the geometry as well as the render pipeline. It shouldn’t but I ran out of time. oglCore handles setting up the projects. Take a look at oglCore::project_7() for an idea of how I set up my environment. There are other pieces to this puzzle like 2D scan filling, a pixel buffer, z-depth buffer(for testing overlap), and many other little functions necessary to get this up and running.

The engine will support multiple objects with their own sets of polygons. If you follow project 7′s setup function you’ll get an idea of how I pass in the data. I don’t recommend using the add_face function of oglGeomMgr. This was written in the early stages of development and was superseded by the add_verts and add_faces functions. Just to make life easier for me.

Additionally it should noted that the code is based off of my OgreGui framework, an empty wrapper for Ogre3D using Windows Forms. Nothing fancy.

No fanfare, no lengthy preamble, just the code to a bezier patch generator:

// Bezier.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <3DIO/3DIO.h>
#include <vector>
#include <string>
 
using namespace tdio_library;
using namespace std;
 
void create_patch(float step);
void save_patch(const string &name);
void load_bez(const string &name);
 
vector<vector3> pts;
vector3 ctrlPts[4][4];
vector<std::vector<int>> faces;
 
int main(int argc, char* argv[])
{
	load_bez("config.txt");
	if(argc >= 2)create_patch(atof(argv[1]));
	else create_patch(0.2);
 
	save_patch("test.obj");
	return 0;
}
void load_bez(const string &name){
	FILE *stream = fopen(name.c_str(),"r");
	char buffer[256];
	int ct = 0;
	while(!feof(stream)){
		if(fgets(buffer,256,stream)==NULL)break;
 
		float x[4],y[4],z[4];
		char ch;
		if(buffer[0] == 'c'){
			sscanf(buffer,"%c %f %f %f %f %f %f %f %f %f %f %f %f",&ch,&x[0],&y[0],&z[0],&x[1],&y[1],&z[1],&x[2],&y[2],&z[2],&x[3],&y[3],&z[3]);
			ctrlPts[ct][0] = vector3(x[0],y[0],z[0]);
			ctrlPts[ct][1] = vector3(x[1],y[1],z[1]);
			ctrlPts[ct][2] = vector3(x[2],y[2],z[2]);
			ctrlPts[ct][3] = vector3(x[3],y[3],z[3]);
			ct++;
		}
 
		if(ct >= 4)break;
	}
	if(ct != 4){
		printf("  - Warning, read %d control lines.  Should be 4\n",ct);
	}
	fclose(stream);
}
void save_patch(const string &name){
	FILE *stream = fopen(name.c_str(),"w");
	for(int v = 0; v < pts.size(); v++){
		fprintf(stream,"v %f %f %f\n",pts[v].x,pts[v].y,pts[v].z);
	}
	for(int f = 0; f < faces.size(); f++){
		fprintf(stream,"f %d %d %d\n",faces[f][0]+1,faces[f][1]+1,faces[f][2]+1);
	}
	fclose(stream);
 
}
vector3 get_bez_pt(float u, float v){
	double tmp = 0;
	double c[4] = {1,3,3,1};
	vector3 ret(0,0,0);
	for(int i = 0; i < 4; i++){
		for(int j = 0; j < 4; j++){
			tmp = c[i]*c[j] * pow(u,i) * pow(1-u,3-i)*pow(v,j)*pow(1-v,3-j);
			ret.x += ctrlPts[i][j].cell[0] *tmp;
			ret.y += ctrlPts[i][j].cell[1] *tmp;
			ret.z += ctrlPts[i][j].cell[2] *tmp;
		}
	}
	return ret;
}
void create_patch(float step){
	printf("-- Create Patch--\n");
	printf("  - Step: %f\n",step);
 
	for(float x = 0; x < 3; x+=step){
		for(float z = 0; z < 3; z+=step){
			vector3 pt = get_bez_pt(x/3,z/3);
			pts.push_back(pt);
		}
	}
	printf("  - nPts: %d\n",pts.size());
 
	int width = (float)(3.0f/step + 1.0);
	int height = width;
 
	printf("  - Height/Width: %d\n",height);
	int f = 0;
	for(int v = 0; v < pts.size(); v++){
		if(v+width+1 >= pts.size())break;
 
		if((v+1) % (int)width != 0 || v ==0){
			std::vector<int> tmp;
			faces.push_back(tmp);
 
		        faces[f].push_back(v);
			faces[f].push_back(v+1);
			faces[f].push_back(v+width);
			f++;
 
			faces.push_back(tmp);
			faces[f].push_back(v+1);
			faces[f].push_back(v+width+1);	
			faces[f].push_back(v+width);
 
			f++;
		}
	}
	printf("  - %d faces created\n",faces.size());
}

The 3DIO.h file can be found my open source repository. The function ‘create_patch()’ creates a uniform patch of triangles between 0 & 3 in the X and Z axes. Gradients should be chosen to be between this range, I recommend 0.09. Control points are loaded in the function ‘load_bez()’ from a configuration file that looks like so:

#row 0
c 0 5 0 0 0 1 0 0 2 0 0 3

#row 2 of control pts
c 1 0 0 1 10 1 1 -15 2 1 0 3

#row 3 of control pts
c 2 0 0 2 -5 1 2 25 2 2 0 3

#row 4 of control pts
c 0 0 0 3 0 1 3 0 2 3 0 3

Each row controls 4 control points. You can ignore the ‘c’ value and concentrate on the following 16 floating point values. Like so: c x1 y1 z1 x2 y2 z2…… I recommend modifying the Y values first. Messing with X/Z can have weird consequences. Output is saves as a very basic .obj file.

The code, as always, is provided “as is”, with little explanation. I suggest reading up on Bezier patches to get an idea of what the code is doing. I’m happy to answer questions like usual but do your homework.

The picture above takes you to a wicked funny comic over on vgcats, a favorite web comic of mine. And how amazingly accurate is his portrayal of your digital cohorts. Somewhat low on life and standing in flesh eating acid? God yes, I can haz ‘teh healz’ please? Or maybe I’m standing on the ledge of a burning apartment building. What an epically awesome time to heal.

The game focuses on real players working together, I get that. But why punish us with brutally dumb AI? At least give it some semblance of realism. I’m used to be ignored by people online. Version 1.1a of the AI should feature obnoxious tween taunts that call in to question my sexuality all while ignoring anything related to “teamwork.” I’m familiar with that style of game play.

Speaking of L4d2, apparently the first round of aim bots and speed hacks are out. Yay! Punk Buster was nice for awhile but it seems time for a new wave of anti-cheat software. With something as obvious as a speed hack I’m surprised the system doesn’t pick it up. One of my fellow players said it best, that it makes the win that much sweeter when you are good enough to out play a cheater with an obvious advantage. Still it does make me a little grump, it ruins what should be a good time by all.

CGAL has an incredibly high learning curve, not helped in any way by the obtuse documentation and the dearth of examples. I’m not arguing that CGAL isn’t an amazing(free) tool but there is something to be said for over engineering a problem.

Ah but you didn’t stop here for my empty words. No, you came here for free code. I see your game and I’ll not dance for you. No I’m done dancing for others, that was long ago and I needed the money.

Here is how to triangulate a known set of vertices in 2D and get back the resulting triangulation without duplicating every vertex:

#include "stdafx.h"
#include "Tri2D.h"
 
#include <windows.h>
#include <vector>
#include <stdio.h>
#include <vector>
#include <string>
#include <fstream>
 
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_euclidean_traits_xy_3.h>
#include <CGAL/Triangulation_hierarchy_2.h>
 
#include <CGAL/Triangulation_2.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/algorithm.h>
 
struct K : CGAL::Exact_predicates_inexact_constructions_kernel {};
typedef CGAL::Triangulation_vertex_base_2<K>             Vbb;
typedef CGAL::Triangulation_hierarchy_vertex_base_2<Vbb> Vb;
typedef CGAL::Triangulation_face_base_2<K>               Fb;
typedef CGAL::Triangulation_data_structure_2<Vb,Fb>      Tds;
typedef CGAL::Delaunay_triangulation_2<K,Tds>            Dt;
typedef CGAL::Triangulation_hierarchy_2<Dt>              Triangulation;
typedef Triangulation::Point                             Point;
typedef CGAL::Creator_uniform_2<double,Point>            Creator;
typedef Triangulation::Vertex_circulator				Vertex_circulator;
typedef Triangulation::Vertex_handle					Vertex_handle;
typedef Triangulation::Triangle							Triangle;
typedef Triangulation::Finite_faces_iterator Face_Iterator;
 
void triangulate(){
        ///Triangulation call
	Triangulation t;
 
	size_t size = 0;
 
        std::map<Vertex_handle,int> vLookup;  ///Vertex lookup table, stores index in to 'verts' at each 'Vertex_handle'
	std::<vector> verts;   ///Vertex buffer
	std::<vector> faces;     ///Face(Triangle/Facet) buffer
 
	{	///Load points from point cloud.  Each line is a single vertex.
		FILE *stream = fopen("face.sc","r");
		while(!feof(stream)){
			char buffer[256];
			if(fgets(buffer,256,stream)==NULL)break;
 
			float x,y,z;
			sscanf(buffer,"%f %f %f",&amp;x,&amp;y,&amp;z);
 
			std::vector tmp;
			tmp.push_back(x);tmp.push_back(y);tmp.push_back(z);
 
			verts.push_back(tmp);
 
                        ///Assign handle to vertex lookup table
			Vertex_handle v0 = t.insert(Point(x,y,z));
			vLookup[v0] = size;
			size += 1;
		}
		fclose(stream);
	}
        {
		///TODO:  If we assume our polygon is convex, add in a uniform set of control points here.
	}
 
	Face_Iterator fit = t.finite_faces_begin();
	{	///Export points as individual triangles to .stl (duplicates are kept.)
		FILE *stream = fopen("out.stl","w");
		fprintf(stream,"solid test\n");
 
		for (fit = t.finite_faces_begin(); fit != t.finite_faces_end(); fit++) {
			Triangle triangle = t.triangle(fit);
			Point p1,p2,p3;
 
			Vertex_handle v0 = fit->vertex(0);
			Vertex_handle v1 = fit->vertex(1);
			Vertex_handle v2 = fit->vertex(2);
 
			printf("F: %d %d %d\n",vLookup[v0],vLookup[v1],vLookup[v2]);
			std::vector tmp;
 
			tmp.push_back(vLookup[v0]);
			tmp.push_back(vLookup[v1]);
			tmp.push_back(vLookup[v2]);
 
			faces.push_back(tmp);
 
			p1 = triangle.vertex(0);
			p2 = triangle.vertex(1);
			p3 = triangle.vertex(2);
 
			fprintf(stream,"\tfacet normal 1 1 1\n");
			fprintf(stream,"\t\touter loop\n");
			fprintf(stream,"\t\t\tvertex %f %f 0\n",p1.x(),p1.y(),0);
			fprintf(stream,"\t\t\tvertex %f %f 0\n",p2.x(),p2.y(),0);
			fprintf(stream,"\t\t\tvertex %f %f 0\n",p3.x(),p3.y(),0);
			fprintf(stream,"\t\tendloop\n");
			fprintf(stream,"\tendfacet\n");
		}
		fprintf(stream,"endsolid test\n");
		fclose(stream);
	}
 
	printf("  - nVtx: %d  nFace: %d\n",verts.size(),faces.size());
	{
		FILE *stream = fopen("out.obj","w");
		for(int v = 0; v < verts.size(); v++){
			//printf("v[%d]: %d \n",v,verts[v].size());
			fprintf(stream,"v %f %f %f\n",verts[v][1],verts[v][2],verts[v][0]);
		}
		for(int f = 0; f < faces.size(); f++){
			fprintf(stream,"f %d %d %d\n",faces[f][0]+1,faces[f][1]+1,faces[f][2]+1);
		}
		fclose(stream);
	}
}
</dt>

And there you have it. Somethings of note:

***Sorry about the missing ‘<' and '>‘ WordPress gobbles them up.