Triangulizing any text, any Font, any Shape, for 3d use...

Shared Code
#1

Hia, I’m back! ;D

now I would like to share with you one of my little projects. basically, I wanted to use a text in 3d-space, and not bitmaps. I’ll keep it short for now, because it’s already 01:36 where I am right now…

The font class in java has some interesting properties for this goal, it allows us to get a general shape for any string. So all I needed to figure out is to triangulate (build triangles) a ‘shape’ object.

here’s how I did it: (click for an larger image)

http://cal007300.student.utwente.nl/vincent/explainsmall.jpg

1) we start with a regular shape. you can get the shape of a text by invoking the createGlyphVector() method on the Font object. this will generate Glyphs, which we can iterate over and get Glyph Outlines from using getGlyphOutline(i) on every Glyph. These Shapes we will try to triangulize. Notice the Shape.getPathIterator receives() a ‘flatness’ parameter which will return an iterator which will only return LINETO objects (as opposed to quadratic and cubic CURVES). This makes it easy for us…

2) Because of the triangulation method we are going to use (Delauney) we need to interpolate the ‘long’ edges.

3) After interpolating, we have the points required to feed to the Delauney triangulation routine

4) This is the result after triangulating, lots of triangles, connecting everything…

5) So we decide which triangles to keep and which to throw away. I check for every triangle-centerpoint if it is within the shape.

6) And this is the result.

I’ve got the Delauney-triangulazing code from this site: http://www.cs.cornell.edu/Info/People/chew/Delaunay.html

The main code which i created was this:


package javafont;

import java.awt.Font;
import java.awt.Shape;
import java.awt.font.FontRenderContext;
import java.awt.font.GlyphVector;
import java.awt.geom.PathIterator;
import java.util.HashSet;
import java.util.Set;

import org.lwjgl.util.vector.Vector2f;

import delaunay.DelaunayTriangulation;
import delaunay.Pnt;
import delaunay.Simplex;

public class ShapeTriangulator {
	public static final double TRISIZE = 10000;
		
	public static Set<Vector2f[]> convertSimplexSetToVector2fSet(Set<Simplex<Pnt>> oldSet) {
		Set<Vector2f[]> finalSet = new HashSet<Vector2f[]>();
		for (Simplex<Pnt> triangle: oldSet) {
			Pnt[] pntArray = triangle.toArray(new Pnt[3]);
			Vector2f[] vecArray = new Vector2f[3];
			
			//System.out.println(pntArray[0] + "," + pntArray[1] + "," + pntArray[2]);
			
			vecArray[0] = new Vector2f((float) pntArray[0].coord(0), (float) pntArray[0].coord(1));
			vecArray[1] = new Vector2f((float) pntArray[1].coord(0), (float) pntArray[1].coord(1));
			vecArray[2] = new Vector2f((float) pntArray[2].coord(0), (float) pntArray[2].coord(1));
		
			finalSet.add(vecArray);
		}
		
		return finalSet;
	}
	
	public static Set<Simplex<Pnt>> triangulateText(Font font, String text, double flatness, double interpolateFlatness) {
		GlyphVector vector = font.createGlyphVector(new FontRenderContext(null, false, false), text);
		
		HashSet<Simplex<Pnt>> finalTriangleSet = new HashSet<Simplex<Pnt>>();
		for(int i=0; i<vector.getNumGlyphs(); i++) {
			//Point2D characterLocation = vector.getGlyphPosition(i);
			Shape characterShape = vector.getGlyphOutline(i);
			
			Set<Simplex<Pnt>> characterTriangleSet = triangulateShape(characterShape, flatness, interpolateFlatness);
		
			finalTriangleSet.addAll(characterTriangleSet);
		}
		
		return finalTriangleSet;
	}
	
	public static Set<Simplex<Pnt>> triangulateShape(Shape shape, double flatness, double interpolateFlatness) {
		return triangulateShape(shape, flatness, interpolateFlatness, 0, 0);
	}
	
	public static Set<Simplex<Pnt>> triangulateShape(Shape shape, double flatness, double interpolateFlatness, double relX, double relY) {
		PathIterator shapePathIterator = shape.getPathIterator(null, flatness);
		
		/*
		 * Build the triangle which encompasses the shape (-0.5,+1) - (+0.5,+1)  - (0,-1) 
		 */
		Simplex<Pnt> tri = new Simplex<Pnt>(
				new Pnt(-TRISIZE/2.0,TRISIZE), 
				new Pnt(+TRISIZE/2.0,TRISIZE), 
				new Pnt(0,-TRISIZE)
		);
		
		// initialize the triangulation with this triangle
		DelaunayTriangulation triangulation = new DelaunayTriangulation(tri);
		
		/*
		 * Add all points of the shape to the triangulation
		 */
		double x = 0, y = 0, px, py;
		while (!shapePathIterator.isDone()) {
			px = x;
			py = y;

			double[] args = new double[6];

			int mode = shapePathIterator.currentSegment(args);
			switch (mode) {
			case PathIterator.SEG_MOVETO:
				x = args[0];
				y = args[1];
				break;
			case PathIterator.SEG_LINETO:
				x = args[0];
				y = args[1];
				
				if(px == x && py == y)
					break;
				
				Pnt p1 = new Pnt(px+relX,py+relY);
				Pnt p2 = new Pnt(x+relX,y+relY);

				triangulation.delaunayPlace(p1);

				Pnt lengthVector = new Pnt(x-px, y-py);
				
				// sqrt( x^2 + y^2 )
				double length =Math.sqrt((lengthVector.coord(0) * lengthVector.coord(0)) +
										 (lengthVector.coord(1) * lengthVector.coord(1)));
				
				double num = length / interpolateFlatness;
				double nx = lengthVector.coord(0) / num;
				double ny = lengthVector.coord(1) / num;
				
				if(num>1) {
					double start = (num - Math.floor(num)) / 2.0;
				
					double cx = p1.coord(0);
					double cy = p1.coord(1);
					double ll = length;
					ll = ll -start;
					while(ll > interpolateFlatness) {
						triangulation.delaunayPlace(new Pnt(cx,cy));
						
						cx = cx + nx;
						cy = cy + ny;
						
						ll = ll -interpolateFlatness;
					}
				}	
				
				triangulation.delaunayPlace(p2);
				break;
			case PathIterator.SEG_QUADTO:
				break;
			case PathIterator.SEG_CUBICTO:
				break;
			case PathIterator.SEG_CLOSE:
				break;
			}

			shapePathIterator.next();
		}
		
		// now add all triangles which are in the shape to the set
		HashSet<Simplex<Pnt>> finalTriangleSet = new HashSet<Simplex<Pnt>>();
		
		for (Simplex<Pnt> triangle: triangulation) {
			 double midX = 0.0f,midY = 0.0f;
			 for (Set<Pnt> edge: triangle.facets()) {
				 Pnt[] endpoint = edge.toArray(new Pnt[2]);
				 midX = midX+endpoint[0].coord(0);
				 midY = midY+endpoint[0].coord(1);
				 midX = midX+endpoint[1].coord(0);
				 midY = midY+endpoint[1].coord(1);
			 }
			 midX /= 6.0;
			 midY /= 6.0;

			 if(shape.contains(midX, midY)) {
				 finalTriangleSet.add(triangle);
			 }
		 }
		
		return finalTriangleSet;	
	}
}

