text:
# I have a calculational problem in applying Model Predictive Control [MPC] with a fixed terminal state, how can I solve that?

I am interested in solving a optimal control input problem with discrete finite time when the reference state value is given, I have designed a cost function with terminal state and then I want use the following equations to compute the optimal $$u$$

\begin{aligned} \label{Kostenfunktion} J_{1}(k)&=\min_{\mathbf{u}}\sum_{j=1}^{N_p-1} \|( \mathbf{x}(k+j|k) -\mathbf{R_{ref}}(k+j) )\|_{\mathbf{Q_i}}^2 + \sum_{j=0}^{N_c-1}\|\mathbf{u}(k+j)\|_{\mathbf{P_i}}^2+ \|\mathbf{x}(k+Np|k)-x_F\|_W^2 \\ \mathbf{H}&=\mathbf{M}_{u}^{T}\mathbf{Q}\mathbf{M}_{u}+\mathbf{P}\\ \mathbf{f}^T&=-\mathbf{M}_{u}^{T}\mathbf{Q}(\mathbf{R}_{ref}-\mathbf{M}_{x}x_{k})\\ \mathbf{u}&=-inv(\mathbf{H})*\mathbf{f}\\ \end{aligned}

$$\mathbf{M}_{x}=\begin{bmatrix} A\\ A^2\\ A^3\\ \vdots \\ A^{N_p} \end{bmatrix}$$ , $$\mathbf{M}_{u} = \begin{bmatrix} B &0 &0 &\cdots & 0\\ AB & B & 0 & \cdots & 0\\ A^2B& AB & 0 &\cdots &0 \\ \vdots & \vdots & \vdots & \vdots &\vdots \\ A^{N_p-1}B & A^{N_p-2}B & A^{N_p-3}B & \cdots & A^{N_p-N_c}B \end{bmatrix}$$

I have two questions

1. How can I choose the terminal state? could I choose free value? (I know there would be some convergence problems when choose free)
2. I would like to using this cost function to compute a trajectory with distance, speed and acceleration. the dynamic model is $$$$x(k+1) = Ax(k) + Bu(k) \\$$$$

A=[0 1 0; 0 0 1;0 0 0];
B=[0 0 1];

I would like to compute a trajectory within, its initial condition is [0 0 0] and the final condition is [10,2.7,0] ($$R_{ref}$$ is also the final condition), $$N_p=N_c=50$$, but from the following figure we can see that the end position couldn't reach the defined end point, I would like to ask, it's about the tuning parameters or the cost function has some problem? Thanks

• You should expand the abbreviation "MCP" . It might help readers if you could characterize the nature of your question: "I have a conceptual problem with the general theory of XYZ" or "I have a calculational problem in applying XYZ" or "I want a sanity check on my proposed thesis topic", or whatever. Nov 5, 2019 at 19:45
• What values for $N_p$ and $N_c$ are you using and did you only solved for the optimal input once and plotted its predicted trajectory or did you only apply the first input of each optimal solution and increased $k$ each time? Nov 5, 2019 at 22:48
• @KwinvanderVeen thank you for your answer. I choose Np=Nc=50, and as you said, I just apply the first input of each optimal solution and increased k at each time. Nov 6, 2019 at 8:12
• @kimchilover thanks Nov 6, 2019 at 8:15

In order to have that the final state is equal to a desired state one could remove the terminal cost term and replace it with an equality constraint. When solving this optimization problem you could use a solver which allows for this, or if you want to do it manually use Lagrange multipliers. Though the equality constraint can also be approximated by making $$W$$ really big.

It can be noted that the solution only guarantees that $$x(k+N_p|k)$$ is equal to the desired state. However, if you solve the problem each time $$k$$ is increased and you only apply the first input of the solution, then you only reach $$x(k+1|k)$$, $$x(k+2|k+1)$$, etc. but never $$x(k+N_p|k)$$. To fix this one could reduce $$N_p$$ and $$N_c$$ by one every time $$k$$ increases, but this should just give the same solution as the fist solution (if the model matches perfectly to the actual system). It can be noted that it is possible to asymptotically converge to the desired state using your implementation, if there exists an input $$u^*$$ such that the desired state $$x^*$$ is stationary, so satisfies $$x^*=A\,x^* + B\,u^*$$ and the cost function is defined as

$$J(k) = \min_u \sum_{j=1}^{N_p-1} \|x(k+j|k) - x^*\|_{Q_i}^2 + \sum_{j=0}^{N_c-1} \|u(k+j) - u^*\|_{P_i}^2.$$

The equality constraint isn't necessary to get the asymptotic convergence of the state to $$x^*$$.

PS: Your model $$(A,B)$$ is a chain of delays, while your labels of your figures suggests that you intended it to be a chain of integrators (your model would be a chain of integrators if it where continuous time, $$\dot{x} = A\,x + B\,u$$). A chain of integrators in discrete time could for example be obtained through zero order hold using

$$A = \begin{bmatrix} 1 & h & 1/2\,h^2 \\ 0 & 1 & h \\ 0 & 0 & 1 \end{bmatrix}, \quad B = \begin{bmatrix} 1/6\,h^3 \\ 1/2\,h^2 \\ h \end{bmatrix},$$

with $$h$$ the sample time.

• Thank you so much for your explanation, that's really helpful! Nov 6, 2019 at 12:28
• I have a little question, could I use first order hold(FOH) to discrete the state space model? may be more accurate? Nov 6, 2019 at 14:11
• @YunhuaHu I don't see why not. Nov 6, 2019 at 14:58
• I have a little question. If I use first oder hold to discrete the state space modul, only B is different from the ZOH method. If we use the same sampling time, what's the difference between the ZOH and FOH discrete method? Jan 3, 2020 at 12:34
• ZOH assumes that the input it held constant during one sample time, while FOH assumes that the input is linearly interpolated between sample times. So these discretization methods only affects the assumed behavior of the input signal. The dynamics of the system, given certain initial conditions, is solved exactly, which is the same in both cases and thus the discretized A is the same. Jan 3, 2020 at 17:00


text:
# Why does the low entropy at the big bang require an explanation? (cosmological arrow of time)

I have read Sean Carrol's book. I have listened to Roger Penrose talk on "Before the Big Bang". Both are offering to explain the mystery of low entropy, highly ordered state, at the Big Bang.

Since the second law of thermodynamics is considered a fundamental law of nature, and since it states that in a closed system entropy either must stay the same or increase, the entropy at the time of the Big Bang must have been much lower than it is now.

Also, the thermodynamic arrow was explained by Boltzmann in 1896 embodied in $S = k\ln W$ which was inscribed on his tombstone. $W$ is the number of distinct microstates of the system. It seems to me that trivially this number will be less in the past than in the future since entropy obeys the 2nd law. This determines the thermodynamic arrow of time.

Why do we need more explanation of a "fundamental law"?

• I see that Lubos has posted this great link on another question: "Is it physically meaningful to talk about the arrow of time in other universes?"--:"Robert Wald arxiv.org/abs/gr-qc/0507094 who argued that the thermodynamic arrow of time - or low entry of the early Universe - can't have a dynamical origin. – Luboš Motl Jan 21 at 18:34" Many thanks, Lubos. I am not going to argue with Robert Wald. Jan 30, 2011 at 7:15
• Thanks, Gordon, for your good contributions. Just a link so that people may simply click: arxiv.org/abs/gr-qc/0507094 Jan 30, 2011 at 7:19
• All these arguments hinge on the assumption that the Universe is a closed system. If you abandon that assumption the whole ball-game changes. So one has to seriously consider whether this assumption is warranted in the first place. After all no closed systems exist in the world that we observe. Not even black holes. Why should the Universe be any different?
– user346
Feb 1, 2011 at 7:22
• – user4552
Aug 14, 2013 at 18:15

This is somewhat controversial issue. But let me present the reasons, as far as I understood, why people like Sir Penrose thinks so.
Their arguments are roughly as follows:

1. The basic microscopic laws of physics are perfectly time symmetric. They are not biased in any time direction past or future.

2. Second law follows from the fact that that given an initial condition of a system which is not in the most probable state will tend to go towards the most probable state by the same microscopic laws. Since number of disordered states are much higher the system will become more and more disordered with time. Accordingly its entropy will increase until a maximum value when the system comes to the thermal equilibrium.

3. Since the microscopic laws are time symmetric the same argument can be made towards the past time direction as well. Given an an initial condition of a system which is not in the most probable state should go towards more disordered (high entropy) states towards past as well. That's what the mathematics of the laws tells us.

4. This is against our experience. Either all the parts of the universe we are observing (including our memories of past) has just undergone a HUGE fluctuation right now to give the impression that there was a more ordered past (which is crazy) OR the system was already even more ordered (low entropy) and more special in the past. But that means even more huge a fluctuation. This reasoning will lead us to conclude that at the moment of big bang the universe was extra ordinarily ordered and most special. It should be so special that it requires explanation.

