gdalgorithms-list

[Algorithms] Efficient Voxel Interpolation / Splatting

[Stefan D. <ste...@gm...>]

Dear List,

I'm trying to implement an efficient splatting algorithm. The input of the
system are two-dimensional images which have position and orientation in
space. Using these input images I want to "fill" a three-dimensional voxel
grid which also has position and orientation in space (Represented by a 4x4
transformation matrix: 3x3 rotation matrix and translation vector).

In order to fill the voxel grid using the pixels on the two-dimensional
input images one needs to implement a splatting / interpolation method which
determines the value of a voxel depending on the position, size and color of
the pixels on the input. There are three splatting methods for my data which
seem to make sense to me.

1. Find the nearest pixel to a voxel and assign the color of the pixel to
the voxel (nearest Neighbor)
2. Find the n-nearest pixels to a voxel and weight the color-contribution of
these pixels inverse linearly with the distance of the pixels to the voxel
3. Find the nearest pixels within a pre-defined distance to the voxel and
weight the color-contribution of these pixels inverse linearly with the
distance to the voxel

In ether way one would iterate through all voxels in the output and find
some pixels on the input images near it. This clearly calls for some sort of
efficient bounding hierarchy creation before conducting the neighbor search.
I was thinking that putting the voxels into an octree data structure and
putting the pixels into a quadtree datastructure might do for a good enough
performance.

Another method to speed up the computation further is to reduce the number
of output voxels (given a fixed voxel size) by aligning the voxel grid
efficiently before the search. I basically try to align the voxel grid in a
way that the two dimensional inputs fit into the object-aligned bounding box
with maximum space occupancy on the voxel grid (minimal number of voxels
given a fixed voxel side length).

I thought of a statistical approach here. The problem boils down to placing
and aligning two of the local coordinate axes of the volume along the
directions with the most variance in the dataset (with the dataset being the
positions of the pixels on the input images). This could be done by
calculating the covariance matrix of those positions and performing a
principal component analysis (PCA) on the covariance matrix. This gives the
eigenvalues and eigenvectors along the main variance directions of the input
pixel positions. The two eigenvectors with the largest eigenvalues would
then be good axes for the coordinate system of the voxel grid. The third
axis can then be determined by the "right-hand-rule".

Regards,

Stefan
-- 
--
Stefan Daenzer
Körnerplatz 8
04107 Leipzig


"Work like you don't need the money, love like you've never been hurt and
dance like no one is watching." - Randall G Leighton

Re: [Algorithms] Efficient Voxel Interpolation / Splatting

[Manuel M. <m.m...@wa...>]

Hi Stefan,

> 1. Find the nearest pixel to a voxel and assign the color of the pixel to
> the voxel (nearest Neighbor)
> 2. Find the n-nearest pixels to a voxel and weight the color-contribution
> of these pixels inverse linearly with the distance of the pixels to the
> voxel 3. Find the nearest pixels within a pre-defined distance to the
> voxel and weight the color-contribution of these pixels inverse linearly
> with the distance to the voxel

Have you considered just using a 3D DDA which traces each 2d image through the 
voxel grid? This might be more efficient, although it will require a larger 
working set (because it involves collection of a number of contributing pixels 
and filtering them as a post-process).

cheers,

  Manuel

Re: [Algorithms] Efficient Voxel Interpolation / Splatting

[Jon O. <jon...@gm...>]

@Manuel: I think he wants to find the nearest point on the image to the
voxel. I'm not sure how a DDA tracing algorithm would help there.

Whats the application?

That all sounds like good ideas. If you want nearest filtering, the first
approach is probably best. I would bet though that you want a smooth output,
like radiating heat.  So option number 3 sounds best for that. Alternatively
to the inverse distance you could do a 3D Gaussian on the data depending on
what kind of output you want.

On Sun, Jun 13, 2010 at 10:38 AM, Stefan Dänzer <ste...@gm...>wrote:

