Sign in to follow this  

Rasterizing triangle in 3D

This topic is 823 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

TFoxJKY.png

 

So I made a thing to rasterize the N dimensional features of N dimensional euclidean simplices (I need to, uh, check which chunks are within the rectangular region seen by camera...rolleyes.gif )

 

Such as this rasterization of the 2-simplices that make up a 4-simplex (hehe fancy words) without the issue (bit blocky tho):

roNqdPK.png

 

Given that its something I wrote late at evening, doing the extension to N dimensions myself (I try to templatize my code), without examples I could find, Im surprised it works reasonably well in most cases.

 

The above image is a triangle rasterized into a voxel grid. Points A, B are at same height, point C is much lower.

 

 

 

However, as you can see, theres an issue with filling triangles (sometimes). Usually theres no holes like above, but in those cases the triangle face - although filled - is a bit blocky too.

 

The above triangle is filled by, for each horizontal slice, finding intersection points with the lines AB and AC, and using bresenham to draw a line between them. The red lines represent this. (note : since the triangle is tall, each red line is more like 3 rasterized lines with same endpoint on X,Z plane where Y is height like (0,0,0) (0,1,0) (0,2,0))

 

It is clear that this method wouldnt work even in 2D.

 

In 2D, you would want the red lines to be axis aligned.

 

I COULD change the axis on which I iterate through the triangle, but the issue would then just happen in another dimension.

 

 

So - since it is impossible for the lines to be axis-aligned, how is one supposed to rasterize a triangle in 3D, avoiding holes?

 

Obviously I can completely change approach and do something like for each voxel check if its contained in the shape, but Im interested whether something similar to this particular approach exists - without the flaw.

 

EDIT:

I guess this might fit math/physics or maybe graphics section better...?

 

EDIT2:

Hmm maybe I can replace Bresenham's with a line drawin algorithm that generates ALL pixels that are intersected by the line (instead of being restricted to one pixel for each unit interval on the main axis)

Edited by Waterlimon

Share this post


Link to post
Share on other sites


Hmm maybe I can replace Bresenham's with a line drawing algorithm that generates ALL pixels that are intersected by the line (instead of being restricted to one pixel for each unit interval on the main axis)

That's probably your simplest route out of this issue.

 

I'm curious what rasterisation of N-simplices is useful for?

Share this post


Link to post
Share on other sites

Are you scan converting on the diagonal? That would be a problem. You should be scan converting horizontal strips between the edges.

 

Never mind. I see what you're doing now. No idea how to solve this.

Edited by MarkS

Share this post


Link to post
Share on other sites


I'm curious what rasterisation of N-simplices is useful for?

 

I guess you could write a buggy N-dimensional software rasterizer tongue.png

 

I was just writing some rasterizing functionalities (to rasterize triangles), and figured it should be possible to templatize the thing in case I need only the outline or perhaps a filled tetrahedron or whatever.

 

I managed to make my line rasterizer to cover all points it intersects, which made the issue go away as expected. Though it was a quick hack so it only affected some methods of getting points out of the line rasterizer... I need to make a whole new class for it instead of breaking my working bresenhaim algorithm >.>

 

Currently I used it to rasterize the rectangle of chunks covered by camera so I know which ones to load, and it works fine given some buffer around the edges (cam corners rounded to integers and using the bresenheim algo for the triangle edges :/)

Share this post


Link to post
Share on other sites

I think scan-line fill algorithm is used in this case. Its idea is described on the image bellow:
 
scanlinerasterizer.png

 
The problem is that he is not rasterizing a 2D projection of a 3D triangle, but rasterizing a 3D triangle in 3D voxel space.

 

[edit]

 

This is REALLY bugging me! angry.png No matter the orientation of the triangle in 3 space, it is still a planar 2D object. This *shouldn't* be hard to figure out and I'm stumped!

Edited by MarkS

Share this post


Link to post
Share on other sites

 

I think scan-line fill algorithm is used in this case. Its idea is described on the image bellow:
 
 

 
The problem is that he is not rasterizing a 2D projection of a 3D triangle, but rasterizing a 3D triangle in 3D voxel space.

 

[edit]

 

This is REALLY bugging me! angry.png No matter the orientation of the triangle in 3 space, it is still a planar 2D object. This *shouldn't* be hard to figure out and I'm stumped!

 

It doesn't matter if it pixels or voxels. For 3D case the algorithm would be like:

1. Slice triangles bounding box with a parallel 2D planes (XY, YZ, XZ, doesn't matter).

2. For each voxel slice find intersection point between triangle sides and two planes that determine a slice. That would give 4 points that may degenerate into 3 or 2.

3. Apply scan-line fill for each set of points.

I can't say for sure, but i think similar approach can be used for higher dimensions as well. And probably it would be quite expensive too.

 

As for the thing that is bugging. Triangle is a planar object, but pixels density along each axis defined by triangle sides is different. Distance between each voxel center along AC is 1, while along AB is ~1.4 (square root of 2). Thus you'll end up having a holes if you fill along AB. 

Here is a picture of what is happening:

NcoKCl1.png

If you try to fill the picture on the left there will be no holes. But as the squares on the left are misaligned with pixels, the real result will be the one on the right.

 

Only when you fill along pixel/voxel axes, triangle will be filled without holes. The thing is it is impossible to achieve. Take a box - that is voxel. take a sheet of paper and a pen. Pen is a normal to a plane defined by triangle. It can go outward the box in any direction. Put the sheet perpendicular to pen. Axes will be aligned only in very specific cases. But it can give an idea for some intrinsical optimizations to the algorithm (to remove slicing at all for 3D case at least).

 

However, dropping Bresenham algorithm and overdrawing some voxels might still be faster.

Share this post


Link to post
Share on other sites

This topic is 823 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this