Critics often point out that prediction and retrodiction is not the same thing forgetting that when one talks about the very "arrow of time" no one can say with justification which is prediction and which is retrodiction. Other than that it is also questionable whether second law can be applied this way to the whole universe or not.

• See the link to the paper by Robert Wald:arxiv.org/find/all/1/… Jan 30, 2011 at 7:31
• OT: (I went to some of the Waldfest in 2006 with my son...it was fun.) Jan 30, 2011 at 7:36
• I have just read the paper and I agree with it. I agree that the specialness of the big bang is required and one can not invoke dynamical theories like chaotic inflation to explain the specialness, which assumes the universe started with a random initial condition.
– user1355
Jan 30, 2011 at 7:45
• @sbi Yes, Wald does argue that, but the point of my posting the link is that he also does not hold that a cosmological explanation is known or perhaps required. He says that cosmological arguments become circular and uses inflation and anthropic examples. Ultimately, he says that the universe came into existence in a special state, period. He has an addendum saying he disagrees with Carrol and Chen. In my view Wald answers the above question I asked as "It doesn't".. He does agree with you about inflation though. Jan 30, 2011 at 16:08
• Well, I will leave it with Wald's paper and we will disagree. Feb 5, 2011 at 17:57

The key issue is: To allow galaxy and star formation, the universe had to start up in an extremely (but not perfectly) homogeneous state. The fact that the initial inhomogeneities were of size 1 part in a gadzillion (as opposed to zero) is what is puzzling.

• Not really. Quantum vacuum fluctuations were inflated by the inflaton field. Jan 30, 2011 at 6:21
• Not sure what you are commenting on. Are you disputing that the initial universe must have had very small but nonzero inhomogeneity? Jan 30, 2011 at 6:58
• Inflation will increase the entropy. So the initial entropy has to be even smaller. Jan 30, 2011 at 7:18
• @Gordon, Wald argued the very opposite in the paper! Inflation can't explain time's arrow. No theories which assumes initial randomness can. That was his point.
– user1355
Jan 30, 2011 at 7:59
• @sbi Yes, Wald does argue that, but the point of my posting the link is that he also does not hold that a cosmological explanation is known or perhaps required. He says that cosmological arguments become circular and uses inflation and anthropic examples. Ultimately, he says that the universe came into existence in a special state, period. He has an addendum saying he disagrees with Carrol and Chen. Jan 30, 2011 at 16:05

Because this violates the assumption that every state ought to be equally likely.

The low entropy of the big bang leads to the second law of thermodynamics, not the other way around.

In fact, as Boltzmann had shown, for almost all states constrained to have a given macroscopic description at a given time, entropy will increase both toward the past as well as the future. For the entropy to have been continually decreasing as we move back to the past for billions of years requires an incredible amount of fine-tuning of the correlations between almost all the particles in the present.

• I still don't follow (agree). I do agree that the initial conditions lead to the 2nd law, but it is a bit of a tautology. Jan 30, 2011 at 6:11
• What leads to the 2nd law and the arrow is the difference in entropy between then and now. I don't see how incredible fine tuning is required. If (say) the universe started as a bubble (say, Linde's eternal inflation model), it must start in a highly ordered state, and inflation can explain the fine tuning. Or not? Jan 30, 2011 at 6:18
• That is, "the correlation between almost all the particles in the present" could be explained by eternal inflation? Jan 30, 2011 at 6:20
• (The -1 wasn't me :) ) Jan 30, 2011 at 7:06
• I think it would require a lot of fine tuning to start with eternal inflation, but once we have eternal inflation, it will continue indefinitely.
– QGR
Feb 1, 2011 at 15:38

format: plain


text:
• Create Account

Is my frustum culling slow ?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

45 replies to this topic

#21belfegor  Members

Posted 31 March 2013 - 07:21 AM

class and type sizes are unrelated to instance adresses.

Excuse my stupidity i still don't understand.

You mean instances of a _Plane in an std::array or vector might not be contiguous in memory (with their default allocator)?

Edited by belfegor, 31 March 2013 - 07:25 AM.

#22Hodgman  Moderators

Posted 31 March 2013 - 07:32 AM

But i don't understand why isn't it already 16byte aligned as data is 4 floats ?

It's made up of primitives, each of which only requires 4-byte alignment to work correctly, so the struct will work as long as it's 4-byte aligned. It doesn't need to be 8 or 16 byte aligned in order to function correctly, only 4-byte aligned (and this is assuming that floats actually need to be 4 byte aligned).

class and type sizes are unrelated to instance adresses.

Excuse my stupidity i still don't understand.
You mean instances of a _Plane in an std::array or vector might not be contiguous in memory (with their default allocator)?

As far as I know:
• std::allocator<T>::allocate (which is used by the std containers) or "new T" will return a block of memory that is correctly aligned for the type "T" (i.e. the address is a multiple of alignof(T))
• malloc( sizeof(T) ) wont.

Edited by Hodgman, 31 March 2013 - 07:35 AM.

#23galop1n  Members

Posted 31 March 2013 - 07:34 AM

if a class is declared as align on a 16 byte boundary, the class size will be a multiple of 16 too, because we can write things like MyClass array[N]; and if array[i] is align on 16, then array[i+1] will too.

But if you write MyClass* array = new MyClass[N]; you have no guarante on the memory address return by new, because the operator new do not receive an alignment value. You will need to overload the operator new of MyClass to do some internal memalign, or globaly override the memory allocator to always return address multiple of 16.

And std::array is a C array, so the memory is contigus but do not rely on a memory allocator, so the compiler is able to align the members with the declspec value (as long as the objet storing an std::array<_Plane,6> is not allocate with a bare new )

#24galop1n  Members

Posted 31 March 2013 - 07:38 AM

As far as I know:

std::allocator::allocate (which is used by the std containers) or "new T" will return a block of memory that is correctly aligned for the type "T".
malloc( sizeof(T) ) wont.

Sadly, the standard do not consider simd types, the largest native alignment use by the default std::alocator is the one for a long long, that is only 8 bytes.

#25belfegor  Members

Posted 31 March 2013 - 08:11 AM

Am i getting this right:

__declspec(align(16))
struct Foo
{
float x;
float y;
float z;
};

storage space for each element would be 16 bytes?

#26Hodgman  Moderators

Posted 31 March 2013 - 08:12 AM

the operator new do not receive an alignment value

This is true, but new is also required to return a block of memory that is suitably aligned to represent any object of the requested size. This is pretty ridiculous, because if you're allocating an object of size 32, the operator new function has absolutely no way of knowing if it should be aligned to 32/16/8/4/2/1 byte boundary, or some other value!

I've found that in practice, most implementations of operator new simply use min(16, size) as the alignment value, and assume that no object would ever require a larger alignment value... This means that objects that have been manually set to use an alignment value of 16 do typically still work ok with new.

However, when you manually set the alignment of a class to some larger value, say, 42 bytes, and then create it with new, these implementations are actually failing to obey the spec... but as you point out, there's no real way for them to be able to comply with the spec!

#27galop1n  Members

Posted 31 March 2013 - 08:23 AM

As i said in a previous post, in practice, new return a memory aligned on 8 ( because the standard require a alignment enough for long long, the largest standard type ) with 32 bits builds and align on 16 with 64 bits build ( not because of the C++ standard, but because of the x64 ABI ).

Of course, because we (programmers) do not like a random behavior, we override the things by ourself, so the allocator will be consistant on PC, X360 or PS3 ( + any other target ).

#28lipsryme  Members

Posted 31 March 2013 - 08:32 AM

What if I were to create a class with nothing but an _AABB inside which is aligned to 16 and store this class inside the std::vector, and then access the _AABB inside for the frustum cull, would that work ?

edit: probably not... so how would I have to work around this?

How about storing it inside a non aligned container, and then create a new _AABB on the stack inside the frustum cull from the non aligned container ? Or is that bad/too slow ? edit: also doesn't work

Edited by lipsryme, 31 March 2013 - 09:20 AM.

#29Hodgman  Moderators

Posted 31 March 2013 - 08:47 AM

std::vector simply has problems with aligned types, especially on MSVC.

Often the solution is to not use it, e.g. the Bullet physics middleware wrote a replacement called btAlignedObjectArray.

#30belfegor  Members

Posted 31 March 2013 - 08:55 AM

@Hodgman

What about making custom allocator for vector with _aligned_malloc/_aligned_free ?

I still don't understand this alignment thing, how does it work. Know any good tutorials for idiots?

Edited by belfegor, 31 March 2013 - 08:55 AM.

#31hellraizer  Members

Posted 31 March 2013 - 09:15 AM

@Hellraizer

On the plus side, the last piece of code in the post (4 boxes at a time) does it correctly

Now i am confused as in 4box version says:

// NOTE: This loop is identical to the CullAABBList_SSE_1() loop. Not shown in order to keep this snippet small.

where that part of code is that you mentioned.

What I meant is, that the calculations of (d+r) and (d-r) in the 4-box-at-a-time loop are correct.

When you substitute the comment you mentioned, with the loop from CullAABBList_SSE_1(), you have to fix the typo I mentioned, in order for it to be correct.

Hope that makes sense.

HellRaiZer

#32lipsryme  Members

Posted 31 March 2013 - 09:15 AM

Yea I'd like to know that too, how to make it aligned to 16 bytes...

I've found something like this: http://code.google.com/p/mastermind-strategy/source/browse/trunk/src/util/aligned_allocator.hpp?r=167

but I'm still getting a compiler error:

c:\program files (x86)\microsoft visual studio 10.0\vc\include\vector(870): error C2719: '_Val': formal parameter with __declspec(align('16')) won't be aligned

see reference to class template instantiation 'std::vector<_Ty,_Ax>' being compiled
1>          with
1>          [
1>              _Ty=_AABB,
1>              _Ax=aligned_allocator<_AABB,16>
1>          ]

Edited by lipsryme, 31 March 2013 - 09:20 AM.

#33belfegor  Members

Posted 31 March 2013 - 09:41 AM

@lipsryme

I get no error using vector (with default allocator), but i am not sure will it work all the time so i need to understand this alignment thing so i can fix possible issues.

My test code (DX9)

#define NUM_TEAPOTS 1024

struct Object
{
_AABB*              bbox;
unsigned int*       state;
D3DXVECTOR3         pos;
};

struct _AABB
{
D3DXVECTOR3 m_Center;
D3DXVECTOR3 m_Extent;
};

...
std::vector<Object>       vObjects;
std::vector<_AABB>        vAABBs;
std::vector<unsigned int> vStates;
...
vObjects.resize(NUM_TEAPOTS);
vAABBs.resize(NUM_TEAPOTS);
vStates.resize(NUM_TEAPOTS);
vOccData.resize(NUM_TEAPOTS);
...//fill data

update()
{
auto frustum = ExtractFrustumPlanes(&cam->getView(), &cam->getProjection());
CullAABBList_SSE_4(&vAABBs[0], vAABBs.size(), &frustum[0], &vStates[0]);

....
for(int i = 0; i < NUM_TEAPOTS; ++i)
{
if(*vObjects[i].state != 0)
draw();
}
}

#34lipsryme  Members

Posted 31 March 2013 - 10:32 AM

Well so I've found an interesting post here: http://stackoverflow.com/questions/9409591/self-contained-stl-compatible-implementation-of-stdvector/9414618#9414618

Which basically says that something like this should work:

#include <vector>

template <typename T>
struct wrapper : public T
{
wrapper() {}
wrapper(const T& rhs) : T(rhs) {}
};

struct __declspec(align(64)) S
{
float x, y, z, w;
};

int main()
{
std::vector< wrapper<S> > v;  // OK, no C2719 error
return 0;
}

And it does compile...but maybe my problem is elsewhere but my culling doesn't work (only outputs 0).

Plus I'm getting an access violation read as soon as I put in up to four AABBs.

here's my code:

void RendererContext::FrustumCull_AABB_SSE(std::vector<aligned_16_wrapper<_AABB>>* aabbList,
unsigned int numAABBs,
_Plane* frustumPlanes,
unsigned int* culledSceneIDs)
{
__declspec(align(16)) static const unsigned int absPlaneMask[4] = {0x7FFFFFFF, 0x7FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF};

__declspec(align(16)) _Plane absFrustumPlanes[6];
for(unsigned int iPlane = 0;iPlane < 6;++iPlane)
{
_mm_store_ps(&absFrustumPlanes[iPlane].nx, xmm_absFrustumPlane);
}

// Process 4 AABBs in each iteration...
unsigned int numIterations = numAABBs >> 2;
for(unsigned int iIter = 0;iIter < numIterations;++iIter)
{
_Vector3f centerWS[4];
centerWS[0].x = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 0].worldPosition.x + aabbList->at((iIter << 2) + 0).center.x;
centerWS[0].y = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 0].worldPosition.y + aabbList->at((iIter << 2) + 0).center.y;
centerWS[0].z = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 0].worldPosition.z + aabbList->at((iIter << 2) + 0).center.z;
centerWS[1].x = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 1].worldPosition.x + aabbList->at((iIter << 2) + 1).center.x;
centerWS[1].y = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 1].worldPosition.y + aabbList->at((iIter << 2) + 1).center.y;
centerWS[1].z = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 1].worldPosition.z + aabbList->at((iIter << 2) + 1).center.z;
centerWS[2].x = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 2].worldPosition.x + aabbList->at((iIter << 2) + 2).center.x;
centerWS[2].y = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 2].worldPosition.y + aabbList->at((iIter << 2) + 2).center.y;
centerWS[2].z = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 2].worldPosition.z + aabbList->at((iIter << 2) + 2).center.z;
centerWS[3].x = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 3].worldPosition.x + aabbList->at((iIter << 2) + 3).center.x;
centerWS[3].y = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 3].worldPosition.y + aabbList->at((iIter << 2) + 3).center.y;
centerWS[3].z = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 3].worldPosition.z + aabbList->at((iIter << 2) + 3).center.z;

