Datastructures to represent a polygon mesh (and/or) SDS

This forum is used to discuss the architecture and design of the next JPatch development version (Jpatch 0.7).

Postby dcuny » Wed Feb 28, 2007 9:24 am

So what's the status on the SDS? :?
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Postby sascha » Wed Feb 28, 2007 1:04 pm

I've spent a lot of time on it, but it's still not in a state where it's of any practical use. Since my initial version I have
  • changed the dicer to take advantage of the fact that 2 of the 4 corners of a slate always have a valence of 4 (and thus can be treated as any regular vertex)
  • added stencils for corners and creases
  • added support for non-closed meshes
  • improved the performance

I had to change some things to allow the dicer to deal with crease/corner tags and hierarchical models. Now all the information needed is available to the dicer (this was a lot of work), but it still doesn't render creases correctly - but I think it must be some easy to fix minor issue somewhere (I just need to find it :?).

I've posted earlier that the performance droppen since I added support for corner/crease tags to the dicer. This was true (it almost dropped by 60%), but I have fixed it and it runs with the same speed as usual now. I have a switch() block in the body of the main loop, and it seems that the amount of code (not the number of cases) in that switch statement has a huge impact on the performance. I can only speculate that if the entire code in the switch() block fits into the CPU cache, execution of the loop is very fast. If it doesn't fit, it has to fetch new instructions in every loop cycle, which dramatically decreases the performance. Anyway, by rewriting the code under the case statements performance went up to normal again, which is a good thing. It's quite a bit faster than the realtime renderer of the old patch-based versions of JPatch, although the subdivision algorithm is much more complex. But it does not yet support multiple materials and a few other things, so I can't yet make any assumptions about the performance of the final realtime-subdivision code - although it looks pretty promising. If I get it to run as GLSL shader this will be mind-bogglingly fast :) - but that's currently not on top of the TODO list.

The crease/corner feature should work really soon now, I'll upload something to play with as soon as I've found and fixed the problem mentioned above.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby dcuny » Wed Feb 28, 2007 7:11 pm

sascha wrote:Now all the information needed is available to the dicer (this was a lot of work), but it still doesn't render creases correctly - but I think it must be some easy to fix minor issue somewhere (I just need to find it :?).
I know the feeling! You've been busy!

I can only speculate that if the entire code in the switch() block fits into the CPU cache, execution of the loop is very fast.
Interesting. :?

The crease/corner feature should work really soon now, I'll upload something to play with as soon as I've found and fixed the problem mentioned above.
Excellent! Thanks for the feedback. :)
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Postby sascha » Wed Feb 28, 2007 9:24 pm

Here are some screenshots that show corner and crease tags in action.
As you can see, the normals are still computed as if the surface was smooth (but that should be easy to fix), and there are strange cracks at the corners and the edge-centers. Right now I'm not sure what's causing them, but I'm working on it.
Image
The images show a simple cube object with different crease and corner tags set (from left to right):
Top row: 1 Normal, 2 and 3 red edge creases set to "infinity", 4 all edge creases set to "infinity"
Bottom row: 1 All edges creases set to "1", 2: All vertex corners set to "infinity", 3: Top corners set to "2", bottom corners set to "1", 4: Top vertices and edges normal, bottom vertex corners set to "infinity", bottom edges creases set to "infinity".
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby pndragon » Wed Feb 28, 2007 11:23 pm

Here are some screenshots

I'm drooling all over my keyboard... It looks beautiful Sascha!!! I can't wait to play with it.

--- Jim
"We're so sorry, Uncle Albert,
But we haven't done a bloody thing all day."
--- Paul McCartney
pndragon
 
Posts: 591
Joined: Sun Dec 05, 2004 1:27 am
Location: North Carolina

Postby pndragon » Wed Feb 28, 2007 11:29 pm

there are strange cracks at the corners and the edge-centers.

Out of curiosity, what does the exported cube look like? Are the cracks only visible in the realtime renderer?

I hope that this is not too stupid of a question.


--- Jim
"We're so sorry, Uncle Albert,
But we haven't done a bloody thing all day."
--- Paul McCartney
pndragon
 
Posts: 591
Joined: Sun Dec 05, 2004 1:27 am
Location: North Carolina

Postby sascha » Thu Mar 01, 2007 7:54 am

As long as there is no hierarchy information (not yet fully supported), and the renderer supports SDS (like RenderMan), there's no problem - JPatch would simply export the geometry with the tags.
If the renderer just accepts triangles, JPatch needs to do the dicing - I've not yet decided how to do this. The current dicer is optimized for realtime rendering. I could re-write it to use double-precision and use it for export too (it would then share the same problems, but don't worry, I'm quite confident that I can solve them within the next few days). Another possibility would be to simply apply the Catmull-Clark algorithm on the Half-Edge datastructure (for exporting) - this is slower, but straightforward to implement.

When points at higher hierarchies exist, things get more complicated. I've read that at least prMan 12.5 has native support for hierarchical meshes, but I can't find the paper describing the RIB syntax anymore. And I don't know if any of the free RenderMan renderers does currently support this. So I guess JPatch has to subdivide the mesh up to the last level where hierarchy-vertices are found, and then export it as a regular SDS. I think it will be easier to do this subdivision directly on the HalfEdge structure. Again, this will be slower, but it's much simplier to impliment (all the connectivity information is maintained in this case - if I'd use the dicer for this, I'd have to re-create the connectivity information at the slate boundaries - a nightmare). And when exporting to a renderer, I think one can live with subdivision times of some 100ms or seconds, while for interactive rendering this is clearly inacceptable.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby sascha » Fri Mar 02, 2007 2:20 pm