> Dear List,
>
> I'm trying to implement an efficient splatting algorithm. The input of the
> system are two-dimensional images which have position and orientation in
> space. Using these input images I want to "fill" a three-dimensional voxel
> grid which also has position and orientation in space (Represented by a 4x4
> transformation matrix: 3x3 rotation matrix and translation vector).
>
> In order to fill the voxel grid using the pixels on the two-dimensional
> input images one needs to implement a splatting / interpolation method which
> determines the value of a voxel depending on the position, size and color of
> the pixels on the input. There are three splatting methods for my data which
> seem to make sense to me.
>
> 1. Find the nearest pixel to a voxel and assign the color of the pixel to
> the voxel (nearest Neighbor)
> 2. Find the n-nearest pixels to a voxel and weight the color-contribution
> of these pixels inverse linearly with the distance of the pixels to the
> voxel
> 3. Find the nearest pixels within a pre-defined distance to the voxel and
> weight the color-contribution of these pixels inverse linearly with the
> distance to the voxel
>
> In ether way one would iterate through all voxels in the output and find
> some pixels on the input images near it. This clearly calls for some sort of
> efficient bounding hierarchy creation before conducting the neighbor search.
> I was thinking that putting the voxels into an octree data structure and
> putting the pixels into a quadtree datastructure might do for a good enough
> performance.
>
> Another method to speed up the computation further is to reduce the number
> of output voxels (given a fixed voxel size) by aligning the voxel grid
> efficiently before the search. I basically try to align the voxel grid in a
> way that the two dimensional inputs fit into the object-aligned bounding box
> with maximum space occupancy on the voxel grid (minimal number of voxels
> given a fixed voxel side length).
>
> I thought of a statistical approach here. The problem boils down to placing
> and aligning two of the local coordinate axes of the volume along the
> directions with the most variance in the dataset (with the dataset being the
> positions of the pixels on the input images). This could be done by
> calculating the covariance matrix of those positions and performing a
> principal component analysis (PCA) on the covariance matrix. This gives the
> eigenvalues and eigenvectors along the main variance directions of the input
> pixel positions. The two eigenvectors with the largest eigenvalues would
> then be good axes for the coordinate system of the voxel grid. The third
> axis can then be determined by the "right-hand-rule".
>
> Regards,
>
> Stefan
> --
> --
> Stefan Daenzer
> Körnerplatz 8
> 04107 Leipzig
>
>
> "Work like you don't need the money, love like you've never been hurt and
> dance like no one is watching." - Randall G Leighton
>
>
> ------------------------------------------------------------------------------
> ThinkGeek and WIRED's GeekDad team up for the Ultimate
> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
> lucky parental unit.  See the prize list and enter to win:
> http://p.sf.net/sfu/thinkgeek-promo
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] Efficient Voxel Interpolation / Splatting

[Manuel M. <m.m...@wa...>]

Hi,

> @Manuel: I think he wants to find the nearest point on the image to the
> voxel. I'm not sure how a DDA tracing algorithm would help there.

I was thinking of the following:
Think of each 2d scanline as a 3d ray which passes through the
voxel grid. Traverse the voxel grid along the ray direction using
DDA, Insert the intersecting pixel spans (in fact a quadrilateral) into the
appropriate voxel. 

Additionally, one could use summed area tables or somesuch to pre-filter/match
the voxel and pixel footprint approximately.

bye,

	Manuel

Re: [Algorithms] Efficient Voxel Interpolation / Splatting

[Jon O. <jon...@gm...>]

Ah, so kind of like a rasterization of the 2d image into the 3d voxel space?

On Sun, Jun 13, 2010 at 1:31 PM, Manuel Massing
<m.m...@wa...>wrote:

> Hi,
>
> > @Manuel: I think he wants to find the nearest point on the image to the
> > voxel. I'm not sure how a DDA tracing algorithm would help there.
>
> I was thinking of the following:
> Think of each 2d scanline as a 3d ray which passes through the
> voxel grid. Traverse the voxel grid along the ray direction using
> DDA, Insert the intersecting pixel spans (in fact a quadrilateral) into the
> appropriate voxel.
>
> Additionally, one could use summed area tables or somesuch to
> pre-filter/match
> the voxel and pixel footprint approximately.
>
> bye,
>
>        Manuel
>
>
> ------------------------------------------------------------------------------
> ThinkGeek and WIRED's GeekDad team up for the Ultimate
> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
> lucky parental unit.  See the prize list and enter to win:
> http://p.sf.net/sfu/thinkgeek-promo
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] Efficient Voxel Interpolation / Splatting

[Jon O. <jon...@gm...>]

If its a 2D image to 3d voxel rasterization algorithm, definitely make a
oct-tree of the voxel data and then intersect it with the 2D image plane
(plus a depth if you want water-tight), and further clip by the extents of
the image. Then for each voxel which is considered intersecting the 2D image
volume, determine the color by projecting the voxel center onto the image
plane then do a sample (bi-linear interp with mip-maps perhaps?) of the
image. You could then alpha the voxel based on the amount that the voxel is
intersected with the volume. For example 20% inside = 20% alpha.

On Sun, Jun 13, 2010 at 1:56 PM, Jon Olick <jon...@gm...> wrote:

> Ah, so kind of like a rasterization of the 2d image into the 3d voxel
> space?
>
>
> On Sun, Jun 13, 2010 at 1:31 PM, Manuel Massing <m.m...@wa...
> > wrote:
>
>> Hi,
>>
>> > @Manuel: I think he wants to find the nearest point on the image to the
>> > voxel. I'm not sure how a DDA tracing algorithm would help there.
>>
>> I was thinking of the following:
>> Think of each 2d scanline as a 3d ray which passes through the
>> voxel grid. Traverse the voxel grid along the ray direction using
>> DDA, Insert the intersecting pixel spans (in fact a quadrilateral) into
>> the
>> appropriate voxel.
>>
>> Additionally, one could use summed area tables or somesuch to
>> pre-filter/match
>> the voxel and pixel footprint approximately.
>>
>> bye,
>>
>>        Manuel
>>
>>
>> ------------------------------------------------------------------------------
>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>> lucky parental unit.  See the prize list and enter to win:
>> http://p.sf.net/sfu/thinkgeek-promo
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
>

Re: [Algorithms] Efficient Voxel Interpolation / Splatting

[Jon W. <jw...@gm...>]

You can incrementally build the 3D voxels by tracing the plane of each
contributing image, using an algorithm similar to Bresenham or Marching
Cubes. As long as the value for each voxel can be composed incrementally,
you can do this for images sequentially without needing extra storage.