_Vector3f extentWS[4];
extentWS[0].x = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 0].worldPosition.x + aabbList->at((iIter << 2) + 0).extent.x;
extentWS[0].y = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 0].worldPosition.y + aabbList->at((iIter << 2) + 0).extent.y;
extentWS[0].z = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 0].worldPosition.z + aabbList->at((iIter << 2) + 0).extent.z;
extentWS[1].x = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 1].worldPosition.x + aabbList->at((iIter << 2) + 1).extent.x;
extentWS[1].y = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 1].worldPosition.y + aabbList->at((iIter << 2) + 1).extent.y;
extentWS[1].z = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 1].worldPosition.z + aabbList->at((iIter << 2) + 1).extent.z;
extentWS[2].x = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 2].worldPosition.x + aabbList->at((iIter << 2) + 2).extent.x;
extentWS[2].y = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 2].worldPosition.y + aabbList->at((iIter << 2) + 2).extent.y;
extentWS[2].z = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 2].worldPosition.z + aabbList->at((iIter << 2) + 2).extent.z;
extentWS[3].x = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 3].worldPosition.x + aabbList->at((iIter << 2) + 3).extent.x;
extentWS[3].y = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 3].worldPosition.y + aabbList->at((iIter << 2) + 3).extent.y;
extentWS[3].z = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[(iIter << 2) + 3].worldPosition.z + aabbList->at((iIter << 2) + 3).extent.z;

// NOTE: Since the aabbList is 16-byte aligned, we can use aligned moves.
// Load the 4 Center/Extents pairs for the 4 AABBs.

// Shuffle the data in order to get all Xs, Ys, etc. in the same register.
__m128 xmm_cx0_cy0_cx1_cy1 = _mm_shuffle_ps(xmm_cx0_cy0_cz0_ex0, xmm_ey0_ez0_cx1_cy1, _MM_SHUFFLE(3, 2, 1, 0));
__m128 xmm_cx2_cy2_cx3_cy3 = _mm_shuffle_ps(xmm_cx2_cy2_cz2_ex2, xmm_ey2_ez2_cx3_cy3, _MM_SHUFFLE(3, 2, 1, 0));
__m128 xmm_aabbCenter0123_x = _mm_shuffle_ps(xmm_cx0_cy0_cx1_cy1, xmm_cx2_cy2_cx3_cy3, _MM_SHUFFLE(2, 0, 2, 0));
__m128 xmm_aabbCenter0123_y = _mm_shuffle_ps(xmm_cx0_cy0_cx1_cy1, xmm_cx2_cy2_cx3_cy3, _MM_SHUFFLE(3, 1, 3, 1));

__m128 xmm_cz0_ex0_cz1_ex1 = _mm_shuffle_ps(xmm_cx0_cy0_cz0_ex0, xmm_cz1_ex1_ey1_ez1, _MM_SHUFFLE(1, 0, 3, 2));
__m128 xmm_cz2_ex2_cz3_ex3 = _mm_shuffle_ps(xmm_cx2_cy2_cz2_ex2, xmm_cz3_ex3_ey3_ez3, _MM_SHUFFLE(1, 0, 3, 2));
__m128 xmm_aabbCenter0123_z = _mm_shuffle_ps(xmm_cz0_ex0_cz1_ex1, xmm_cz2_ex2_cz3_ex3, _MM_SHUFFLE(2, 0, 2, 0));
__m128 xmm_aabbExtent0123_x = _mm_shuffle_ps(xmm_cz0_ex0_cz1_ex1, xmm_cz2_ex2_cz3_ex3, _MM_SHUFFLE(3, 1, 3, 1));

