polygon triangulation speed

ynjh_jo · August 12, 2007, 5:53am

I never observe it’s speed before, so I’m asking it now. Is it used to be slow for hundreds of vertices polygon ?
In the following scene, I have 300 vertices polygon, built by EggPolygon. The triangulation takes 7-8 seconds long, on my 2.8 GHz proc, while (sorry for comparing) Maya can handle 600 vtx in less than half second.
Is it my fault using the Egg libraries, or is there any better way ?

from pandac.PandaModules import EggData,EggVertexPool,EggPolygon,EggVertex,Point3D,loadEggData,loadPrcFileData
loadPrcFileData('','''
# egg-mesh 0
egg-show-quads 1
''')
from direct.gui.OnscreenText import OnscreenText
import direct.directbase.DirectStart
from random import random
polyEggData = EggData()
polyVPool = EggVertexPool('')
poly = EggPolygon()
np=aspect2d.attachNewNode('')
child=np.attachNewNode('')
num=300
degInc=360./num
for v in range(num):
    np.setR(-v*degInc)
    child.setX(.6+.4*random())
    vertex = EggVertex()
    vertex.setPos(Point3D(child.getX(aspect2d),0,child.getZ(aspect2d)))
    poly.addVertex(polyVPool.addVertex(vertex))
polyEggData.addChild(poly)
OnscreenText(text='triangulating %s vertices polygon...' %num,scale=.05,sort=1000)
base.graphicsEngine.renderFrame()
base.graphicsEngine.renderFrame()

triangulateBegin=globalClock.getRealTime()
geomNode=loadEggData(polyEggData)
elapsedTime=globalClock.getRealTime()-triangulateBegin

OnscreenText(text='done in '+str(elapsedTime),pos=(0,-.1),scale=.1,sort=1000)
fill=aspect2d.attachNewNode(geomNode)
fill.analyze()
wire=fill.instanceUnderNode(aspect2d,'')
wire.setRenderModeWireframe(1)
wire.setColor(0,0,0,1)
run()

PS : I’m in the middle of creating interactive 3D model “slicing”. I only need clipping & holes filling, because I’d like to keep the model untouched, so I can slice them while walking around.
screenshot :

Thanks in advance.

drwr · August 12, 2007, 2:51pm

The egg library was never designed for real-time performance. Try the Triangulator class instead. Here’s your code modified to use that:

from pandac.PandaModules import Triangulator,GeomVertexData,GeomVertexFormat,GeomVertexWriter,GeomTriangles,Geom,GeomNode

from direct.gui.OnscreenText import OnscreenText
import direct.directbase.DirectStart
from random import random
trig = Triangulator()
np=aspect2d.attachNewNode('')
child=np.attachNewNode('')

vdata = GeomVertexData('trig', GeomVertexFormat.getV3(), Geom.UHStatic)
vwriter = GeomVertexWriter(vdata, 'vertex')

num=300
degInc=360./num
for v in range(num):
    np.setR(-v*degInc)
    child.setX(.6+.4*random())
    x, z = child.getX(aspect2d),child.getZ(aspect2d)
    vi = trig.addVertex(x, z)
    vwriter.addData3f(x, 0, z)
    trig.addPolygonVertex(vi)

OnscreenText(text='triangulating %s vertices polygon...' %num,scale=.05,sort=1000)
base.graphicsEngine.renderFrame()
base.graphicsEngine.renderFrame()

triangulateBegin=globalClock.getRealTime()
trig.triangulate()
elapsedTime=globalClock.getRealTime()-triangulateBegin

OnscreenText(text='done in '+str(elapsedTime),pos=(0,-.1),scale=.1,sort=1000)

prim = GeomTriangles(Geom.UHStatic)
for i in range(trig.getNumTriangles()):
    prim.addVertices(trig.getTriangleV0(i),
                     trig.getTriangleV1(i),
                     trig.getTriangleV2(i))
    prim.closePrimitive()

geom = Geom(vdata)
geom.addPrimitive(prim)

geomNode = GeomNode('trig')
geomNode.addGeom(geom)

fill=aspect2d.attachNewNode(geomNode)
fill.analyze()
wire=fill.instanceUnderNode(aspect2d,'')
wire.setRenderModeWireframe(1)
wire.setColor(0,0,0,1)

David

ynjh_jo · August 13, 2007, 2:26am