And, yes, recursive tree-like data structures are almost always used for
voxels, because > 90% of the voxel volume is either all-solid or all-open.

Btw: if you're interested in voxel terrain, you probably should check out
the implementation in the C4 engine. It's pretty nice feature-wise, and high
quality code as well. The source license is $350, although you probably want
to be careful with the license terms; you probably can't copy and paste code
from the engine into your own code, for example.

Sincerely,

jw


--
Americans might object: there is no way we would sacrifice our living
standards for the benefit of people in the rest of the world. Nevertheless,
whether we get there willingly or not, we shall soon have lower consumption
rates, because our present rates are unsustainable.



On Sun, Jun 13, 2010 at 12:10 PM, Jon Olick <jon...@gm...> wrote:

> If its a 2D image to 3d voxel rasterization algorithm, definitely make a
> oct-tree of the voxel data and then intersect it with the 2D image plane
> (plus a depth if you want water-tight), and further clip by the extents of
> the image. Then for each voxel which is considered intersecting the 2D image
> volume, determine the color by projecting the voxel center onto the image
> plane then do a sample (bi-linear interp with mip-maps perhaps?) of the
> image. You could then alpha the voxel based on the amount that the voxel is
> intersected with the volume. For example 20% inside = 20% alpha.
>
> On Sun, Jun 13, 2010 at 1:56 PM, Jon Olick <jon...@gm...> wrote:
>
>> Ah, so kind of like a rasterization of the 2d image into the 3d voxel
>> space?
>>
>>
>> On Sun, Jun 13, 2010 at 1:31 PM, Manuel Massing <
>> m.m...@wa...> wrote:
>>
>>> Hi,
>>>
>>> > @Manuel: I think he wants to find the nearest point on the image to the
>>> > voxel. I'm not sure how a DDA tracing algorithm would help there.
>>>
>>> I was thinking of the following:
>>> Think of each 2d scanline as a 3d ray which passes through the
>>> voxel grid. Traverse the voxel grid along the ray direction using
>>> DDA, Insert the intersecting pixel spans (in fact a quadrilateral) into
>>> the
>>> appropriate voxel.
>>>
>>> Additionally, one could use summed area tables or somesuch to
>>> pre-filter/match
>>> the voxel and pixel footprint approximately.
>>>
>>> bye,
>>>
>>>        Manuel
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>>> lucky parental unit.  See the prize list and enter to win:
>>> http://p.sf.net/sfu/thinkgeek-promo
>>> _______________________________________________
>>> GDAlgorithms-list mailing list
>>> GDA...@li...
>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>> Archives:
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>
>>
>>
>
>
> ------------------------------------------------------------------------------
> ThinkGeek and WIRED's GeekDad team up for the Ultimate
> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
> lucky parental unit.  See the prize list and enter to win:
> http://p.sf.net/sfu/thinkgeek-promo
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] Efficient Voxel Interpolation / Splatting

[Stefan D. <ste...@gm...>]

Very interesting approaches here,

@Manuel: I think the 3D-DDA (or the Bresenham 3D Algorithm suggested by Jon
Watte) might be the way to go.

@Jon Olic: The application is 3-D Ultrasound (US) reconstruction from
spatially positioned and oriented 2-D US images. We basically use an optical
tracking system and spatially track the US-Probe. This way we can record
3D-US volumes using a conventional 2D-US machine. Your suggested
rasterization algorithm which projects the voxel center onto the image plane
and calculates the distance of the projected point in the plane looks also
fine, but i'm not sure if I can implement it more efficiently than a
modified Bresenham 3D or 3D-DDA algorithm.

@Jon Watte: If we end up weighting the contribution of each pixel in the
proximity of a voxel inverse linearly to the distance to the voxel center,
there might not be a way around using some extra storage for each voxel. We
might end up storing distance and color of a pixel for each voxel during
distance calculation and (as Manuel mentioned also) calculating the color of
each voxel as a post processing step. I don't see any way how it would be
possible to compose the value for each voxel incrementally. Am I missing
something here?

Thanks for this excellent discussion so far,

Stefan


On Tue, Jun 15, 2010 at 6:52 PM, Jon Watte <jw...@gm...> wrote:

> You can incrementally build the 3D voxels by tracing the plane of each
> contributing image, using an algorithm similar to Bresenham or Marching
> Cubes. As long as the value for each voxel can be composed incrementally,
> you can do this for images sequentially without needing extra storage.
>
> And, yes, recursive tree-like data structures are almost always used for
> voxels, because > 90% of the voxel volume is either all-solid or all-open.
>
> Btw: if you're interested in voxel terrain, you probably should check out
> the implementation in the C4 engine. It's pretty nice feature-wise, and high
> quality code as well. The source license is $350, although you probably want
> to be careful with the license terms; you probably can't copy and paste code
> from the engine into your own code, for example.
>
> Sincerely,
>
> jw
>
>
> --
> Americans might object: there is no way we would sacrifice our living
> standards for the benefit of people in the rest of the world. Nevertheless,
> whether we get there willingly or not, we shall soon have lower consumption
> rates, because our present rates are unsustainable.
>
>
>
> On Sun, Jun 13, 2010 at 12:10 PM, Jon Olick <jon...@gm...> wrote:
>
>> If its a 2D image to 3d voxel rasterization algorithm, definitely make a
>> oct-tree of the voxel data and then intersect it with the 2D image plane
>> (plus a depth if you want water-tight), and further clip by the extents of
>> the image. Then for each voxel which is considered intersecting the 2D image
>> volume, determine the color by projecting the voxel center onto the image
>> plane then do a sample (bi-linear interp with mip-maps perhaps?) of the
>> image. You could then alpha the voxel based on the amount that the voxel is
>> intersected with the volume. For example 20% inside = 20% alpha.
>>
>> On Sun, Jun 13, 2010 at 1:56 PM, Jon Olick <jon...@gm...> wrote:
>>
>>> Ah, so kind of like a rasterization of the 2d image into the 3d voxel
>>> space?
>>>
>>>
>>> On Sun, Jun 13, 2010 at 1:31 PM, Manuel Massing <
>>> m.m...@wa...> wrote:
>>>
>>>> Hi,
>>>>
>>>> > @Manuel: I think he wants to find the nearest point on the image to
>>>> the
>>>> > voxel. I'm not sure how a DDA tracing algorithm would help there.
>>>>
>>>> I was thinking of the following:
>>>> Think of each 2d scanline as a 3d ray which passes through the
>>>> voxel grid. Traverse the voxel grid along the ray direction using
>>>> DDA, Insert the intersecting pixel spans (in fact a quadrilateral) into
>>>> the
>>>> appropriate voxel.
>>>>
>>>> Additionally, one could use summed area tables or somesuch to
>>>> pre-filter/match
>>>> the voxel and pixel footprint approximately.
>>>>
>>>> bye,
>>>>
>>>>        Manuel
>>>>
>>>>
>>>> ------------------------------------------------------------------------------
>>>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>>>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>>>> lucky parental unit.  See the prize list and enter to win:
>>>> http://p.sf.net/sfu/thinkgeek-promo
>>>> _______________________________________________
>>>> GDAlgorithms-list mailing list
>>>> GDA...@li...
>>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>> Archives:
>>>>
>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>>
>>>
>>>
>>
>>
>> ------------------------------------------------------------------------------
>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>> lucky parental unit.  See the prize list and enter to win:
>> http://p.sf.net/sfu/thinkgeek-promo
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
>
>
> ------------------------------------------------------------------------------
> ThinkGeek and WIRED's GeekDad team up for the Ultimate
> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
> lucky parental unit.  See the prize list and enter to win:
> http://p.sf.net/sfu/thinkgeek-promo
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>



-- 
--
Stefan Daenzer
Körnerplatz 8
04107 Leipzig

Tel.: +49-176-61157550

"Work like you don't need the money, love like you've never been hurt and
dance like no one is watching." - Randall G Leighton

Re: [Algorithms] Efficient Voxel Interpolation / Splatting

[Jon W. <jw...@gm...>]

If the algorithm requires "rich" data, then no, you can't incrementally
compute it.

If the algorithm ends up with a probability/density function for each target
voxel after each image pass, then you could just adjust the probabilities
based on the new data, which is possible to do incrementally.

Sincerely,

jw


--
Americans might object: there is no way we would sacrifice our living
standards for the benefit of people in the rest of the world. Nevertheless,
whether we get there willingly or not, we shall soon have lower consumption
rates, because our present rates are unsustainable.



On Wed, Jun 16, 2010 at 4:00 AM, Stefan Dänzer <ste...@gm...>wrote:

