Thomas Willhalm <tho### [at] uni-konstanzde> wrote:
> Sorry, but I can't completely agree with you. This approach isn't that bad. 

  I didn't say it's bad. I said that it takes memory (while the raytracing
method doesn't). Yes, it takes a linear amount of memory with respect to
the number of triangles, but as the number of triangles can sometimes be
counted in millions, it is a considerable amount of memory.
  Of course if you implement it properly, it doesn't really matter with
current computers (if the search takes some megabytes of memory, who cares?).

> What you want to do is to visit all triangles. What you describe is more or 
> less a depth-first search in the dual graph of the mesh.

  Yes, a depth-first search is the best way to go. However, it needs to
be made with care so that it doesn't take too much memory (ie. to avoid
pushing a triangle onto the stack more than once).
  In fact, the best approach is not to make a true depth-first search, but
a slightly modified one:

  - We have to be able to mark triangles as "not handled" and "handled"
  0. Initialize all triangles as "not handled".
  1. Push a triangle onto the stack and mark it as "handled".
  2. Pop a triangle from the top of the stack (and remove it from there).
  3. For each three triangles adjacent to this one: if the triangle is
     marked "not handled", then fix it, mark it as "handled" and push it
     onto the stack.
  4. If the stack is not empty, return to step 2.

  This does not perform a true depth-first search, but it doesn't matter
because it makes the job with the minimum amount of stack usage (ie. a
triangle is never pushed onto the stack more than once).
  Of course it requires that the mesh is connected.

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message