and this is how you could use it:


String text = "World Domination";
		
Font myFont = new Font("Verdana", Font.PLAIN, 10);
		
triangleSet = 
	ShapeTriangulator.convertSimplexSetToVector2fSet(
			ShapeTriangulator.triangulateText(myFont, text, 0.1, 0.5)
	);

here you can download the full source code plus some demos: http://cal007300.student.utwente.nl/vincent/javafont2.rar (255kb)

I hope you enjoy this code, as an excersize ( :stuck_out_tongue: ) I’ll leave to you some interesting ideas:

  • Extrusion (making it fully 3d, instead of 2d)
  • optimiziation

Regards,

  • Vince
#2

:o WOW! Very Cool! This is a really great resource. It will beinteresting to see how this effects the speed of displaying text, over the standard textured sprite method! Very good work!!

#3

It’s cool, but keeping in mind I know nothing about Delauney, it seems to generate far more triangles than necessary. I think a secondary goal of a tool like this should be to keep the triangle count down.

Still an excellent piece of work though, thanks for sharing!

#4

He does mention that he put it out for improvement and optimization! Go for it! :smiley:

#5

For text this size, high polycount doesn’t really matter. Only a few letters will fit on your screen anyway :slight_smile:

Something to be proud of, that’s for sure.

#6

You can determine how flat or interpolated the final triangulation will be, the picture above is just to explain the process.

here is how the same shape would look with ‘rougher’ flatness/interpolation values…

(click the image for a larger version)

http://cal007300.student.utwente.nl/vincent/interpolateexamplesmall.jpg

now I should probably explain what the flatness and interpolation values mean ;D
(here is some room for improvement btw)

the flatness value is passed directly to the Shape.getPathIterator so for an explanation of that I suggest clicking the link to the java API doc. Basically, higher values means a ‘rougher’ path.

Now as we traverse this path, I use the interpolation value to determine in how many pieces a single segment must be cut. basically I divide the length of a piece by the interpolation value. So in the end, any segment will not be -longer- than that value. So, the same goes here, the larger this value, the rougher the image. The reason I do this has to do with the delaunay method. Because the delaunay method doesn’t take notice of the shape of the object, it sometimes removes segments from the outline of the shape. This happened mostly with longer pieces. So I added this interpolation thingie. This also solved another problem I was foreseeing, a shape in 3d is much more useful (for lightning/exploding/warping purposes) if the triangles which make up the shape are of a uniform size more or less.

And yes, there are many opportunities for this friendly community to improve and or expand on this idea :wink: I’m particularly interested if anyone has ideas on how to extrude such an object to make it fully 3d.

And finally thank you for the encouraging comments ^_^…

#7

You can reduce the number of triangles by running a triangle reduction algorithm on the mesh. It is also used in dynamic lods. A short description is that it will try to move a vertex to one if it’s neighbors without changing the shape. In your case it would remove most of the triangles on the right side of the “a”.

Extrusion is fairly simple I think. The edges that needs to be extrudes is the one that do not share a neighbour.

#8

Very nice results.

Makes me want to stop what I’m doing and slot this into my little project :slight_smile: Must… resist… :slight_smile:

#9

Very cool progress! When you get avaried group of smart folks all looking at a problem, you invariablly get a very nice solution! That’s what I love about open-source!!

#10

Yeah, except that I haven’t changed anything, I’ve merely explained how the existing functionality works :wink: still, your statement is true.

#11

Duplicate all those triangles and offset them along the z-axis. Then you need to stitch them together by “sewing” the points to their duplicates as you follow around the path making a wall of triangles.

I’ll leave it to someone else to translate that into code :wink:

#12

[quote]here you can download the full source code plus some demos: http://cal007300.student.utwente.nl/vincent/javafont2.rar (255kb)
[/quote]
I get a time out when trying to follow the url. Can I get it from somewhere else?

/Andreas

#13

Yeah, my host went down. Have to look for another one :<

#14

Does anyone have the source for this, as the links are dead. :frowning:

Cheers,
Dr. A>