> Very interesting approaches here,
>
> @Manuel: I think the 3D-DDA (or the Bresenham 3D Algorithm suggested by Jon
> Watte) might be the way to go.
>
> @Jon Olic: The application is 3-D Ultrasound (US) reconstruction from
> spatially positioned and oriented 2-D US images. We basically use an optical
> tracking system and spatially track the US-Probe. This way we can record
> 3D-US volumes using a conventional 2D-US machine. Your suggested
> rasterization algorithm which projects the voxel center onto the image plane
> and calculates the distance of the projected point in the plane looks also
> fine, but i'm not sure if I can implement it more efficiently than a
> modified Bresenham 3D or 3D-DDA algorithm.
>
> @Jon Watte: If we end up weighting the contribution of each pixel in the
> proximity of a voxel inverse linearly to the distance to the voxel center,
> there might not be a way around using some extra storage for each voxel. We
> might end up storing distance and color of a pixel for each voxel during
> distance calculation and (as Manuel mentioned also) calculating the color of
> each voxel as a post processing step. I don't see any way how it would be
> possible to compose the value for each voxel incrementally. Am I missing
> something here?
>
> Thanks for this excellent discussion so far,
>
> Stefan
>
>
> On Tue, Jun 15, 2010 at 6:52 PM, Jon Watte <jw...@gm...> wrote:
>
>> You can incrementally build the 3D voxels by tracing the plane of each
>> contributing image, using an algorithm similar to Bresenham or Marching
>> Cubes. As long as the value for each voxel can be composed incrementally,
>> you can do this for images sequentially without needing extra storage.
>>
>> And, yes, recursive tree-like data structures are almost always used for
>> voxels, because > 90% of the voxel volume is either all-solid or all-open.
>>
>> Btw: if you're interested in voxel terrain, you probably should check out
>> the implementation in the C4 engine. It's pretty nice feature-wise, and high
>> quality code as well. The source license is $350, although you probably want
>> to be careful with the license terms; you probably can't copy and paste code
>> from the engine into your own code, for example.
>>
>> Sincerely,
>>
>> jw
>>
>>
>> --
>> Americans might object: there is no way we would sacrifice our living
>> standards for the benefit of people in the rest of the world. Nevertheless,
>> whether we get there willingly or not, we shall soon have lower consumption
>> rates, because our present rates are unsustainable.
>>
>>
>>
>> On Sun, Jun 13, 2010 at 12:10 PM, Jon Olick <jon...@gm...> wrote:
>>
>>> If its a 2D image to 3d voxel rasterization algorithm, definitely make a
>>> oct-tree of the voxel data and then intersect it with the 2D image plane
>>> (plus a depth if you want water-tight), and further clip by the extents of
>>> the image. Then for each voxel which is considered intersecting the 2D image
>>> volume, determine the color by projecting the voxel center onto the image
>>> plane then do a sample (bi-linear interp with mip-maps perhaps?) of the
>>> image. You could then alpha the voxel based on the amount that the voxel is
>>> intersected with the volume. For example 20% inside = 20% alpha.
>>>
>>> On Sun, Jun 13, 2010 at 1:56 PM, Jon Olick <jon...@gm...> wrote:
>>>
>>>> Ah, so kind of like a rasterization of the 2d image into the 3d voxel
>>>> space?
>>>>
>>>>
>>>> On Sun, Jun 13, 2010 at 1:31 PM, Manuel Massing <
>>>> m.m...@wa...> wrote:
>>>>
>>>>> Hi,
>>>>>
>>>>> > @Manuel: I think he wants to find the nearest point on the image to
>>>>> the
>>>>> > voxel. I'm not sure how a DDA tracing algorithm would help there.
>>>>>
>>>>> I was thinking of the following:
>>>>> Think of each 2d scanline as a 3d ray which passes through the
>>>>> voxel grid. Traverse the voxel grid along the ray direction using
>>>>> DDA, Insert the intersecting pixel spans (in fact a quadrilateral) into
>>>>> the
>>>>> appropriate voxel.
>>>>>
>>>>> Additionally, one could use summed area tables or somesuch to
>>>>> pre-filter/match
>>>>> the voxel and pixel footprint approximately.
>>>>>
>>>>> bye,
>>>>>
>>>>>        Manuel
>>>>>
>>>>>
>>>>> ------------------------------------------------------------------------------
>>>>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>>>>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>>>>> lucky parental unit.  See the prize list and enter to win:
>>>>> http://p.sf.net/sfu/thinkgeek-promo
>>>>> _______________________________________________
>>>>> GDAlgorithms-list mailing list
>>>>> GDA...@li...
>>>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>>> Archives:
>>>>>
>>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>>>
>>>>
>>>>
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>>> lucky parental unit.  See the prize list and enter to win:
>>> http://p.sf.net/sfu/thinkgeek-promo
>>> _______________________________________________
>>> GDAlgorithms-list mailing list
>>> GDA...@li...
>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>> Archives:
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>
>>
>>
>>
>> ------------------------------------------------------------------------------
>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>> lucky parental unit.  See the prize list and enter to win:
>> http://p.sf.net/sfu/thinkgeek-promo
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
>
>
> --
> --
> Stefan Daenzer
> Körnerplatz 8
> 04107 Leipzig
>
> Tel.: +49-176-61157550
>
>
> "Work like you don't need the money, love like you've never been hurt and
> dance like no one is watching." - Randall G Leighton
>
>
> ------------------------------------------------------------------------------
> ThinkGeek and WIRED's GeekDad team up for the Ultimate
> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
> lucky parental unit.  See the prize list and enter to win:
> http://p.sf.net/sfu/thinkgeek-promo
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] Efficient Voxel Interpolation / Splatting

[Stefan D. <ste...@gm...>]

Jon,

I'm not sure how one would model this as a probability density function. If
one would want the voxel value to be the expected value of the probability
density function, at least the variance of each contributing pixel would
have to be stored for each pixel. Also, there needs to be a function which
takes distance and value of a pixel as parameters and maps it into the space
of the probability density function of a voxel.

Am I missing something with the probability-density function approach?

Stefan

On Wed, Jun 16, 2010 at 9:13 PM, Jon Watte <jw...@gm...> wrote:

> If the algorithm requires "rich" data, then no, you can't incrementally
> compute it.
>
> If the algorithm ends up with a probability/density function for each
> target voxel after each image pass, then you could just adjust the
> probabilities based on the new data, which is possible to do incrementally.
>
> Sincerely,
>
> jw
>
>
> --
> Americans might object: there is no way we would sacrifice our living
> standards for the benefit of people in the rest of the world. Nevertheless,
> whether we get there willingly or not, we shall soon have lower consumption
> rates, because our present rates are unsustainable.
>
>
>
> On Wed, Jun 16, 2010 at 4:00 AM, Stefan Dänzer <ste...@gm...>wrote:
>
>> Very interesting approaches here,
>>
>> @Manuel: I think the 3D-DDA (or the Bresenham 3D Algorithm suggested by
>> Jon Watte) might be the way to go.
>>
>> @Jon Olic: The application is 3-D Ultrasound (US) reconstruction from
>> spatially positioned and oriented 2-D US images. We basically use an optical
>> tracking system and spatially track the US-Probe. This way we can record
>> 3D-US volumes using a conventional 2D-US machine. Your suggested
>> rasterization algorithm which projects the voxel center onto the image plane
>> and calculates the distance of the projected point in the plane looks also
>> fine, but i'm not sure if I can implement it more efficiently than a
>> modified Bresenham 3D or 3D-DDA algorithm.
>>
>> @Jon Watte: If we end up weighting the contribution of each pixel in the
>> proximity of a voxel inverse linearly to the distance to the voxel center,
>> there might not be a way around using some extra storage for each voxel. We
>> might end up storing distance and color of a pixel for each voxel during
>> distance calculation and (as Manuel mentioned also) calculating the color of
>> each voxel as a post processing step. I don't see any way how it would be
>> possible to compose the value for each voxel incrementally. Am I missing
>> something here?
>>
>> Thanks for this excellent discussion so far,
>>
>> Stefan
>>
>>
>> On Tue, Jun 15, 2010 at 6:52 PM, Jon Watte <jw...@gm...> wrote:
>>
>>> You can incrementally build the 3D voxels by tracing the plane of each
>>> contributing image, using an algorithm similar to Bresenham or Marching
>>> Cubes. As long as the value for each voxel can be composed incrementally,
>>> you can do this for images sequentially without needing extra storage.
>>>
>>> And, yes, recursive tree-like data structures are almost always used for
>>> voxels, because > 90% of the voxel volume is either all-solid or all-open.
>>>
>>> Btw: if you're interested in voxel terrain, you probably should check out
>>> the implementation in the C4 engine. It's pretty nice feature-wise, and high
>>> quality code as well. The source license is $350, although you probably want
>>> to be careful with the license terms; you probably can't copy and paste code
>>> from the engine into your own code, for example.
>>>
>>> Sincerely,
>>>
>>> jw
>>>
>>>
>>> --
>>> Americans might object: there is no way we would sacrifice our living
>>> standards for the benefit of people in the rest of the world. Nevertheless,
>>> whether we get there willingly or not, we shall soon have lower consumption
>>> rates, because our present rates are unsustainable.
>>>
>>>
>>>
>>> On Sun, Jun 13, 2010 at 12:10 PM, Jon Olick <jon...@gm...> wrote:
>>>
>>>> If its a 2D image to 3d voxel rasterization algorithm, definitely make a
>>>> oct-tree of the voxel data and then intersect it with the 2D image plane
>>>> (plus a depth if you want water-tight), and further clip by the extents of
>>>> the image. Then for each voxel which is considered intersecting the 2D image
>>>> volume, determine the color by projecting the voxel center onto the image
>>>> plane then do a sample (bi-linear interp with mip-maps perhaps?) of the
>>>> image. You could then alpha the voxel based on the amount that the voxel is
>>>> intersected with the volume. For example 20% inside = 20% alpha.
>>>>
>>>> On Sun, Jun 13, 2010 at 1:56 PM, Jon Olick <jon...@gm...> wrote:
>>>>
>>>>> Ah, so kind of like a rasterization of the 2d image into the 3d voxel
>>>>> space?
>>>>>
>>>>>
>>>>> On Sun, Jun 13, 2010 at 1:31 PM, Manuel Massing <
>>>>> m.m...@wa...> wrote:
>>>>>
>>>>>> Hi,
>>>>>>
>>>>>> > @Manuel: I think he wants to find the nearest point on the image to
>>>>>> the
>>>>>> > voxel. I'm not sure how a DDA tracing algorithm would help there.
>>>>>>
>>>>>> I was thinking of the following:
>>>>>> Think of each 2d scanline as a 3d ray which passes through the
>>>>>> voxel grid. Traverse the voxel grid along the ray direction using
>>>>>> DDA, Insert the intersecting pixel spans (in fact a quadrilateral)
>>>>>> into the
>>>>>> appropriate voxel.
>>>>>>
>>>>>> Additionally, one could use summed area tables or somesuch to
>>>>>> pre-filter/match
>>>>>> the voxel and pixel footprint approximately.
>>>>>>
>>>>>> bye,
>>>>>>
>>>>>>        Manuel
>>>>>>
>>>>>>
>>>>>> ------------------------------------------------------------------------------
>>>>>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>>>>>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>>>>>> lucky parental unit.  See the prize list and enter to win:
>>>>>> http://p.sf.net/sfu/thinkgeek-promo
>>>>>> _______________________________________________
>>>>>> GDAlgorithms-list mailing list
>>>>>> GDA...@li...
>>>>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>>>> Archives:
>>>>>>
>>>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>>>>
>>>>>
>>>>>
>>>>
>>>>
>>>> ------------------------------------------------------------------------------
>>>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>>>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>>>> lucky parental unit.  See the prize list and enter to win:
>>>> http://p.sf.net/sfu/thinkgeek-promo
>>>> _______________________________________________
>>>> GDAlgorithms-list mailing list
>>>> GDA...@li...
>>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>> Archives:
>>>>
>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>>
>>>
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>>> lucky parental unit.  See the prize list and enter to win:
>>> http://p.sf.net/sfu/thinkgeek-promo
>>> _______________________________________________
>>> GDAlgorithms-list mailing list
>>> GDA...@li...
>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>> Archives:
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>
>>
>>
>>
>> --
>> --
>> Stefan Daenzer
>> Körnerplatz 8
>> 04107 Leipzig
>>
>> Tel.: +49-176-61157550
>>
>>
>> "Work like you don't need the money, love like you've never been hurt and
>> dance like no one is watching." - Randall G Leighton
>>
>>
>> ------------------------------------------------------------------------------
>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>> lucky parental unit.  See the prize list and enter to win:
>> http://p.sf.net/sfu/thinkgeek-promo
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
>
>
> ------------------------------------------------------------------------------
> ThinkGeek and WIRED's GeekDad team up for the Ultimate
> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
> lucky parental unit.  See the prize list and enter to win:
> http://p.sf.net/sfu/thinkgeek-promo
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>



