nekonme: glitch with graphics shape drawing?

classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

nekonme: glitch with graphics shape drawing?

davidedc
Hi Hugh, All,

I noticed a substantial difference in how nekonme strokes/fills a path as opposed to flash - at least in an instance I stumbled upon today.

Here is the link to the two programs (haxe vs flash) and pictures of the simplest shape that shows the difference (five vertexes):
https://docs.google.com/present/edit?id=0AdIoFN4Io_zNZGQ5Ymp2NmNfNjQxNXgybms2OGc&hl=en_GB

Is this a known difference between the rendering engines, or some flag/way of doing things that I'm not aware of? Or rather a bug?

Cheers,
Davide Della Casa
--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: nekonme: glitch with graphics shape drawing?

Jan_Flanders
Have you tried closing the path/shape with a final: graphics.lineTo( 70, 0 );
It seems to be implicitly closing the path or shape by using the
before last coordinate instead of the last.

Jan

On Wed, Mar 30, 2011 at 9:14 PM, Davide Della Casa <[hidden email]> wrote:

> Hi Hugh, All,
>
> I noticed a substantial difference in how nekonme strokes/fills a path as opposed to flash - at least in an instance I stumbled upon today.
>
> Here is the link to the two programs (haxe vs flash) and pictures of the simplest shape that shows the difference (five vertexes):
> https://docs.google.com/present/edit?id=0AdIoFN4Io_zNZGQ5Ymp2NmNfNjQxNXgybms2OGc&hl=en_GB
>
> Is this a known difference between the rendering engines, or some flag/way of doing things that I'm not aware of? Or rather a bug?
>
> Cheers,
> Davide Della Casa
> --
> haXe - an open source web programming language
> http://haxe.org
>

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: nekonme: glitch with graphics shape drawing?

davidedc
Adding a final "graphics.lineTo(70,0);" fixes the stroke on the right side (the closing stroke). But that extra fill between vertexes 1,4,5 remains.

D

On 30 Mar 2011, at 21:18, Jan Flanders wrote:

> Have you tried closing the path/shape with a final: graphics.lineTo( 70, 0 );
> It seems to be implicitly closing the path or shape by using the
> before last coordinate instead of the last.
>
> Jan
>
> On Wed, Mar 30, 2011 at 9:14 PM, Davide Della Casa <[hidden email]> wrote:
>> Hi Hugh, All,
>>
>> I noticed a substantial difference in how nekonme strokes/fills a path as opposed to flash - at least in an instance I stumbled upon today.
>>
>> Here is the link to the two programs (haxe vs flash) and pictures of the simplest shape that shows the difference (five vertexes):
>> https://docs.google.com/present/edit?id=0AdIoFN4Io_zNZGQ5Ymp2NmNfNjQxNXgybms2OGc&hl=en_GB
>>
>> Is this a known difference between the rendering engines, or some flag/way of doing things that I'm not aware of? Or rather a bug?
>>
>> Cheers,
>> Davide Della Casa
>> --
>> haXe - an open source web programming language
>> http://haxe.org
>>
>
> --
> haXe - an open source web programming language
> http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: nekonme: glitch with graphics shape drawing?

Tarwin Stroh-Spijer
In reply to this post by Jan_Flanders
You might also want to do an explicit endFill. I think Flash does these auto-magically which is argueably bad.


Tarwin Stroh-Spijer
_______________________

Touch My Pixel
http://www.touchmypixel.com/
phone: +61 3 8060 5321
_______________________


On Thu, Mar 31, 2011 at 7:18 AM, Jan Flanders <[hidden email]> wrote:
Have you tried closing the path/shape with a final: graphics.lineTo( 70, 0 );
It seems to be implicitly closing the path or shape by using the
before last coordinate instead of the last.

Jan

On Wed, Mar 30, 2011 at 9:14 PM, Davide Della Casa <[hidden email]> wrote:
> Hi Hugh, All,
>
> I noticed a substantial difference in how nekonme strokes/fills a path as opposed to flash - at least in an instance I stumbled upon today.
>
> Here is the link to the two programs (haxe vs flash) and pictures of the simplest shape that shows the difference (five vertexes):
> https://docs.google.com/present/edit?id=0AdIoFN4Io_zNZGQ5Ymp2NmNfNjQxNXgybms2OGc&hl=en_GB
>
> Is this a known difference between the rendering engines, or some flag/way of doing things that I'm not aware of? Or rather a bug?
>
> Cheers,
> Davide Della Casa
> --
> haXe - an open source web programming language
> http://haxe.org
>

--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: nekonme: glitch with graphics shape drawing?

davidedc
hmmm the endFill doesn't seem to fix it either...

D

On 30 Mar 2011, at 21:29, Tarwin Stroh-Spijer wrote:

You might also want to do an explicit endFill. I think Flash does these auto-magically which is argueably bad.


Tarwin Stroh-Spijer
_______________________

Touch My Pixel
http://www.touchmypixel.com/
phone: +61 3 8060 5321
_______________________


On Thu, Mar 31, 2011 at 7:18 AM, Jan Flanders <[hidden email]> wrote:
Have you tried closing the path/shape with a final: graphics.lineTo( 70, 0 );
It seems to be implicitly closing the path or shape by using the
before last coordinate instead of the last.

Jan

On Wed, Mar 30, 2011 at 9:14 PM, Davide Della Casa <[hidden email]> wrote:
> Hi Hugh, All,
>
> I noticed a substantial difference in how nekonme strokes/fills a path as opposed to flash - at least in an instance I stumbled upon today.
>
> Here is the link to the two programs (haxe vs flash) and pictures of the simplest shape that shows the difference (five vertexes):
> https://docs.google.com/present/edit?id=0AdIoFN4Io_zNZGQ5Ymp2NmNfNjQxNXgybms2OGc&hl=en_GB
>
> Is this a known difference between the rendering engines, or some flag/way of doing things that I'm not aware of? Or rather a bug?
>
> Cheers,
> Davide Della Casa
> --
> haXe - an open source web programming language
> http://haxe.org
>

--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: nekonme: glitch with graphics shape drawing?

davidedc
It's like, for the fill, the path seems to be rendered with a triangle fan (sharing the first vertex), instead of a polygon path.

