I'm working on a patch for POV, and I'd like to keep it in c, but I've come
up with a problem, namely, I don't really want to program a complex data
structure in c, but I need to.

See, I've got a matrix of edge counts from vertex to vertex in a mesh.  In
general, the count is 0, and only for a very few is it larger (5-7 per
vertex, I'd guess, but there are many thousand vertices in a large mesh)

My initial run works fine, but it uses a basic matrix of values for storing
these.  It's mostly empty, and *very* expensive, due to the large number of
vertices.

If I were working in c++, I could store non-zero elements in a map with a
lookup, but in c that isn't an option.  So I'm left with implementing my own
data structure, which is icky.

Or, maybe there's something already out there.  Does anyone know of such a
data structure that I could use, maybe within POV itself?  If not, I might
just write the bit of code I need in c++ and say to heck with it, but I'd
rather stay 'standard', if such can ever be said when discussing a patch. :/

Geoff

Post a reply to this message

In article <3b5453ba@news.povray.org> , Geoff Wedig 
<wed### [at] darwinepbicwruedu>  wrote:

> Or, maybe there's something already out there.  Does anyone know of such a
> data structure that I could use

A map can be represented as a tree.  While in C++ the the implementation is
an detail you unlikely need to be concerned about and it doesn't have to be
a tree, but could be a more efficient data structure, in this case a binary
tree will do fine and con always be optimized later.  Even better, there is
be plenty of code out there for binary trees, probably even on your harddisk
:-)

     Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

"Geoff Wedig" <wed### [at] darwinepbicwruedu> wrote in message
news:3b5453ba@news.povray.org...
>
> I'm working on a patch for POV, and I'd like to keep it in c, but I've
come
> up with a problem, namely, I don't really want to program a complex data
> structure in c, but I need to.
>

    Hmm, I think there should be a way to simplify what your doing, to make
it easier to code in c, but I can't get my head around what you're trying to
achieve...

    What do you mean by "edge counts from vertex to vertex" ?
    What are you trying to achieve ?

--
Scott Hill.
Software Engineer.
E-Mail        : sco### [at] innocentcom
Pandora's Box : http://www.pandora-software.com

*Everything in this message/post is purely IMHO and no-one-else's*

Post a reply to this message

Thorsten Froehlich <tho### [at] trfde> wrote:

> In article <3b5453ba@news.povray.org> , Geoff Wedig 
> <wed### [at] darwinepbicwruedu>  wrote:

>> Or, maybe there's something already out there.  Does anyone know of such a
>> data structure that I could use

> A map can be represented as a tree.  While in C++ the the implementation is
> an detail you unlikely need to be concerned about and it doesn't have to be
> a tree, but could be a more efficient data structure, in this case a binary
> tree will do fine and con always be optimized later. 

I know.  But I hate coding simple data structures.  It's just far too much
work when there're probably easier ways.


 Even better, there is
> be plenty of code out there for binary trees, probably even on your harddisk
> :-)

Yeah, but I don't know of a good one.  And actually, since I don't think
such a thing comes with cygwin (except as c++), I don't think so.  Maybe
over on my linux drive, but I'd have no idea where to look.

What I've done is separated out the section that needs a map, and compiled
that under c++.  It may need to be changed if I ever want to release this
patch, but I'll worry about it then.

Geoff

Post a reply to this message

Scott Hill <sco### [at] innocentcom> wrote:

> "Geoff Wedig" <wed### [at] darwinepbicwruedu> wrote in message
> news:3b5453ba@news.povray.org...
>>
>> I'm working on a patch for POV, and I'd like to keep it in c, but I've
> come
>> up with a problem, namely, I don't really want to program a complex data
>> structure in c, but I need to.
>>

>     Hmm, I think there should be a way to simplify what your doing, to make
> it easier to code in c, but I can't get my head around what you're trying to
> achieve...

>     What do you mean by "edge counts from vertex to vertex" ?
>     What are you trying to achieve ?

Ok, a mesh is a set of vertices, and triangles connectting triples of those
vertices.  Each triangle can be seen as a set of three edges, or pairs of
vertices connected by the edge of the triangle, making the system a basic
undirected graph.  Now, since triangles share edges, some vertex pairs share
multiple edges.  I am testing to see if the mesh can be regarded as a sheet,
that there is a universal up and down that can be defined so that we can
calculate the normal at each point based upon the triangles at that point. 
Meshes where a pair share more than two edges (a pinwheel sort of thing
perhaps), and/or meshes where a universal sidedness can't be defined (mobius
strips) make for difficulties in automatically generating normals without
splitting single points into multiple ones.

Geoff

Post a reply to this message