Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (492)
Games in Android Showcase (112)
games submitted by our members
Games in WIP (556)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Triangulizing any text, any Font, any Shape, for 3d use...  (Read 5578 times)
0 Members and 1 Guest are viewing this topic.
Offline tusaki

Junior Member


Medals: 1


In a mad world only the mad are sane.


« Posted 2005-10-22 23:58:24 »

Hia, I'm back!  Grin

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)


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:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
158  
159  
160  
161  
162  
163  
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:

1  
2  
3  
4  
5  
6  
7  
8  
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 ( Tongue ) I'll leave to you some interesting ideas:
 * Extrusion (making it fully 3d, instead of 2d)
 * optimiziation

Regards,
-  Vince
Offline cborders

Junior Member





« Reply #1 - Posted 2005-10-23 00:13:49 »

 Shocked  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!!
Offline swpalmer

JGO Coder




Where's the Kaboom?


« Reply #2 - Posted 2005-10-23 00:23:53 »

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!

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline cborders

Junior Member





« Reply #3 - Posted 2005-10-23 00:41:07 »

He does mention that he put it out for improvement and optimization!  Go for it! Cheesy
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 784
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #4 - Posted 2005-10-23 00:52:24 »

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

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

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline tusaki

Junior Member


Medals: 1


In a mad world only the mad are sane.


« Reply #5 - Posted 2005-10-23 08:23:08 »

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)


now I should probably explain what the flatness and interpolation values mean  Grin
(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 ;-) 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 ^_^...
Offline tom
« Reply #6 - Posted 2005-10-23 11:01:35 »

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.

Offline anarchotron

Junior Member




...precious bodily fluids.


« Reply #7 - Posted 2005-10-23 14:03:25 »

Very nice results.

Makes me want to stop what I'm doing and slot this into my little project Smiley  Must... resist.... Smiley
Offline cborders

Junior Member





« Reply #8 - Posted 2005-10-23 17:01:10 »

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!!
Offline tusaki

Junior Member


Medals: 1


In a mad world only the mad are sane.


« Reply #9 - Posted 2005-10-23 17:05:34 »

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!!

Yeah, except that I haven't changed anything, I've merely explained how the existing functionality works ;-) still, your statement is true.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline swpalmer

JGO Coder




Where's the Kaboom?


« Reply #10 - Posted 2005-10-24 01:38:09 »

I'm particularly interested if anyone has ideas on how to extrude such an object to make it fully 3d.

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

Offline andreas.jarund

Innocent Bystander





« Reply #11 - Posted 2006-03-31 07:46:57 »

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

I get a time out when trying to follow the url. Can I get it from somewhere else?

/Andreas
Offline tusaki

Junior Member


Medals: 1


In a mad world only the mad are sane.


« Reply #12 - Posted 2006-04-02 13:03:30 »

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

Junior Member




Hoping to become a Java Titan someday!


« Reply #13 - Posted 2007-01-03 16:34:40 »

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

Cheers,
Dr. A>
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Nickropheliac (16 views)
2014-08-31 22:59:12

TehJavaDev (23 views)
2014-08-28 18:26:30

CopyableCougar4 (33 views)
2014-08-22 19:31:30

atombrot (42 views)
2014-08-19 09:29:53

Tekkerue (41 views)
2014-08-16 06:45:27

Tekkerue (35 views)
2014-08-16 06:22:17

Tekkerue (26 views)
2014-08-16 06:20:21

Tekkerue (37 views)
2014-08-16 06:12:11

Rayexar (73 views)
2014-08-11 02:49:23

BurntPizza (49 views)
2014-08-09 21:09:32
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!