__m128 xmm_ey0_ez0_ey1_ez1 = _mm_shuffle_ps(xmm_ey0_ez0_cx1_cy1, xmm_cz1_ex1_ey1_ez1, _MM_SHUFFLE(3, 2, 1, 0));
__m128 xmm_ey2_ez2_ey3_ez3 = _mm_shuffle_ps(xmm_ey2_ez2_cx3_cy3, xmm_cz3_ex3_ey3_ez3, _MM_SHUFFLE(3, 2, 1, 0));
__m128 xmm_aabbExtent0123_y = _mm_shuffle_ps(xmm_ey0_ez0_ey1_ez1, xmm_ey2_ez2_ey3_ez3, _MM_SHUFFLE(2, 0, 2, 0));
__m128 xmm_aabbExtent0123_z = _mm_shuffle_ps(xmm_ey0_ez0_ey1_ez1, xmm_ey2_ez2_ey3_ez3, _MM_SHUFFLE(3, 1, 3, 1));

unsigned int in_out_flag = 0x0F; // = 01111b Assume that all 4 boxes are inside the frustum.
unsigned int intersect_flag = 0x00; // = 00000b if intersect_flag[i] == 1 then this box intersects the frustum.
for(unsigned int iPlane = 0;iPlane < 6;++iPlane)
{
// Calculate d...
__m128 xmm_d = _mm_mul_ps(xmm_frustumPlane_Component, xmm_aabbCenter0123_x);

xmm_frustumPlane_Component = _mm_mul_ps(xmm_frustumPlane_Component, xmm_aabbCenter0123_y);

xmm_frustumPlane_Component = _mm_mul_ps(xmm_frustumPlane_Component, xmm_aabbCenter0123_z);

// Calculate r...
__m128 xmm_r = _mm_mul_ps(xmm_aabbExtent0123_x, xmm_frustumPlane_Component);

xmm_frustumPlane_Component = _mm_mul_ps(xmm_frustumPlane_Component, xmm_aabbExtent0123_y);

xmm_frustumPlane_Component = _mm_mul_ps(xmm_frustumPlane_Component, xmm_aabbExtent0123_z);

// Calculate d + r + frustumPlane.d

// Check which boxes are outside this plane (if any)...
// NOTE: At this point whichever component of the xmm_d_p_r reg is negative, the corresponding
// box is outside the frustum.
in_out_flag &= ~in_out_flag_curPlane; // NOTed the mask because it's 1 for each box which is outside the frustum, and in_out_flag holds the opposite.

// If all boxes have been marked as outside the frustum, stop checking the rest of the planes.
if(!in_out_flag)
break;

// Calculate d - r + frustumPlane.d
__m128 xmm_d_m_r = _mm_sub_ps(xmm_d, xmm_r);

// Check which boxes intersect the frustum...
intersect_flag |= intersect_flag_curPlane;
}

// Calculate the state of the AABB from the 2 flags.
// If the i-th bit from in_out_flag is 0, then the result will be 0 independent of value intersect_flag
// If the i-th bit from in_out_flag is 1, then the result will be either 1 or 2 depending on the intersect_flag.
culledSceneIDs[(iIter << 2) + 0] = ((in_out_flag & 0x00000001) >> 0) << ((intersect_flag & 0x00000001) >> 0);
culledSceneIDs[(iIter << 2) + 1] = ((in_out_flag & 0x00000002) >> 1) << ((intersect_flag & 0x00000002) >> 1);
culledSceneIDs[(iIter << 2) + 2] = ((in_out_flag & 0x00000004) >> 2) << ((intersect_flag & 0x00000004) >> 2);
culledSceneIDs[(iIter << 2) + 3] = ((in_out_flag & 0x00000008) >> 3) << ((intersect_flag & 0x00000008) >> 3);
}

// Process the rest of the AABBs one by one...
for(unsigned int iAABB = numIterations << 2; iAABB < numAABBs;++iAABB)
{
_Vector3f centerWS;
centerWS.x = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[iAABB].worldPosition.x + aabbList->at(iAABB).center.x;
centerWS.y = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[iAABB].worldPosition.y + aabbList->at(iAABB).center.y;
centerWS.z = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[iAABB].worldPosition.z + aabbList->at(iAABB).center.z;

_Vector3f extentWS;
extentWS.x = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[iAABB].worldPosition.x + aabbList->at(iAABB).extent.x;
extentWS.y = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[iAABB].worldPosition.y + aabbList->at(iAABB).extent.y;
extentWS.z = this->sceneContext->GetCurrentScene()->GetDesc()->primitives[iAABB].worldPosition.z + aabbList->at(iAABB).extent.z;

unsigned int result = 1; // Assume that the aabb will be Inside the frustum
for(unsigned int iPlane = 0;iPlane < 6;++iPlane)
{
__m128 xmm_d = _mm_mul_ss(xmm_aabbCenter_x, xmm_frustumPlane_Component);

__m128 xmm_r = _mm_mul_ss(xmm_aabbExtent_x, xmm_absFrustumPlane_Component);

__m128 xmm_d_m_r = _mm_add_ss(_mm_sub_ss(xmm_d, xmm_r), xmm_frustumPlane_d);

// Shuffle d_p_r and d_m_r in order to perform only one _mm_movmask_ps
__m128 xmm_d_p_r__d_m_r = _mm_shuffle_ps(xmm_d_p_r, xmm_d_m_r, _MM_SHUFFLE(0, 0, 0, 0));

// Bit 0 holds the sign of d + r and bit 2 holds the sign of d - r
{
result = 0; // Outside
break;
}
result = 2; // Intersect
}

culledSceneIDs[iAABB] = result;
}
}

#35hellraizer  Members

Posted 31 March 2013 - 11:53 AM

I believe the changes you made in the code is the problem. To be more exact:

The original code read the centers and extends of the 4 AABBs from an array with the following layout:

c0.x, c0.y, c0.z, e0.x, e0.y, e0.z, c1.x, c1.y, c1.z, e1.x, e1.y, e1.z, c2.x, c2.y, c2.z, e2.x, e2.y, e2.z, c3.x, c3.y, c3.z, e3.x, e3.y, e3.z, ...

When the following instructions are executed, the XMM registers hold the values mentioned in their name:

// NOTE: Since the aabbList is 16-byte aligned, we can use aligned moves.
// Load the 4 Center/Extents pairs for the 4 AABBs.
__m128 xmm_cx0_cy0_cz0_ex0 = _mm_load_ps(&aabbList[(iIter << 2) + 0].m_Center.x);
__m128 xmm_ey0_ez0_cx1_cy1 = _mm_load_ps(&aabbList[(iIter << 2) + 0].m_Extent.y);
__m128 xmm_cz1_ex1_ey1_ez1 = _mm_load_ps(&aabbList[(iIter << 2) + 1].m_Center.z);
__m128 xmm_cx2_cy2_cz2_ex2 = _mm_load_ps(&aabbList[(iIter << 2) + 2].m_Center.x);
__m128 xmm_ey2_ez2_cx3_cy3 = _mm_load_ps(&aabbList[(iIter << 2) + 2].m_Extent.y);
__m128 xmm_cz3_ex3_ey3_ez3 = _mm_load_ps(&aabbList[(iIter << 2) + 3].m_Center.z);

If we assume that the initial aabbList array is 16-byte aligned, all loads are 16-byte aligned and the instructions are executed correctly. This is the reason we are loading the XMM regs with those specific array offsets.

On the other hand, your code doesn't do the same thing. It just stores the AABBs on the stack and the layout isn't the one expected by the code. The best case scenario is that your layout is:

c0.x, c0.y, c0.z, c1.x, c1.y, c1.z, c2.x, c2.y, c2.z, c3.x, c3.y, c3.z, e0.x, e0.y, e0.z, e1.x, e1.y, e1.z, e2.x, e2.y, e2.z, e3.x, e3.y, e3.z

but:

1) I think you can't be 100% sure about that (e.g. that the compiler will place the centers before the extends)

2) It's not guaranteed to be 16-byte aligned.

3) Most importantly, it's not what the code expects.

If you have to read the AABBs the way you did (one element at a time) I would suggest something like this:

__declspec(align(16)) _Vector3f aabbData[8];

aabbData[0].x = ... // center0.x
aabbData[0].y = ... // center0.y
aabbData[0].z = ... // center0.z
aabbData[1].x = ... // extend0.x
...

And then use this array to load the XMM regs as in the original code snippet.

PS. If you try to understand what the code does with those SSE instructions, you might be able to "optimize" it and get rid of the loads and shuffles completely. This is in case you continue to read the AABB data the way you do it.

Edited by hellraizer, 31 March 2013 - 11:56 AM.

HellRaiZer

#36lipsryme  Members

Posted 31 March 2013 - 01:20 PM

But how is it that my array is not aligned the same way ?

_AABB is defined as

struct _Vector3f
{
float x, y, z;
};

struct _AABB
{
_Vector3f center;
_Vector3f extent;
};

struct __declspec(align(16)) _Plane
{
float nx, ny, nz, d;
};

wouldn't that have the same alignment as it's supposed to ?

