Ron Parker heeft geschreven in bericht <36e9176a.0@news.povray.org>...
>Consider a mesh of a bowl.  Any point in the part where the Chocolate
>Frosted Sugar Bombs go would be considered "inside" by this method, as
>would a good number of points in the environment, including some below
>the surface of the table (due to the rim of the bowl).
>
>Even convex polyhedra would have problems.  Consider a football (without
>seams.)  It's convex, but the intersections of the prisms associated with
>triangles near opposite ends are outside the surface of the football.


I'm not hamperd by any knowledge of programming and raytracing theory, so if
what I try to say is bare nonsense have a good laugh, but please tell me
why.

I can imagine using planes instead of prisms to represent the triangles (in
a closed mesh). First use Ron's method to check if the mesh is closed. Then
for every triangle calculate the normal. Follow each normal in both
directions and count the intersections, to determine the inside (odd
number). Then replace the triangle by a plane with the "outside normal".
Then for every plane check wether all points of the mesh are on the inside
of the plane. Give these triangles the status intersection. All others get
the status union.
Now get the first triangle/plane with the status union, check what status
the neighbour triangles have. Is it union, put all these planes in a union
statement. Check the neighbours of the neighbours and so on until all
neighbour  triangles have the status intersection. Now go to the next "union
triangle" that is not in the first union already. Start a new union.
Repeat all this till there are no union triangles left. Now put all the
union blocks together with all triangles with status intersection in an
intersection block. The result should be a solid shape.
Does this make sense?
Something like this:

intersection{
      union{
         plane{-z, 0.5}
         plane{<-1,0,-1>,0}
         plane{< 1,0,-1>,0}
      }
      plane{-z, 1.5}
      plane{<-1,0,-1>,(4*sqrt(2)/2)}
      plane{< 1,0,-1>,(4*sqrt(2)/2)}
      plane{-x,3.5}
      plane{ x,3.5}
      plane{<-1,0, 1>,(4*sqrt(2)/2)}
      plane{< 1,0, 1>,(4*sqrt(2)/2)}
      plane{ z, 1.5}
      union{
         plane{ z, 0.5}
         plane{<-1,0, 1>,0}
         plane{< 1,0, 1>,0}
      }
   plane{y,1}
   plane{-y,1}
   pigment {rgb 0.8}
}

ingo
--
Met dank aan de muze met het glazen oog.

Post a reply to this message

On Fri, 12 Mar 1999 21:54:32 +0100, ingo <ing### [at] ingodemonnl> wrote:
>I can imagine using planes instead of prisms to represent the triangles (in
>a closed mesh). First use Ron's method to check if the mesh is closed. Then
>for every triangle calculate the normal. 

>Follow each normal in both
>directions and count the intersections, to determine the inside (odd
>number). 

This has all the same drawbacks as the original proposal, of course.  
There are better ways to find the outside normal.  In fact, the one I'm
thinking of is the same kind of algorithm you've proposed: 

1. start with a random triangle and pick a direction to be called "outside."  
2. Propagate this decision to its neighbors, and their neighbors, and so on 
   until there are no more neighbors.  Now you have a connected, closed piece 
   of the mesh with consistent normals.  
3. Pick a point outside the bounding box of the mesh.
4. If the point is "inside" the piece using the test below, flip all the 
   normals.  
5. If there are any triangles left that are not in the "mesh so far," pick one 
   and build a closed, connected surface for it using steps 1-4.  
6. If one of the points on the new piece is inside the "mesh so far", flip its 
   normals again before adding it to the "mesh so far."  
7. If any piece of the "mesh so far" is inside the new piece, flip that piece's 
   normals before adding the new piece.  Do this for every piece that's inside
   the new piece.
8. Repeat from step 5 until you run out of unused triangles.

>Then replace the triangle by a plane with the "outside normal".

If you know the outside normal for every triangle, your work is done.  For
any given point, just fire a ray at a random triangle in the mesh.  At the
first intersection (possibly not the triangle you fired at) check the normal.
If it points away from you, you're inside.  If it points toward you, you're
not.  If it's perpendicular, ignore it and try firing at a different triangle.

[plausible solution snipped for space]
>Does this make sense?

It makes sense.  I think it would even work.  But I think it'd be even slower
than intersection-counting.  It would almost certainly be slower than the 
method I've proposed.

Post a reply to this message

Ron Parker wrote in message <36e7f128.0@news.povray.org>...
>On Thu, 11 Mar 1999 22:03:44 +0800, Gordon <gbe### [at] birdcameroncomau>
wrote:
>>I've found that doing what Ken has done usually works. You can usually use
>>differences to chop bits off meshes. If you try to reverse the difference,
>>take the mesh from the sphere, it doesn't quite work though. The mesh
>>appears as an infinitely thin surface (which makes sense I guess) and
>>appears to behave as such in CSGs.
>
>Are you sure?  It seems it should work the other way, since meshes
>are defined to have no inside.  Difference is just intersection with
>an inverse, so I'll use intersection to explain:
>
>What intersection does is find all ray-object intersections with each
>component object, then filter the results so only the intersections
>that are inside all other component objects are returned.  Since
>nothing is inside a mesh, all intersections with non-mesh objects
>should be ignored.  Intersections with the mesh object would survive.
>The result seems like it would be quite unlike an intersection.
>
>difference{sphere{...}mesh{...}} would return all intersections
>with the sphere, plus whatever mesh surfaces fall inside the sphere.
>For opaque objects, the result should be a sphere.
>
>difference{mesh{...}sphere{...}} would return whatever intersections
>with the mesh fall outside the sphere, but no intersections with the
>sphere.  The result would be a hole in your mesh, not a spherical
>cutout.

A hole in the mesh is what I mean't. I was considering the mesh to be a
surface not a solid. So the difference{mesh{}sphere{}} does let me "trim" a
mesh which is often useful. I agree completely that POVRay doesn't currently
deal with meshes as solid objects in any sensible way.

>
>>On the topic in general, I would think the method of using the normals to
>>determine the "inside" was more useful as this way open meshes could also
be
>>used. I still have a little trouble picturing how this would work exactly
>>though!
>
>Quite simply, it wouldn't really.  The "inside" of such a mesh would not
>be well-defined, as whether a given point were inside or outside would
>depend on which triangle it hit when testing.  Some points would always
>be inside, of course, and some outside, but for anything but a simple flat
>mesh you'd have lots of points that were undefined.
>

From the programmers point of view, I agree. What I mean't was that from a
modellers point of view, this may be more useful. Though if it can't be
implemented, I guess the point is moot.

Regards
Gordon

Post a reply to this message