Mark Gordon <mtg### [at] mailbagcom> wrote:
: If the polygons are not convex, recursively lop off pointy bits as
: triangles until they are.

  If you take any three points of the polygon, how can you be sure that
the triangle defined by them is completely inside the polygon?

-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):5;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message

Nieminen Juha wrote:
> 
> Mark Gordon <mtg### [at] mailbagcom> wrote:
> : If the polygons are not convex, recursively lop off pointy bits as
> : triangles until they are.
> 
>   If you take any three points of the polygon, how can you be sure that
> the triangle defined by them is completely inside the polygon?

I made implicit reference to a "pointy bit test" ... yeah, that's right.
;-)

Assume the polygon is defined as a sequence of points on its periphery. 
A triplet of points on the edge of the polygon forms a "pointy bit" (my
jargon) if the interior angle formed at the second point (as measured in
the plane defined by the three points) is less than 180 degrees.  If the
interior angle formed at the second point is greater than 180 degrees
it's an, um, "anti-pointy bit". :-)  If it's exactly 180, you may as
well remove the middle point as redundant.

Conversion to radians is left as an exercise for the reader. ;-)

Pardon me for being a bit punchy - didn't get much sleep.

-- 
Mark Gordon
mtg### [at] povrayorg

Post a reply to this message

On Mon, 30 Aug 1999 07:52:45 -0500, Mark Gordon wrote:
>Nieminen Juha wrote:
>> 
>> Mark Gordon <mtg### [at] mailbagcom> wrote:
>> : If the polygons are not convex, recursively lop off pointy bits as
>> : triangles until they are.
>> 
>>   If you take any three points of the polygon, how can you be sure that
>> the triangle defined by them is completely inside the polygon?
>
>I made implicit reference to a "pointy bit test" ... yeah, that's right.
>;-)
>
>Assume the polygon is defined as a sequence of points on its periphery. 
>A triplet of points on the edge of the polygon forms a "pointy bit" (my
>jargon) if the interior angle formed at the second point (as measured in
>the plane defined by the three points) is less than 180 degrees.  If the
>interior angle formed at the second point is greater than 180 degrees
>it's an, um, "anti-pointy bit". :-)  If it's exactly 180, you may as
>well remove the middle point as redundant.

Unfortunately, it's not quite that easy.  You can't lop of just any
pointy bit.  Take a simple isosceles triangle.  Add a new vertex at
the center of the base.  Move that vertex upward, so what you get looks
like a rather angular version of the Federation emblem from Star Trek.
Note that the angle surrounding the topmost vertex qualifies as a 
"pointy bit" yet the resulting triangle is neither inside nor outside
the polygon.

Post a reply to this message

Mark Gordon <mtg### [at] mailbagcom> wrote:
: Assume the polygon is defined as a sequence of points on its periphery. 
: A triplet of points on the edge of the polygon forms a "pointy bit" (my
: jargon) if the interior angle formed at the second point (as measured in
: the plane defined by the three points) is less than 180 degrees.  If the
: interior angle formed at the second point is greater than 180 degrees
: it's an, um, "anti-pointy bit". :-)  If it's exactly 180, you may as
: well remove the middle point as redundant.

  This doesn't work. A vertex of the polygon may lie inside the triangle.
If this is so, the triangle will be partially outside the polygon.
  Think about an 'L' made of 6 vertices. Now take the upper left vertex,
the lower left vertex and the lower right vertex. The triangle they define
"seems" to be inside the polygon, but it doesn't.

-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):5;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message

Ron Parker wrote:
> 
> Unfortunately, it's not quite that easy.  You can't lop of just any
> pointy bit.  Take a simple isosceles triangle.  Add a new vertex at
> the center of the base.  Move that vertex upward, so what you get looks
> like a rather angular version of the Federation emblem from Star Trek.
> Note that the angle surrounding the topmost vertex qualifies as a
> "pointy bit" yet the resulting triangle is neither inside nor outside
> the polygon.

Point well taken.  Like I said, I was a bit sleep deprived.

-- 
Mark Gordon
mtg### [at] povrayorg

Post a reply to this message

Hi,

>I wonder if Thomas has had similar problems. I have noticed that when converting
>some models with 3DWin that no matter what the smoothing angle specified there
>are some times a few to several triangles that are still represented as simple
>triangles instead of as smooth triangles.