The following code does work (the culling works) but as soon as I put in a fourth element it crashes with an access violation...

crashing at this line:

__m128 xmm_cx0_cy0_cz0_ex0 = _mm_load_ps(&aabbList[(iIter << 2) + 0].center.x);

Here's the full code:

void RendererContext::FrustumCull_AABB_SSE(_AABB* aabbList,
unsigned int numAABBs,
_Plane* frustumPlanes,
unsigned int* culledSceneIDs)
{
__declspec(align(16)) static const unsigned int absPlaneMask[4] = {0x7FFFFFFF, 0x7FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF};

__declspec(align(16)) _Plane absFrustumPlanes[6];
for(unsigned int iPlane = 0;iPlane < 6;++iPlane)
{
_mm_store_ps(&absFrustumPlanes[iPlane].nx, xmm_absFrustumPlane);
}

// Process 4 AABBs in each iteration...
unsigned int numIterations = numAABBs >> 2;
for(unsigned int iIter = 0;iIter < numIterations;++iIter)
{
// NOTE: Since the aabbList is 16-byte aligned, we can use aligned moves.
// Load the 4 Center/Extents pairs for the 4 AABBs.
__m128 xmm_cx0_cy0_cz0_ex0 = _mm_load_ps(&aabbList[(iIter << 2) + 0].center.x);
__m128 xmm_ey0_ez0_cx1_cy1 = _mm_load_ps(&aabbList[(iIter << 2) + 0].extent.y);
__m128 xmm_cz1_ex1_ey1_ez1 = _mm_load_ps(&aabbList[(iIter << 2) + 1].center.z);
__m128 xmm_cx2_cy2_cz2_ex2 = _mm_load_ps(&aabbList[(iIter << 2) + 2].center.x);
__m128 xmm_ey2_ez2_cx3_cy3 = _mm_load_ps(&aabbList[(iIter << 2) + 2].extent.y);
__m128 xmm_cz3_ex3_ey3_ez3 = _mm_load_ps(&aabbList[(iIter << 2) + 3].center.z);

// Shuffle the data in order to get all Xs, Ys, etc. in the same register.
__m128 xmm_cx0_cy0_cx1_cy1 = _mm_shuffle_ps(xmm_cx0_cy0_cz0_ex0, xmm_ey0_ez0_cx1_cy1, _MM_SHUFFLE(3, 2, 1, 0));
__m128 xmm_cx2_cy2_cx3_cy3 = _mm_shuffle_ps(xmm_cx2_cy2_cz2_ex2, xmm_ey2_ez2_cx3_cy3, _MM_SHUFFLE(3, 2, 1, 0));
__m128 xmm_aabbCenter0123_x = _mm_shuffle_ps(xmm_cx0_cy0_cx1_cy1, xmm_cx2_cy2_cx3_cy3, _MM_SHUFFLE(2, 0, 2, 0));
__m128 xmm_aabbCenter0123_y = _mm_shuffle_ps(xmm_cx0_cy0_cx1_cy1, xmm_cx2_cy2_cx3_cy3, _MM_SHUFFLE(3, 1, 3, 1));

__m128 xmm_cz0_ex0_cz1_ex1 = _mm_shuffle_ps(xmm_cx0_cy0_cz0_ex0, xmm_cz1_ex1_ey1_ez1, _MM_SHUFFLE(1, 0, 3, 2));
__m128 xmm_cz2_ex2_cz3_ex3 = _mm_shuffle_ps(xmm_cx2_cy2_cz2_ex2, xmm_cz3_ex3_ey3_ez3, _MM_SHUFFLE(1, 0, 3, 2));
__m128 xmm_aabbCenter0123_z = _mm_shuffle_ps(xmm_cz0_ex0_cz1_ex1, xmm_cz2_ex2_cz3_ex3, _MM_SHUFFLE(2, 0, 2, 0));
__m128 xmm_aabbExtent0123_x = _mm_shuffle_ps(xmm_cz0_ex0_cz1_ex1, xmm_cz2_ex2_cz3_ex3, _MM_SHUFFLE(3, 1, 3, 1));

__m128 xmm_ey0_ez0_ey1_ez1 = _mm_shuffle_ps(xmm_ey0_ez0_cx1_cy1, xmm_cz1_ex1_ey1_ez1, _MM_SHUFFLE(3, 2, 1, 0));
__m128 xmm_ey2_ez2_ey3_ez3 = _mm_shuffle_ps(xmm_ey2_ez2_cx3_cy3, xmm_cz3_ex3_ey3_ez3, _MM_SHUFFLE(3, 2, 1, 0));
__m128 xmm_aabbExtent0123_y = _mm_shuffle_ps(xmm_ey0_ez0_ey1_ez1, xmm_ey2_ez2_ey3_ez3, _MM_SHUFFLE(2, 0, 2, 0));
__m128 xmm_aabbExtent0123_z = _mm_shuffle_ps(xmm_ey0_ez0_ey1_ez1, xmm_ey2_ez2_ey3_ez3, _MM_SHUFFLE(3, 1, 3, 1));

unsigned int in_out_flag = 0x0F; // = 01111b Assume that all 4 boxes are inside the frustum.
unsigned int intersect_flag = 0x00; // = 00000b if intersect_flag[i] == 1 then this box intersects the frustum.
for(unsigned int iPlane = 0;iPlane < 6;++iPlane)
{
// Calculate d...
__m128 xmm_d = _mm_mul_ps(xmm_frustumPlane_Component, xmm_aabbCenter0123_x);

xmm_frustumPlane_Component = _mm_mul_ps(xmm_frustumPlane_Component, xmm_aabbCenter0123_y);

xmm_frustumPlane_Component = _mm_mul_ps(xmm_frustumPlane_Component, xmm_aabbCenter0123_z);

// Calculate r...
__m128 xmm_r = _mm_mul_ps(xmm_aabbExtent0123_x, xmm_frustumPlane_Component);

xmm_frustumPlane_Component = _mm_mul_ps(xmm_frustumPlane_Component, xmm_aabbExtent0123_y);

xmm_frustumPlane_Component = _mm_mul_ps(xmm_frustumPlane_Component, xmm_aabbExtent0123_z);

// Calculate d + r + frustumPlane.d

// Check which boxes are outside this plane (if any)...
// NOTE: At this point whichever component of the xmm_d_p_r reg is negative, the corresponding
// box is outside the frustum.
in_out_flag &= ~in_out_flag_curPlane; // NOTed the mask because it's 1 for each box which is outside the frustum, and in_out_flag holds the opposite.

// If all boxes have been marked as outside the frustum, stop checking the rest of the planes.
if(!in_out_flag)
break;

// Calculate d - r + frustumPlane.d
__m128 xmm_d_m_r = _mm_sub_ps(xmm_d, xmm_r);

// Check which boxes intersect the frustum...
intersect_flag |= intersect_flag_curPlane;
}

// Calculate the state of the AABB from the 2 flags.
// If the i-th bit from in_out_flag is 0, then the result will be 0 independent of value intersect_flag
// If the i-th bit from in_out_flag is 1, then the result will be either 1 or 2 depending on the intersect_flag.
culledSceneIDs[(iIter << 2) + 0] = ((in_out_flag & 0x00000001) >> 0) << ((intersect_flag & 0x00000001) >> 0);
culledSceneIDs[(iIter << 2) + 1] = ((in_out_flag & 0x00000002) >> 1) << ((intersect_flag & 0x00000002) >> 1);
culledSceneIDs[(iIter << 2) + 2] = ((in_out_flag & 0x00000004) >> 2) << ((intersect_flag & 0x00000004) >> 2);
culledSceneIDs[(iIter << 2) + 3] = ((in_out_flag & 0x00000008) >> 3) << ((intersect_flag & 0x00000008) >> 3);
}

// Process the rest of the AABBs one by one...
for(unsigned int iAABB = numIterations << 2; iAABB < numAABBs;++iAABB)
{

unsigned int result = 1; // Assume that the aabb will be Inside the frustum
for(unsigned int iPlane = 0;iPlane < 6;++iPlane)
{
__m128 xmm_d = _mm_mul_ss(xmm_aabbCenter_x, xmm_frustumPlane_Component);

__m128 xmm_r = _mm_mul_ss(xmm_aabbExtent_x, xmm_absFrustumPlane_Component);

// Shuffle d_p_r and d_m_r in order to perform only one _mm_movmask_ps
__m128 xmm_d_p_r__d_m_r = _mm_shuffle_ps(xmm_d_p_r, xmm_d_m_r, _MM_SHUFFLE(0, 0, 0, 0));

// Bit 0 holds the sign of d + r and bit 2 holds the sign of d - r
{
result = 0; // Outside
break;
}
result = 2; // Intersect
}

culledSceneIDs[iAABB] = result;
}
}

called like this:

	// Get View Frustum planes
_Plane frustumPlanes[6];
this->perspectiveCamera->GetFrustumPlanes(frustumPlanes);

