Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Triangulating complex polygons

Name: Anonymous 2009-03-17 20:02

I'm trying to find an easy to implement algorithm that will take a non-convex polygon with no holes and find a triangulation of it.  My googling is returning a lot of math when what I really need is an algorithm or some source code to work from.

Name: Anonymous 2009-03-17 20:05

Hi, I'm trying to do my homework and Google doesn't have any source code I can steal.  I run Linux so I'm a real programmer can you guys help me by giving me code that I can compile and pretend like I'm programming.

Name: Anonymous 2009-03-17 20:09

>>2
Wrong, they don't make you do computational geometry in CS schools.  It is because the fastest collision detection algorithms only work on convex polygons.  I'm asking for any links that explain how to do this in polynomial time that aren't 100 page math papers.

Name: Anonymous 2009-03-17 20:10

>>3
If Lisp was a car, it wouldn't start if you forget to close any of the doors.

Name: Anonymous 2009-03-17 20:11

>>3
Any answer would be a 100 page math paper.  Learn your fucking job.

Name: Anonymous 2009-03-17 20:15

>>5
We here at /prog/ only know how to do expert memery. What, you thought we knew anything about Computer Science? Lol, you naive fool.

Name: Anonymous 2009-03-17 20:15

>>3
If Java was a car, it would be your office.

Name: Anonymous 2009-03-17 20:17

>>7
What is that suppsoed to mean?

Name: Anonymous 2009-03-17 22:44

>>8
[b][i]Doesn't get /prog/

Name: Anonymous 2009-03-17 22:52

>>9
lol, BBcode fail.

Name: Anonymous 2009-03-18 2:07

>>10
[b][i]Doesn't get /prog/

Name: Anonymous 2009-03-18 6:07

Resurrection bump

Name: Anonymous 2009-03-18 7:02

    originalVerts = ds->numVerts;
   
    numVerts = 0;
    for ( i = 0 ; i < ds->numVerts ; i++ )
    {
        counts[i] = 0;
        firstVert[i] = numVerts;

        // copy first vert
        if ( numVerts == MAX_SURFACE_VERTS ) {
            Error( "MAX_SURFACE_VERTS" );
        }
        verts[numVerts] = ds->verts[i];
        originals[numVerts] = i;
        numVerts++;

        // check to see if there are any t junctions before the next vert
        v1 = &ds->verts[i];
        v2 = &ds->verts[ (i+1) % ds->numVerts ];

        j = (int)ds->verts[i].lightmap[ 0 ][ 0 ];
        if ( j == -1 ) {
            continue;        // degenerate edge
        }
        e = &edgeLines[ j ];
       
        VectorSubtract( v1->xyz, e->origin, delta );
        start = DotProduct( delta, e->dir );

        VectorSubtract( v2->xyz, e->origin, delta );
        end = DotProduct( delta, e->dir );


        if ( start < end ) {
            p = e->chain.next;
        } else {
            p = e->chain.prev;
        }

        for (  ; p != &e->chain ;  ) {
            if ( start < end ) {
                if ( p->intercept > end - ON_EPSILON ) {
                    break;
                }
            } else {
                if ( p->intercept < end + ON_EPSILON ) {
                    break;
                }
            }

            if (
                ( start < end && p->intercept > start + ON_EPSILON ) ||
                ( start > end && p->intercept < start - ON_EPSILON ) ) {
                // insert this point
                if ( numVerts == MAX_SURFACE_VERTS ) {
                    Error( "MAX_SURFACE_VERTS" );
                }
               
                /* take the exact intercept point */
                VectorCopy( p->xyz, verts[ numVerts ].xyz );
               
                /* interpolate the texture coordinates */
                frac = ( p->intercept - start ) / ( end - start );
                for ( j = 0 ; j < 2 ; j++ ) {
                    verts[ numVerts ].st[j] = v1->st[j] +
                        frac * ( v2->st[j] - v1->st[j] );
                }
               
                /* copy the normal (FIXME: what about nonplanar surfaces? */
                VectorCopy( v1->normal, verts[ numVerts ].normal );
               
                /* ydnar: interpolate the color */
                for( k = 0; k < MAX_LIGHTMAPS; k++ )
                {
                    for( j = 0; j < 4; j++ )
                    {
                        c = (float) v1->color[ k ][ j ] + frac * ((float) v2->color[ k ][ j ] - (float) v1->color[ k ][ j ]);
                        verts[ numVerts ].color[ k ][ j ] = (byte) (c < 255.0f ? c : 255);
                    }
                }
               
                /* next... */
                originals[ numVerts ] = i;
                numVerts++;
                counts[ i ]++;
            }

            if ( start < end ) {
                p = p->next;
            } else {
                p = p->prev;
            }
        }
    }

    c_addedVerts += numVerts - ds->numVerts;
    c_totalVerts += numVerts;


    // FIXME: check to see if the entire surface degenerated
    // after snapping

    // rotate the points so that the initial vertex is between
    // two non-subdivided edges
    for ( i = 0 ; i < numVerts ; i++ ) {
        if ( originals[ (i+1) % numVerts ] == originals[ i ] ) {
            continue;
        }
        j = (i + numVerts - 1 ) % numVerts;
        k = (i + numVerts - 2 ) % numVerts;
        if ( originals[ j ] == originals[ k ] ) {
            continue;
        }
        break;
    }

    if ( i == 0 ) {
        // fine the way it is
        c_natural++;

        ds->numVerts = numVerts;
        ds->verts = safe_malloc( numVerts * sizeof( *ds->verts ) );
        memcpy( ds->verts, verts, numVerts * sizeof( *ds->verts ) );

        return;
    }
    if ( i == numVerts ) {
        // create a vertex in the middle to start the fan
        c_cant++;

/*
        memset ( &verts[numVerts], 0, sizeof( verts[numVerts] ) );
        for ( i = 0 ; i < numVerts ; i++ ) {
            for ( j = 0 ; j < 10 ; j++ ) {
                verts[numVerts].xyz[j] += verts[i].xyz[j];
            }
        }
        for ( j = 0 ; j < 10 ; j++ ) {
            verts[numVerts].xyz[j] /= numVerts;
        }

        i = numVerts;
        numVerts++;
*/
    } else {
        // just rotate the vertexes
        c_rotate++;

    }

    ds->numVerts = numVerts;
    ds->verts = safe_malloc( numVerts * sizeof( *ds->verts ) );

    for ( j = 0 ; j < ds->numVerts ; j++ ) {
        ds->verts[j] = verts[ ( j + i ) % ds->numVerts ];
    }

Hope that helps!

Name: Anonymous 2009-03-18 14:35

>>13
The lightmap and texture variables along with rotating vertexes indicated that this was probably not relevant.  A google search shows that this is an excerpt from the quake3 source code and is indeed not relevant.  Thanks for trying though!

Name: Anonymous 2009-03-18 14:56

For a large enough epsilon, your problem is already solved.

Name: Anonymous 2009-03-18 15:00

Lightmap was here. Stencil volumes and shadow maps are losers.

Name: Anonymous 2010-12-21 13:37

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -