bugGnash - The GNU Flash player - Bugs: bug #20249, triangulation code doesn't work...

 
 

bug #20249: triangulation code doesn't work for certain cases.

Submitted by:  Ming Li <inetdragon>
Submitted on:  Mon 25 Jun 2007 10:29:16 AM UTC  
 
Category: coreSeverity: 3 - Normal
Release: NoneStatus: Invalid
Privacy: PublicAssigned to: None
Open/Closed: Closed

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

Wed 04 Jul 2007 12:20:40 PM UTC, comment #4:

Hello Li

Thanks for letting us know about your experience with Gnash code and your helpful suggestions.

Unfortunately your problem is with a modified version of a Gnash code fragment that is taken out of Gnash into another context and we cannot debug that.

Since we have no evidence that Gnash suffers from the same problem that you are describing I am closing this item. If you can reproduce the problem with a SWF movie that crashes Gnash itself, we will be happy to re-open the item.

Again, thanks for getting in touch about this - we will remember this in case it helps explain some other bug.

Martin Guy <martinwguy>
Thu 28 Jun 2007 01:21:38 AM UTC, comment #3:

just an hint to produce an SWF.
You can pick the DrawingApiTest.as file and add a non-closed filled square to see what the proprietary player does with it.

Sandro Santilli <strk>
Project Member
Tue 26 Jun 2007 08:15:31 AM UTC, comment #2:

I've found this problem when I want to extract the triangulation function for my own project. Therefore, I don't have a flash file.

It seems that the triangulation function doesn't require that the polygon be closed. I've got the same crash with and without attach the vertex (0,0) to the square.

A vertex in a polygon is reflex if the internal angle is greater than 180 degrees. Speaking less technically, it's the vertex which causes the concavity.

The following is my test program. Actually I just copied from the test code from triangulate_float.cpp and adapted it to int32 version.

-------------------------------------------------------
#include "triangulate.h"

int main(int argc, char* argv[])
{
std::vector<int32_t> result;
std::vector<std::vector<int32_t> > paths;

// Make a square.
paths.resize(1);
paths[0].push_back(0);
paths[0].push_back(0);
paths[0].push_back(3);
paths[0].push_back(0);
paths[0].push_back(3);
paths[0].push_back(3);
paths[0].push_back(0);
paths[0].push_back(3);

//the program crashes with and without this vertex
paths[0].push_back(0);
paths[0].push_back(0);

// Triangulate.
triangulate::compute(&result, paths.size(), &paths[0]);

// Dump.
for (int i = 0; i < result.size(); i++)
{
printf("%d\n", result[i]);
}
}

Ming Li <inetdragon>
Mon 25 Jun 2007 03:30:56 PM UTC, comment #1:

Huh? Isn't (0,0), (1,0), (1,1), (0,1) just a square?

Note that Flash requires that all shapes have closed paths, so the example would need to be:

(0,0), (1,0), (1,1), (0,1), (0,0)

Also, can you explain what you mean by "reflex vertices"?

Please attach a sample movie that crashes the player...

Udo Giacomozzi <udog>
Project Member
Mon 25 Jun 2007 10:29:16 AM UTC, original submission:

The triangulation code doesn't work for
1. a convex polygon [ a simple example would be (0,0), (1,0), (1,1), (0,1) ]
2. a concave polygon, the reflex vertices of which form a zero-area boundingbox.
A simple test program just crashes.

Reason:
=======
In poly<coord_t>::init_for_ear_clipping in triangulate_impl.h, if there is no reflex vertex or the reflex vertices form a zero-area boundingbox, e.g., there is only one reflex vertex, the m_reflex_point_index will have a zero-area boundingbox as its member variable.

Later in the function get_containing_cell_clamped in grid_index.h,
there will be a divide-by-zero exception.

Possible fix:
============
add the following code
if(reflex_bound.get_width() == 0)
{
reflex_bound.min.x -= 1;
reflex_bound.max.x += 1;
}

if(reflex_bound.get_height() == 0)
{
reflex_bound.min.y -= 1;
reflex_bound.max.y += 1;
}

before this line:
m_reflex_point_index = new grid_index_point<coord_t, int>(reflex_bound, x_cells, y_cells);

in poly<coord_t>::init_for_ear_clipping in triangulate_impl.h.

Ming Li <inetdragon>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach File(s):
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by strk (Posted a comment)
  • -unavailable- added by udog (Posted a comment)
  • -unavailable- added by inetdragon (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 3 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Wed 04 Jul 2007 12:20:40 PM UTCmartinwguyStatusNone=>Invalid
      Open/ClosedOpen=>Closed
    Mon 25 Jun 2007 10:29:16 AM UTCinetdragonCarbon-Copy-=>Added -unavailable-

    Back to the top


    Powered by Savane 3.1-cleanup1