std::vector< wrapper<_AABB> > aabbs = this->contentManager->GetAABBData();
unsigned int aabbSize = aabbs.size();
std::vector<unsigned int> culledSceneEntityIDs;
culledSceneEntityIDs.reserve(aabbSize);
for(size_t i = 0; i < aabbSize; ++i)
{
culledSceneEntityIDs.push_back(999999);
}
if(aabbSize > 0)
{
this->FrustumCull_AABB_SSE(&aabbs[0], aabbSize, frustumPlanes, &culledSceneEntityIDs[0]);
}

wrapper being:

template <typename T>
struct wrapper : public T
{
wrapper() {}
wrapper(const T& rhs) : T(rhs) {}
};

Now I tried checking its size with:

unsigned int TEST = sizeof(aabbs[0]);
unsigned int TEST2 = sizeof(_Vector3f);

and it returns 24, so doesn't that mean it is correctly aligned. So the first vector center would be 4 bytes each with extent.x being the fourth in the first 16 bytes, right ?

Same result checking size inside the loop before the line that makes it crash.

unsigned int alignmentTest = sizeof(aabbList[(iIter << 2) + 0]); // RESULT IS 24

ok so this post is getting ridiculously long already xD but why does this fail ?

	_AABB test[2];
test[0].center.x = 2.0f;
test[0].center.y = 1.0f;
test[0].center.z = 0.0f;
test[0].extent.x = 0.1f;
test[0].extent.y = 0.5f;
test[0].extent.z = 1.0f;
test[1].center.x = 2.0f;
test[1].center.y = 1.0f;
test[1].center.z = 0.0f;
test[1].extent.x = 0.1f;
test[1].extent.y = 0.5f;
test[1].extent.z = 1.0f;

same error as inside the frustum cull. I feel the error is somewhere else here...

Edited by lipsryme, 31 March 2013 - 03:03 PM.

#37Hodgman  Moderators

Posted 31 March 2013 - 09:13 PM

but I'm still getting a compiler error:
c:\program files (x86)\microsoft visual studio 10.0\vc\include\vector(870): error C2719: '_Val': formal parameter with __declspec(align('16')) won't be aligned

This is a bug in visual studio's implementation of the standard containers -- the resize method takes a 'T' argument by value, and MSVC does not support pass-by-value with declspec-align'ed types... std::vector simply doesn't compile under MSVC when it's used with one of these types

Hence the alternative versions, like the Bullet version I posted earlier (which you can steal the source for, and use it by itself without Bullet) or other projects, like RDESTL.

#38hellraizer  Members

Posted 01 April 2013 - 02:27 AM

@lipsryme

If you get an access violation as soon as you add a 4th aabb in the list it means that your aabbList array isn't 16-byte aligned. Two choices here:

1) Explicitly allocate the aabbList array to be 16-byte aligned (e.g. using _aligned_malloc()) or

Hope that helps.

PS. To test if an array address is 16-byte aligned you can use one of the functions found here: http://stackoverflow.com/a/1898487/2136504

E.g. Check &aabbList[(iIter << 2) + 0].center.x and if it returns true but the _mm_load_ps() fails then something else is wrong with your array.

Edited by hellraizer, 01 April 2013 - 02:36 AM.

HellRaiZer

#39lipsryme  Members

Posted 01 April 2013 - 03:39 AM

You're right it does return false. I just tried it using an unaligned call and it does seem to work.

What do you think I should do about translating the center vector to my world space?

Should I do that separately inside the update loop for every AABB in my scene ?

And I'm going to try to steal some of the source code from that physics sdk (bullet).

Edited by lipsryme, 01 April 2013 - 03:39 AM.

#40hellraizer  Members

Posted 01 April 2013 - 04:34 AM

If the AABBs correspond to static geometry, translating them to world space every frame is an overkill. You should do it once at start up.

If it's about dynamic geometry, then it shouldn't be that simple when rotation is involved. If your objects rotate, you should calculate the AABB from the OBB defined by the original AABB and the object's transformation, in case you want to use the same code for all your objects. Otherwise you can find/write another function which culls OBBs against the frustum.