I've been able to fix both problems with the cracks. I'll clean up everything this weekend and will upload a demo of what I have by the end of this weekend or on Monday. Don't expect too much, you won't be able to model anything with it - right now you can load models in .off format, display them and, drag the vertices around and manipulate the crease and corner attributes of edges and vertices respectively.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby dcuny » Fri Mar 02, 2007 6:08 pm

Sounds like progress. :)
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Postby sascha » Fri Mar 02, 2007 10:02 pm

Yes, but I'm a bit disappointed with the performance. The dicer seems to be ok - it can subdivide a number of faces down to level 6 (i.e. generating 1024 quads per slate) in virtually no time (and I still have some optimizations in mind which I'll implement later). However, if there are many faces that are only diced to level 2, performance becomes inacceptably slow. I'll have to track down the source of this phenomenon. That's why I'll need to try it with some real models, the fact that the cube can be tesselated to level 5 in less than 20ms tells nothing about the "real world" performance.

Nevertheless, I will make a jar-file of what I have available by the end of the weekend, I promise :wink:
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby dcuny » Fri Mar 02, 2007 10:41 pm

sascha wrote:However, if there are many faces that are only diced to level 2, performance becomes inacceptably slow.
"Unacceptably", not "inacceptably".

Does the renderer have to dynamically re-dice the object for each refresh, or can it cache the mesh, and only update the parts that are being edited?

But I can see how being able to do this on the fly without restriction is the optimal thing... When it comes time to mess with bones and morphs, you need the interface to be fluid.

Nevertheless, I will make a jar-file of what I have available by the end of the weekend, I promise :wink:
Great. It'll be fun to play with it. :)
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Postby sascha » Sat Mar 03, 2007 11:58 am

"Unacceptably", not "inacceptably".

Oh, thanks. Is there some rule for when to use "un-" and when to use "in-"?

Does the renderer have to dynamically re-dice the object for each refresh, or can it cache the mesh, and only update the parts that are being edited?

No, it doesn't cache anything, for two reasons:
1. The goal is to have a "silicon" version of the dicer that runs entirely on the graphics hardware (it will run as an OpenGL fragment shader and should be about 20 times faster than the software version). There won't be much difference in rendering a quad and dicing and rendering a slate of an SDS mesh then, so trying to cache anything would actually slow things down.

2. I tried to implement some caching with patches, and found that it is quite tricky to keep track of which parts of the cache became invalid.

And as I said, I think that even this purely CPU based version of the dicer is quite fast (and there's still room for improvement), so the bottleneck has to be somewhere esle.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby dcuny » Sat Mar 03, 2007 1:45 pm

sascha wrote:Is there some rule for when to use "un-" and when to use "in-"?
Not that I know of. :(

And as I said, I think that even this purely CPU based version of the dicer is quite fast (and there's still room for improvement), so the bottleneck has to be somewhere esle.
Well, then good luck tracking it down. Does Java have a profiler? :?
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Postby sascha » Sun Mar 04, 2007 9:42 am

I think the VM can collect all the statistics needed for profiling. Unfortunately Eclipse has no built-in profiler, and most plugins are commercial. I'll have a look.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby sascha » Fri Mar 09, 2007 5:05 pm

I think the SDS dicer is working now. I was able to get rid of an annoying limitation:
Image
Such faces can be rendered now (the point at the center will automatically become a corner in this case), so only the inherent limitations remain (surfaces must be manifold and orientable). Non-closed surfaces are possible now, the boundaries are treated as b-splines (compatible with RenderMan's "interpolate boundary" switch).
Here's a rendering of the SDS teapot:
Image
The teapot has 448 faces, and the realtime renderer can on-the-fly subdivide and render it at about 10 frames per second, which is still not satisfactory - a moderately complex object will have between 500 and 2000 faces.
It's interesting that it becomes faster when you zoom in: The average subdivision level increases, but the number of slates to be diced and drawn decreases (off-screen slates are culled). This is because the dicer is fast, but there seemst to be a high constant setup-cost per slate, see below.
I have three ideas to improve it:
  • Culling backfacing slates - if all the normals of a slate point away from the viewer, it can be culled - I guess this should sort about one third of the slates out (they don't have to be diced then).
  • The setup cost of the dicer seems to be quite high. It has to analyze each slate and initialize the arrays needed for subdivision. This is even done for slates that are so small on screen that actually no subdivision is done. This is the case if a complex object is completely visible on screen: Lots of small faces, so the average subdivision level is virtually 0, but all of the slates have to be rendered. I think in this case it should dramatically improve the performance if I bypass the dicer for slates that don't have to be diced.
  • Implement a fast evaluation algorithm (using precomputed tables of the sampled basis-functions) for slates without creases/corners and without hierarchy.
I'll keep you up to date and post a new version to play once I've implemented the first two things.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

PreviousNext

Return to JPatch 0.7 development

Who is online

Users browsing this forum: No registered users and 1 guest

cron