GREEEAT !
but I couldn’t get it to work, Python always crashes when triangulate().

drwr · August 15, 2007, 6:42pm

Hmm, are you using 1.4.0? It works fine for me.

David

ynjh_jo · August 16, 2007, 10:27am

yes, 1.4.0. thanks for your clarification, David.
seems 1.4.0 have some VC8 compilation faults. If I remember it correctly, the previous official versions compiled with VC7, right ?
Other issues :
discourse.panda3d.org/viewtopic.php?t=2865

ynjh_jo · August 16, 2007, 11:54am

oh, the fault is inside msvcr80.dll
I’ve tried to get another copy of it, but doesn’t change anything.

Josh_Yelon · August 16, 2007, 4:59pm

I need to run this under the debugger.

There are a few places in panda where they use C++ code that looks like this:

int *array_base = &array[0]

Technically, that’s incorrect: it is illegal to access element zero unless the array has an element zero. Since VC7 doesn’t do array bounds-checking, it doesn’t notice. We’ve been gradually finding and repairing these, but they still pop up from time to time. This might be one of those.

ynjh_jo · December 16, 2007, 4:28pm

Back to this again.
I just managed to download VC++ 2005 Xpress & SDKs and successfully built P3D for the 1st time.
I noticed that some early-out index checking are already done in triangulator.cxx, but there is still 1 hole left.
Currently on CVS :