Hmm, current 3DWin import of OBJ files is very simple. It processes
only face information (no normals or uv faces). Smoothing is done in a
seperate stage. 

I have found and tested some very strange OBJ files with missing
vertices, wrong face to vertex links, double faces and lots of
degenerated faces.

3DWin tries to fix this errors and throws out such faces.

-Thomas

Post a reply to this message

On Wed, 01 Sep 1999 06:11:34 GMT, NOS### [at] ibmnet (Thomas
Baier) wrote:

[snip]
>I have found and tested some very strange OBJ files with missing
>vertices, wrong face to vertex links, double faces and lots of
>degenerated faces.
>
>3DWin tries to fix this errors and throws out such faces.
>
OBJ files do seem to be annoyingly... poorly written, don't they?
Degenerate faces is the first problem that surprised me (closely
followed by faces with 26 verteces - which I think I've now sussed).
the number of degenerate faces the average .OBJ contains is almost
depressing.

Double faces I think I know the reason for. A lot of modellers seem to
get the normals *wrong* and so users sometimes make a copy of the
model, flip the normals, and combine the two sets of meshes.

Dirty, and probably works in many cases (i.e. patches holes) but time
and memory are both wasted. I can't help but feel it'd cause some
renderers to cough and splutter too  - though as I've not knowingly
come across this yet I don't know how much POV "likes" or dislikes it.

I'd expect there to be "coincident faces" (is that the term?) problems
though.


Cheers,

Cliff Bowman
Why not pay my 3D Dr Who site a visit at http://www.who3d.cwc.net/

Post a reply to this message

On Tue, 31 Aug 1999 21:17:41 -0500, Mark Gordon <mtg### [at] mailbagcom>
wrote:

>Ron Parker wrote:
>> 
>> Unfortunately, it's not quite that easy.  You can't lop of just any
>> pointy bit.  Take a simple isosceles triangle.  Add a new vertex at
>> the center of the base.  Move that vertex upward, so what you get looks
>> like a rather angular version of the Federation emblem from Star Trek.
>> Note that the angle surrounding the topmost vertex qualifies as a
>> "pointy bit" yet the resulting triangle is neither inside nor outside
>> the polygon.
>
>Point well taken.  Like I said, I was a bit sleep deprived.
>

It would appear from empiracle evidence that .OBJ writers are using
the many-verteces face as a space saving technique (obviously 20-odd
coplanar triangles take less file space when expressed as a single
face than as numerous triangles). I have yet to find a face which
isn't convex, or one that isn't co-planar. As such I've got a simple
solution in place just waiting for a .OBJ file with the right
deficiencies to make the program translate incorrectly <eg>

Please - no one build a .OBJ in a text editor just to break the
program!


Cheers,

Cliff Bowman
Why not pay my 3D Dr Who site a visit at http://www.who3d.cwc.net/

Post a reply to this message

On Wed, 01 Sep 1999 23:45:37 GMT, c.b### [at] cwcomnet (Cliff Bowman)
wrote:

>On Wed, 01 Sep 1999 06:11:34 GMT, NOS### [at] ibmnet (Thomas
>Baier) wrote:
>
>
>Double faces I think I know the reason for. A lot of modellers seem to
>get the normals *wrong* and so users sometimes make a copy of the
>model, flip the normals, and combine the two sets of meshes.

Right.

>
>Dirty, and probably works in many cases (i.e. patches holes) but time
>and memory are both wasted. I can't help but feel it'd cause some
>renderers to cough and splutter too  - though as I've not knowingly
>come across this yet I don't know how much POV "likes" or dislikes it.
>
>I'd expect there to be "coincident faces" (is that the term?) problems
>though.

I'm not really sure what you mean.

But one of the problems is that bordering faces do not use same the
vertices.

Anyway, you have to go around all problems to make a robust converter.

You have to build in some checks, which make the import slower.

-tb

Post a reply to this message

On Wed, 01 Sep 1999 23:45:37 GMT, Cliff Bowman wrote:

>Double faces I think I know the reason for. A lot of modellers seem to
>get the normals *wrong* and so users sometimes make a copy of the
>model, flip the normals, and combine the two sets of meshes.

I've actually seen this approach RECOMMENDED in an otherwise good
book.  Might have had something to do with the book being written
for an inferior modeller like MAX, though... <big grin for Lance>

Post a reply to this message