In case you go about the OBB route, it might be faster to just check the bounding sphere (which isn't affected by rotation) against the frustum, at the expense of rendering a few more objects (bounding spheres tend to be larger that AABBs depending on the object they enclose).

Edited by hellraizer, 01 April 2013 - 04:35 AM.

HellRaiZer

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.


text:
×

# Physical Chemistry - Electrochemistry - 2

Before reading this post, please read the first post here : Physical Chemistry - Electrochemistry - 1

STANDARD HYDROGEN ELECTRODE
A standard hydrogen electrode is prepared by dipping a Platinum strip in $$1M HCl$$ around which $$H_2$$ gas at $$1$$ atm pressure is bubbled in an inverted test tube. At $$25^oC$$, its standard reduction potential is defined to be zero.

STANDARD ELECTRODE POTENTIALS
As discussed in the previous post, the potential of any electrode is the potential difference between it and the electrolyte surrounding the electrode.
However, this potential depends upon the nature of the metal, concentration of the metallic ions in solution and the temperature of the solution.

Hence, again, we have to define a standard.
When the ions are at unit activity and the temperature is $$25^oC$$ ($$298K$$), the potential difference is called a Standard Electrode Potential ($$E_o$$).

Now,
the potential of a single electrode cannot be determined, but the potential difference between two electrodes can be accurately measured.
By convention, the electrode potential of S.H.E has been assigned a value of zero Volts.

POSITIVE(+) AND NEGATIVE(-) POTENTIALS
$$\bullet$$ If, on combining an electrode $$A$$ with the S.H.E, a reduction process (gain of electrons) occurs at the electrode, the potential of the electrode is called as reduction potential.
It is given a "+" sign as reduction potential or a "-" sign as oxidation potential.

$$\bullet$$ On the other hand, if, on combining an electrode $$B$$ with the S.H.E, an oxidation process (loss of electrons) occurs at $$B$$, the electrode potential (half-cell potential) is called as the oxidation potential.
It is given a "+" sign as oxidation potential or a "-" sign as reduction potential.

Thus, in short,
at Standard conditions,
Oxidation Potential for any half cell $$=$$ $$-$$(Reduction Potential)
Reduction Potential for any half cell $$=$$ $$-$$(Oxidation Potential)

In the next post, we shall discuss, the experimentally determined Electrochemical Series, and how it is used to determine the EMF of any cell.

Read the next post here : Physical Chemistry - Electrochemistry - 3

Note by Anish Puthuraya
3 years, 1 month ago

Sort by:

Why they use Hydrogen electrode as a standard? I thought gases is harder to handle than solid? · 3 years, 1 month ago

It is generally done to form a good standard basis. This kind of stuff is done a lot, especially on linear algebra and it makes it somewhat "elegant". So this is something that we kinda agreed upon. To make a reference electrode because as this note says, we can't determine the potential of a single electrode... And really, it just forms a sort of like a baseline originating historically. Like "building" electrochemistry from scratch. I guess, think of it like 360$$^\circ$$ is one circle, why 360? Because of something people agreed upon years before (Babylonians had base 60 and ~360 days per year). x'D Hopefully, that's satisfying. I probably might've even interpreted your question incorrectly, but anyways, that's all I can say. ^^ · 3 years, 1 month ago

Well said. · 3 years, 1 month ago

Well, Hydrogen is the first element, so I guess it is fair to choose it as a standard. I cant think of any other reason. If you don't choose Hydrogen as standard, what else would you choose? I dont know. · 3 years, 1 month ago

×


text:
# Why does the Dirac equation reduce the fermionic degree of freedom by half

We know that in 4D a Dirac spinor has 4 complex components or 8 real components meaning 8 real off shell degrees of freedom (please correct me if I say something wrong here). When we go on-shell i.e impose Dirac equation on the spinor, half of them are killed thereby leaving only 4 real on-shell degrees of freedom. I want to see explicitly why is the Dirac equation killing half of the off-shell degrees of freedom.

• Have you tried solving the Dirac equation? Maybe you can express some components in terms of others? – innisfree May 11 '15 at 19:11
• aahh of course!! you are right! Thanks!! So by the same argument this should hold true in any number of dimensions right? My goal is to show is in any dimension – Orbifold May 11 '15 at 19:19
• the reduction happens because the Dirac equation is first-order; $\pi_\psi= dL/d\psi = i\psi^\dagger$, for example (it won't happen for a scalar) I think in any number of dimensions the dof will be halved, but idk for sure – innisfree May 11 '15 at 19:23
• @innisfree I can see how it explicitly works out in the answer posted below but I can't seem to understand your argument exactly. Can you elaborate a bit as to why the equation of motion being of the first order implies halving of the number of degrees of freedom? If we take a free theory of (massive) complex vector bosons then also the same thing would happen? I seem to think so because $\pi_\psi\propto \psi^\dagger$ would even hold for free (massive) complex vector bosons, right? Thank you! :-) – Dvij Mankad May 2 '19 at 14:24
• I suppose some gauge invariance would need to be sacrificed for having a massive complex vector boson theory but I think that is irrelevant here, right? – Dvij Mankad May 2 '19 at 14:26

Dirac equation $\left( i \gamma^\mu \partial_\mu - m\right) \psi=0$ gives in momentum space $$\left(\gamma^\mu p_\mu - m\right)\psi(p)=0$$ which becomes in the rest frame $p^\mu= (m,\vec{0})$ $$\left(\gamma^0 - 1\right)\psi(p)=0$$ Now you can show that $\gamma^0 - 1$ is a projection operator of rank $D/2$, or more explicitly work in the Dirac representation where $$\gamma^0 = \left( \begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array}\right)\Rightarrow \gamma^0 - 1\propto \left( \begin{array}{cc} 0 & 0 \\ 0 & 1 \end{array}\right)$$ Then you can see how in the Dirac representation and the $CoM$ frame, the dirac equation just sets the lower half of the spinor's components to zero. Then since the counting of $DoF$ is independent of both the Lorentz frame and the Clifford algebra representation you get the desired result.


text:
## Gibb's Free energy

$\Delta G^{\circ}= \Delta H^{\circ} - T \Delta S^{\circ}$

$\Delta G^{\circ}= -RT\ln K$

$\Delta G^{\circ}= \sum \Delta G_{f}^{\circ}(products) - \sum \Delta G_{f}^{\circ}(reactants)$

marcus lin 1E
Posts: 54
Joined: Fri Sep 28, 2018 12:28 am

### Gibb's Free energy

When is deltaG negative and positive? What's the significance?

Sean Reyes 1J
Posts: 67
Joined: Fri Sep 28, 2018 12:24 am

### Re: Gibb's Free energy

When delta G is negative, this signifies that a reaction will proceed spontaneously. If delta G is postive, this means that the reverse reaction will be spontaneous and the forward reaction will be non spontaneous. Delta G is guaranteed to be negative when delta H is negative and delta S is positive. If it’s the reverse (delta S is negative and delta H is positive), then the value of delta G will be positive. When the signs of delta H and delta S are the same, then the sign of delta G will be dependent on the temperature

Sarah Zhao 4C
Posts: 64
Joined: Fri Sep 28, 2018 12:28 am

### Re: Gibb's Free energy

Use the Gibb's Free Energy equation to determine spontaneity. While is is usually true that delta G follows the sign for delta H, please do not use this as a rule of thumb.

almaochoa2D
Posts: 67
Joined: Fri Sep 28, 2018 12:23 am

### Re: Gibb's Free energy

Delta G is spontaneity. From what I understand is if delta G is spontaneous it is also endothermic and if delta G is negative it is not spontaneous and it is exothermic.

505211599
Posts: 60
Joined: Fri Sep 28, 2018 12:28 am

### Re: Gibb's Free energy

delta g represents the spontaneity, so if it is negative it will be spontaneous and if positive it will be non-spontaneous.

### Who is online

Users browsing this forum: No registered users and 0 guests


text:
# Single node/leaf of binary tree

#### Ryan$Joined Dec 14, 2018 178 Hi, I'm just wondering and not finding the reason why if we have a tree with single node or actually if we have a leaf node of binary tree so it's by default satisfy the min/max heap property .. why?! the min/max heap property is claiming that the root of the tree must be greater/smaller from its children respectively to max/min heap. there's no declaration if there's no children then what to decide.. as a result how we actually make a decision that if there's a root/node without children then we are saying its already satisfy min/max heap property?! Maybe I'm not understanding the definition of min/max heap property and when its called min/max heap property. thanks ! Last edited: #### WBahn Joined Mar 31, 2012 26,398 The definition is all you need. Let's focus on just a minheap. A minheap requires that, for every node in the tree, the subtree rooted at that node must be no larger than any of the other nodes in that subtree. If there are any nodes in the subtree that are smaller than the root node, then the subtree (and the tree as a whole) fails to satisfy the heap criterion. If you have a tree with a single node, are there any other nodes in the tree that are smaller than the root node? If not, then it satisfies the heap criterion. Thread Starter #### Ryan$

Joined Dec 14, 2018
178
The definition is all you need.

Let's focus on just a minheap. A minheap requires that, for every node in the tree, the subtree rooted at that node must be no larger than any of the other nodes in that subtree.

If there are any nodes in the subtree that are smaller than the root node, then the subtree (and the tree as a whole) fails to satisfy the heap criterion.

If you have a tree with a single node, are there any other nodes in the tree that are smaller than the root node?

If not, then it satisfies the heap criterion.
I appreciate you very much, and let me explain what I was know about the definition of min heap: to satisfy min heap property must occur: the children of the root is smaller than the root itself(parents) , how could I conclude from this the leaf is satisfy in trivially the min heap property?! here I'm stuck in .. because I realized the definition of min heap in wrong way I stuck in!

thanks in advance, convinced me very much!

#### WBahn

Joined Mar 31, 2012
26,398
I appreciate you very much, and let me explain what I was know about the definition of min heap: to satisfy min heap property must occur: the children of the root is smaller than the root itself(parents) ,
You've got two problems here. A minheap gets it's name because the minimum value of all the data stored in the structure is at the root node. What you are attempting to describe is a max heap. Second, even adjusting for this mistake, this is not the definition and this definition will lead to problems. The definition is that the root must be no larger than any of its children, or equivalently, no child can be smaller than its parent. Your definition, that the root must be smaller, means that it is impossible to put two data values that are equal into a heap because you will have someplace were a parent is equal to its child, which would violate a definition that said it had to be smaller.

how could I conclude from this the leaf is satisfy in trivially the min heap property?! here I'm stuck in .. because I realized the definition of min heap in wrong way I stuck in!

thanks in advance, convinced me very much!
If I was accepting applications for some dangerous assignment and had a rule that only people that do not have children under the age of ten will be accepted, could someone that doesn't have any children apply without violating the rule? Of course! Someone that doesn't have ANY children trivially satisfies the requirement of not having children under the age of ten.

It's the same thing here. If the requirement for a minheap is that no node has any children that have a smaller value than the parent, then a node that has no children at all trivially satisfies that requirement because it is IMPOSSIBLE for a node with no children to have a child that has a smaller value than it does!


text:
# Crypto checkpoint 3

### Problem

Where are Alice and Bob planing to meet after the heist?
start color red, F, o, r, space, s, e, c, u, r, i, t, y, space, r, e, a, s, o, n, s, end color red convert your answer into a number using this Polybius square:
For Example:
hi = 2223
bye = 125115
23 = 5455


text:
## International System of Units and Common Metrology Terms

Metrology is a science based on comparisons. A measurement of voltage, length, pressure or force must be compared to a well known and defined value, in order to produce a valid result. When performing comparisons, the existence of references for all measurement quantities is necessary. These references and their derived quantities are defined in the International System of Units (SI).

The International System of Units (SI) is the foundation of modern metrology. The abbreviation SI is taken from the French name, Système International d’Unités, and is actually the modern form of the metric system. SI was established in 1960 by the General Conference of Weights and Measures.

The SI units are used internationally and they are the basis of all modern measurements. There are also Customary units (inch, foot, pound, and yard) which are defined in accordance with the SI units. For example, an inch is defined as being2,54 centimetresin length.

National Laboratories perform experiments to realize the SI units as defined. Some of these experiments lead to a representation of the unit. For example the representation of the “Volt” unit is realized with a Josephson array.

The System of Units

The SI consists of 29 units:

•  7 Base Units
• 2 Supplementary Units
• 20 Derivative Units

Base Units

The seven base units, from which all other measurement parameters are traced, are: length, mass, time, electric current, thermodynamic temperature, luminous intensity and amount of substance.

Length

The meter (m) is the SI unit of measurement for length. It is defined as the distance travelled by light in vacuum during a time interval of 1/299792458 second.

Mass

The kilogram (kg) is the SI unit of measurement for mass. Kg is the only unit which is still defined as a physical artefact, the mass of the International Prototype Kilogram which is a cylinder of platinum iridium alloy kept by BIPM inParis,France.

Time

The SI unit of time is the second (s). It is defined as the duration of 9 192 631 770 cycles of radiation corresponding to the transition between the two hyperfine levels of the ground state of the caesium 133 atom.

Electric Current

The SI unit of measurement for electric current is the ampere (A). It is defined as the constant electric current producing a force of 2×10-7 newtons per meter of length, if maintained in two straight parallel conductors of infinite length, one meter apart in vacuum.

Thermodynamic Temperature

The Kelvin (K) is the SI unit of measurement for thermodynamic temperature. It is defined as the 1/273.16 of the thermodynamic temperature of the triple point of water.

Luminous Intensity

The Candela (cd) is the SI unit of measurement for luminous intensity. It is defined as the luminous intensity in a given direction of a source that emits monochromatic radiation at a frequency of 540×1012 Hertz, with a radiant intensity in that direction of 1/683 Watts per steradian.

Amount of Substance

The SI unit of measurement for an amount of substance is the mole (mol). It is defined as the amount of substance of a system that contains as many elementary entities as there are atoms in0.012 kilogram of carbon 12.

Supplementary Units

Plane angles and solid angles are the two supplementary units in the SI system. They are dimensionless quantities and are defined as follows:

Plane Angles

The SI unit of measurement for plane angles is the radian (rad). It is defined as a plane angle with vertex at the centre of a circle that is subtended by an arc equal in length to the radius.

Solid Angles

The steradian (sr) is the SI unit of measurement for solid angles. It is defined as the solid angle with vertex at the centre of a sphere that is subtended by an area of a spherical circle equal to that of a square with sides equal in the length to the radius.

Derived Units

There are 20 derived units which are obtained by combining the seven SI base units with each other and with other derived or supplementary units. The table below presents the derived units and their relation to the base units. As time goes on, more derived units may be added in order to cover the needs of science.

Parameter Unit Value In Terms of Si Base Units Value In Terms of Other SI Units
Frequency Hertz (Hz) $\frac{1}{s}$
Force Newton (N) $\frac{kg-m}{s^2}$
Pressure Pascal (Pa) $\frac{kg}{m-s^2}$ $\frac{N}{m^2}$
Work or Energy Joule (J) $\frac{kg-m^2}{s^2}$ $n-m$
Power Watt (W) $\frac{kg-m^2}{s^3}$ $j-s$
Electrical Potential Volt (V) $\frac{kg-m^2}{s^3-A}$ $W-A$
Electrical Resistance Ohm (Ω) $\frac{kg-m^2}{s^3-A^2}$ $V-A$
Quantity of Charge Coulomb (C) $\frac{s-A}$
Electrical Capacitance Farad (F) $\frac{s^4-A^2}{kg-m^2}$ $C-V$
Conductance Siemens (S) $\frac{s^3-A^2}{kg-m^2}$ $A-V$
Magnetic Flux Weber (Wb) $\frac{kg-m^2}{s^2-A}$ $V-S$
Magnetic Flux Density Tesla (T) $\frac{kg}{s^2-A}$ $\frac{Wb}{m^2}$
Inductance Henry (H) $\frac{kg-m^2}{s^2-A^2}$ $Wb-A$
Temperature Celsius Degrees Celsius (°C) $K$
Luminous Flux Lumen (lm) $cd$ $cd-sr$
Illuminance Lux (lx) $cd-m^2$ $lm-m^2$
Radioactivity Becquerel (Bq) $1-s$
Absorbed Dose Gray (Gy) $\frac{m-s^2}{s^2}$ $\frac{J}{kg}$
Equivalent Dose Sievert (Sv) $\frac{m^2}{s^2}$ $\frac{j}{kg}$
Catalytic Activity Katal (kat) $\frac{mol}{s}$

Common Metrology Terms

Everybody who is involved in metrology, from calibration technicians to customers in search of the suitable calibration laboratory, must have a good knowledge of the most commonly used metrology terms. Some of these terms are defined below in simple words.

• Accuracy (Measurement Accuracy): A number which indicates the closeness of a measured value to the true value.
• Adjustment: An operation that is performed in order to initially establish or restore at a later point an instrument’s specified performance level.
• Calibration: A set of operations performed in accordance with a definite and documented procedure that compares the measurements performed by an instrument, to those made by a more accurate instrument or standard, for the purpose of detecting and reporting or eliminating by adjustment any errors in the instrument tested.
• Calibration Interval: A specified or designated period of time between calibrations of an instrument. During this interval the instrument should remain within specified performance levels.
• Calibration Label: A label affixed to an instrument to show its calibration status. Usually the label contains the instrument’s identification, the person who performed the last calibration, the date of the last calibration and the date of the next calibration.
• Calibration Laboratory: A work space equipped with the appropriate test instruments, controlled environment, trained personnel and documented calibration procedures. Cal Labs perform many routine calibrations.
• Calibration Report: A document which describes the calibration, provides the calibration results, mentions the calibration responsible, the conditions of measurements, the equipment used, the procedure of measurement and the measurement uncertainties.
• Error (Measurement Error): The difference between the measured value and the true value of a measurement. The actual value of an error can never be known exactly, only estimated.
• Measurement: A set of operations performed on a physical object or system according to an established, documented procedure, in order to determine the value of the object or system.
• Metrology: The science of measurement. It contains everything that has to do with measurement: Designing, performing, documenting the measurement, evaluating and analyzing the results, calculating the measurement uncertainties.
• Seal (Tamper Seal): A seal of appropriate design and material that is attached to an instrument to clearly indicate tampering. The purpose is to ensure warranty of calibration.
• Specification: A documented presentation of the parameters, including accuracy or uncertainty, describing the capability of an instrument.
• Standard (1) (Measurement Standard): An object, artifact, instrument, system or experiment that stores, represents or provides a physical quantity which serves as the basis for measuring the quantity.
• Standard (2) (Paper Standard): A document describing the operations and processes that must be performed in order for a particular goal to be achieved. A well known standard is ISO 17025 which describes the requirements for the competence of testing and calibration laboratories.
• Tolerance: The limits of the range of values that apply to a properly functioning measuring instrument. This term is strongly connected to the accuracy term.
• Traceability: A calibration is traceable when each instrument and standard, in hierarchy stretching back to the national standards, was itself properly calibrated and the results properly documented. The documentation provides the information needed to prove that all calibrations in the calibration chain were properly performed.
• Uncertainty: An estimate of the range of values, usually centered on the measurement value, which contains the true value of a measured quantity, with a stated probability.
• Verification: The set of operations that assures that specified requirements have been met, or leads to a decision to perform adjustments, repair, downgrade performance or remove from use.
• ppm (parts per million): a convenient way if expressing small fraction and percentages. For example, 15 ppm = 15 / 1000000 or 0.000015 or 0.0015%.
• Unit Under Test (UUT): The instrument that is being tested / calibrated.

Written by Sofia


text:
# Number of Galois conjugates

Let $L/\mathbb Q$ be a (finite) Galois extension of degree $n$ with Galois group $\Gamma$. We know that there is a primitive element or generator $\alpha$ of this extension.

My question:

Is the number of Galois conjugates of $\alpha$ (i.e. the length of the orbit of $\alpha$ under $\Gamma$) smaller than or equal to the order of the Galois group?

And under which conditions are they the same?

• If $\alpha$ is a generator, then it necessarily has $n$ distinct conjugates. For if $\alpha$ is fixed by an element $\sigma\in\Gamma$ then $\alpha$ belongs to a proper subfield, namely $\operatorname{Inv}(\langle\sigma\rangle)$, and hence cannot be a generator. – Jyrki Lahtonen Jun 22 '15 at 15:56

What does the Orbit-Stabilizer theorem tell us? If $\Gamma = \textrm{Gal}(L/\mathbb{Q})$, then because the extension is finite, $$|\Gamma | = |\Gamma \cdot \alpha| \cdot | \textrm{Stab}_{\Gamma}(\alpha)|.$$ In particular, the number $|\Gamma \cdot \alpha|$ of Galois conjugates of $\alpha$ is less than or equal to the order $|\Gamma|$ of the Galois group. (It will, in fact, be an equality: the stabilizer of $\alpha$ must be trivial, else $\alpha$ would not be a generator.)
• let $\alpha$ be an algebraic element over $\mathbb Q$, and $f$ is the irreducible polynomial of $\alpha$, with $deg(f)=n$. What can we say about other roots of $f$ in the field $\mathbb Q(\alpha)$? Are they necessarily conjungate with $\alpha$? – Yilong Zhang Jun 23 '15 at 8:16
• Yes all of the roots of $f$ will be Galois conjugate - the key point is that the extension $\mathbb{Q}(\alpha) / \mathbb{Q}$ is Galois. – msteve Jun 23 '15 at 15:23
• Now all of the roots of $f$ are Galois conjugate, then can we say every permuatation $\sigma \in S_n$ act on these $n$ roots induce a $\mathbb Q$-automorphism of the whole field $\mathbb Q(\alpha)$? If yes, then the order of $ord(Gal(\mathbb Q(\alpha)/\mathbb Q)) =ord(S_n)=n!$. Is there anything wrong with my reasoning? – Yilong Zhang Jun 23 '15 at 15:32
• Just because the Galois group acts transitively on the roots does not mean it is equal to $S_n$, or more generally, there are groups that act transitively that are not symmetric groups e.g. $\mathbb{Z}/n\mathbb{Z}$ acts transitively on itself but is not equal to $S_n$. – msteve Jun 23 '15 at 15:40
• For a Galois theory example, consider the polynomial $x^3-3x-1$, which is irreducible over $\mathbb{Q}$. The splitting field of this polynomial has Galois group $A_3$. – msteve Jun 23 '15 at 15:41