The stroke is just not closed (doing the end-fill doesn't draw the last stroke either).

D

On 30 Mar 2011, at 22:38, Davide Della Casa wrote:

hmmm the endFill doesn't seem to fix it either...

D

On 30 Mar 2011, at 21:29, Tarwin Stroh-Spijer wrote:

You might also want to do an explicit endFill. I think Flash does these auto-magically which is argueably bad.


Tarwin Stroh-Spijer
_______________________

Touch My Pixel
http://www.touchmypixel.com/
phone: +61 3 8060 5321
_______________________


On Thu, Mar 31, 2011 at 7:18 AM, Jan Flanders <[hidden email]> wrote:
Have you tried closing the path/shape with a final: graphics.lineTo( 70, 0 );
It seems to be implicitly closing the path or shape by using the
before last coordinate instead of the last.

Jan

On Wed, Mar 30, 2011 at 9:14 PM, Davide Della Casa <[hidden email]> wrote:
> Hi Hugh, All,
>
> I noticed a substantial difference in how nekonme strokes/fills a path as opposed to flash - at least in an instance I stumbled upon today.
>
> Here is the link to the two programs (haxe vs flash) and pictures of the simplest shape that shows the difference (five vertexes):
> https://docs.google.com/present/edit?id=0AdIoFN4Io_zNZGQ5Ymp2NmNfNjQxNXgybms2OGc&hl=en_GB
>
> Is this a known difference between the rendering engines, or some flag/way of doing things that I'm not aware of? Or rather a bug?
>
> Cheers,
> Davide Della Casa
> --
> haXe - an open source web programming language
> http://haxe.org
>

--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org



--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: nekonme: glitch with graphics shape drawing?

Gamehaxe
Hi,
Yes - it is using a triangle fan.
The software renderer does this correctly, but the opengl renderer
goes for the fastest method, which is wrong for concave objects.
The "correct" answer is to triangulate the objects, which is possible,
but I have not got around to this.

Hugh

> It's like, for the fill, the path seems to be rendered with a triangle  
> fan (sharing the first vertex), instead of a polygon path.
>
> The stroke is just not closed (doing the end-fill doesn't draw the last  
> stroke either).
>
> D
>
> On 30 Mar 2011, at 22:38, Davide Della Casa wrote:
>
>> hmmm the endFill doesn't seem to fix it either...
>>
>> D
>>
>> On 30 Mar 2011, at 21:29, Tarwin Stroh-Spijer wrote:
>>
>>> You might also want to do an explicit endFill. I think Flash does  
>>> these auto-magically which is argueably bad.
>>>
>>>
>>> Tarwin Stroh-Spijer
>>> _______________________
>>>
>>> Touch My Pixel
>>> http://www.touchmypixel.com/
>>> phone: +61 3 8060 5321
>>> _______________________
>>>
>>>
>>> On Thu, Mar 31, 2011 at 7:18 AM, Jan Flanders <[hidden email]> wrote:
>>> Have you tried closing the path/shape with a final: graphics.lineTo(  
>>> 70, 0 );
>>> It seems to be implicitly closing the path or shape by using the
>>> before last coordinate instead of the last.
>>>
>>> Jan
>>>
>>> On Wed, Mar 30, 2011 at 9:14 PM, Davide Della Casa  
>>> <[hidden email]> wrote:
>>> > Hi Hugh, All,
>>> >
>>> > I noticed a substantial difference in how nekonme strokes/fills a  
>>> path as opposed to flash - at least in an instance I stumbled upon  
>>> today.
>>> >
>>> > Here is the link to the two programs (haxe vs flash) and pictures of  
>>> the simplest shape that shows the difference (five vertexes):
>>> >  
>>> https://docs.google.com/present/edit?id=0AdIoFN4Io_zNZGQ5Ymp2NmNfNjQxNXgybms2OGc&hl=en_GB
>>> >
>>> > Is this a known difference between the rendering engines, or some  
>>> flag/way of doing things that I'm not aware of? Or rather a bug?
>>> >
>>> > Cheers,
>>> > Davide Della Casa
>>> > --
>>> > haXe - an open source web programming language
>>> > http://haxe.org
>>> >
>>>
>>> --
>>> haXe - an open source web programming language
>>> http://haxe.org
>>>
>>> --
>>> haXe - an open source web programming language
>>> http://haxe.org
>>

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: nekonme: glitch with graphics shape drawing?

davidedc
I see.

There is a "TODO: tesselate" comment in draw_object.cpp line 533 ( http://www.google.com/codesearch/p?hl=en#Z6a0dKU6Lh4/trunk/project/draw_object.cpp&q=lineTo%20package:http://nekonme%5C.googlecode%5C.com&l=553 ), is that the place?

Could I just put in there in line 555 a call to a triangulation routine that takes mPoints and returns a new array of "triangulated" points? Maybe change n with the new triangle count? Would that local change be sufficient or would it be a deeper change than that?If that's sufficient, have you got a preferred triangulation routine?

And how about the last "closing" stroke, any pointers to that?

Lots of questions, sorry, I'm using lots of vector graphics...

Cheers,
Davide

On 31 Mar 2011, at 01:02, Hugh Sanderson wrote:

> Hi,
> Yes - it is using a triangle fan.
> The software renderer does this correctly, but the opengl renderer
> goes for the fastest method, which is wrong for concave objects.
> The "correct" answer is to triangulate the objects, which is possible,
> but I have not got around to this.
>
> Hugh
>
>> It's like, for the fill, the path seems to be rendered with a triangle fan (sharing the first vertex), instead of a polygon path.
>>
>> The stroke is just not closed (doing the end-fill doesn't draw the last stroke either).
>>
>> D
>>
>> On 30 Mar 2011, at 22:38, Davide Della Casa wrote:
>>
>>> hmmm the endFill doesn't seem to fix it either...
>>>
>>> D
>>>
>>> On 30 Mar 2011, at 21:29, Tarwin Stroh-Spijer wrote:
>>>
>>>> You might also want to do an explicit endFill. I think Flash does these auto-magically which is argueably bad.
>>>>
>>>>
>>>> Tarwin Stroh-Spijer
>>>> _______________________
>>>>
>>>> Touch My Pixel
>>>> http://www.touchmypixel.com/
>>>> phone: +61 3 8060 5321
>>>> _______________________
>>>>
>>>>
>>>> On Thu, Mar 31, 2011 at 7:18 AM, Jan Flanders <[hidden email]> wrote:
>>>> Have you tried closing the path/shape with a final: graphics.lineTo( 70, 0 );
>>>> It seems to be implicitly closing the path or shape by using the
>>>> before last coordinate instead of the last.
>>>>
>>>> Jan
>>>>
>>>> On Wed, Mar 30, 2011 at 9:14 PM, Davide Della Casa <[hidden email]> wrote:
>>>> > Hi Hugh, All,
>>>> >
>>>> > I noticed a substantial difference in how nekonme strokes/fills a path as opposed to flash - at least in an instance I stumbled upon today.
>>>> >
>>>> > Here is the link to the two programs (haxe vs flash) and pictures of the simplest shape that shows the difference (five vertexes):
>>>> > https://docs.google.com/present/edit?id=0AdIoFN4Io_zNZGQ5Ymp2NmNfNjQxNXgybms2OGc&hl=en_GB
>>>> >
>>>> > Is this a known difference between the rendering engines, or some flag/way of doing things that I'm not aware of? Or rather a bug?
>>>> >
>>>> > Cheers,
>>>> > Davide Della Casa
>>>> > --
>>>> > haXe - an open source web programming language
>>>> > http://haxe.org
>>>> >
>>>>
>>>> --
>>>> haXe - an open source web programming language
>>>> http://haxe.org
>>>>
>>>> --
>>>> haXe - an open source web programming language
>>>> http://haxe.org
>>>
>
> --
> haXe - an open source web programming language
> http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: nekonme: glitch with graphics shape drawing?

davidedc
P.S. I just read this survey on triangulation routines here http://www.vterrain.org/Implementation/Libs/triangulate.html .

There is one with a good review which is very compact (1-page) and self-contained, would be probably something within my abilities to integrate in nekonme: http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml

Doesn't support holes, but it would be a start.

D

On 31 Mar 2011, at 10:59, Davide Della Casa wrote:

I see.

There is a "TODO: tesselate" comment in draw_object.cpp line 533 ( http://www.google.com/codesearch/p?hl=en#Z6a0dKU6Lh4/trunk/project/draw_object.cpp&q=lineTo%20package:http://nekonme%5C.googlecode%5C.com&l=553 ), is that the place?

Could I just put in there in line 555 a call to a triangulation routine that takes mPoints and returns a new array of "triangulated" points? Maybe change n with the new triangle count? Would that local change be sufficient or would it be a deeper change than that?If that's sufficient, have you got a preferred triangulation routine?

And how about the last "closing" stroke, any pointers to that?

Lots of questions, sorry, I'm using lots of vector graphics...

Cheers,
Davide

On 31 Mar 2011, at 01:02, Hugh Sanderson wrote:

Hi,
Yes - it is using a triangle fan.
The software renderer does this correctly, but the opengl renderer
goes for the fastest method, which is wrong for concave objects.
The "correct" answer is to triangulate the objects, which is possible,
but I have not got around to this.

Hugh

It's like, for the fill, the path seems to be rendered with a triangle fan (sharing the first vertex), instead of a polygon path.

The stroke is just not closed (doing the end-fill doesn't draw the last stroke either).

D

On 30 Mar 2011, at 22:38, Davide Della Casa wrote:

hmmm the endFill doesn't seem to fix it either...

D

On 30 Mar 2011, at 21:29, Tarwin Stroh-Spijer wrote:

You might also want to do an explicit endFill. I think Flash does these auto-magically which is argueably bad.


Tarwin Stroh-Spijer
_______________________

Touch My Pixel
http://www.touchmypixel.com/
phone: +61 3 8060 5321
_______________________


On Thu, Mar 31, 2011 at 7:18 AM, Jan Flanders <[hidden email]> wrote:
Have you tried closing the path/shape with a final: graphics.lineTo( 70, 0 );
It seems to be implicitly closing the path or shape by using the
before last coordinate instead of the last.

Jan

On Wed, Mar 30, 2011 at 9:14 PM, Davide Della Casa <[hidden email]> wrote:
Hi Hugh, All,

I noticed a substantial difference in how nekonme strokes/fills a path as opposed to flash - at least in an instance I stumbled upon today.

Here is the link to the two programs (haxe vs flash) and pictures of the simplest shape that shows the difference (five vertexes):
https://docs.google.com/present/edit?id=0AdIoFN4Io_zNZGQ5Ymp2NmNfNjQxNXgybms2OGc&hl=en_GB

Is this a known difference between the rendering engines, or some flag/way of doing things that I'm not aware of? Or rather a bug?

Cheers,
Davide Della Casa
--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org

--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org



--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: nekonme: glitch with graphics shape drawing?

Gamehaxe
In reply to this post by davidedc
Hi,
That is an old file - the code has been rearranged since then.
The current code is in "Hardware.cpp", in "AddObject".
Here, it walks over the "Commands" for lineto/moveto commands
an adds them to the "vertices" arrays. A single "DrawElement" is
built with a reference to a sub-range of the vertices.
The type is set with something like this: mElement.mPrimType =  
inJob.mTriangles ? ptTriangles : ptTriangleFan

So just before the elements.push_back(mElement), you could check to see if
it is a triangle fan for a concave object and actually add several smaller  
elements
instead.  Each of these "elements" corresponds to a gl draw call in the  
OpenGLCOntext.cpp.
If you do this here, then the code will already have broken the curves into
a series of lines.

The "Job" at this point is either a line (stroke) job or a fill job.
The begin/end is partially handled here I think ("last move" etc),
but perhaps in the calling routine too - can't remember. First, work
out if it is only an opengl problem, or if the software render has the
same issues too.

Hugh




> I see.
>
> There is a "TODO: tesselate" comment in draw_object.cpp line 533 (  
> http://www.google.com/codesearch/p?hl=en#Z6a0dKU6Lh4/trunk/project/draw_object.cpp&q=lineTo%20package:http://nekonme%5C.googlecode%5C.com&l=553 
> ), is that the place?
>
> Could I just put in there in line 555 a call to a triangulation routine  
> that takes mPoints and returns a new array of "triangulated" points?  
> Maybe change n with the new triangle count? Would that local change be  
> sufficient or would it be a deeper change than that?If that's  
> sufficient, have you got a preferred triangulation routine?
>
> And how about the last "closing" stroke, any pointers to that?
>
> Lots of questions, sorry, I'm using lots of vector graphics...
>
> Cheers,
> Davide
>
> On 31 Mar 2011, at 01:02, Hugh Sanderson wrote:
>
>> Hi,
>> Yes - it is using a triangle fan.
>> The software renderer does this correctly, but the opengl renderer
>> goes for the fastest method, which is wrong for concave objects.
>> The "correct" answer is to triangulate the objects, which is possible,
>> but I have not got around to this.
>>
>> Hugh
>>
>>> It's like, for the fill, the path seems to be rendered with a triangle  
>>> fan (sharing the first vertex), instead of a polygon path.
>>>
>>> The stroke is just not closed (doing the end-fill doesn't draw the  
>>> last stroke either).
>>>
>>> D
>>>
>>> On 30 Mar 2011, at 22:38, Davide Della Casa wrote:
>>>
>>>> hmmm the endFill doesn't seem to fix it either...
>>>>
>>>> D
>>>>
>>>> On 30 Mar 2011, at 21:29, Tarwin Stroh-Spijer wrote:
>>>>
>>>>> You might also want to do an explicit endFill. I think Flash does  
>>>>> these auto-magically which is argueably bad.
>>>>>
>>>>>
>>>>> Tarwin Stroh-Spijer
>>>>> _______________________
>>>>>
>>>>> Touch My Pixel
>>>>> http://www.touchmypixel.com/
>>>>> phone: +61 3 8060 5321
>>>>> _______________________
>>>>>
>>>>>
>>>>> On Thu, Mar 31, 2011 at 7:18 AM, Jan Flanders <[hidden email]>  
>>>>> wrote:
>>>>> Have you tried closing the path/shape with a final: graphics.lineTo(  
>>>>> 70, 0 );
>>>>> It seems to be implicitly closing the path or shape by using the
>>>>> before last coordinate instead of the last.
>>>>>
>>>>> Jan
>>>>>
>>>>> On Wed, Mar 30, 2011 at 9:14 PM, Davide Della Casa  
>>>>> <[hidden email]> wrote:
>>>>> > Hi Hugh, All,
>>>>> >
>>>>> > I noticed a substantial difference in how nekonme strokes/fills a  
>>>>> path as opposed to flash - at least in an instance I stumbled upon  
>>>>> today.
>>>>> >
>>>>> > Here is the link to the two programs (haxe vs flash) and pictures  
>>>>> of the simplest shape that shows the difference (five vertexes):
>>>>> >  
>>>>> https://docs.google.com/present/edit?id=0AdIoFN4Io_zNZGQ5Ymp2NmNfNjQxNXgybms2OGc&hl=en_GB
>>>>> >
>>>>> > Is this a known difference between the rendering engines, or some  
>>>>> flag/way of doing things that I'm not aware of? Or rather a bug?
>>>>> >
>>>>> > Cheers,
>>>>> > Davide Della Casa
>>>>> > --
>>>>> > haXe - an open source web programming language
>>>>> > http://haxe.org
>>>>> >
>>>>>
>>>>> --
>>>>> haXe - an open source web programming language
>>>>> http://haxe.org
>>>>>
>>>>> --
>>>>> haXe - an open source web programming language
>>>>> http://haxe.org
>>>>
>>
>> --
>> haXe - an open source web programming language
>> http://haxe.org
>
>
> --
> haXe - an open source web programming language
> http://haxe.org

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: nekonme: glitch with graphics shape drawing?

Gamehaxe
In reply to this post by davidedc
Hi,
You might be able to do a quick test to see if a poly needs tesselation
(it is possible to have 1 concave point if that is where you start)
by making sure the triangles don't double back by checking the sign
of the cross product of all the triangles in the fan.
This would keep the code efficient in the case where triangulation
is not required. eg, round rectangles etc.
Fans/strips are more efficient than single triangles (require fewer
vertices to specify) so are better if you can do it.
A simple algorithm is to just built the fan until you can't any longer,
and the start a new one.  You have to stop when the triangles double
back, or when the triangle contains another point in the contour (so
it is slightly more complex than the "do I need to do anything" test).
And you have to start where the angle is <=180 in the "inside" sense.

But anything you come up with will be good, as long at a fast test is
done first to determine if you need to do more processing.

Hugh


> P.S. I just read this survey on triangulation routines here  
> http://www.vterrain.org/Implementation/Libs/triangulate.html .
>
> There is one with a good review which is very compact (1-page) and  
> self-contained, would be probably something within my abilities to  
> integrate in nekonme:  
> http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml
>
> Doesn't support holes, but it would be a start.
>
> D
>
> On 31 Mar 2011, at 10:59, Davide Della Casa wrote:
>
>> I see.
>>
>> There is a "TODO: tesselate" comment in draw_object.cpp line 533 (  
>> http://www.google.com/codesearch/p?hl=en#Z6a0dKU6Lh4/trunk/project/draw_object.cpp&q=lineTo%20package:http://nekonme%5C.googlecode%5C.com&l=553 
>> ), is that the place?
>>
>> Could I just put in there in line 555 a call to a triangulation routine  
>> that takes mPoints and returns a new array of "triangulated" points?  
>> Maybe change n with the new triangle count? Would that local change be  
>> sufficient or would it be a deeper change than that?If that's  
>> sufficient, have you got a preferred triangulation routine?
>>
>> And how about the last "closing" stroke, any pointers to that?
>>
>> Lots of questions, sorry, I'm using lots of vector graphics...
>>
>> Cheers,
>> Davide
>>
>> On 31 Mar 2011, at 01:02, Hugh Sanderson wrote:
>>
>>> Hi,
>>> Yes - it is using a triangle fan.
>>> The software renderer does this correctly, but the opengl renderer
>>> goes for the fastest method, which is wrong for concave objects.
>>> The "correct" answer is to triangulate the objects, which is possible,
>>> but I have not got around to this.
>>>
>>> Hugh
>>>
>>>> It's like, for the fill, the path seems to be rendered with a  
>>>> triangle fan (sharing the first vertex), instead of a polygon path.
>>>>
>>>> The stroke is just not closed (doing the end-fill doesn't draw the  
>>>> last stroke either).
>>>>
>>>> D
>>>>
>>>> On 30 Mar 2011, at 22:38, Davide Della Casa wrote:
>>>>
>>>>> hmmm the endFill doesn't seem to fix it either...
>>>>>
>>>>> D
>>>>>
>>>>> On 30 Mar 2011, at 21:29, Tarwin Stroh-Spijer wrote:
>>>>>
>>>>>> You might also want to do an explicit endFill. I think Flash does  
>>>>>> these auto-magically which is argueably bad.
>>>>>>
>>>>>>
>>>>>> Tarwin Stroh-Spijer
>>>>>> _______________________
>>>>>>
>>>>>> Touch My Pixel
>>>>>> http://www.touchmypixel.com/
>>>>>> phone: +61 3 8060 5321
>>>>>> _______________________
>>>>>>
>>>>>>
>>>>>> On Thu, Mar 31, 2011 at 7:18 AM, Jan Flanders <[hidden email]>  
>>>>>> wrote:
>>>>>> Have you tried closing the path/shape with a final:  
>>>>>> graphics.lineTo( 70, 0 );
>>>>>> It seems to be implicitly closing the path or shape by using the
>>>>>> before last coordinate instead of the last.
>>>>>>
>>>>>> Jan
>>>>>>
>>>>>> On Wed, Mar 30, 2011 at 9:14 PM, Davide Della Casa  
>>>>>> <[hidden email]> wrote:
>>>>>>> Hi Hugh, All,
>>>>>>>
>>>>>>> I noticed a substantial difference in how nekonme strokes/fills a  
>>>>>>> path as opposed to flash - at least in an instance I stumbled upon  
>>>>>>> today.
>>>>>>>
>>>>>>> Here is the link to the two programs (haxe vs flash) and pictures  
>>>>>>> of the simplest shape that shows the difference (five vertexes):
>>>>>>> https://docs.google.com/present/edit?id=0AdIoFN4Io_zNZGQ5Ymp2NmNfNjQxNXgybms2OGc&hl=en_GB
>>>>>>>
>>>>>>> Is this a known difference between the rendering engines, or some  
>>>>>>> flag/way of doing things that I'm not aware of? Or rather a bug?
>>>>>>>
>>>>>>> Cheers,
>>>>>>> Davide Della Casa
>>>>>>> --
>>>>>>> haXe - an open source web programming language
>>>>>>> http://haxe.org
>>>>>>>
>>>>>>
>>>>>> --
>>>>>> haXe - an open source web programming language
>>>>>> http://haxe.org
>>>>>>
>>>>>> --
>>>>>> haXe - an open source web programming language
>>>>>> http://haxe.org
>>>>>
>>>
>>> --
>>> haXe - an open source web programming language
>>> http://haxe.org
>>

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: nekonme: glitch with graphics shape drawing?

Gamehaxe
In reply to this post by davidedc
Hi,
Also, in a previous life, I implemented the "FIST" triangulation.
See below for a fragment of the general idea.  This does not try
to build "big fans", but pulls out individual triangles.
You can also create a single element of type "triangles", and dump
all the individual triangles in there.

I have not compiled this for many years - but at least this code is my
code, so it is public domain (now).

The hardest thing about taking an existing algorithm is to make it
work with the existing data structures - so good luck.

Hugh





void DebugPoly(const TS2DList &poly)
    {
    for(TS2DList::const_iterator p=poly.begin();p!=poly.end();++p)
       printf(" %d,%d\n",(*p).x,(*p).y);
    }
// Triangulate using ear clipping method ...
typedef std::list<TS2D> TS2DPoints;
typedef std::set<TS2D> PointSet;

struct LPoint
    {
    TS2D   p;
    int    pid;
    LPoint *next;
    LPoint *prev;

    double cross()
       {
       TS2D to_prev = prev->p - p;
       TS2D to_next = next->p - p;
       return to_prev.cross(to_next);
       }
    bool concave()
       {
       return(cross()>0.0);
       }

    bool convex()
       {
       return(cross()<0.0);
       }
    };

typedef std::vector<LPoint> LPoints;
typedef QUnorderedSet<LPoint *,OffsetIDX<LPoint *> > PointPtrSet;


bool IsEar(const PointPtrSet &concave_points,LPoint *pi)
    {
    LPoint *prev = pi->prev;

    TS2D corner(prev->p);
    if (concave_points.contains(prev))
       return(false);

    TS2D v1( pi->p - corner );
    TS2D v2( prev->prev->p - corner );
    double denom = v1.cross(v2);

    if (denom==0.0)  // flat triangle
       {
       // Need to be consistent so we don't get opposite-sense triangles
       //  over the top of each other.
       // Don't worry about this here !
       return true;
       }


    PointPtrSet::const_iterator it = concave_points.begin();
    PointPtrSet::const_iterator end = concave_points.end();
    for( ; it!=end; ++it )
       {
       TS2D v( (*it)->p-corner );
       double a = v.cross(v2);
       double b = v1.cross(v);
       if (a>=0.0 && b>=0.0 && (a+b)<denom && (a+b)>0)
          return false;
       }
    return(true);
    }

bool FindDiag(const PointPtrSet &concave_points,LPoint *p0,
        LPoint *&p1,LPoint *&p2)
    {
    LPoint *p = p0;
    int point;
    double beta;
    do {
       //if (concave_points.find(p)==concave_points.end())
          {
          TS2D corner = p->p;
          TS2D v1( p->prev->p - corner );
          TS2D v2( p->next->p - corner );
          double denom = v1.cross(v2);
          for(LPoint *other=p->next; other!= p->prev; other = other->next)
             {
             TS2D v( other->p-corner );
             double a = v.cross(v2);
             double b = v1.cross(v);
             if (a>0.0 && b>0.0)
                {
                // Found candidate, check for intersections ...
                for(LPoint *l=p->prev;l!=other->next;l=l->prev)
                   if  
(Intersect(v,l->p-corner,l->prev->p-corner,point,beta))
                      break;
                if (l!=other->next) continue;

                for(LPoint *r=p->next;l!=other->prev;r=r->next)
                   if  
(Intersect(v,r->p-corner,r->next->p-corner,point,beta))
                      break;
                if (r!=other->prev) continue;

                // found !
                p1 = p;
                p2 = other;
                return true;
                }
             }
          }
       p = p->next;
       } while(p!=p0);

    return(false);
    }





void CheckConcave(const PointPtrSet &points,LPoint *p0,int size)
    {
    LPoint *p = p0;
    int osize = size;
    do
       {
       bool is_concave =  points.contains(p);
       if ( is_concave != p->concave() )
          {
          printf("Convex error %d (%d,%d) ?\n",osize,p->p.x,p->p.y);
          printf("  found : %d\n",points.find(p)!=points.end());
          printf("  concave : %d\n",p->concave());
          *(int *)0=0;
          }
       size --;
       p = p->next;
       } while(p!=p0);
    if (size!=0)
       printf("Odd size ?\n");
    }

void Recalc(PointPtrSet &concave_points,LPoint *pi)
    {
    if ( concave_points.contains(pi) )
       {
       if ( !pi->concave() )
          concave_points.erase(pi);
       }
    else
       {
       if ( pi->concave() )
          concave_points.insert(pi);
       }
    }


static int debug_file = 0;

void Triangulate(TriList &triangles,const int *point_id,int size,
       const TS2D *point_val,IntVec *bad_tri)
    {
    int i;

    LPoints     lpoints(size);

    triangles.reserve(triangles.size()+size-1);

    int dest = 0;
    for(i=0;i<size;++i)
       {
       if ( dest==0 || lpoints[dest-1].pid != point_id[i])
          {
          lpoints[dest].p =    point_val[point_id[i]];
          lpoints[dest].pid =  point_id[i];
          dest++;
          }
       }
    size = dest;
    for(i=0;i<size;++i)
       {
       lpoints[i].next = &lpoints[ (i+1)%size ];
       lpoints[i].prev = &lpoints[ (i+size-1)%size ];
       }

    LPoint *p0 = &lpoints[0];
    PointPtrSet concave_points(OffsetIDX<LPoint *>(p0),size);

    int osize  = size;
    LPoint *pi=0;

    bool force_ear = false;

    LPoint *p_con = p0;
    do
       {
       if (p_con->concave())
          concave_points.insert(p_con);
       p_con = p_con->next;
       } while(p_con!=p0);


    while(size>2)
       {
       if (!force_ear)
          pi = p0->next->next;

       while((force_ear || pi!=p0) && size>2)
          {
          if (concave_points.empty() || IsEar(concave_points,pi) ||
               force_ear)
             {
             // Have ear triangle - yay - clip it
             /*
               pi->pr->pr  pi->prev
                     /+----+
                    /  ..   \
                   /     ..  \
                           .. +-----
                            pi

             */
             Tri tri;

             //if (!force_ear || pi->prev->convex())
                {
                tri.pid[0] = pi->prev->prev->pid;
                tri.pid[1] = pi->prev->pid;
                tri.pid[2] = pi->pid;

                if (tri.pid[0]!=tri.pid[1] && tri.pid[1]!=tri.pid[2]
                   && tri.pid[0]!=tri.pid[2])
                   triangles.push_back(tri);
                #ifdef DOPRINT
                else
                   printf("Degenerate tri.\n");
                #endif
                }

             // Snip pi->prev...
             concave_points.erase( pi->prev );

             pi->prev->prev->next = pi;
             pi->prev = pi->prev->prev;
             // Have we become concave or convex ?
             Recalc(concave_points,pi);
             // Has the previous one become convex ?
             Recalc(concave_points,pi->prev);

             // Start at p0 again ...
             if (pi->prev == p0)
                pi=pi->next;

             size --;
             // CheckConcave(concave_points,p0,size);
             force_ear = false;
             }
          else
             pi = pi->next;
          }
       if (size>2 )
          {
          if ( bad_tri)
             {
             LPoint *b1=0,*b2=0;
             /*
             if (0 && FindDiag(concave_points,p0,b1,b2))
                {
                // Call recursively...
                IntVec loop1;
                loop1.reserve(size);
                LPoint *p;
                for(p=b1;p!=b2;p=p->next)
                   loop1.push_back(p->pid);
                loop1.push_back(p->pid);

                Triangulate(triangles,loop1,point_val,bad_tri);

                IntVec loop2;
                loop2.reserve(size);
                for(p=b2;p!=b1;p=p->next)
                   loop2.push_back(p->pid);
                loop2.push_back(p->pid);

                Triangulate(triangles,loop2,point_val,bad_tri);
                break;
                }
             else
             */
                {
                // No diagonals - just finish up ...
                /*
                for(int j=0;j<point_id.size();j++)
                   {
                   bad_tri->push_back(point_id[j]);
                   bad_tri->push_back(point_id[ (j+1)%point_id.size()]);
                   }
                */
                pi = p0;
                do
                  {
                  bad_tri->push_back(pi->pid);
                  bad_tri->push_back(pi->next->pid);
                  pi = pi->next;
                  } while(pi!=p0);
                bad_tri = 0;
                break;
                }
             }

          #ifdef DOPRINT
          printf("Mis-triangulated points : %d\n",size);

          pi = p0;
          do
            {
            printf(" %d,%d,%d\n",pi->p.x,pi->p.y,
                  concave_points.find(pi)!=concave_points.end());
            pi = pi->next;
            } while(pi!=p0);
          printf("----\n");
          #endif

          //printf("From\n");
          //DebugPoly(point_id);

          // look for "least concave" point ...
          pi = p0->next->next;
          double best_val = -1e99;
          LPoint *least_concave = 0;
          double smallest_val = 1e99;
          LPoint *smallest = 0;
          while(pi!=p0)
             {
             //if (concave_points.find(pi->prev)!=concave_points.end())
             if (concave_points.contains(pi->prev))
                {
                double cross = pi->cross();
                if (cross>best_val)
                   {
                   best_val = cross;
                   least_concave = pi;
                   }
                }
             else if (!least_concave)
                {
                double cross = pi->cross();
                if (cross<smallest_val)
                   {
                   smallest_val = cross;
                   smallest = pi;
                   }
                }
             pi = pi->next;
             }

          if (least_concave)
             pi = least_concave;
          else
             pi = smallest;

          force_ear = true;
          }
       }
    }

> P.S. I just read this survey on triangulation routines here  
> http://www.vterrain.org/Implementation/Libs/triangulate.html .
>
> There is one with a good review which is very compact (1-page) and  
> self-contained, would be probably something within my abilities to  
> integrate in nekonme:  
> http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml
>
> Doesn't support holes, but it would be a start.
>
>
>>>
>>> --
>>> haXe - an open source web programming language
>>> http://haxe.org
>>

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: nekonme: glitch with graphics shape drawing?

davidedc
Hi Hugh,

I'll start easy trying not to ruin performance in normal convex cases. I'll wait for the vertexes to be all in, then run this algorithm http://is.gd/oSxtMJ , then if concave split into simple triangles using this one http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml end then spend like a month debugging, and then maybe after a tough-base to the looney bin we can revisit. Hopefully the bottlenecks will be somewhere else completely (wishful thinking).

Can we keep track of whether the path was originated by standard "flash" functions for convex shapes (drawCircle and the likes)? Could we skip any convexity test whatsoever in that case? Or would there be complications due to intersecting shapes? Oh my, I don't even want to start thinking about intersecting shapes.

Cheers,
Davide

On 31 Mar 2011, at 14:52, Hugh Sanderson wrote:

Hi,
Also, in a previous life, I implemented the "FIST" triangulation.
See below for a fragment of the general idea.  This does not try
to build "big fans", but pulls out individual triangles.
You can also create a single element of type "triangles", and dump
all the individual triangles in there.

I have not compiled this for many years - but at least this code is my
code, so it is public domain (now).

The hardest thing about taking an existing algorithm is to make it
work with the existing data structures - so good luck.

Hugh





void DebugPoly(const TS2DList &poly)
  {
  for(TS2DList::const_iterator p=poly.begin();p!=poly.end();++p)
     printf(" %d,%d\n",(*p).x,(*p).y);
  }
// Triangulate using ear clipping method ...
typedef std::list<TS2D> TS2DPoints;
typedef std::set<TS2D> PointSet;

struct LPoint
  {
  TS2D   p;
  int    pid;
  LPoint *next;
  LPoint *prev;

  double cross()
     {
     TS2D to_prev = prev->p - p;
     TS2D to_next = next->p - p;
     return to_prev.cross(to_next);
     }
  bool concave()
     {
     return(cross()>0.0);
     }

  bool convex()
     {
     return(cross()<0.0);
     }
  };

typedef std::vector<LPoint> LPoints;
typedef QUnorderedSet<LPoint *,OffsetIDX<LPoint *> > PointPtrSet;


bool IsEar(const PointPtrSet &concave_points,LPoint *pi)
  {
  LPoint *prev = pi->prev;

  TS2D corner(prev->p);
  if (concave_points.contains(prev))
     return(false);

  TS2D v1( pi->p - corner );
  TS2D v2( prev->prev->p - corner );
  double denom = v1.cross(v2);

  if (denom==0.0)  // flat triangle
     {
     // Need to be consistent so we don't get opposite-sense triangles
     //  over the top of each other.
     // Don't worry about this here !
     return true;
     }


  PointPtrSet::const_iterator it = concave_points.begin();
  PointPtrSet::const_iterator end = concave_points.end();
  for( ; it!=end; ++it )
     {
     TS2D v( (*it)->p-corner );
     double a = v.cross(v2);
     double b = v1.cross(v);
     if (a>=0.0 && b>=0.0 && (a+b)<denom && (a+b)>0)
        return false;
     }
  return(true);
  }

bool FindDiag(const PointPtrSet &concave_points,LPoint *p0,
      LPoint *&p1,LPoint *&p2)
  {
  LPoint *p = p0;
  int point;
  double beta;
  do {
     //if (concave_points.find(p)==concave_points.end())
        {
        TS2D corner = p->p;
        TS2D v1( p->prev->p - corner );
        TS2D v2( p->next->p - corner );
        double denom = v1.cross(v2);
        for(LPoint *other=p->next; other!= p->prev; other = other->next)
           {
           TS2D v( other->p-corner );
           double a = v.cross(v2);
           double b = v1.cross(v);
           if (a>0.0 && b>0.0)
              {
              // Found candidate, check for intersections ...
              for(LPoint *l=p->prev;l!=other->next;l=l->prev)
                 if (Intersect(v,l->p-corner,l->prev->p-corner,point,beta))
                    break;
              if (l!=other->next) continue;

              for(LPoint *r=p->next;l!=other->prev;r=r->next)
                 if (Intersect(v,r->p-corner,r->next->p-corner,point,beta))
                    break;
              if (r!=other->prev) continue;

              // found !
              p1 = p;
              p2 = other;
              return true;
              }
           }
        }
     p = p->next;
     } while(p!=p0);

  return(false);
  }





void CheckConcave(const PointPtrSet &points,LPoint *p0,int size)
  {
  LPoint *p = p0;
  int osize = size;
  do
     {
     bool is_concave =  points.contains(p);
     if ( is_concave != p->concave() )
        {
        printf("Convex error %d (%d,%d) ?\n",osize,p->p.x,p->p.y);
        printf("  found : %d\n",points.find(p)!=points.end());
        printf("  concave : %d\n",p->concave());
        *(int *)0=0;
        }
     size --;
     p = p->next;
     } while(p!=p0);
  if (size!=0)
     printf("Odd size ?\n");
  }

void Recalc(PointPtrSet &concave_points,LPoint *pi)
  {
  if ( concave_points.contains(pi) )
     {
     if ( !pi->concave() )
        concave_points.erase(pi);
     }
  else
     {
     if ( pi->concave() )
        concave_points.insert(pi);
     }
  }


static int debug_file = 0;

void Triangulate(TriList &triangles,const int *point_id,int size,
     const TS2D *point_val,IntVec *bad_tri)
  {
  int i;

  LPoints     lpoints(size);

  triangles.reserve(triangles.size()+size-1);

  int dest = 0;
  for(i=0;i<size;++i)
     {
     if ( dest==0 || lpoints[dest-1].pid != point_id[i])
        {
        lpoints[dest].p =    point_val[point_id[i]];
        lpoints[dest].pid =  point_id[i];
        dest++;
        }
     }
  size = dest;
  for(i=0;i<size;++i)
     {
     lpoints[i].next = &lpoints[ (i+1)%size ];
     lpoints[i].prev = &lpoints[ (i+size-1)%size ];
     }

  LPoint *p0 = &lpoints[0];
  PointPtrSet concave_points(OffsetIDX<LPoint *>(p0),size);

  int osize  = size;
  LPoint *pi=0;

  bool force_ear = false;

  LPoint *p_con = p0;
  do
     {
     if (p_con->concave())
        concave_points.insert(p_con);
     p_con = p_con->next;
     } while(p_con!=p0);


  while(size>2)
     {
     if (!force_ear)
        pi = p0->next->next;

     while((force_ear || pi!=p0) && size>2)
        {
        if (concave_points.empty() || IsEar(concave_points,pi) ||
             force_ear)
           {
           // Have ear triangle - yay - clip it
           /*
             pi->pr->pr  pi->prev
                   /+----+
                  /  ..   \
                 /     ..  \
                         .. +-----
                          pi

           */
           Tri tri;

           //if (!force_ear || pi->prev->convex())
              {
              tri.pid[0] = pi->prev->prev->pid;
              tri.pid[1] = pi->prev->pid;
              tri.pid[2] = pi->pid;

              if (tri.pid[0]!=tri.pid[1] && tri.pid[1]!=tri.pid[2]
                 && tri.pid[0]!=tri.pid[2])
                 triangles.push_back(tri);
              #ifdef DOPRINT
              else
                 printf("Degenerate tri.\n");
              #endif
              }

           // Snip pi->prev...
           concave_points.erase( pi->prev );

           pi->prev->prev->next = pi;
           pi->prev = pi->prev->prev;
           // Have we become concave or convex ?
           Recalc(concave_points,pi);
           // Has the previous one become convex ?
           Recalc(concave_points,pi->prev);

           // Start at p0 again ...
           if (pi->prev == p0)
              pi=pi->next;

           size --;
           // CheckConcave(concave_points,p0,size);
           force_ear = false;
           }
        else
           pi = pi->next;
        }
     if (size>2 )
        {
        if ( bad_tri)
           {
           LPoint *b1=0,*b2=0;
           /*
           if (0 && FindDiag(concave_points,p0,b1,b2))
              {
              // Call recursively...
              IntVec loop1;
              loop1.reserve(size);
              LPoint *p;
              for(p=b1;p!=b2;p=p->next)
                 loop1.push_back(p->pid);
              loop1.push_back(p->pid);

              Triangulate(triangles,loop1,point_val,bad_tri);

              IntVec loop2;
              loop2.reserve(size);
              for(p=b2;p!=b1;p=p->next)
                 loop2.push_back(p->pid);
              loop2.push_back(p->pid);

              Triangulate(triangles,loop2,point_val,bad_tri);
              break;
              }
           else
           */
              {
              // No diagonals - just finish up ...
              /*
              for(int j=0;j<point_id.size();j++)
                 {
                 bad_tri->push_back(point_id[j]);
                 bad_tri->push_back(point_id[ (j+1)%point_id.size()]);
                 }
              */
              pi = p0;
              do
                {
                bad_tri->push_back(pi->pid);
                bad_tri->push_back(pi->next->pid);
                pi = pi->next;
                } while(pi!=p0);
              bad_tri = 0;
              break;
              }
           }

        #ifdef DOPRINT
        printf("Mis-triangulated points : %d\n",size);

        pi = p0;
        do
          {
          printf(" %d,%d,%d\n",pi->p.x,pi->p.y,
                concave_points.find(pi)!=concave_points.end());
          pi = pi->next;
          } while(pi!=p0);
        printf("----\n");
        #endif

        //printf("From\n");
        //DebugPoly(point_id);

        // look for "least concave" point ...
        pi = p0->next->next;
        double best_val = -1e99;
        LPoint *least_concave = 0;
        double smallest_val = 1e99;
        LPoint *smallest = 0;
        while(pi!=p0)
           {
           //if (concave_points.find(pi->prev)!=concave_points.end())
           if (concave_points.contains(pi->prev))
              {
              double cross = pi->cross();
              if (cross>best_val)
                 {
                 best_val = cross;
                 least_concave = pi;
                 }
              }
           else if (!least_concave)
              {
              double cross = pi->cross();
              if (cross<smallest_val)
                 {
                 smallest_val = cross;
                 smallest = pi;
                 }
              }
           pi = pi->next;
           }

        if (least_concave)
           pi = least_concave;
        else
           pi = smallest;

        force_ear = true;
        }
     }
  }

P.S. I just read this survey on triangulation routines here http://www.vterrain.org/Implementation/Libs/triangulate.html .

There is one with a good review which is very compact (1-page) and self-contained, would be probably something within my abilities to integrate in nekonme: http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml

Doesn't support holes, but it would be a start.



--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org


--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: nekonme: glitch with graphics shape drawing?

Joshua Harlan Lifton
Hi Davide and Hugh,

I just ran into this same problem with concave fills. Any progress
toward a solution? Happy to help where I can.

Cheers,
Josh

On Thu, Mar 31, 2011 at 3:46 PM, Davide Della Casa <[hidden email]> wrote:

> Hi Hugh,
> I'll start easy trying not to ruin performance in normal convex cases. I'll
> wait for the vertexes to be all in, then run this
> algorithm http://is.gd/oSxtMJ , then if concave split into simple triangles
> using this
> one http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml end
> then spend like a month debugging, and then maybe after a tough-base to the
> looney bin we can revisit. Hopefully the bottlenecks will be somewhere else
> completely (wishful thinking).
> Can we keep track of whether the path was originated by standard "flash"
> functions for convex shapes (drawCircle and the likes)? Could we skip any
> convexity test whatsoever in that case? Or would there be complications due
> to intersecting shapes? Oh my, I don't even want to start thinking about
> intersecting shapes.
> Cheers,
> Davide
> On 31 Mar 2011, at 14:52, Hugh Sanderson wrote:
>
> Hi,
> Also, in a previous life, I implemented the "FIST" triangulation.
> See below for a fragment of the general idea.  This does not try
> to build "big fans", but pulls out individual triangles.
> You can also create a single element of type "triangles", and dump
> all the individual triangles in there.
>
> I have not compiled this for many years - but at least this code is my
> code, so it is public domain (now).
>
> The hardest thing about taking an existing algorithm is to make it
> work with the existing data structures - so good luck.
>
> Hugh
>
>
>
>
>
> void DebugPoly(const TS2DList &poly)
>   {
>   for(TS2DList::const_iterator p=poly.begin();p!=poly.end();++p)
>      printf(" %d,%d\n",(*p).x,(*p).y);
>   }
> // Triangulate using ear clipping method ...
> typedef std::list<TS2D> TS2DPoints;
> typedef std::set<TS2D> PointSet;
>
> struct LPoint
>   {
>   TS2D   p;
>   int    pid;
>   LPoint *next;
>   LPoint *prev;
>
>   double cross()
>      {
>      TS2D to_prev = prev->p - p;
>      TS2D to_next = next->p - p;
>      return to_prev.cross(to_next);
>      }
>   bool concave()
>      {
>      return(cross()>0.0);
>      }
>
>   bool convex()
>      {
>      return(cross()<0.0);
>      }
>   };
>
> typedef std::vector<LPoint> LPoints;
> typedef QUnorderedSet<LPoint *,OffsetIDX<LPoint *> > PointPtrSet;
>
>
> bool IsEar(const PointPtrSet &concave_points,LPoint *pi)
>   {
>   LPoint *prev = pi->prev;
>
>   TS2D corner(prev->p);
>   if (concave_points.contains(prev))
>      return(false);
>
>   TS2D v1( pi->p - corner );
>   TS2D v2( prev->prev->p - corner );
>   double denom = v1.cross(v2);
>
>   if (denom==0.0)  // flat triangle
>      {
>      // Need to be consistent so we don't get opposite-sense triangles
>      //  over the top of each other.
>      // Don't worry about this here !
>      return true;
>      }
>
>
>   PointPtrSet::const_iterator it = concave_points.begin();
>   PointPtrSet::const_iterator end = concave_points.end();
>   for( ; it!=end; ++it )
>      {
>      TS2D v( (*it)->p-corner );
>      double a = v.cross(v2);
>      double b = v1.cross(v);
>      if (a>=0.0 && b>=0.0 && (a+b)<denom && (a+b)>0)
>         return false;
>      }
>   return(true);
>   }
>
> bool FindDiag(const PointPtrSet &concave_points,LPoint *p0,
>       LPoint *&p1,LPoint *&p2)
>   {
>   LPoint *p = p0;
>   int point;
>   double beta;
>   do {
>      //if (concave_points.find(p)==concave_points.end())
>         {
>         TS2D corner = p->p;
>         TS2D v1( p->prev->p - corner );
>         TS2D v2( p->next->p - corner );
>         double denom = v1.cross(v2);
>         for(LPoint *other=p->next; other!= p->prev; other = other->next)
>            {
>            TS2D v( other->p-corner );
>            double a = v.cross(v2);
>            double b = v1.cross(v);
>            if (a>0.0 && b>0.0)
>               {
>               // Found candidate, check for intersections ...
>               for(LPoint *l=p->prev;l!=other->next;l=l->prev)
>                  if (Intersect(v,l->p-corner,l->prev->p-corner,point,beta))
>                     break;
>               if (l!=other->next) continue;
>
>               for(LPoint *r=p->next;l!=other->prev;r=r->next)
>                  if (Intersect(v,r->p-corner,r->next->p-corner,point,beta))
>                     break;
>               if (r!=other->prev) continue;
>
>               // found !
>               p1 = p;
>               p2 = other;
>               return true;
>               }
>            }
>         }
>      p = p->next;
>      } while(p!=p0);
>
>   return(false);
>   }
>
>
>
>
>
> void CheckConcave(const PointPtrSet &points,LPoint *p0,int size)
>   {
>   LPoint *p = p0;
>   int osize = size;
>   do
>      {
>      bool is_concave =  points.contains(p);
>      if ( is_concave != p->concave() )
>         {
>         printf("Convex error %d (%d,%d) ?\n",osize,p->p.x,p->p.y);
>         printf("  found : %d\n",points.find(p)!=points.end());
>         printf("  concave : %d\n",p->concave());
>         *(int *)0=0;
>         }
>      size --;
>      p = p->next;
>      } while(p!=p0);
>   if (size!=0)
>      printf("Odd size ?\n");
>   }
>
> void Recalc(PointPtrSet &concave_points,LPoint *pi)
>   {
>   if ( concave_points.contains(pi) )
>      {
>      if ( !pi->concave() )
>         concave_points.erase(pi);
>      }
>   else
>      {
>      if ( pi->concave() )
>         concave_points.insert(pi);
>      }
>   }
>
>
> static int debug_file = 0;
>
> void Triangulate(TriList &triangles,const int *point_id,int size,
>      const TS2D *point_val,IntVec *bad_tri)
>   {
>   int i;
>
>   LPoints     lpoints(size);
>
>   triangles.reserve(triangles.size()+size-1);
>
>   int dest = 0;
>   for(i=0;i<size;++i)
>      {
>      if ( dest==0 || lpoints[dest-1].pid != point_id[i])
>         {
>         lpoints[dest].p =    point_val[point_id[i]];
>         lpoints[dest].pid =  point_id[i];
>         dest++;
>         }
>      }
>   size = dest;
>   for(i=0;i<size;++i)
>      {
>      lpoints[i].next = &lpoints[ (i+1)%size ];
>      lpoints[i].prev = &lpoints[ (i+size-1)%size ];
>      }
>
>   LPoint *p0 = &lpoints[0];
>   PointPtrSet concave_points(OffsetIDX<LPoint *>(p0),size);
>
>   int osize  = size;
>   LPoint *pi=0;
>
>   bool force_ear = false;
>
>   LPoint *p_con = p0;
>   do
>      {
>      if (p_con->concave())
>         concave_points.insert(p_con);
>      p_con = p_con->next;
>      } while(p_con!=p0);
>
>
>   while(size>2)
>      {
>      if (!force_ear)
>         pi = p0->next->next;
>
>      while((force_ear || pi!=p0) && size>2)
>         {
>         if (concave_points.empty() || IsEar(concave_points,pi) ||
>              force_ear)
>            {
>            // Have ear triangle - yay - clip it
>            /*
>              pi->pr->pr  pi->prev
>                    /+----+
>                   /  ..   \
>                  /     ..  \
>                          .. +-----
>                           pi
>
>            */
>            Tri tri;
>
>            //if (!force_ear || pi->prev->convex())
>               {
>               tri.pid[0] = pi->prev->prev->pid;
>               tri.pid[1] = pi->prev->pid;
>               tri.pid[2] = pi->pid;
>
>               if (tri.pid[0]!=tri.pid[1] && tri.pid[1]!=tri.pid[2]
>                  && tri.pid[0]!=tri.pid[2])
>                  triangles.push_back(tri);
>               #ifdef DOPRINT
>               else
>                  printf("Degenerate tri.\n");
>               #endif
>               }
>
>            // Snip pi->prev...
>            concave_points.erase( pi->prev );
>
>            pi->prev->prev->next = pi;
>            pi->prev = pi->prev->prev;
>            // Have we become concave or convex ?
>            Recalc(concave_points,pi);
>            // Has the previous one become convex ?
>            Recalc(concave_points,pi->prev);
>
>            // Start at p0 again ...
>            if (pi->prev == p0)
>               pi=pi->next;
>
>            size --;
>            // CheckConcave(concave_points,p0,size);
>            force_ear = false;
>            }
>         else
>            pi = pi->next;
>         }
>      if (size>2 )
>         {
>         if ( bad_tri)
>            {
>            LPoint *b1=0,*b2=0;
>            /*
>            if (0 && FindDiag(concave_points,p0,b1,b2))
>               {
>               // Call recursively...
>               IntVec loop1;
>               loop1.reserve(size);
>               LPoint *p;
>               for(p=b1;p!=b2;p=p->next)
>                  loop1.push_back(p->pid);
>               loop1.push_back(p->pid);
>
>               Triangulate(triangles,loop1,point_val,bad_tri);
>
>               IntVec loop2;
>               loop2.reserve(size);
>               for(p=b2;p!=b1;p=p->next)
>                  loop2.push_back(p->pid);
>               loop2.push_back(p->pid);
>
>               Triangulate(triangles,loop2,point_val,bad_tri);
>               break;
>               }
>            else
>            */
>               {
>               // No diagonals - just finish up ...
>               /*
>               for(int j=0;j<point_id.size();j++)
>                  {
>                  bad_tri->push_back(point_id[j]);
>                  bad_tri->push_back(point_id[ (j+1)%point_id.size()]);
>                  }
>               */
>               pi = p0;
>               do
>                 {
>                 bad_tri->push_back(pi->pid);
>                 bad_tri->push_back(pi->next->pid);
>                 pi = pi->next;
>                 } while(pi!=p0);
>               bad_tri = 0;
>               break;
>               }
>            }
>
>         #ifdef DOPRINT
>         printf("Mis-triangulated points : %d\n",size);
>
>         pi = p0;
>         do
>           {
>           printf(" %d,%d,%d\n",pi->p.x,pi->p.y,
>                 concave_points.find(pi)!=concave_points.end());
>           pi = pi->next;
>           } while(pi!=p0);
>         printf("----\n");
>         #endif
>
>         //printf("From\n");
>         //DebugPoly(point_id);
>
>         // look for "least concave" point ...
>         pi = p0->next->next;
>         double best_val = -1e99;
>         LPoint *least_concave = 0;
>         double smallest_val = 1e99;
>         LPoint *smallest = 0;
>         while(pi!=p0)
>            {
>            //if (concave_points.find(pi->prev)!=concave_points.end())
>            if (concave_points.contains(pi->prev))
>               {
>               double cross = pi->cross();
>               if (cross>best_val)
>                  {
>                  best_val = cross;
>                  least_concave = pi;
>                  }
>               }
>            else if (!least_concave)
>               {
>               double cross = pi->cross();
>               if (cross<smallest_val)
>                  {
>                  smallest_val = cross;
>                  smallest = pi;
>                  }
>               }
>            pi = pi->next;
>            }
>
>         if (least_concave)
>            pi = least_concave;
>         else
>            pi = smallest;
>
>         force_ear = true;
>         }
>      }
>   }
>
> P.S. I just read this survey on triangulation routines here
> http://www.vterrain.org/Implementation/Libs/triangulate.html .
>
> There is one with a good review which is very compact (1-page) and
> self-contained, would be probably something within my abilities to integrate
> in nekonme:
> http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml
>
> Doesn't support holes, but it would be a start.
>
>
>
> --
>
> haXe - an open source web programming language
>
> http://haxe.org
>
>
> --
> haXe - an open source web programming language
> http://haxe.org
>
>
> --
> haXe - an open source web programming language
> http://haxe.org
>

--
haXe - an open source web programming language
http://haxe.org
Reply | Threaded
Open this post in threaded view
|

Re: nekonme: glitch with graphics shape drawing?

davidedc
Hi Joshua,

no progress on my side.

If this is still open, the way I'd do it is the way I've written below.

I don't think Hugh replied to whether we can/should "mark" the shapes that we know come from convex flash shapes (rounded rectangles, ellipses, etc.) - but that's an implementation detail to save some (many?) cpu cycles in a piece of code that Hugh was keen to keep fast. I'd assume it can be done.

I hope Hugh wasn't put off by my "looney bin" comment.

D

On 13 May 2011, at 19:30, Joshua Harlan Lifton wrote:

> Hi Davide and Hugh,
>
> I just ran into this same problem with concave fills. Any progress
> toward a solution? Happy to help where I can.
>
> Cheers,
> Josh
>
> On Thu, Mar 31, 2011 at 3:46 PM, Davide Della Casa <[hidden email]> wrote:
>> Hi Hugh,
>> I'll start easy trying not to ruin performance in normal convex cases. I'll
>> wait for the vertexes to be all in, then run this
>> algorithm http://is.gd/oSxtMJ , then if concave split into simple triangles
>> using this
>> one http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml end
>> then spend like a month debugging, and then maybe after a tough-base to the
>> looney bin we can revisit. Hopefully the bottlenecks will be somewhere else
>> completely (wishful thinking).
>> Can we keep track of whether the path was originated by standard "flash"
>> functions for convex shapes (drawCircle and the likes)? Could we skip any
>> convexity test whatsoever in that case? Or would there be complications due
>> to intersecting shapes? Oh my, I don't even want to start thinking about
>> intersecting shapes.
>> Cheers,
>> Davide
>> On 31 Mar 2011, at 14:52, Hugh Sanderson wrote:
>>
>> Hi,
>> Also, in a previous life, I implemented the "FIST" triangulation.
>> See below for a fragment of the general idea.  This does not try
>> to build "big fans", but pulls out individual triangles.
>> You can also create a single element of type "triangles", and dump
>> all the individual triangles in there.
>>
>> I have not compiled this for many years - but at least this code is my
>> code, so it is public domain (now).
>>
>> The hardest thing about taking an existing algorithm is to make it
>> work with the existing data structures - so good luck.
>>
>> Hugh
>>
>>
>>
>>
>>
>> void DebugPoly(const TS2DList &poly)
>>   {
>>   for(TS2DList::const_iterator p=poly.begin();p!=poly.end();++p)
>>      printf(" %d,%d\n",(*p).x,(*p).y);
>>   }
>> // Triangulate using ear clipping method ...
>> typedef std::list<TS2D> TS2DPoints;
>> typedef std::set<TS2D> PointSet;
>>
>> struct LPoint
>>   {
>>   TS2D   p;
>>   int    pid;
>>   LPoint *next;
>>   LPoint *prev;
>>
>>   double cross()
>>      {
>>      TS2D to_prev = prev->p - p;
>>      TS2D to_next = next->p - p;
>>      return to_prev.cross(to_next);
>>      }
>>   bool concave()
>>      {
>>      return(cross()>0.0);
>>      }
>>
>>   bool convex()
>>      {
>>      return(cross()<0.0);
>>      }
>>   };
>>
>> typedef std::vector<LPoint> LPoints;
>> typedef QUnorderedSet<LPoint *,OffsetIDX<LPoint *> > PointPtrSet;
>>
>>
>> bool IsEar(const PointPtrSet &concave_points,LPoint *pi)
>>   {
>>   LPoint *prev = pi->prev;
>>
>>   TS2D corner(prev->p);
>>   if (concave_points.contains(prev))
>>      return(false);
>>
>>   TS2D v1( pi->p - corner );
>>   TS2D v2( prev->prev->p - corner );
>>   double denom = v1.cross(v2);
>>
>>   if (denom==0.0)  // flat triangle
>>      {
>>      // Need to be consistent so we don't get opposite-sense triangles
>>      //  over the top of each other.
>>      // Don't worry about this here !
>>      return true;
>>      }
>>
>>
>>   PointPtrSet::const_iterator it = concave_points.begin();
>>   PointPtrSet::const_iterator end = concave_points.end();
>>   for( ; it!=end; ++it )
>>      {
>>      TS2D v( (*it)->p-corner );
>>      double a = v.cross(v2);
>>      double b = v1.cross(v);
>>      if (a>=0.0 && b>=0.0 && (a+b)<denom && (a+b)>0)
>>         return false;
>>      }
>>   return(true);
>>   }
>>
>> bool FindDiag(const PointPtrSet &concave_points,LPoint *p0,
>>       LPoint *&p1,LPoint *&p2)
>>   {
>>   LPoint *p = p0;
>>   int point;
>>   double beta;
>>   do {
>>      //if (concave_points.find(p)==concave_points.end())
>>         {
>>         TS2D corner = p->p;
>>         TS2D v1( p->prev->p - corner );
>>         TS2D v2( p->next->p - corner );
>>         double denom = v1.cross(v2);
>>         for(LPoint *other=p->next; other!= p->prev; other = other->next)
>>            {
>>            TS2D v( other->p-corner );
>>            double a = v.cross(v2);
>>            double b = v1.cross(v);
>>            if (a>0.0 && b>0.0)
>>               {
>>               // Found candidate, check for intersections ...
>>               for(LPoint *l=p->prev;l!=other->next;l=l->prev)
>>                  if (Intersect(v,l->p-corner,l->prev->p-corner,point,beta))
>>                     break;
>>               if (l!=other->next) continue;
>>
>>               for(LPoint *r=p->next;l!=other->prev;r=r->next)
>>                  if (Intersect(v,r->p-corner,r->next->p-corner,point,beta))
>>                     break;
>>               if (r!=other->prev) continue;
>>
>>               // found !
>>               p1 = p;
>>               p2 = other;
>>               return true;
>>               }
>>            }
>>         }
>>      p = p->next;
>>      } while(p!=p0);
>>
>>   return(false);
>>   }
>>
>>
>>
>>
>>
>> void CheckConcave(const PointPtrSet &points,LPoint *p0,int size)
>>   {
>>   LPoint *p = p0;
>>   int osize = size;
>>   do
>>      {
>>      bool is_concave =  points.contains(p);
>>      if ( is_concave != p->concave() )
>>         {
>>         printf("Convex error %d (%d,%d) ?\n",osize,p->p.x,p->p.y);
>>         printf("  found : %d\n",points.find(p)!=points.end());
>>         printf("  concave : %d\n",p->concave());
>>         *(int *)0=0;
>>         }
>>      size --;
>>      p = p->next;
>>      } while(p!=p0);
>>   if (size!=0)
>>      printf("Odd size ?\n");
>>   }
>>
>> void Recalc(PointPtrSet &concave_points,LPoint *pi)
>>   {
>>   if ( concave_points.contains(pi) )
>>      {
>>      if ( !pi->concave() )
>>         concave_points.erase(pi);
>>      }
>>   else
>>      {
>>      if ( pi->concave() )
>>         concave_points.insert(pi);
>>      }
>>   }
>>
>>
>> static int debug_file = 0;
>>
>> void Triangulate(TriList &triangles,const int *point_id,int size,
>>      const TS2D *point_val,IntVec *bad_tri)
>>   {
>>   int i;
>>
>>   LPoints     lpoints(size);
>>
>>   triangles.reserve(triangles.size()+size-1);
>>
>>   int dest = 0;
>>   for(i=0;i<size;++i)
>>      {
>>      if ( dest==0 || lpoints[dest-1].pid != point_id[i])
>>         {
>>         lpoints[dest].p =    point_val[point_id[i]];
>>         lpoints[dest].pid =  point_id[i];
>>         dest++;
>>         }
>>      }
>>   size = dest;
>>   for(i=0;i<size;++i)
>>      {
>>      lpoints[i].next = &lpoints[ (i+1)%size ];
>>      lpoints[i].prev = &lpoints[ (i+size-1)%size ];
>>      }
>>
>>   LPoint *p0 = &lpoints[0];
>>   PointPtrSet concave_points(OffsetIDX<LPoint *>(p0),size);
>>
>>   int osize  = size;
>>   LPoint *pi=0;
>>
>>   bool force_ear = false;
>>
>>   LPoint *p_con = p0;
>>   do
>>      {
>>      if (p_con->concave())
>>         concave_points.insert(p_con);
>>      p_con = p_con->next;
>>      } while(p_con!=p0);
>>
>>
>>   while(size>2)
>>      {
>>      if (!force_ear)
>>         pi = p0->next->next;
>>
>>      while((force_ear || pi!=p0) && size>2)
>>         {
>>         if (concave_points.empty() || IsEar(concave_points,pi) ||
>>              force_ear)
>>            {
>>            // Have ear triangle - yay - clip it
>>            /*
>>              pi->pr->pr  pi->prev
>>                    /+----+
>>                   /  ..   \
>>                  /     ..  \
>>                          .. +-----
>>                           pi
>>
>>            */
>>            Tri tri;
>>
>>            //if (!force_ear || pi->prev->convex())
>>               {
>>               tri.pid[0] = pi->prev->prev->pid;
>>               tri.pid[1] = pi->prev->pid;
>>               tri.pid[2] = pi->pid;
>>
>>               if (tri.pid[0]!=tri.pid[1] && tri.pid[1]!=tri.pid[2]
>>                  && tri.pid[0]!=tri.pid[2])
>>                  triangles.push_back(tri);
>>               #ifdef DOPRINT
>>               else
>>                  printf("Degenerate tri.\n");
>>               #endif
>>               }
>>
>>            // Snip pi->prev...
>>            concave_points.erase( pi->prev );
>>
>>            pi->prev->prev->next = pi;
>>            pi->prev = pi->prev->prev;
>>            // Have we become concave or convex ?
>>            Recalc(concave_points,pi);
>>            // Has the previous one become convex ?
>>            Recalc(concave_points,pi->prev);
>>
>>            // Start at p0 again ...
>>            if (pi->prev == p0)
>>               pi=pi->next;
>>
>>            size --;
>>            // CheckConcave(concave_points,p0,size);
>>            force_ear = false;
>>            }
>>         else
>>            pi = pi->next;
>>         }
>>      if (size>2 )
>>         {
>>         if ( bad_tri)
>>            {
>>            LPoint *b1=0,*b2=0;
>>            /*
>>            if (0 && FindDiag(concave_points,p0,b1,b2))
>>               {
>>               // Call recursively...
>>               IntVec loop1;
>>               loop1.reserve(size);
>>               LPoint *p;
>>               for(p=b1;p!=b2;p=p->next)
>>                  loop1.push_back(p->pid);
>>               loop1.push_back(p->pid);
>>
>>               Triangulate(triangles,loop1,point_val,bad_tri);
>>
>>               IntVec loop2;
>>               loop2.reserve(size);
>>               for(p=b2;p!=b1;p=p->next)
>>                  loop2.push_back(p->pid);
>>               loop2.push_back(p->pid);
>>
>>               Triangulate(triangles,loop2,point_val,bad_tri);
>>               break;
>>               }
>>            else
>>            */
>>               {
>>               // No diagonals - just finish up ...
>>               /*
>>               for(int j=0;j<point_id.size();j++)
>>                  {
>>                  bad_tri->push_back(point_id[j]);
>>                  bad_tri->push_back(point_id[ (j+1)%point_id.size()]);
>>                  }
>>               */
>>               pi = p0;
>>               do
>>                 {
>>                 bad_tri->push_back(pi->pid);
>>                 bad_tri->push_back(pi->next->pid);
>>                 pi = pi->next;
>>                 } while(pi!=p0);
>>               bad_tri = 0;
>>               break;
>>               }
>>            }
>>
>>         #ifdef DOPRINT
>>         printf("Mis-triangulated points : %d\n",size);
>>
>>         pi = p0;
>>         do
>>           {
>>           printf(" %d,%d,%d\n",pi->p.x,pi->p.y,
>>                 concave_points.find(pi)!=concave_points.end());
>>           pi = pi->next;
>>           } while(pi!=p0);
>>         printf("----\n");
>>         #endif
>>
>>         //printf("From\n");
>>         //DebugPoly(point_id);
>>
>>         // look for "least concave" point ...
>>         pi = p0->next->next;
>>         double best_val = -1e99;
>>         LPoint *least_concave = 0;
>>         double smallest_val = 1e99;
>>         LPoint *smallest = 0;
>>         while(pi!=p0)
>>            {
>>            //if (concave_points.find(pi->prev)!=concave_points.end())
>>            if (concave_points.contains(pi->prev))
>>               {
>>               double cross = pi->cross();
>>               if (cross>best_val)
>>                  {
>>                  best_val = cross;
>>                  least_concave = pi;
>>                  }
>>               }
>>            else if (!least_concave)
>>               {
>>               double cross = pi->cross();
>>               if (cross<smallest_val)
>>                  {
>>                  smallest_val = cross;
>>                  smallest = pi;
>>                  }
>>               }
>>            pi = pi->next;
>>            }
>>
>>         if (least_concave)
>>            pi = least_concave;
>>         else
>>            pi = smallest;
>>
>>         force_ear = true;
>>         }
>>      }
>>   }
>>
>> P.S. I just read this survey on triangulation routines here
>> http://www.vterrain.org/Implementation/Libs/triangulate.html .
>>
>> There is one with a good review which is very compact (1-page) and
>> self-contained, would be probably something within my abilities to integrate
>> in nekonme:
>> http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml
>>
>> Doesn't support holes, but it would be a start.
>>
>>
>>
>> --
>>
>> haXe - an open source web programming language
>>
>> http://haxe.org
>>
>>
>> --
>> haXe - an open source web programming language
>> http://haxe.org
>>
>>
>> --
>> haXe - an open source web programming language
>> http://haxe.org
>>
> --
> haXe - an open source web programming language
> http://haxe.org


--
haXe - an open source web programming language
http://haxe.org