int Triangulator::
traverse_polygon(int mcur, int trnum, int from, int dir) {
  //  printf("traverse_polygon(%d, %d, %d, %d)\n", mcur, trnum, from, dir);

  trap_t *t = &tr[trnum];
  //  int howsplit;
  int mnew;
  int v0, v1;  //, v0next, v1next;
  int retval = 0;  //, tmp;
  int do_switch = false;

  if (mcur < 0 || trnum <= 0)
    return 0;

  //  printf("visited size = %d, visited[trnum] = %d\n", visited.size(), visited[trnum]);

  if (visited[trnum])
    return 0;

  visited[trnum] = true;

It will return if (mcur < 0 || trnum <= 0), but before that line, trnum is already used.
I fixed it this way :

int Triangulator::
traverse_polygon(int mcur, int trnum, int from, int dir) {
    //printf("traverse_polygon(%d, %d, %d, %d)\n", mcur, trnum, from, dir);

  if (mcur < 0 || trnum <= 0)
    return 0;
  if (visited[trnum])
    return 0;

  trap_t *t = &tr[trnum];
  //  int howsplit;
  int mnew;
  int v0, v1;  //, v0next, v1next;
  int retval = 0;  //, tmp;
  int do_switch = false;

    //printf("visited size = %d, visited[trnum] = %d\n", visited.size(), visited[trnum]);

  visited[trnum] = true;

Now I can get 1000 vertices polygon triangulated in 0.015 second ! WHOOOOOOOHOOO

ynjh_jo · December 17, 2007, 3:14pm

I found something else. That industrious algo doesn’t do anything if the segments are a perfect straight line, causes nasty endless while loop in Triangulator::triangulate_single_polygon. It always jumps to non-convex code, which increments ri until infinity.

      if (ri > 0)/* reflex chain is non-empty */
 {
   if (CROSS(vert[v].pt, vert[rc[ri - 1]].pt,
     vert[rc[ri]].pt) > 0)
     {/* convex corner: cut if off */
               _result.push_back(Triangle(this, rc[ri - 1], rc[ri], v));
       ri--;
               rc.pop_back();
               nassertv(ri + 1 == (int)rc.size());
     }
   else/* non-convex */
     {/* add v to the chain */
       ri++;
               rc.push_back(v);
               nassertv(ri + 1 == (int)rc.size());
       vpos = mchain[vpos].next;
       v = mchain[vpos].vnum;
     }
 }

I fixed this by simply discarded it from the chain, inserted an if to the existing code for transferring it from rc to _result.

      if (ri > 0)		/* reflex chain is non-empty */
 {
   float crossResult = CROSS(vert[v].pt, vert[rc[ri - 1]].pt,
                             vert[rc[ri]].pt);
	  if ( crossResult >= 0 )  /* could be convex corner or straight */
	    {
         if ( crossResult > 0)  /* convex corner: cut it off */
              _result.push_back(Triangle(this, rc[ri - 1], rc[ri], v));
         /* else : perfectly straight, will be abandoned anyway */
	      ri--;
              rc.pop_back();
              nassertv(ri + 1 == (int)rc.size());
	    }
   else /* concave, add v to the chain */
	    {
	      ri++;
              rc.push_back(v);
              nassertv(ri + 1 == (int)rc.size());
	      vpos = mchain[vpos].next;
	      v = mchain[vpos].vnum;
	    }
 }

ynjh_jo · December 27, 2007, 9:27am

There is still a flaw in that algo. It couldn’t survive this polygon :
customPoly=(
(0, -0.329999148100614548) ,
(1, -0.329999148100614548) ,
(-1, -.5) ,
(-1, -0.329999148100614548) ,
(-.7, -0.329999146237969398) ,
(-.5, -0.329999146237969398) ,
)
In that case, ri increases endlessly.
I tried to fix it by giving a tiny tolerance (-1.0e-15) rather than 0, but didn’t work :

   float crossResult = CROSS(vert[v].pt, vert[rc[ri - 1]].pt,
                             vert[rc[ri]].pt);
   if ( crossResult >= -1.0e-15 )  /* could be convex corner or straight */
     {
         printf("convec/straight, ri = %d, ",ri);
         cout<<"cross = "<<crossResult<<", v = "<<v<<", endv = "<<endv<<endl;
         if ( crossResult > 0)  /* convex corner: cut it off */
              _result.push_back(Triangle(this, rc[ri - 1], rc[ri], v));
         /* else : perfectly straight, will be abandoned anyway */
       ri--;
              rc.pop_back();
              nassertv(ri + 1 == (int)rc.size());
     }
   else /* concave, add v to the chain */
     {
       ri++;
         printf("concave, ri = %d, ",ri);
         cout<<"cross = "<<crossResult<<", v = "<<v<<", endv = "<<endv<<endl;
              rc.push_back(v);
              nassertv(ri + 1 == (int)rc.size());
       vpos = mchain[vpos].next;
       v = mchain[vpos].vnum;
     }

log :
concave, ri = 2, cross = -1.86265e-009, v = 4, endv = 2
concave, ri = 2, cross = -0.119001, v = 5, endv = 2
empty, ri = 1
concave, ri = 2, cross = -1.86265e-009, v = 1, endv = 2
concave, ri = 3, cross = -1.86265e-009, v = 3, endv = 2
concave, ri = 2, cross = -3.72529e-009, v = 4, endv = 2
concave, ri = 2, cross = -1.86265e-009, v = 1, endv = 2
concave, ri = 3, cross = -1.86265e-009, v = 2, endv = 2
concave, ri = 3, cross = -1.86265e-009, v = 3, endv = 2
concave, ri = 2, cross = -1.86265e-009, v = 1, endv = 2
concave, ri = 2, cross = -3.72529e-009, v = 4, endv = 2
concave, ri = 2, cross = -0.289001, v = 5, endv = 2
empty, ri = 1
concave, ri = 2, cross = -1.86265e-009, v = 1, endv = 2
concave, ri = 3, cross = -1.86265e-009, v = 3, endv = 2
concave, ri = 2, cross = -3.72529e-009, v = 4, endv = 2
concave, ri = 2, cross = -1.86265e-009, v = 1, endv = 2
concave, ri = 3, cross = -1.86265e-009, v = 2, endv = 2
concave, ri = 3, cross = -1.86265e-009, v = 3, endv = 2
concave, ri = 2, cross = -1.86265e-009, v = 1, endv = 2
concave, ri = 2, cross = -3.72529e-009, v = 4, endv = 2
concave, ri = 2, cross = -0.289001, v = 5, endv = 2
empty, ri = 1
concave, ri = 2, cross = -1.86265e-009, v = 1, endv = 2
concave, ri = 3, cross = -1.86265e-009, v = 3, endv = 2
concave, ri = 2, cross = -3.72529e-009, v = 4, endv = 2
concave, ri = 2, cross = -1.86265e-009, v = 1, endv = 2
.
repeated endlessly
.

It couldn’t catch that case. Even the 1st one (cross = -1.86265e-009) was wrong, it should jump to convex/straight, but didn’t.
This didn’t work too :

   double crossResult = CROSS(vert[v].pt, vert[rc[ri - 1]].pt,
                             vert[rc[ri]].pt);
   if ( crossResult >=double(-1.0e-15) )  /* could be convex corner or straight */

THIS WORKS :

   float crossResult = CROSS(vert[v].pt, vert[rc[ri - 1]].pt,
                             vert[rc[ri]].pt);
   if ( (crossResult >= 0) ||
        ((crossResult<0) && (fabs(crossResult)>1.0e-15)) )  /* could be convex corner or straight */

I’m simply a newb in C++, I don’t know any better way.
log :
convec/straight, ri = 1, cross = -1.86265e-009, v = 4, endv = 2
empty, ri = 1
convec/straight, ri = 1, cross = 0.0510003, v = 5, endv = 2
empty, ri = 1
convec/straight, ri = 1, cross = 0.289001, v = 6, endv = 2
empty, ri = 1
convec/straight, ri = 1, cross = -1.86265e-009, v = 1, endv = 2
empty, ri = 1
convec/straight, ri = 1, cross = -0, v = 3, endv = 2
empty, ri = 1
convec/straight, ri = 1, cross = 0, v = 4, endv = 2
empty, ri = 1
convec/straight, ri = 1, cross = 1.86265e-009, v = 1, endv = 2
empty, ri = 1

But, unfortunately, by doing it this way, for sharp spikes, it wouldn’t work properly (I tried it with the spiky circle sample, 500-1000 vertices).
Any ideas ?
Thanks.

drwr · January 3, 2008, 3:11am

Hmm. The algorithm in question was imported almost verbatim from a paper somebody had written on the subject. (The URL of the source is documented in the comments.) Guess there are a few flaws in it.

I’m not intimately familiar with the algorithm, so it’s difficult for me to propose a solution. Wonder if it’s worth attempting to contact the original author of the paper? Other than that, it may just require getting comfortable with the mathematics to figure out exactly what the algorithm is trying to do.

David

ynjh_jo · January 6, 2008, 10:54am

Thanks for your response, David.
Yes, I’ve read that paper after you pointed me to triangulator class, and it’s too huge for me to understand the whole thing.

The last problem was purely my fault. I changed C_EPS to 1.0e-15, and restoring it back to 1.0e-7 solved that problem. You see, the comment is tempting, and I got trapped.

Would you please commit the first 2 fixes to CVS ? Otherwise, none of 3 text render modes would work too (solid, polygon, extruded), since they rely on DynamicTextFont::render_polygon_contours, which uses triangulator class.

Thanks

drwr · January 8, 2008, 4:01am

OK, done. Thanks for finding the problems and suggesting fixes!

David

ynjh_jo · January 10, 2008, 5:00pm

GRRRRRRRREAT !!!
Thanks soooo much.

lonestarr · January 28, 2008, 11:24pm

Hello,

You guys should not use this code implementation, I’ve tested it with many configurations, and despite your fixes and mine (mainly to avoid other crash and to end up infinite loops) it still does not handle many cases…

The best advices I’ve read are there:
vterrain.org/Implementation/ … ulate.html

Which leads me to this code:
flipcode.com/archives/Effici … tion.shtml

It works and the code is human-readable. I think your engine deserves it!

All the best…
lonestarr

drwr · January 29, 2008, 12:57am

Ah, but this is the algorithm that doesn’t handle holes, right?

I added the triangulator class specifically when I needed an algorithm that could handle holes. (It was first used to render polygonal text.)

If we are to replace that algorithm with a superior one, we will have to find a replacement that handles holes.

David

ynjh_jo · January 29, 2008, 7:43am

lonestarr, do you mind to clarify those cases (polygon points/vtx sequence) ? Don’t mention intersecting segments, since it’s out of that-algo ability, but easy to solve.

lonestarr · January 29, 2008, 4:48pm

*** EDIT *** I put first the wrong test, it did self intersect ***

You are true, the Radcliff code does not handle holes.

Maybe that’s just me. I’m dealing with 3D files coming from everywhere and they may be too ugly to be sent to this code.
Anyway, here is one of my test:

with the following face (extracted from an OBJ file):

v 5.916842 20.580193 0.000000
v 3.348836 22.715282 0.000000
v 1.109456 23.603827 0.000000
v -1.295157 23.752747 0.000000
v -3.627062 23.147301 0.000000
v -5.655509 21.847401 0.000000
v -7.179783 19.981676 0.000000
v -8.049051 17.734739 0.000000
v -8.177299 15.328937 0.000000
v -7.551836 13.002322 0.000000
v -6.234550 10.985119 0.000000
v -4.355794 9.476937 0.000000
v -2.101471 8.627010 0.000000
v 0.305347 8.519444 0.000000
v 2.626501 9.164879 0.000000
v 5.406940 11.014855 0.000000
v 9.651721 25.072369 0.000000
v 6.368266 27.802296 0.000000
v 2.399210 29.377146 0.000000
v -1.862703 29.641087 0.000000
v -5.995747 28.568001 0.000000
v -9.590948 26.264071 0.000000
v -12.292556 22.957277 0.000000
v -13.833239 18.974833 0.000000
v -14.060544 14.710808 0.000000
v -12.951978 10.587137 0.000000
v -10.617235 7.011868 0.000000
v -7.287346 4.338780 0.000000
v -3.291807 2.832379 0.000000
v 0.974013 2.641729 0.000000
v 5.088004 3.785692 0.000000
v 8.643077 6.151074 0.000000
f 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17

(the z coordinate is not used here)

in monotonate_trapezoids / traverse_polygon … traverse_polygon / make_new_monotone_poly
this last one is called with v1==-1 where I added the following security code is:

  if (v0<0 || v0>SEGSIZE)
	  return -1;

  if (v1<0 || v1>SEGSIZE)
	  return -1;

the above test was done with the original code, eg:

int triangulate_polygon(int n, double vertices[][2], int triangles[][3]);

I have the same result with the other implementation I’ve found, where the prototype is:

	int triangulate_polygon(int ncontours, int cntr[], double vertices[][2], int triangles[][3]);

Let me know if I am wrong…
Thank you.

-lonestarr

lonestarr · January 29, 2008, 7:09pm

I’ve tested it (it shows a ‘C’) with the triangulate.exe found in the zip archive here and it crashes.

Here is the same data in the right format (it may be easier to use than OBJ for your test with your engine):

1

32
5.916842 20.580193
3.348836 22.715282
1.109456 23.603827
-1.295157 23.752747
-3.627062 23.147301
-5.655509 21.847401
-7.179783 19.981676
-8.049051 17.734739
-8.177299 15.328937
-7.551836 13.002322
-6.234550 10.985119
-4.355794 9.476937
-2.101471 8.627010
0.305347 8.519444
2.626501 9.164879
5.406940 11.014855
8.643077 6.151074
5.088004 3.785692
0.974013 2.641729
-3.291807 2.832379
-7.287346 4.338780
-10.617235 7.011868
-12.951978 10.587137
-14.060544 14.710808
-13.833239 18.974833
-12.292556 22.957277
-9.590948 26.264071
-5.995747 28.568001
-1.862703 29.641087
2.399210 29.377146
6.368266 27.802296
9.651721 25.072369

ynjh_jo · January 29, 2008, 7:40pm

It didn’t crash with Panda, and this is what I got :

[size=75]customPoly=(
(5.916842, 20.580193), #1
(3.348836, 22.715282), #2
(1.109456, 23.603827), #3
(-1.295157, 23.752747), #4
(-3.627062, 23.147301), #5
(-5.655509, 21.847401), #6
(-7.179783, 19.981676), #7
(-8.049051, 17.734739), #8
(-8.177299, 15.328937), #9
(-7.551836, 13.002322), #10
(-6.234550, 10.985119), #11
(-4.355794, 9.476937), #12
(-2.101471, 8.627010), #13
(0.305347, 8.519444), #14
(2.626501, 9.164879), #15
(5.406940, 11.014855), #16
(8.643077, 6.151074), #32
(5.088004, 3.785692), #31
(0.974013, 2.641729), #30
(-3.291807, 2.832379), #29
(-7.287346, 4.338780), #28
(-10.617235, 7.011868), #27
(-12.951978, 10.587137), #26
(-14.060544, 14.710808), #25
(-13.833239, 18.974833), #24
(-12.292556, 22.957277), #23
(-9.590948, 26.264071), #22
(-5.995747, 28.568001), #21
(-1.862703, 29.641087), #20
(2.399210, 29.377146), #19
(6.368266, 27.802296), #18
(9.651721, 25.072369), #17
)[/size]