-- 
--
Stefan Daenzer
Körnerplatz 8
04107 Leipzig

Tel.: +49-176-61157550

"Work like you don't need the money, love like you've never been hurt and
dance like no one is watching." - Randall G Leighton

Re: [Algorithms] Efficient Voxel Interpolation / Splatting

[Jon W. <jw...@gm...>]

>
> at least the variance of each contributing pixel would have to be stored
> for each pixel


Unless I miss something, the variance is possible to calculate
incrementally. You store the sum of the elements, the sum of the square of
the elements, and the number of elements contributing, all of which can be
incrementally added to. But maybe I'm missing something?

Sincerely,

jw


--
Americans might object: there is no way we would sacrifice our living
standards for the benefit of people in the rest of the world. Nevertheless,
whether we get there willingly or not, we shall soon have lower consumption
rates, because our present rates are unsustainable.



On Fri, Jun 18, 2010 at 2:05 AM, Stefan Dänzer <ste...@gm...>wrote:

> Jon,
>
> I'm not sure how one would model this as a probability density function. If
> one would want the voxel value to be the expected value of the probability
> density function, at least the variance of each contributing pixel would
> have to be stored for each pixel. Also, there needs to be a function which
> takes distance and value of a pixel as parameters and maps it into the space
> of the probability density function of a voxel.
>
> Am I missing something with the probability-density function approach?
>
> Stefan
>
> On Wed, Jun 16, 2010 at 9:13 PM, Jon Watte <jw...@gm...> wrote:
>
>> If the algorithm requires "rich" data, then no, you can't incrementally
>> compute it.
>>
>> If the algorithm ends up with a probability/density function for each
>> target voxel after each image pass, then you could just adjust the
>> probabilities based on the new data, which is possible to do incrementally.
>>
>> Sincerely,
>>
>> jw
>>
>>
>> --
>> Americans might object: there is no way we would sacrifice our living
>> standards for the benefit of people in the rest of the world. Nevertheless,
>> whether we get there willingly or not, we shall soon have lower consumption
>> rates, because our present rates are unsustainable.
>>
>>
>>
>> On Wed, Jun 16, 2010 at 4:00 AM, Stefan Dänzer <ste...@gm...>wrote:
>>
>>> Very interesting approaches here,
>>>
>>> @Manuel: I think the 3D-DDA (or the Bresenham 3D Algorithm suggested by
>>> Jon Watte) might be the way to go.
>>>
>>> @Jon Olic: The application is 3-D Ultrasound (US) reconstruction from
>>> spatially positioned and oriented 2-D US images. We basically use an optical
>>> tracking system and spatially track the US-Probe. This way we can record
>>> 3D-US volumes using a conventional 2D-US machine. Your suggested
>>> rasterization algorithm which projects the voxel center onto the image plane
>>> and calculates the distance of the projected point in the plane looks also
>>> fine, but i'm not sure if I can implement it more efficiently than a
>>> modified Bresenham 3D or 3D-DDA algorithm.
>>>
>>> @Jon Watte: If we end up weighting the contribution of each pixel in the
>>> proximity of a voxel inverse linearly to the distance to the voxel center,
>>> there might not be a way around using some extra storage for each voxel. We
>>> might end up storing distance and color of a pixel for each voxel during
>>> distance calculation and (as Manuel mentioned also) calculating the color of
>>> each voxel as a post processing step. I don't see any way how it would be
>>> possible to compose the value for each voxel incrementally. Am I missing
>>> something here?
>>>
>>> Thanks for this excellent discussion so far,
>>>
>>> Stefan
>>>
>>>
>>> On Tue, Jun 15, 2010 at 6:52 PM, Jon Watte <jw...@gm...> wrote:
>>>
>>>> You can incrementally build the 3D voxels by tracing the plane of each
>>>> contributing image, using an algorithm similar to Bresenham or Marching
>>>> Cubes. As long as the value for each voxel can be composed incrementally,
>>>> you can do this for images sequentially without needing extra storage.
>>>>
>>>> And, yes, recursive tree-like data structures are almost always used for
>>>> voxels, because > 90% of the voxel volume is either all-solid or all-open.
>>>>
>>>> Btw: if you're interested in voxel terrain, you probably should check
>>>> out the implementation in the C4 engine. It's pretty nice feature-wise, and
>>>> high quality code as well. The source license is $350, although you probably
>>>> want to be careful with the license terms; you probably can't copy and paste
>>>> code from the engine into your own code, for example.
>>>>
>>>> Sincerely,
>>>>
>>>> jw
>>>>
>>>>
>>>> --
>>>> Americans might object: there is no way we would sacrifice our living
>>>> standards for the benefit of people in the rest of the world. Nevertheless,
>>>> whether we get there willingly or not, we shall soon have lower consumption
>>>> rates, because our present rates are unsustainable.
>>>>
>>>>
>>>>
>>>> On Sun, Jun 13, 2010 at 12:10 PM, Jon Olick <jon...@gm...>wrote:
>>>>
>>>>> If its a 2D image to 3d voxel rasterization algorithm, definitely make
>>>>> a oct-tree of the voxel data and then intersect it with the 2D image plane
>>>>> (plus a depth if you want water-tight), and further clip by the extents of
>>>>> the image. Then for each voxel which is considered intersecting the 2D image
>>>>> volume, determine the color by projecting the voxel center onto the image
>>>>> plane then do a sample (bi-linear interp with mip-maps perhaps?) of the
>>>>> image. You could then alpha the voxel based on the amount that the voxel is
>>>>> intersected with the volume. For example 20% inside = 20% alpha.
>>>>>
>>>>> On Sun, Jun 13, 2010 at 1:56 PM, Jon Olick <jon...@gm...>wrote:
>>>>>
>>>>>> Ah, so kind of like a rasterization of the 2d image into the 3d voxel
>>>>>> space?
>>>>>>
>>>>>>
>>>>>> On Sun, Jun 13, 2010 at 1:31 PM, Manuel Massing <
>>>>>> m.m...@wa...> wrote:
>>>>>>
>>>>>>> Hi,
>>>>>>>
>>>>>>> > @Manuel: I think he wants to find the nearest point on the image to
>>>>>>> the
>>>>>>> > voxel. I'm not sure how a DDA tracing algorithm would help there.
>>>>>>>
>>>>>>> I was thinking of the following:
>>>>>>> Think of each 2d scanline as a 3d ray which passes through the
>>>>>>> voxel grid. Traverse the voxel grid along the ray direction using
>>>>>>> DDA, Insert the intersecting pixel spans (in fact a quadrilateral)
>>>>>>> into the
>>>>>>> appropriate voxel.
>>>>>>>
>>>>>>> Additionally, one could use summed area tables or somesuch to
>>>>>>> pre-filter/match
>>>>>>> the voxel and pixel footprint approximately.
>>>>>>>
>>>>>>> bye,
>>>>>>>
>>>>>>>        Manuel
>>>>>>>
>>>>>>>
>>>>>>> ------------------------------------------------------------------------------
>>>>>>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>>>>>>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>>>>>>> lucky parental unit.  See the prize list and enter to win:
>>>>>>> http://p.sf.net/sfu/thinkgeek-promo
>>>>>>> _______________________________________________
>>>>>>> GDAlgorithms-list mailing list
>>>>>>> GDA...@li...
>>>>>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>>>>> Archives:
>>>>>>>
>>>>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>> ------------------------------------------------------------------------------
>>>>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>>>>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>>>>> lucky parental unit.  See the prize list and enter to win:
>>>>> http://p.sf.net/sfu/thinkgeek-promo
>>>>> _______________________________________________
>>>>> GDAlgorithms-list mailing list
>>>>> GDA...@li...
>>>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>>> Archives:
>>>>>
>>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>>>
>>>>
>>>>
>>>>
>>>> ------------------------------------------------------------------------------
>>>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>>>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>>>> lucky parental unit.  See the prize list and enter to win:
>>>> http://p.sf.net/sfu/thinkgeek-promo
>>>> _______________________________________________
>>>> GDAlgorithms-list mailing list
>>>> GDA...@li...
>>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>>> Archives:
>>>>
>>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>>
>>>
>>>
>>>
>>> --
>>> --
>>> Stefan Daenzer
>>> Körnerplatz 8
>>> 04107 Leipzig
>>>
>>> Tel.: +49-176-61157550
>>>
>>>
>>> "Work like you don't need the money, love like you've never been hurt and
>>> dance like no one is watching." - Randall G Leighton
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>>> lucky parental unit.  See the prize list and enter to win:
>>> http://p.sf.net/sfu/thinkgeek-promo
>>> _______________________________________________
>>> GDAlgorithms-list mailing list
>>> GDA...@li...
>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>> Archives:
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>
>>
>>
>>
>> ------------------------------------------------------------------------------
>> ThinkGeek and WIRED's GeekDad team up for the Ultimate
>> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
>> lucky parental unit.  See the prize list and enter to win:
>> http://p.sf.net/sfu/thinkgeek-promo
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
>
>
> --
> --
> Stefan Daenzer
> Körnerplatz 8
> 04107 Leipzig
>
> Tel.: +49-176-61157550
>
> "Work like you don't need the money, love like you've never been hurt and
> dance like no one is watching." - Randall G Leighton
>
>
> ------------------------------------------------------------------------------
> ThinkGeek and WIRED's GeekDad team up for the Ultimate
> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
> lucky parental unit.  See the prize list and enter to win:
> http://p.sf.net/sfu/thinkgeek-promo
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>